# What are some nice uses of ultraproducts/ultrapowers?

Motivated by a recent post (Non-definability of graph 3-colorability in first-order logic), I was wondering: what are some nice arguments based on ultraproducts? I don't mind definability results, but I would like to know if they have found uses in some more outer fields (for example have they ever been used in computability theory in any meaningful way, given that it is my favorite branch of logic).

Here are a few common uses that come to mind:

• Large cardinals. Ultrapowers are used pervasively in large cardinal set theory. Most of the familiar large cardinal concepts can be characterized by their relation to certain kinds of ultrapowers of the set-theoretic universe.

• Nonstandard analysis. Ultrapowers provide one of the robust ways to construct hyperreal fields $$\mathbb{R}^*$$, a real-closed field with infinitesimal elements and the transfer principle. The nonstandard analogue $$f^*$$ of every function $$f$$ on the reals is simply the ultrapower of it. Meanwhile, this answer shows a sense in which ultrafilters are inherently part of nonstandard analysis — a set $$X$$ is large, if a fixed nonstandard number is in $$X^*$$ — and one can then show that the ultrapower of $$\mathbb{R}$$ by this ultrafilter is a submodel of that particular instance of the hyperreals.

• Compactness theorem. One can prove the compactness theorem in model theory by the use of a suitable ultraproduct. If a theory $$T$$ is finitely satisfiable, then take the set of all finite subsets $$t \subset T$$, and a model $$M_t\models t$$, and find an ultrafilter $$\mu$$ such that every sentence is in $$\mu$$-almost every $$t$$. So the ultrapower $$\prod M_t/\mu$$ will satisfy every sentence in $$T$$.

• Alternative to König's lemma. If a set of tiles has the property that it tiles arbitrarily large squares in the plane, then it also tiles the whole plane. One can prove this by König's lemma, by setting up a certain tree. But one can also prove it by ultraproducts — one takes the ultraproduct of increasing large finite tilings, and the standard part of the ultraproduct provides a full tiling of the plane. And there are many similar instances where ultraproducts provide an alternative to König's lemma.

• Voting theory. Consider a group of individuals with individual preferences, which we want to unify into an amalgamated group preference relation, such as in the case of voting. Both Arrow's impossibility theorem and the Gibbard-Satterthwaite theorem can be seen as the claim that if certain very reasonable assumptions on these individual and group preference relations hold, then the group preference relation is determined by an ultrafilter on the individuals. In effect, the group preference must be the ultraproduct of the individual preferences. In the case of a finite population, since all ultrafilters on a finite set are principal, this means one individual serves as dictator.

In a sense the ultraproduct construction provides a powerful means by which to amalgamate many different structures into one, and this aspect of ultraproducts is manifested in the proof of the compactness theorem, in nonstandard analysis (where the amalgamation of increasing tiny numbers becomes an infinitesimal), and in voting theory. So these different applications are unified by the idea of amalgamation of structure.

• For König's lemma, presumably the standard part will be applied to the limited portion of the ultraproduct. Jul 20 at 12:21
• I would say instead that the standard part of the ultraproduct is a limited portion of the ultraproduct, which is a tiling of some large nonstandard number square. Jul 20 at 12:39
• These are all very interesting. What I find fascinating from my very little knowledge of these structures is just how incredibly versatile and complex they can be. I am not sure I know of anything quite like this with the exception of something like forcing/priority arguments. Jul 20 at 21:00
• @JoelDavidHamkins, what do you mean by a "nonstandard square"? A square of size $n\times n$ where $n$ is a nonstandard integer? If so, then the standard part does not apply. If your goal is to obtain a standard tiling of the standard plane, you would have to apply the standard part to the limited (i.e., "finite") part of the ultraproduct. Jul 24 at 7:54
• @MikhailKatz Yes, that's what I mean, and I don't agree that "standard part does not apply." This is well established terminology for that meaning. The standard part of a nonstandard object is the part of it in the standard realm. The standard part of a nonstandard binary sequence is the binary sequence at standard places; the standard part of a nonstandard model of PA consists of the numbers arising at finite distance from 0; the standard part of a tiling of a nonstandard square is the tiling at the standard coordinates. It is important that there are only finitely many tile types. Jul 24 at 11:57

One of my favourite applications is proving that $$\sqrt2$$ is irrational using ultraproducts.

