## September 30, 2012

### 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 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.

Posted at September 30, 2012 5:11 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2564

### 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.

Posted by: Wouter Stekelenburg on September 30, 2012 2:32 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

That could be a start — thanks a lot. I’ll need to think about that.

(Incidentally, I fixed your Latex, which originally came out raw — lots of visible dollar signs etc. If you want to use Latex in a comment, you have to select a suitable option from the dropdown menu marked “Text Filter” in the comment window. Any option containing the word “itex” will do. I use “itex to MathML with parbreaks”.)

Posted by: Tom Leinster on September 30, 2012 2:37 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

I guess the result in your last sentence implies that ultrafilters on a set $K$ correspond one-to-one with functors $\mathbf{Set}^K \to \mathbf{Set}$ that (i) preserve finite limits, (ii) preserve finite coproducts, and (iii) have the weak lifting property that you describe. The correspondence is given by ultraproducts: an ultrafilter $\Omega$ on $K$ corresponds to the functor $\prod_\Omega \colon \mathbf{Set}^K \to \mathbf{Set}$.

That’s good, but I have two reservations. First, I don’t like this weak lifting property — it just seems ad hoc. Second, we’re not taking advantage of the fact that ultraproducts are defined on lots of categories, not just $\mathbf{Set}$. But maybe this is one of those nice situations where two problems cancel each other out?

Posted by: Tom Leinster on September 30, 2012 3:18 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

So what is, say, the codensity monad of the forgetful functor from ‘categories with finite limits and filtered colimits’ to ‘categories with finite limits’?

Posted by: Mike Shulman on September 30, 2012 4:37 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

Does this functor have a left adjoint? (Or at least, a left adjoint in a suitable 2-dimensional sense?) If so, the codensity monad is the monad induced by the adjunction.

Let’s see. The forgetful functor from (categories with filtered colimits) to (categories) does have a left adjoint, at least on small categories, and it sends $\mathbf{A}$ to $Flat(\mathbf{A}^{op}, Set)$. If $\mathbf{A}$ has finite limits, does $Flat(\mathbf{A}^{op}, Set)$? Without thinking about it too hard, I suppose it does.

The answer to your question must depend on whether “categories with finite limits and filtered colimits” secretly includes the condition that they commute.

Wait — isn’t it true on general principles that the forgetful functor you mention is 2-monadic?

Posted by: Tom Leinster on September 30, 2012 8:17 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

I haven’t thought about this very much, but the direction of your questions suggests that maybe we ought to impose some sort of finiteness condition on our “categories with finite limits and filtered colimits” (in addition to a commutativity). Maybe they should be locally finitely presentable.

Posted by: Mike Shulman on October 1, 2012 12:41 AM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

One tiny bit evidence that ultraproducts are not the most natural way for category theoretic model theory is that Awodey and Forssell avoid them in their duality theorem for first-order logic in First-Order Logical Duality.

Just like the Boolean Algebra (syntax for propositional logic)-Stone space (of models of propositional theories) duality, they develop a duality between the syntactic categories for first-order theories (Boolean coherent categories) and topological groupoids (of models).

…the categories of models of coherent theories can not, in general, be expected to have more structure than those for classical first-order theories. What they do have are ultra-products. Although ultra-products are not an intrinsic feature of categories of models (for coherent theories), in the sense that they are not a categorical invariant, Makkai [7] shows that model categories and the category of sets can be equipped with a notion of ultra-product structure—turning them into so-called ultra-categories—which allows for the characterization of definable set functors as those functors that preserve this additional structure.

By contrast, they

…present a ‘syntax-semantics’ duality which shows how to recover a coherent decidable or a classical first-order theory from its models. Compared with the duality theory of Makkai [7, 8], we give an alternative notion of external structure with which to equip the models, which in our case is topological instead of based on ultra-products. This permits the use of topos theory in establishing the main results, and in particular results in a semantic construction of the classifying topos of the theory.

