ultrapowers and higher order logic - MathOverflow

ultrapowers and higher order logic

2011-01-10T14:36:47Z

One of the reasons I think ultrapowers are interesting is the following corollary of Łoś's theorem:

Let $V$ be a relational structure and $^*V$ an ultrapower of $V$. Then a first order statement about $V$ is true if and only if the corresponding statement for $^*V$ is true, where the relations $R$ on $V$ are replaced by their enlargements $^*R$.

This suggests the following question: what construction should replace the ultraproduct if I want a similar result for 2nd or higher order statements? A little googling suggests that a book by van Benthem called Modal Logic and Classical Logic might contain an answer, but I don't have access to a copy.

Answer by Joel David Hamkins for ultrapowers and higher order logic

2011-01-10T22:38:27Z

The interpretation of higher-order logic depends of course on the set-theoretic background in which it is computed. And if one is willing to change this set-theoretic background, then one may arrive at an answer to the question.

The situation is that whenever one is considering the ultrapower of a given structure $\cal M$ by an ultrafilter $U$ on $I$, then one might simultaneously consider the ultrapower of all other structures $\cal N$ by $U$, and realize that all such ultrapowers and ultraproducts by $U$ fit together in a coherent way, given by the ultrapower of the entire set-theoretic universe by $U$. In particular, one may take the ultrapower of the higher-order structures built from $\cal M$ by applying the power set operation, as indicated by Gerhard, and conclude a higher-order analogue of the fact you mention in the question. Indeed, one may apply the power set transfinitely.

Specifically, if you have an ultrafilter $U$ on a set $I$, then one may form the ultrapower of the entire set-theoretic universe $V$ by building the structure $\bar V=V^I/U$, consisting of the appropriate equivalence classes $[f]_U$, where $f:I\to V$ is any function on $I$ to set-theoretic objects $f(i)$. Each point $[f]_U$ amounts to the ultraproduct $(\Pi_i f(i))/U$, and in this way each ultraproduct construction is seen as a special case of the ultrapower of the universe (reversing the usual description of ultrapowers as special cases of ultraproducts).

By Los's theorem, the canonical map $j:V\to M$ mapping each object $x$ to $[x]_U$, which is essentially the ultrapower of $x$ by $U$, is an elementary embedding in the language of set theory. This implies, in particular, that $\bar V$ is a model of the axioms of set theory, and furthermore, that any set-theoretic statement about any structure $\cal M$, including higher-order statements of any higher order, including transfinite order, is preserved from the structure $\cal M$ to the image $j({\cal M})$, as interpreted in the new set-theoretic universe $\bar V$. Thus, higher order statements about $\cal M$ in $V$ are directly preserved to the corresponding higher-order statements about the ultrapower of $\cal M$, but interpreted now in $\bar V$.

Answer by Pasha Zusmanovich for ultrapowers and higher order logic

2011-05-07T18:27:22Z

Disclaimer: I am amateur, take everything with a grain of salt.

I was asking myself the same question a while ago. I dare to suggest that this question naturally arises to every person after just a cursory acquaintance with model theory. Meaning, ultraproducts are such cool things, and Los' theorem is so damn powerful, but the most interesting properties of algebraic structures are not expressible in the first-order language!

I haven't seen the book by van Benthem you mention, but I strongly doubt that modal logic is the direction into which one might to seek answer to this question.

My impression that the answer to this question is disappointing: there is no such construction. A (variant of a) longer and somewhat more substantial answer could be, probably, obtained from: H.J. Keisler, Model Theory for Infinitary Logic. Logic with countable conjunctions and finite quantifiers, North-Holland, 1971. In the weak forms of the second-order logic considered there, compactness theorem, which is a backbone of the first-order theory, fails miserably, and ultraproducts turned out to be even not remotely useful.

Answer by Zsbán Ambrus for ultrapowers and higher order logic

2011-05-07T21:19:39Z

Look. Suppose you take an infinite sequence of sets $ A_0, A_1, A_2, \dots $ (with no structure apart from equality, that is, no relations or functions), such that $ A_n $ has $ n $ elements. If you take a ultraproduct of these sets (using a non-principal ultrafilter over their indices), can the product be a finite set? No, because for any natural number $ n $, all but finite of these sets have more than $ n $ elements, and ther being more than non-equal $ n $ elements is a first-order property, so this same property must be true for the ultraproduct as well, so the product has more than $ n $ elements for any natural number $ n $. So far, so good.

But now suppose you could take some kind of advanced ultraproduct of these sets that keeps not only the first order statements but all second order statements that are true in the majority of the sets. But there being only finitely many elements is a second order statement, so this advanced ultraproduct would have to be finite as well, because all the sets are finite. This is, in simple terms, why you can't have such a generalization of ultraproducts.

Answer by Goldstern for ultrapowers and higher order logic

2011-05-27T15:52:00Z

As pointed out by Matthew Towers, any ultrapower construction that preserves second order statements must be trivial at least in those cases where the original structure satisfies a categorical second order statement.

But there may be fragments of second order logic that can be preserved by ultrapowers and/or ultraproducts.

As a trivial example, any purely existential second order statement which is true in all factors will be true in the ultraproduct (since an expansion of the original structure by new predicates induces an expansion of the ultraproduct).
As a trivial non-example: already the purely universal and monadic second order statement "every subset containing 0 and closed under successor is the whole set" is not preserved in any nontrivial ultrapower of the natural numbers, nor can it be preserved in any (nontrivial) proposed "advanced ultrapower construction".