This requires knowing a nontrivial fact, that there are infinitely many prime numbers $$p$$ such that $$x^2\not\equiv 2\pmod p$$ for all $$x$$. In other words, $$\Bbb F_p$$ does not have a solution for $$x^2-2=0$$. Once we know there are infinitely many such prime numbers, we can take the ultraproduct of these $$\Bbb F_p$$ to obtain a field of characteristics $$0$$ where $$x^2-2=0$$ does not have a solution, since $$\Bbb Q$$ is a subfield of that field, it is impossible that $$x^2-2$$ can be solved there, and therefore $$\sqrt2$$ is irrational.

• This is pretty much as outside of the "usual" domain as it gets for an application, very nice answer. Jul 21 at 18:56
• Ooh, I haven't seen this one before - lovely! Jul 23 at 0:07

Ultraproducts are useful in certain applications to combinatorics, with a famous example being Hrushovski's work on finite approximate groups, followed by the structure theorem of Breuillard, Green, and Tao (also using ultraproducts).

The general idea is that instead of proving an asymptotic statement about all finite objects of a certain kind, one instead proves a companion result about a single infinite object. For a toy example, we can prove Ramsey's theorem for finite graphs as follows.

Given an integer $$n$$, we want to prove the existence of an integer $$R(n)$$ such that any finite graph with $$R(n)$$ vertices contains a complete or independent subgraph on $$n$$ vertices. Suppose not. Then we have a fixed $$n$$ such that for every integer $$k$$, there is a graph $$\Gamma_k$$ with $$k$$ vertices containing no complete or independent subgraph of size $$k$$. Let $$\Gamma$$ be a nonprincipal ultraproduct of the family $$(\Gamma_k)_{k\geq 1}$$. Now $$\Gamma$$ is an infinite graph. One then proves a lemma (Ramsey for infinite graphs): any infinite graph contains an infinite complete or independent subgraph. In particular, $$\Gamma$$ contains an complete or independent subgraph on $$n$$ vertices. This latter statement is expressible by a first order sentence, which then must hold of some (in fact infinitely many) $$\Gamma_k$$, a contradiction.

This example is good for illustrating the method in a simple way. But it is perhaps not very satisfying because in this case, the infinite statement (Ramsey for an infinite graph) is not significantly easier to prove than the initial asymptotic statement (Ramsey for finite graphs). In the real life examples showing up in research papers, this is not the case. Often the point is that methods from other fields, such as model theory, can be used to attack the infinite statement in ways that are not clearly adaptable to finite structures. This is certainly the case for the work on approximate groups mentioned above where, in addition to model theory, there are also very nontrivial results about locally compact Lie groups in play.

One downside to the ultraproduct approach is that the statements proved are qualitative by nature, rather than quantitative. For example, the proof above of Ramsey's theorem gives no information about a bound on $$R(n)$$ in terms of $$n$$. In some cases, if one understands the "companion proof" for infinite structures deeply enough, then one can see how to finitize the proof and carry it out in a quantitative way. For example, the proof of Ramsey for an infinite graph finitizes in a clear way to a direct proof for a finite graphs yielding a bound for $$R(n)$$ on the order of $$4^n$$. In other cases however, the finitization of the infinite proof can be much more challenging. Something I like about this kind of work is that even if one is able to replace the infinite qualitative proof with a finitary quantitative one, it is often the case that the model theoretic contributions of the infinite proof were instrumental in cracking the finitary proof. On the other hand, there are some examples where a quantitative finite proof is still open (e.g., the work on finite approximate groups).

• Proving things about finite objects by first proving them about infinite versions of them sounds impossible without knowing about ultraproducts beforehand. Thanks for the great answer. Jul 20 at 21:11
• This is a great answer. It seems quite close to the perspective that Tao outlines in Ultraproducts as a bridge between discrete and continuous analysis. Jul 21 at 9:21

The paper Chromatic homotopy theory is asymptotically algebraic (by Barthel, Schlank and Stapleton) is an interesting example. In chromatic homotopy theory we study the category $$\mathcal{L}(p,n)$$ of spectral local with respect to the Johnson-Wilson theory $$E(p,n)$$, where $$p$$ is a prime and $$n$$ is a positive integer. It is a folklore idea that when $$p$$ is large relative to $$n$$, the properties of $$\mathcal{L}(p,n)$$ become more and more algebraic and more and more independent of $$p$$, in some sense. The cited paper formalises this idea by taking a kind of ultraproduct over primes. There is also a sequel called Monochromatic homotopy theory is asymptotically algebraic.

