Using Ultrapowers to Solve Problems

05 Dec 2021

An Ultraproduct is a construction from mathematical logic that lets us prove (first order) statements about some family of structures by studying a single object which somehow captures the behavior of the family. In this post we’ll talk about ultraproducts – what are they, what do they do, and most importantly how can we actually use them to solve problems?

First, what are ultraproducts anyways?

Fix a sequence of groups (say) \((G_n)_{n \in \mathbb{N}}\). Then we can take their product and get a new group $\prod G_n$ with coordinate-wise operations. We would like to modify this construction in order to get a group $\prod_\mathcal{U} G_n$ (called the Ultraproduct of the $G_n$s) which has better model theoretic properties. We’ll go deeper into the specifics of the construction later but for now, it’s enough to know that the ultraproduct has the following properties:

• Elements of $\prod_\mathcal{U} G_n$ are (equivalence classes of) tuples $(g_1, g_2, g_3, \ldots)$, where $g_n \in G_n$.
• $\prod_\mathcal{U} G_n$ thinks that some first-order property is true if and only if all but finitely many of the $G_n$s do¹. For example, if all but finitely many of the $G_n$ are abelian, then the ultraproduct will be abelian too, since abelianness is defined by the first order sentence $\forall x . \forall y. x^{-1}y^{-1}xy = 1$.

One special case of interest is where all the $G_n$ are actually the same! We call this the Ultrapower of $G$, written $G^\mathcal{U}$.

It might seem strange that this construction is useful. After all, by the bullet point above, we know that $G^\mathcal{U}$ thinks that something is true if and only if $G$ does. So isn’t it just $G$? What do we gain by moving to the ultrapower?

The answer is caught up in the “first-order” qualifier! It turns out that there can be lots of differences between $G$ and $G^\mathcal{U}$. For instance, $\mathbb{Z}^\mathcal{U}$ is uncountable, (in particular, it is not cyclic).

To know which properties we can transfer back and forth between $G$ and $G^\mathcal{U}$, then, we need to know what it means for a property to be “first order”. I’m going to assume some familiarity with basic model theory, but I’ll include abbreviated definitions for completeness². See the footnote here³

---

Ok, so let’s quickly write down what an ultraproduct is. Even though I’m assuming some familiarity with logic, it’s nice to have a refresher⁴. For concreteness, we’ll work with countable ultraproducts, since they’re a bit simpler to think about and they’re the only ones I’ve ever personally needed.

Fix a first order language $\mathcal{L}$, fix $\mathcal{L}$-structures $A_n$ for $n \in \mathbb{N}$. Fix moreover a nonprincipal ultrafilter $\mathcal{U}$ on $\mathbb{N}$. Intuitively $\mathcal{U}$ is a family of “large” subsets of $\mathbb{N}$. What do I mean by large? Well:

Then we can look at the Ultraproduct⁵

\[\prod_\mathcal{U} A_n \triangleq \prod A_n \big / \sim\]

where we say that $\overline{a} \sim \overline{b}$ whenever they agree “almost everywhere”, in the sense that

\[\{ n \mid a_n = b_n \} \in \mathcal{U}.\]

The critical result in this area is Łoś’s Theorem (pronounced roughly like “Wash’s Theorem”) which says that:

The main character of today’s post is the ultrapower, but I can’t help but say a few words about why ultraproducts are useful. I’ll contain myself, though, and just give the following idea:

If you have a sequence of objects you want to study, say the groups \(\mathsf{GL}_n(\mathbb{C})\), then it might be worth considering their ultraproduct. Łoś’s Theorem says that the ultraproduct will behave similarly to the \(\mathsf{GL}_n(\mathbb{C})\)s, so many of your well trodden techniques will probably work. Conversely, anything (first order) you can prove about the ultraproduct immediately tells you the same is true for all but finitely many $n$!

As a concrete example, consider the family $\overline{\mathbb{F}_p}$ of algebraic closures of finite fields.

Then the ultraproduct $\prod_\mathcal{U} \overline{\mathbb{F}_p}$ is⁶

1. cardinality continuum
2. algebraically closed
3. characteristic $0$

Thus it’s (noncanonically!) isomorphic to $\mathbb{C}$.

