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 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_{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_{U} G_{n}$ are (equivalence classes of) tuples $(g_{1}, g_{2}, g_{3}, \dots)$ , where $g_{n} \in G_{n}$ .
$\prod_{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} x y = 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^{U}$ .

It might seem strange that this construction is useful. After all, by the bullet point above, we know that $G^{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^{U}$ . For instance, $Z^{U}$ is uncountable, (in particular, it is not cyclic).

To know which properties we can transfer back and forth between $G$ and $G^{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 $L$ , fix $L$ -structures $A_{n}$ for $n \in N$ . Fix moreover a nonprincipal ultrafilter $U$ on $N$ . Intuitively $U$ is a family of “large” subsets of $N$ . What do I mean by large? Well:

No finite set is large
If $A \subseteq N$ is large, then every $B \supseteq A$ is also large
If $A_{1}$ and $A_{2}$ are both large, then so is $A_{1} \cap A_{2}$
For every set $A$ , either $A$ or $A^{c}$ is large

Then we can look at the Ultraproduct⁵

\prod_{U} A_{n} ≜ \prod A_{n} / \sim

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

{n ∣ a_{n} = b_{n}} \in U .

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

\prod_{U} ⊨ φ ⟺ {n ∣ A_{n} ⊨ φ} \in U

That is, truth in the ultraproduct is exactly truth in “almost all” of the $A_{n}$ !

As a fairly quick exercise, you should prove this if you have some experience with model theory.

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 ${GL}_{n} (C)$ , then it might be worth considering their ultraproduct. Łoś’s Theorem says that the ultraproduct will behave similarly to the ${GL}_{n} (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 $\overset{―}{F_{p}}$ of algebraic closures of finite fields.

Then the ultraproduct $\prod_{U} \overset{―}{F_{p}}$ is⁶

cardinality continuum
algebraically closed
characteristic $0$

Thus it’s (noncanonically!) isomorphic to $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 $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 $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^{U}$ . Most notably, we get an inclusion

A ↪ A^{U}

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

Moreover, since $A$ models its own diagram, we see that $A^{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^{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^{U}$ look very different! Maybe we can leverage these differences in order to prove things in the $A^{U}$ setting!

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

^{*} R ≜ R^{U}

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

ϵ ≜ (1, 1 / 2, 1 / 3, 1 / 4, 1 / 5, \dots)

is an infinitesimal in the sense that

$ϵ > 0 = (0, 0, 0, 0, 0, \dots)$
$ϵ < a = (a, a, a, a, a, \dots)$ for any real number $a > 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:

If $x, y \in^{*} R$ , we say that $x \approx y$ when their difference is infinitesimal.

$f$ is continuous⁸ at $x \in R$ if and only if $f (x) \approx f (y)$ whenever $x \approx y$

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^{U}$ in order to study some limiting propeties of elements of $A$ . For instance, the infinitesimal $ϵ$ from before is a single element of $A^{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^{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 $R$ to $^{*} 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^{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 $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 $N$ is well ordered. So you can only subtract for so long before you have to stop. In the ultrapower $N^{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 $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 work inside $N^{U}$ .

Say you were able to prove that there is a nonstandard twin prime. That is, a pair of numbers $p$ and $p + 2$ which are both prime, and neither of which is equivalent to the constant $(q, q, q, q, q, \dots)$ for any $q \in N$ .

Then the twin prime conjecture is true¹⁰.

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 ^_^.

Technically this is only true of nonprincipal ultraproducts. ↩
Pun intended ↩
Let $σ$ be a collection of “primitive symbols” which are necessary for talking about a given object of study. For example:
- If we’re interested in groups, we might take $σ = ⟨ 1, \cdot,^{- 1} ⟩$
- for ordered rings we might take $σ = ⟨ \leq, 0, 1, +, -, \cdot ⟩$
- If we’re interested in graphs, we might take $σ = ⟨ E ⟩$ (where $E (x, y)$ says that $x$ and $y$ are adjacent)
Then the First Order Language associated to $σ$ (often written $L (σ)$ (sometimes $L_{FO} (σ)$ or $L_{ω, ω} (σ)$ if we’re working with multiple different logics at once) is the collection of formulas we can build using
1. primitive symbols from $σ$
2. connectives: $\land$ , $\lor$ , $\neg$ , $\to$ , $\leftrightarrow$ , etc.
3. variables like $x$ , $y$ , etc.
4. $=$
5. quantifiers: $\forall x$ , $\exists x$
⚠ our quantifiers can only quantify over elements of our structure! This is the “first” in “first order”.
Now we see that there’s no way to write down “ $G$ is cyclic” in a first order way. The obvious idea
$\exists g . \forall x . \exists n \in Z . g^{n} = x$
doesn’t work because we’re quantifying over $Z$ , which is not our structure. Similarly, we can’t write
$\exists g . \forall x . (x = 1) \lor (x = g) \lor (x = g^{- 1}) \lor (x = g^{2}) \lor (x = g^{- 2}) \lor \dots$
since that is an infinite string of symbols. We only allow finite conjunctions or disjunctions.

Lastly, given a formula $φ \in L (σ)$ and a Model $M$ (that is, a set $M$ equipped with constants, operations, and relations for each symbol in $σ$ ) we write $M ⊨ φ$ to mean that, when $φ$ is interpreted using the operations of $M$ , it becomes true.
Here are some nice exercises you might try to get familiar with first order logic:

For $σ = ⟨ E ⟩$ the language of graphs, for each exercise below, write a formula $φ \in L (σ)$ so that a graph $G ⊨ φ$ if and only if it satisfies the criterion in the exercise:
1. $G$ is complete.
2. $G$ contains a triangle.
3. For any (fixed) finite graph $Γ$ , express $G$ contains a copy of $Γ$ as a subgraph. What about as a full subgraph? Can you make $G ⊨ φ_{Γ}$ if and only if $G ≅ Γ$ ?
For $σ = ⟨ 1, \cdot,^{- 1} ⟩$ the language of groups:
1. $| G | \leq n$ . What about $| G | \geq n$ ?
2. $G$ is $2$ -step nilpotent (think about iterated commutators)
3. For any (fixed) finite group $H$ , express $H \leq G$ . What about $G ≅ H$ ? (Think about the (finite!) multiplication table for $H$ ).
↩
Also, not all model theory courses include ultraproducts! For instance, I know the graduate model theory classes at CMU, (for some inexplicable reason), don’t talk about them. ↩
This seems to depend only very mildly on the choice of ultraproduct, and it’s reasonable to ask how the choice of ultraproduct effects the resulting structure. This tends to be quite subtle, see here, say, and for most use cases we don’t worry too much about which ultrafilter to take (even though it does matter. See here)

That said, there are certain applications where we really do want to choose an ultrafilter with special properties, say regularity. You can read about what kind of bonus information we get when we take ultrapowers over regular ultrafilters here, say. ↩
In order,
1. is a fairly easy computation, see here
2. is because we can write down sentences $φ_{n} = \forall a_{0}, a_{1} \dots a_{n} . \exists x . a_{0} + a_{1} x + \dots + a_{n} x^{n} = 0$ which say that every polynomial of degree $n$ has a root.
3. is because for every $q > 0$ , cofinitely many $\overset{―}{F_{p}}$ think that $\underset{q times}{\underset{⏟}{1 + 1 + \dots + 1}} \neq 0$ . So the ultraproduct is a field, but cannot be characteristic $q$ for any $q > 0$ .
↩
Properties that you can (and should!) read more about in the fantastic Lectures on the Hyperreals by Goldblatt.

I have particularly fond memories of this book, because it was one of the first math textbooks that I read by myself, rather than having to read it for a class. ↩
It’s important here that $x \in R$ . If we allow $x \in^{*} R$ , we actually get uniform continuity!

This may appear counterintuitive at first, but does make some intuitive sense after a while. Again, I’ll point you to Goldblatt’s book for more. ↩
An old way of thinking? This is much closer to how analysis was thought about before it was placed on a truly rigorous footing through limits. ↩
As a hint, first show that a nonstandard natural number must be bigger than every standard natural number. For instance, the standard number $3$ satisfies the formula
$\forall x . x < 3 ⟺ x = 0 \lor x = 1 \lor x = 2$
so the only numbers less than $3$ are standard. Obviously we can do this for any standard number, and the claim follows.

Next, show that, since $p$ is nonstandard, we must have
$\exists p . isTwinPrime (p) \land p > 3$ $\exists p . isTwinPrime (p) \land p > 10, 000$ $\exists p . isTwinPrime (p) \land p > 10^{100}$
etc. in $N^{U}$ .

Do you see why (after transferring these theorems back to $N$ ) this means there must be infinitely many twin primes? ↩