But who knows maybe you need ultraproducts for things other than reconstructing a theory from its models. I wonder how compactness arguments work in their set-up. Presumably adding sentences to a theory is a process of quotienting on the syntax side dualized to an inclusion of models on the semantics side. So, there’s something about quotienting by finite subtheories on the syntax side and non-empty inclusions on the semantics side.

Posted by: David Corfield on September 30, 2012 4:49 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

Thanks for this, David. Of course, I’m not remotely competent to comment on the place of ultraproducts in model theory. They might be important in other contexts, though: for example, there’s a book by Hans Schoutens called The Use of Ultraproducts in Commutative Algebra.

I like thinking about topological compactness in terms of ultrafilter convergence. (For example, I like the fact that a space is compact if and only if every ultrafilter on it converges to at least one point.) I wonder whether it’s coincidence that I also like thinking about logical compactness in terms of ultraproducts. I’ll explain why I like this with a standard example.

Let’s say that an element $\varepsilon$ of an ordered field $k$ is infinitesimal if $\varepsilon \gt 0$ and $n \cdot \varepsilon \lt 1$ for all $n \in \mathbb{N}$.

Question: is there some ordered field containing an infinitesimal element?

Classic answer: yes. Add a constant symbol $\varepsilon$ to the first-order language of ordered fields, write $OF$ for the set of (first-order) axioms for ordered fields, and consider the set of axioms

$\Gamma = OF \cup \{ \varepsilon \gt 0 \} \cup \{ \varepsilon \lt 1,   \varepsilon + \varepsilon \lt 1,   \varepsilon + \varepsilon + \varepsilon \lt 1,   \ldots \}.$

Every finite subset of $\Gamma$ has a model, e.g. $\mathbb{R}$ equipped with a suitably small positive $\varepsilon$. So by the compactness theorem, $\Gamma$ itself has a model, as required.

Not-quite-so-classic answer: yes. Choose a nonprincipal ultrafilter $\Omega$ on $\mathbb{N}$. The ultrapower $\prod_\Omega \mathbb{R}$ has the structure of an ordered field, and contains an element

$\varepsilon = [(1, 1/2, 1/3, \ldots)].$

This $\varepsilon$ is infinitesimal. Indeed, it’s $\gt 0$ since each term $1/n$ is $\gt 0$. Also, given $n \in \mathbb{N}$, we have

$n \cdot \varepsilon = [(n, n/2, n/3, \ldots)]$

and all but finitely many of the terms $n, n/2, n/3, \ldots$ are $\lt 1$, so $n\cdot \varepsilon$ itself is $\lt 1$.

Comparison of the two answers The two answers are essentially the same: if you take the proof of the compactness theorem via ultraproducts and unwind it in the case at hand, the first answer becomes the second. Nevertheless, one can point to some aesthetic differences.

The first answer has the advantage that it makes no obtrusively arbitrary choices (unlike the second, where I chose arbitrarily not only an ultrafilter on $\mathbb{N}$ but also a real sequence converging to $0$). There is some arbitrariness there, though, since the compactness theorem merely asserts that there exists a model for $\Gamma$, and it’s certainly not unique.

The second answer has the advantage that it exhibits in an unmysterious way an ordered field with an infinitesimal element. (Well: maybe you think there’s some mystery involved in the existence of nonprincipal ultrafilters. If so, at least you can say that all the mystery is parcelled up there.) Moreover, the proof that the constructed $\varepsilon$ really is infinitesimal evokes the familiar idea that the first finite chunk of a sequence is unimportant.

The second answer also has the advantage — at least, it’s an advantage if you’re uncomfortable with logical terms — that it doesn’t use words like “model”, “language” and “first order”. It’s closer to the mainstream of structural mathematics. All you need to know is something about ultraproducts, and that doesn’t require a course on logic either.

I’m not trying to argue that one thing is better than the other; I’m just thinking aloud.