Since any question about polynomials and their roots is expressible in the first order language of fields, this gives one formalization of the informal “Lefschetz Principle”, which says that doing algebraic geometry over $\mathbb{C}$ is “roughly the same” as doing algebraic geometry over any algebraically closed field of sufficiently large characteristic.

---

So then, let’s move on to ultrapowers!

If $A$ is one fixed $\mathcal{L}$-structure, then we can look at the ultraproduct of the constant sequence $A_n = A$. In this case, we call the resulting structure the Ultrapower, which we write as $A^\mathcal{U}$. Most notably, we get an inclusion

\[A \hookrightarrow A^\mathcal{U}\]

sending $a \in A$ to the (equivalence class of the) constant sequence $(a,a,a,a,a,\ldots)$.

Moreover, since $A$ models its own diagram, we see that $A^\mathcal{U}$ models the diagram of $A$ as well, in a way that’s compatible with the above embedding. This means the “constant sequence” function is actually an elementary embedding. So $A$ and $A^\mathcal{U}$ agree on every first order question you can ask about $A$.

Of course, we, from the outside looking in, can tell that $A$ and $A^\mathcal{U}$ look very different! Maybe we can leverage these differences in order to prove things in the $A^\mathcal{U}$ setting!

The canonical example of this phenomenon is nonstandard analysis, where we study the “hyperreal numbers”

\[{}^* \mathbb{R} \triangleq \mathbb{R}^\mathcal{U}\]

which have lots of nice properties⁷. For instance, the hyperreal number

\[\epsilon \triangleq (1, 1/2, 1/3, 1/4, 1/5, \ldots)\]

is an infinitesimal in the sense that

1. $\epsilon \gt 0 = (0,0,0,0,0,\ldots)$
2. $\epsilon \lt a = (a,a,a,a,a,\ldots)$ for any real number $a \gt 0$.

Then nonstandard analysis uses the extra elements given to us by the ultrapower in order to give us neat and intuitive definitions like the following:

Not only do these new definitions give us a new way of thinking⁹ about classical analysis, they’re even useful for letting us prove new things! Nowhere is this clearer than on Terry Tao’s blog, where he uses nonstandard analysis to great effect!

---

The trick behind ultrapowers, then, is to use our new ~bonus elements~ in $A^\mathcal{U}$ in order to study some limiting propeties of elements of $A$. For instance, the infinitesimal $\epsilon$ from before is a single element of $A^\mathcal{U}$ which expresses the features held simultaenously by the sequence $1/n$.

Following the example of prime fields, we can also use ultrapowers to kill certain “bad properties” of elements. If we have a sequence of elements of $A$ that are related (in that they share certain first order properties) but all have different “defects” (maybe they have torsion, etc.), then the sequence of these elements, viewed as a member of the ultrapower, will share all the properties that relate the original elements, but will share none of the defects! In this way, we can view elements of $A^\mathcal{U}$ as “idealized elements” of $A$.

We can also use ultrapowers to kill “bad properties” of $A$ as a whole, as long as those bad properties are non-first order. For instance, in the passage from $\mathbb{R}$ to ${}^* \mathbb{R}$, we kill the archimedian-ness by introducing infinitesimals. Similarly, there are proofs that are much easier for infinite sets than for finite sets. Having infinitely many elements gives you more flexibility with certain arguments. Well if your desired outcome is first-order expressible, then just prove it for $A^\mathcal{U}$ (which is always infinite. Indeed, of size continuum when $A$ is finite), and transfer back to $A$!

More speculatively, maybe there’s a proof in $\mathbb{N}$ that you want to perform, but for some reason you need to know that you can always keep subtracting. Well, that’s a problem because $\mathbb{N}$ is well ordered. So you can only subtract for so long before you have to stop. In the ultrapower $\mathbb{N}^\mathcal{U}$, though we don’t have this issue! You can keep subtracting from any nonstandard element as many times as you like. So do your argument here, and show a nonstandard element does what you want. Then write your claim as “there exists a number doing what I want”, and transfer back to $\mathbb{N}$!

---

As a last aside, I’ll leave you with an old example from the class where I met my undergraduate advisor. I’ll leave it as an exercise that might be somewhat tricky depending on how much nonstandard analysis you’ve seen:

We’ve “simplified” the search for infinitely many twin primes into the search for one nonstandard twin prime!

Of course, I have no idea how one would go about finding a nonstandard twin prime! But this is a cute problem nonetheless ^_^.

---