One common slogan is that ultrapower arguments rely on the axiom of choice. This isn't as true as it may sound, though. The technique still has purchase in other contexts, such as inner models where determinacy holds. For example, assuming large cardinals every set of reals in $$L(\mathbb{R})$$ is "tame" in various nice senses; in particular, the Martin measure on the Turing degrees is actually a countably complete ultrafilter. In The higher infinite, Kanamori discusses applications of this measure and its relatives; for a recent example, in Part 1 of Martin's Conjecture for order-preserving and measure-preserving functions, Patrick Lutz and Benjamin Siskind used it to make progress on Martin's Conjecture about functions on the Turing degrees.

(Since Patrick is a frequent contributor here, I hope he'll expand on this!)

A ring $$R$$ (commutative, with identity) is said to be solid if the unique homomorphism $$\mathbb{Z} \to R$$ is an epimorphism in the category of rings, or equivalently if $$r \otimes 1 = 1 \otimes r$$ in $$R \otimes R$$ for all $$r \in R$$.

The rings $$\mathbb{Q}$$ and $$\mathbb{Z}/p$$ (for primes $$p$$) are each solid. But is the ring $$\mathbb{Q} \times \prod_{\text{primes } p} \mathbb{Z}/p$$ solid?

No, it's not. Here's a proof that uses an ultraproduct.

Admittedly this proof is rather elaborate, and there may well be simpler proofs (perhaps already published decades ago) that don't use ultraproducts or even any form of choice. You can take that as a challenge. Nevertheless, it's an instance where ultraproducts can be used to answer a question in the mainstream of algebra.

Interestingly, the proof has some points in common with Asaf's wonderful proof of the irrationality of $$\sqrt{2}$$.

• (For the challenge) Note that $E' = \prod_p \mathbf{Z}/p$ has a quotient field $E$ of characteristic $0$ (take any maximal ideal containing $\oplus_p \mathbf{Z}/p$). So if $\mathbf{Z} \to \mathbf{Q} \times E'$ was an epimorphism, by base change and composition-stability of epimorphisms, we learn that $\mathbf{Q} \to \mathbf{Q} \times E$ is an epimorphism. But this is clearly false: the latter has two visibly distinct maps to $E$ (via either projection) that become the same on the source. Jul 23 at 2:29
• @Anonymous +1 because your proof is simpler in the sense that it doesn't use the fact that $-1$ is a square mod $p$ for infinitely many $p$. But it does implicitly use ultraproducts: an ultraproduct of the $\mathbb{Z}/p\mathbb{Z}$ is exactly the same thing as a quotient of the product ring by a maximal ideal. So this doesn't answer the challenge, at least the way I read it. Jul 23 at 17:29
• The argument uses the axiom of choice (used to choose a maximal ideal in a nonzero ring); is that equivalent to using ultraproducts? In any case, I realized that even this is not necessary. Indeed, the ring $S = (\prod_p \mathbf{Z}/p)/(\oplus_p \mathbf{Z}/p)$ is clearly nonzero. It is also a $\mathbf{Q}$-algebra as any nonzero integer $n$ is invertible in $\prod_{p > n} \mathbf{Z}/p$ and thus also in $S$. So $\mathbf{Q} \times S$ has two distinct maps to $S$ (via either projection) which obviously agree on $\mathbf{Z}$, and thus $\mathbf{Z} \to \mathbf{Q} \times S$ is not an epimorphism. Jul 23 at 18:27
• @Anonymous Your original argument does implicitly use an ultraproduct. You quotient $\prod \mathbb{Z}/p$ by a maximal ideal $I$. That quotient is precisely the ultraproduct $(\prod \mathbb{Z}/p)/\mathcal{U}$ with respect to the following ultrafilter $\mathcal{U}$ on the set of primes: a subset $A$ of the primes belongs to $\mathcal{U}$ iff $x_A \in I$, where $x_A \in \prod \mathbb{Z}/p$ has $p$th coordinate $0$ if $p \in A$ and $1$ otherwise. Jul 25 at 10:33
• @Anonymous Great! FYI, your construction is a special case of the "reduced product", a generalization of the ultraproduct that works with a general filter instead of an ultrafilter. In your case, quotienting by the direct sum ideal corresponds to taking the reduced product by the cofinite filter, which does not require choice. The use of choice in the ultraproduct proof is exactly in extending the cofinite filter to an ultrafilter (in algebraic language, extending the direct sum ideal to a maximal ideal). Jul 28 at 17:58