### Where Do Ultraproducts Come From?

#### Posted by Tom Leinster

I move jobs tomorrow: from Glasgow to Edinburgh, city of James Clerk Maxwell, Arthur Conan Doyle, Robert Louis Stevenson and Dolly the Sheep. But before I go, I want to give you the fourth and final post on my new paper, Codensity and the ultrafilter monad.

It’s not like the first three. There, I explained some definite facts: what codensity monads are, and how they naturally throw up various interesting mathematical structures. But this post contains nothing new except speculation. Specifically, I’ll speculate that codensity monads naturally throw up the notion of ultraproduct — though at present, I can’t see how.

### Introduction to ultraproducts

Before I speculate about the connection with codensity, I’ll explain what ultraproducts are. If you already know, skip to the next heading, near the end of the post.

Ultraproducts are probably most associated with logic, but the definition is, in fact, purely set-theoretic.

Let $X$ be a set, $\Omega$ an ultrafilter on $X$, and $S_\bullet = (S_x)_{x
\in X}$ a family of sets. Since $\Omega$ is a set of subsets of $X$, it’s
ordered by inclusion. There’s a functor $(\Omega, \subseteq)^{op} \to
\mathbf{Set}$ defined on objects by $Y \mapsto \prod_{y \in Y} S_y$, and on
morphisms by projection. The **ultraproduct**

$\prod_\Omega S_\bullet$

is the colimit of this functor.

Explicitly, an element of $\prod_\Omega S_\bullet$ is an equivalence class of pairs $(Y, (s_y)_{y \in Y})$ where $Y \in \Omega$, $s_y \in S_y$, and the equivalence relation $\sim$ is defined by

$(s_y)_{y \in Y} \sim (t_z)_{z \in Z} \iff \{ x \in Y \cap Z : s_x = t_x \} \in \Omega.$

Let’s agree to call a subset of $X$ **large** if it belongs to the
ultrafilter $\Omega$, and **small** otherwise. Then an element of the
ultraproduct is an equivalence class of families $(s_y)_{y \in Y} \in
\prod_{y \in Y} S_y$ indexed over some large subset $Y$ of $X$, with two such
families identified if they agree in a large number of coordinates.

(If all the sets $S_x$ are nonempty then there’s a slightly simpler explicit description, but that won’t be relevant here.)

**Trivial example** The only easy examples of ultrafilters are the
principal ultrafilters. In that case, ultraproducts are *really* trivial:
when $\Omega$ is the principal ultrafilter on an element $x$ of $X$, the
ultraproduct $\prod_\Omega S_\bullet$ is simply $S_x$.

A few of us discussed ultraproducts in response to
David’s post a few weeks ago.
Moshe
Kamensky expressed the
opinion that in model theory, ultraproducts are mostly a technical tool,
and one can find similar opinions expressed in the well-known book *Model
Theory* by Wilfrid Hodges. On the other hand, the equally well-known
book *Model Theory* by Chang and Keisler devotes one entire chapter
out of seven to ultraproducts.

So, I don’t know whether there’s a consensus among model theorists as to the importance of ultraproducts. But I’ll try to explain what I understand to be their importance, using a bit of categorical language.

As the definition above shows, ultraproducts are constructed using two kinds of (co)limit in $\mathbf{Set}$: products, and colimits over $(\Omega, \subseteq)^{op}$. This latter category is filtered, because $\Omega$ is a filter. So, ultraproducts are constructed out of products and filtered colimits. It follows that the functor

$\prod_\Omega \colon \mathbf{Set}^X \to \mathbf{Set}$

preserves finite limits.

Actually, everything so far is true if $\Omega$ is a mere filter, not
necessarily an ultrafilter. (I know I haven’t defined filters, only
ultrafilters.
If you don’t know what filters are, it doesn’t really matter — all you need to know is that they’re more general than ultrafilters.) Now using the fact that $\Omega$ is
an *ultra*filter, we can show that the functor

$\prod_\Omega \colon \mathbf{Set}^X \to \mathbf{Set}$

also preserves finite coproducts. It has other exactness properties too (e.g. it preserves image factorizations), but I think they all follow quite easily from the fact that it preserves finite limits and finite coproducts.

I’ll now explain the kind of thing that ultraproducts can do, by means of an extended example.