Posted by: Tom Leinster on September 30, 2012 9:25 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

It may be worth remarking that not only can you prove the compactness theorem using ultraproducts, but in fact the compactness theorem is logically equivalent to the ultrafilter theorem (every proper filter is contained in an ultrafilter), as a weak form of the axiom of choice.

Posted by: Mike Shulman on October 1, 2012 12:40 AM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

Interesting — I didn’t know that.

Posted by: Tom Leinster on October 1, 2012 12:51 AM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

The Wikipedia entry has

…the compactness theorem is equivalent to Gödel’s completeness theorem, and both are equivalent to the Boolean prime ideal theorem, a weak form of the axiom of choice.

and the Boolean prime ideal theorem states that

… ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on sets is known as the ultrafilter lemma.

Johnstone has notes on the prime ideal theorem in ‘Stone Spaces’, if memory serves.

I wonder if there’s an interesting take on compactness in the Awodey-Forssell picture.

Posted by: David Corfield on October 1, 2012 9:00 AM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

Were we to study category theoretic takes on completeness, we might look at:

• S. Awodey. Continuity and logical completeness: an application of sheaf theory and topoi. In The Age of Alternative Logics, pages 139-149. Springer, 2006.

• S. Awodey and C. Butz, Topological completeness for higher-order logic. Journal of Symbolic Logic 65(3), (2000) pp. 1168–82.

• M. Makkai. Generalized sketches as a framework for completeness theorems. Part I, Journal of Pure and Applied Algebra, 115(1):49-79, 1997.

• M. Makkai. Generalized sketches as a framework for completeness theorems. Part II, Journal of Pure and Applied Algebra, 115(2):179–212, 1997.

• M. Makkai and G.E. Reyes. Completeness results for intuitionistic and modal logic in a categorical setting. Annals of Pure and Applied Logic, 72(1):25-101, 1995.

A good resource for categorical logic is the bibliography provided by Hans Halvorson.

Posted by: David Corfield on October 1, 2012 11:23 AM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

Constructions of infinitesimals come in various shapes and sizes; this is a topic considered by G.H. Hardy and many others, long before Abraham Robinson came on the scene.

About the simplest ordered field which contains an infinitesimal is the field of germs of rational functions $\mathbb{R} \to \mathbb{R}$ “at infinity”, where functions are ordered by saying $f \leq g$ if $f(x) \leq g(x)$ for all sufficiently large $x$. It’s not too hard to see that for any two rational $f, g$, either $f(x) \lt g(x)$ or $f(x) = g(x)$ or $g(x) \lt f(x)$ for all sufficiently large $x$ (because if that weren’t true, then the graphs of $f$ and $g$ would intersect infinitely often, and we know that can’t happen for rational functions unless they are identically equal). Thus, germs of such functions do give an ordered field.

In this setting, ordinary reals are identified with germs of constant functions. The germ of $f(x) = x$, being greater than any constant, is an “infinite” element, and similarly any function of the form $f(x) = n/x$ is an infinitesimal element.

Ordered fields gotten by taking germs at infinity of suitable classes of functions are called “Hardy fields”. Hardy himself was interested in the asymptotics of functions that can be obtained by taking rational functions, the exponential and logarithmic functions, and closing under the four arithmetic operations and under composition. Germs of functions in this class give a very rich supply of infinite and infinitesimal quantities.

As I understand it, the idea of taking an ultraproduct is sort of an ultimate extrapolation of this idea of taking germs of functions “at infinity” to get infinitesimals.

First, the Stone-Cech compactification is a universal way of adding “ideal points at infinity” to complete the discrete space $\mathbb{N}$ to a compact space $\beta(\mathbb{N})$. Note that the inclusion $\mathbb{N} \hookrightarrow \mathbb{N} \cup \{\infty\}$ into the one-point compactification has a unique extension to a continuous map $\beta(\mathbb{N}) \to \mathbb{N} \cup \{\infty\}$, where the points in the fiber over $\infty$ are exactly the non-principal ultrafilters; in that sense, we can think of each non-principal ultrafilter as a “point at infinity”.

