# ultrapowers and higher order logic

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.

-
There is a rough analogy between variables of order k in nth order logic and members of Q_k(U), where U is the underlying universe of the model and Q_n+1(U) is the power set of Q_n(U) when n>0, with Q_1(U) being U. (Actually, 2d order variables can range over relations which is more like members of P(U^t), or subsets of tuples of U, but lets keep the analogy rough.) That suggests using quotients of powers of Q_k(U) for kth order statements of U. An issue is whether this allows quantifying over relations of different arities. Gerhard "Ask Me About System Design" Paseman, 2011.01.10 –  Gerhard Paseman Jan 10 '11 at 15:27

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$.

-
thanks Joel, that's very interesting. Do you have any idea what happens if we insist on staying within (say) ZFC? My thoughts were that categoricity of certain sets of axioms suggest that there's no non-trivial analogue to the ultrapower in general. –  Matthew Towers Jan 11 '11 at 14:42
@mt: Joel did stay within ZFC, in the sense that the $\bar V$ he described satisfies each ZFC axiom just as well as the original universe $V$ did. But the meaning of second-order statements in $\bar V$ is different because the set variables range only over $\bar V$. For example, the completeness property of the reals says that the ultrapower of the reals is complete in the sense that every bounded nonempty subset that is an element of $\bar V$ has a least upper bound. So that ultrapower is not complete in the same sense as the ordinary real numbers (completeness for all subsets). –  Andreas Blass Jan 15 '11 at 21:47

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.

-
Yes, I thought of something similar. Since the second order axioms of the reals are categorical, the "advanced ultrapower" of the reals must be isomorphic to the reals again. –  Matthew Towers May 7 '11 at 21:27
Similarly for the second order axioms for the natural numbers. (In fact, a single axiom is enough in both cases.) –  Goldstern May 27 '11 at 15:13

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.

-

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".
-