**Extended example** This is all about fields. Fix an
ultrafilter $\Omega$ on a set $X$. As noted above, this determines a functor
$\prod_\Omega \colon \mathbf{Set}^X \to \mathbf{Set}$, which
preserves, among other things, finite products. Since the theory of (commutative) rings is a finite product
theory, there’s an induced functor

$\prod_\Omega \colon \mathbf{Ring}^X \to \mathbf{Ring}.$

If $(R_x)_{x \in X}$ is a family of rings then the ring structure on the set $\prod_\Omega R_\bullet$ is the obvious, pointwise, structure.

This in turn restricts to a functor

$\prod_\Omega \colon \mathbf{Field}^X \to \mathbf{Field}.$

Why? There’s probably a nice abstract argument, but — mainly for the sake of practising with the definition — here’s an explicit one. (Skip this paragraph if you’re not in the mood for details.) The claim is that if $(k_x)_{x \in X}$ is an $X$-indexed family of fields then the ring $\prod_\Omega k_\bullet$ is also a field. So, take a nonzero element of $\prod_\Omega k_\bullet$. Such an element is the equivalence class of some family $(c_y)_{y \in Y}$ where $c_y \in k_y$ and $Y \subseteq X$ is large. Since it’s nonzero, a large number of the elements $c_y \in k_y$ are nonzero and therefore invertible. Their inverses $c_y^{-1}$ then determine an element of $\prod_\Omega k_\bullet$, and it’s easy to show that it’s the inverse of our original element. That does it.

We’ve just shown that ultraproducts have a nice preservation property that
ordinary products don’t. The *product* of fields is most definitely
not a field!

Next, let’s think about the characteristics of the fields involved. I won’t prove a systematic result on the characteristic of the ultraproduct $\prod_\Omega k_\bullet$ in terms of the characteristics of the individual fields $k_x$; I’ll just do a single example.

Suppose that $X = \{1, 2, 3, \ldots\}$, and that the fields $k_1, k_2, k_3, \ldots$ have respective characteristics $2, 3, 5, \ldots$ — so we’ve got one field of each prime characteristic.

Also assume that our ultrafilter $\Omega$ on $X$ is nonprincipal. This means that every singleton $\{x\}$ is small. But in an ultrafilter, a finite union of small sets is always small, so it’s equivalent to say that every finite subset of $X$ is small.

Now, what’s the characteristic of the field $\prod_\Omega k_\bullet$?

Well, the multiplicative unit of $\prod_\Omega k_\bullet$ is

$[(1, 1, 1, \ldots)]$

where $(1, 1, \ldots) \in k_1 \times k_2 \times \cdots$ and the square brackets mean equivalence class. So, when $n$ is a positive integer, the element “$n\cdot 1$” of $\prod_\Omega k_\bullet$ is

$[(n\cdot 1, n\cdot 1, n\cdot 1, \ldots)]$

where the $i$th term $n \cdot 1$ is an element of $k_i$. On the other hand, the zero of $\prod_\Omega k_\bullet$ is

$[(0, 0, 0, \ldots)].$

So $n \cdot 1 = 0$ in $\prod_\Omega k_\bullet$ if and only if $n \cdot 1 = 0$ in a large number of the fields $k_1$, $k_2$, $k_3$, …. But that’s never the case: if $n\cdot 1$ in $k_i$ then the $i$th prime divides $n$, so there are only finitely many such $i$, and finite subsets of $X$ are small.

So, $\prod_\Omega k_\bullet$ has characteristic zero.

Here’s a dramatic way to think about it. Imagine, implausibly, that we know no examples of fields of characteristic zero. Maybe the only fields we know are those of the form $\mathbb{Z}/p\mathbb{Z}$ for prime $p$. Then the ultraproduct construction automatically provides us with an example — in fact, many examples — of a field of characteristic zero.

That’s the end of the extended example. Those who know about these things will have recognized, barely concealed beneath its surface, two important theorems:

- Łoś’s theorem, also known as the fundamental theorem of ultraproducts. If each of the sets $S_x$ is a structure (of a given signature) in the sense of model theory, then so too is $\prod_\Omega S_\bullet$, in a natural way. (For example, if each of the sets $S_x$ is a ring then so is $\prod_\Omega S_\bullet$.) Łoś’s theorem states that a first-order statement is true in $\prod_\Omega S_\bullet$ if and only if it is true in a large number of the structures $S_x$.
- The compactness theorem, which states that if $\Gamma$ is a set of first-order statements and each finite subset of $\Gamma$ has a model, then $\Gamma$ itself has a model. For example, let $\Delta$ be the set of axioms for a field. Just knowing about the fields $\mathbb{Z}/p\mathbb{Z}$ tells us that each finite subset of $\Delta \cup \{ 2\cdot 1 \neq 0, 3 \cdot 1 \neq 0, 5 \cdot 1 \neq 0, \ldots \}$ has a model. Using ultraproducts, we constructed from these fields of positive characteristic a field of characteristic zero. That’s hardly an impressive achievement, but it points to a general fact: the compactness theorem can easily be proved by following the same pattern, using ultraproducts. And the compactness theorem can be used to prove much more startling results than the trivial one about characteristic zero: see Wikipedia, for instance.

### Speculation on ultraproducts and codensity

Suppose, once more, that we have an ultrafilter $\Omega$ on a set $X$.

Back here, I described *integration against an ultrafilter*.
Integration against $\Omega$ defines, for each finite set $B$, a function

$\int - \, d \Omega \colon B^X \to B.$

It’s natural in $B$, meaning that given any map $B \to C$ of finite sets, the evident square commutes.

Just now, I reviewed the definition of *ultraproduct with respect to
an ultrafilter*. I only described ultraproducts of families of *sets*,
but the definition works just as well when $\mathbf{Set}$ is replaced by
any other category with products and filtered colimits. Taking
ultraproducts with respect to $\Omega$ defines, for each such category $\mathbf{B}$, a functor

$\prod_\Omega \colon \mathbf{B}^X \to \mathbf{B}.$

It’s natural in $\mathbf{B}$, meaning that given any functor $\mathbf{B} \to \mathbf{C}$ preserving products and filtered colimits, the evident square commutes up to canonical isomorphism.

This suggests that the process of taking ultraproducts is a categorification of the process of integrating against an ultrafilter. Can we make that precise? I don’t know.

Ordered sets sometimes provide a stepping stone between sets (0-categories) and categories (1-categories). Let $B$ be a finite lattice. As a set, $B$ is finite, and as a category, $B$ has products and filtered colimits. It’s easy to see that the processes of integration and ultraproduct coincide in $B$: whenever $(b_x)_{x \in X}$ is a family of elements of $B$,

$\int_\Omega b_\bullet = \prod_\Omega b_\bullet.$

That’s encouraging.

Back here, we saw that ultrafilters on $X$ not only give
rise to, but actually *correspond one-to-one with*, natural families of
functions

$\Bigl( B^X \to B \Bigr)_{B \in \mathbf{FinSet}}.$

In other language, this says that the ultrafilter monad is the codensity monad of the inclusion functor $\mathbf{FinSet} \hookrightarrow \mathbf{Set}$.

Are there similar statements for ultraproducts? That is, do ultrafilters on $X$ not only give rise to, but actually correspond one-to-one with, natural families of maps

$\Bigl( \mathbf{B}^X \to \mathbf{B} \Bigr)$

indexed over ‘nice’ categories $\mathbf{B}$? And can we rephrase this correspondence as a neat assertion about a codensity monad? Again, I don’t know.

It’s not obvious to me how to see this idea through. Among other things, the question arises of distinguishing between ultrafilters and general filters, which suggests that something’s wrong. Perhaps I haven’t got the right level of generality. But given the close formal resemblance between ultraproducts and integration against an ultrafilter, it’s hard to resist speculating. I hope someone will be able to see a clear path through.

## Re: Where Do Ultraproducts Come From?

I’m not sure how this ties into the codensity monad story, but the following observation about the connection between filters and functors $\mathbf{Set}/\kappa \to\mathbf{Set}$ may be helpful.

A functor $F:\mathbf{Set}/\kappa \to\mathbf{Set}$ induced by a filter has the fibration-like property that every map $X\to F Y$ has a lifting $X'\to Y$. This weak lifting property requires the axiom of choice and there may be no terminal lifting, so the functor is not always actually a fibration.

Every left exact functor induces a filter: the filter of subterminal that are mapped to the terminal object. If a left exact functor $F:\mathbf{Set}/\kappa \to\mathbf{Set}$ has the weak lifting property, it is isomorphic to the left exact functor induced by its filter.