Let $U \in \beta(\mathbb{N})$ be a point at infinity. We say that two functions $f, g: \mathbb{N} \to \mathbb{R}$ have the same germ at $U$ if they are equal on all “sufficiently small” neighborhoods of $U$ in the Stone space $\beta(\mathbb{N})$. A basis of such neighborhoods is parametrized by subsets $S \in P(\mathbb{N})$, i.e., sets of the form

$\hat{S} = \{x \in \beta(\mathbb{N}): S \in x\}$

form a basis of (cl)open sets for $\beta(\mathbb{N})$. To say two functions $f, g: \mathbb{N} \to \mathbb{R}$ agree on some neighborhood of $U$ therefore means that for some $S \in U$, we have $f(n) = g(n)$ for all $n \in S$. Just as in the definition of ultraproduct.

Such ultraproducts are obviously quite enormous ordered field extensions of the reals, since the $f: \mathbb{N} \to \mathbb{R}$ we are considering don’t have to be particularly nice functions (like rational functions, or the sorts of functions considered by Hardy). It’s nice (although easy to see) that we indeed have an ordered field (i.e., the trichotomy law is satisfied), and there are enough elements in the field that it’s real closed and we can perform analytic operations on them – an advantage that Robinson infinitesimals have over your general run-of-the-mill Hardy fields.

Posted by: Todd Trimble on October 1, 2012 2:14 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

The germs-of-rational-functions example of an ordered field is really nice — thanks!

Posted by: Tom Leinster on October 2, 2012 10:17 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

By the way, Tom, what’s the move to Edinburgh?

Posted by: David Corfield on September 30, 2012 4:54 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

It’s a Chancellor’s fellowship, with a twist that’s too boring to go into here. In practice, it will involve similar commitments to my current job, but with reduced teaching and rain. (There’s 40% less rain in Edinburgh than Glasgow. Can you believe that? The two cities are less than an hour apart by train, but one has nearly twice the rainfall of the other.)

Posted by: Tom Leinster on September 30, 2012 8:28 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

So that’s at least two cheers and probably three, as I suspect you’re being modest.

These are prestigious awards aimed at high potential academics in the early stages of their careers who have begun to establish a reputation for top quality research.

Posted by: David Corfield on October 1, 2012 9:05 AM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

The twist is that I’m not really in the early stage of my “career”… Anyway, thanks. I’m writing this now from a sunny office in Edinburgh.

Posted by: Tom Leinster on October 1, 2012 1:15 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

Sorry for not having anything more constructive to say, but the correct spelling is “Łoś”, not “Łoš”.

Posted by: Karol Szumiło on October 1, 2012 7:32 AM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

Oops. Thanks for letting me know. Fixed now.

Posted by: Tom Leinster on October 1, 2012 7:43 AM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

I just want to throw in a couple of historical references on ultraproducts in categorical context which haven’t yet come up in the discussions on the blog:

The oldest source is probably

T. Okhuma, Ultrapowers in categories, Yokohama Math. J. 14
(1966), pp. 17-37.

The definition of ultraproducts as filtered colimits seems to originate from here

catégories, Journal of Algebra, Vol. 21, No. 3, pp. 410-421, June 1972.

Sabah Fakir expanded on this in his dissertation under J. Bénabou which contains a good deal of model theory in locally presentable cats and is online at numdat:

S.Fakir: Objets algèbriquement clos et injectifs dans les catégories localement présentables, Mémoires de la S.M.F tome 42 (1975) 5-75

In the following epoch two articles in the Can.J.Math. deal with categorical closure properties of ultraproducts:

G.Matthiessen: Regular and strongly finitary structures
over strongly algebroidal categories, Vol. XXX, No. 2, 1978, pp. 250-261

