The n-Category Café

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 ultrafilter, 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.