P.Bankston: Some obstacles to duality in topological algebra, Vol.XXXIV, No. 1, 1982, pp. 80-90

In the meantime in eastern Europe H.Andréka and I.Németi among others also studied categorical ultraproducts. The following online paper might serve as a pointer to this strang:

H.H.Bui, I.Németi: Problems with the category theoretic notions of ultraproducts, Bulletin of the Section of Logic Volume 10/3 (1981), pp. 122-126

In the context of the codensity monad where profinite structures show up naturally the following more recent paper might be interesting:
H.L.Mariano: Profinite structures are retracts of ultraproducts of finite structures, (arxiv math/0401095).

And finally, somewhat off the categorical track to ultraproducts, i would like to mention the classical and eminently readable source on what can be done with ultraproducts in model theory:

Bell,Slomson: Models and ultraproducts, North-Holland 1969 (reprint available from Dover).

This list is not meant to be exhaustive but intends to supplement the references already mentioned with some other articles I am aware of. Further references can be found in the references of the above listed or in the notes of R.Diaconescu ‘Institution-independent model theory’, Birkhäuser 2008.

—-

By the way, Tom, as you mention Kelly’s book in the historical section of your paper, you might as well refer to Dubuc, ‘Kan extensions in enriched category theory’, LNM 145, 1970. Dubuc does quite a bit of work with the codensity monad e.g. you find a version of prop.6.5 on p.74, which is, I guess, a translation to the enriched context of Linton’s generalisation of the syntax-semantics adjunction from Lawvere’s dissertation.

Posted by: thomas holder on October 2, 2012 2:50 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

Wow, that’s impressive!

At the very least, I should look up Okhuma and Dubuc. I should also look up Fakir and Haddad’s paper — the construction of ultraproducts as filtered colimits maybe isn’t such a big deal, but I’m curious to know what else is in there.

Posted by: Tom Leinster on October 2, 2012 10:53 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

The categorical definition of ultraproducts might be somewhat tricky though as Bui-Németi mention that in the cat of totally ordered sets categorical ultraproducts fail to exist in cases where the model theoretic ultraproducts do exist.
Before ending up with the list I had merely the intention to promote Fakir’s dissertation as he even treats model completions and model companions which I have never seen coming up in categorical discussions anywhere else. There is a fair deal of model-theoretic algebra and its translation into category theory which at the time must have been really innovative.
I haven’t actually seen the first two papers. If you happen to come across the Okhuma paper please correct me if I have been wrong with the attribution of the definition to Fakir-Haddad. There is some confusion about this in the literature: Bui-Németi refer to Okhuma and as Fakir does not cite him in his dissertation he was probably simply not aware of the reference.

Posted by: thomas holder on October 3, 2012 10:50 AM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

Right, I’ll add Bui–Németi to my list. Do you know the paper of Barr cited in my own paper? It has a short appendix on ultraproducts, which is kind of a little rant, but an interesting one. I think he makes the point there that ultraproducts can exist in categories that don’t have all products (though I might not be remembering correctly).

Here’s a simple example. Take a finite set $B$, seen as a discrete category. Also take a set $X$, an ultrafilter $\Omega$ on $X$, and an $X$-indexed family $(b_x)_{x \in X}$ of elements of $B$. What should we take the ultraproduct $\prod_\Omega b_\bullet$ to be?

Obviously the category $B$ is very far from having all products. Yet, we can make sense of the ultraproduct. For since $B$ is finite, there’s some $Z \in \Omega$ such that $(b_z)_{z \in Z}$ is a constant family — the constant being $\int_X b_\bullet \, d\Omega$. It follows that for any $Y \in \Omega$, all but a small number of the elements $b_y$ ($y \in Y$) are equal to $\int_X b_\bullet \, d\Omega$.

Usually when constructing the ultraproduct we’d take the filtered colimit of $\prod_{y \in Y} b_y$ over all $Y \in \Omega$. But it’s in the spirit of things to let $Y$ range over only the large subsets of $Z$ (since in any case, $Y \cap Z$ is a large subset of $Y$ that’s also a subset of $Z$). The product of a constant family in a discrete category is just that constant, so the filtered colimit of $\prod_{y \in Y} b_y$ over all large $Y \subseteq Z$ is simply $\int_X b_\bullet \, d\Omega$ again. So that’s the right thing to take the ultraproduct to be.

Posted by: Tom Leinster on October 3, 2012 11:42 AM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

Thanks for the example, I’ll have a look at the Barr paper.
I kind of pushed the Bui-Németi paper also because Diaconescu mentions that the Hungarian school uses an entirely different approach to ultraproducts and their paper refers to the following one with a rather interesting title:

H. Andréka and I. Németi, Los lemma holds in every category,
Studia Sci. Math. Hungar., Vol. 13 (1978), pp. 361-376.

(sorry for the inadequate spelling of Los due to my lack of typographical sophistication!)

Posted by: thomas holder on October 3, 2012 2:43 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

After taking a look at the Fakir-Haddad paper I must correct myself: they credit Okhuma with the categorical definition of ultraproducts.

I keep bumping into other online-papers on the subject:

D.Ellerman: Sheaves of structures and generalized ultraproducts, Ann.Math.Logic 7, 1974

J.Kennison: Triples and compact sheaf representations, J.Pure.Appl.Alg. 20, 1981

As Tom mentions in the paper, the ultraproduct A_U of a family (A_i,i in X) arises as the stalk at the ultrafilter U of a sheaf on the set ßX of ultrafilters on X. The process is functorial. There is even an adjunction between the functor mapping a discrete sheaf on X to this so called ultrasheaf on ßX and the forgetful functor mapping a compact sheaf to its underlying discrete sheaf. Kennison shows that the forgetful functor is monadic so the ultrasheaf monad ressembles the ultrafilter monad.
I am not sure how far analogical thinking goes in a digital era but this suggests: finite sets relate to ultrafilters like finite families relate to sheaves of ultraproducts!

Before I stop let me mention two more papers that are available online:

Lawvere considers generalized ultraproducts in

‘Quantifiers and Sheaves’, Actes du congrès international des mathématiciens, Nice 1970, Tome I, Gauthier-Villars

Awodey, Steve and Eliasson, Jonas, “Ultrasheaves and Double Negation” (2003). Department of Philosophy. Paper 68.

Posted by: thomas holder on October 16, 2012 7:02 PM | Permalink | Reply to this

You are bringing together ideas from a very wide range of disciplines that have hitherto not had much categorical attention, so we can hope to see lots of useful comments from outside our subject. On the other hand, you have started from categorical principles and I know that you have good categorical intuition, so I am looking forward to a nice piece of category theory at the end of it that will not rely so heavily on set theory as the traditional material that you have described.

I take issue with your statement that “ultrafilters are inevitable”, because it is uninformative and loaded. What you might say instead is that they are “complementary” to finite sets, but (linguistically) implicit in that is an idea of what the “complete” things are. I had previously thought of directed or filtered diagrams as the “purely infinite” ones, but that was when the “complete” things were complete semilattices: in your case they are perhaps complete Boolean algebras or toposes.

So you have obtained ultrafilters by subtracting finite sets from all sets, and the set-theoretic ideas come from the latter, even if you replace sets by an elementary topos.

What do you actually require of an inclusion of categories in this role in order to reproduce mathematical phenomena similar to those that you have described?

Can you find examples of such inclusions where (meaningful parts of your development still go through but) this “difference” is much smaller?

For example, for me finite sets are compact Hausdorff overt discrete spaces. So I might consider them as a subcategory of a model of Abstract Stone Duality (or the category of locally compact sober spaces) or some other constructive formulation of topology.

Posted by: Paul Taylor on October 1, 2012 2:20 PM | Permalink | Reply to this

### Re: less set theory please

Thanks for the interesting thoughts. It’s funny that you say “less set theory”, because where this paper started for me wasn’t set theory at all: it was measure theory.

I’d been wondering whether (in some nebulous sense) measure spaces could be completely understood by chopping them into a finite number of pieces. For example, entropy for measures on a finite set is very easy, and I thought this chopping idea might help me to get a grip on entropy for general measure spaces. (I really mean probability spaces here, not measure spaces, but that’s beside the point.) I expressed this thought to Mark Meckes, who instinctively guessed that it wouldn’t work.

When I tried to make my question precise, I ended up with this: is the category of measure spaces with finite underlying set codense in the category of all measure spaces? After a while I realized that I didn’t even know whether the category of finite sets was codense in the category of sets. Once I’d figured out that the answer to that was no, it was fairly easy to deduce that the answer to the question about measure spaces was also no. The reason is the same: the existence of nonprincipal ultrafilters.

(So Mark was right.)

In the end I decided that the measure space question wasn’t that interesting — it’s just the $\mathbf{FinSet} \hookrightarrow \mathbf{Set}$ example with a bit of window-dressing. So, disloyally, I dropped it from the paper that it had brought into existence.

What do you actually require of an inclusion of categories in this role in order to reproduce mathematical phenomena similar to those that you have described?

I don’t know. I suppose I only have a hazy idea of what would count as similar phenomena, so it’s hard to say. I did go through lots of examples of codensity monads, in my head or on paper. In a lot of cases, something trivial or semi-trivial came out. (Under “semi-trivial” I’d put the examples that come from inclusions of ordered sets.) In other cases, I couldn’t see what the codensity monad was or whether it existed. (For example, I don’t know whether the free group functor from sets to groups has a codensity monad.) I probably included in the paper all the interesting ones I thought of.

By the way, would you count the vector space example, $\mathbf{FDVect} \hookrightarrow \mathbf{Vect}$, as inherently set-theoretic?

Can you find examples of such inclusions where (meaningful parts of your development still go through but) this “difference” is much smaller?

I just now tried things like the inclusion of the category of nonempty sets into $\mathbf{Set}$, or the inclusion of a category into the same category with a terminal object freely adjoined, thus aiming for something where the difference is really small. But the answers seem to be trivial (which is maybe inevitable). I can’t think of any interesting example in the middle.

Posted by: Tom Leinster on October 2, 2012 10:43 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

So what might $\mathbf{Set}$, $\mathbf{Ring}$, $\mathbf{Field}$ belong to that we can integrate functions valued in them against an ultrafilter? Presumably the category of models of any first-order theory would do.

How to characterise the model categories (or groupoids) of first-order theories? Makkai speaks of ultra-categories or groupoids, e.g., ones equipped with a notion of ultraproduct structure.

Would we then be looking to include ultra-groupoids, or whatever, in some larger (2-)category and forming a codensity monad?

Hmm, I can’t get hold of any of Makkai’s writings on this

• Michael Makkai. Stone duality for first order logic. Advances in Mathematics, 65(2):97-170, 1987.
• Michael Makkai. Strong conceptual completeness for first order logic. Annals of Pure and Applied Logic, 40:167-215, 1988.
• Michael Makkai. Duality and Definability in First Order Logic. Number 503 in Memoirs of the American Mathematical Society. American Mathematical Society, 1993.

An ultra-groupoid is a groupoid with ultraproducts and limit ultrapowers, as well as additional ultraproduct and limit ultrapower related structure, including certain relations on arrows and a notion of ultra-morphism, see [19]. Together with structure preserving (up to specified transition isomorphisms) groupoid functors (ultra-functors) and certain invertible natural transformations between them (ultra-transformations), these form the groupoid-enriched category of ultra groupoids.

Then you can set up a duality with the 2-category of

Boolean pretopoi, coherent functors between the pretopoi, and invertible natural transformation between functors.

But maybe good category theorists as we are, we should prefer Awodey and Forssell’s Stone groupoids of models.

Hmm, do you know of any codensity 2-monads from the inclusion of 2-categories? Shouldn’t the $X$ of the ‘voters’ be generalised to something more than a possibly infinite set?

Posted by: David Corfield on October 1, 2012 3:08 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

Shouldn’t the $X$ of the ‘voters’ be generalised to something more than a possibly infinite set?

Yes, quite possibly. I’d had the same thought, but I don’t have much of an idea what the answer might be.

Posted by: Tom Leinster on October 2, 2012 11:04 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

I guess one thing going on is that voting over Fields works like this. For a set $X$ of voters, we have

$X \to Fields,$

which is

$X \to Sets^{Th(Field)}.$

If I could say this is equivalent to a map

$Th(Field) \to Sets^X,$

then the latter can be postcomposed with ultrafilter integration

$Sets^X \to Sets,$

giving a map $Th(Field) \to Set$, i.e., a field.

But what world do all these objects live in? All the people I mentioned before would have $Th(Field)$ as a Boolean pretopos. $Sets$ is an ambimorphic, dualizing object, living in the syntactic and semantic worlds.

Posted by: David Corfield on October 3, 2012 10:00 AM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

I’m not sure I understand what you mean, David. Given an ultrafilter $\Omega$ on a set $X$, integration against $\Omega$ defines a map $B^X \to B$ for any finite set $B$. It doesn’t define a functor $Set^X \to Set$. Or when you wrote “ultrafilter integration $Sets^X \to Sets$”, did you actually mean “ultraproduct $Sets^X \to Sets$”?

Posted by: Tom Leinster on October 5, 2012 2:49 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

Whoops, yes, I meant ultraproduct. Presumably models of classical theories are inheriting the capacity of sets to form ultraproducts.

Posted by: David Corfield on October 5, 2012 9:32 PM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

Michael Makkai. Stone duality for first order logic. Advances in Mathematics, 65(2):97-170, 1987.

Michael Makkai. Strong conceptual completeness for first order logic. Annals of Pure and Applied Logic, 40:167-215, 1988.

Posted by: David Roberts on October 4, 2012 2:53 AM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

Ah good, thanks. It seemed that via one route our library only had these journals in limited time ranges.

Anyway, let’s see, from the second

The essence of the main result of [14] is that the functors commuting with ultraproducts and ultramorphisms are exactly the definable functors of (the pretopos completion of) $T$.

So, given the set of models of a first-order theory $T$, we can reconstruct the theory (or its pretopos completion) by locating those functors commuting as said. These are definable functors, i.e., of the kind which sends objects in the category of models to their interpretations of a specific formula.

However,

…the objection was made by some that the notion of ultramorphism is too complicated to be of real interest.

In [15], I reformulated the result in the form of a structure theorem on (part of) the (meta-) 2-category PRETOP of all pretoposes in which theorem Set plays a distinguished role. The result now took the form of a construction of a 2-functor into PRETOP taking values that are Set and some iterated small limits formed Strong conceptual completeness out of Set, which could be shown to be codense at all small pretoposes. The point of the paper was that, apparently, the mere existence of such a functor was non-trivial, and it represented a more conceptual version of the result of [14].

The main result of the present paper is a two fold improvement on [15]. On the one hand, it shows the codensity of an appropriate functor at each member of a class of pretoposes not only including all small pretoposes but also containing Set and its iterated small limits. This allows one to talk about the codensity of a functor into a natural 2-category of pretoposes in the full sense, not just at certain objects of it. On the other hand, by a general lifting lemma, one is now able to conclude the codensity of a simply defined full inclusion.

Good to see codensity looming large.

Posted by: David Corfield on October 4, 2012 8:47 AM | Permalink | Reply to this

### Re: Where Do Ultraproducts Come From?

I was trying to be subtle, but oh well:

Posted by: David Roberts on October 5, 2012 3:03 AM | Permalink | Reply to this