[Math] Is the ultraproduct concept fundamentally category-theoretic

ct.category-theorylo.logicmodel-theoryset-theory

Once again, I would like to take advantage of the large number of knowledgable category theorists on this site for a question I have about category-theoretic aspects of a fundamental logic concept.

My question is whether the ultraproduct construction is fundamentally a category-theoretic concept.

The ultraproduct/ultrapower construction of Łos is used pervasively in logic, particularly in model theory and also in set theory, where nearly all of the larger large cardinal axioms can be formulated in terms of the existence of certain kinds of ultrapowers of the universe.

My question is, is the ultraproduct fundamentally a category-theoretic construction, in the sense that it is characterized by some natural category-theoretic universal property? How about the special case of ultrapowers?

I would be very interested, if there were a natural universal characterization in terms of the usual Hom sets for these first order structures, namely, first order elementary embeddings and/or homomorphisms. (Needless to say, I would be much less interested in a characterization that amounted merely to a translation of the Łos construction or of Łos's theorem into category-theoretic language.)

Background. Suppose we have a collection of structures Mi for i in J, all of the same first order type (e.g. groups, partial orders, graphs, fields, whatever), and U is an ultrafilter on the index set J. This means that U is a nonempty collection of nonempty subsets of J, containing every set or its complement, and closed under intersection and superset. The ultraproduct ΠMi /U consists of equivalence classes [f]U, where f is a function with domain J, with f(i) in Mi, and f ∼Ug iff {i in J | f(i)=g(i)} in U. One imposes structure on the ultraproduct by saying that a relation holds in the product, if it holds on a set in U, and similarly for functions. Łos's theorem then states that the ultraproduct satisfies a first order formula φ([f]u) if and only if {i in J | Mi satisfies φ(f(i))} is in U. That is, truth in the ultraproduct amounts to truth on a U-large set of coordinates. The special case when all Mi are the same model M, we arrive at the ultrapower MJ /U. In this case, there is a natural map from M into MJ /U, defined by x maps to [cx]U, where cx is the constant function with value x. It is easy to see that this map is an elementary embedding from M into the ultrapower.

This question is a more focused instance of a probably-too-general question I asked here, and I may have several more in the future.

Best Answer

Yes. This is the content of the final section of my paper Codensity and the ultrafilter monad. Loosely, what's shown there is:

There is a standard piece of categorical machinery which, when fed as input the concept of finiteness of a family of structures, produces as output the concept of ultraproduct.

Let me say immediately that the result is due not to me, but to the anonymous referee. In the version of the paper I submitted to the journal (and in earlier arXiv versions), the final section essentially said "it looks like we should be able to describe the ultraproduct construction as a codensity monad, but I don't see how". The referee showed how, and I've included his or her theorem in the final version of the paper.

The "standard piece of categorical machinery" is the notion of codensity monad. "Recall" that (subject to the existence of certain limits) any functor $G\colon \mathcal{B} \to \mathcal{A}$ induces a monad on $\mathcal{A}$, the codensity monad of $G$. In the case where $G$ has a left adjoint $F$, this is just the monad $GF$, but codensity monads are defined in much wider generality.

(If you don't know what a monad is, then for the purposes of this answer, you can interpret "monad on $\mathcal{A}$" as "functor $\mathcal{A} \to \mathcal{A}$", although it's rather more than that.)

Fix a category $\mathcal{E}$ with small products and filtered colimits. (In model theory, this might typically be the category of structures for some finitary signature.) Let $\mathbf{Fam}(\mathcal{E})$ be the category in which an object is a set $X$ together with a family $(S_x)_{x \in X}$ of objects $S_x$ of $\mathcal{E}$. I'll skip the definition of the maps, but you can find it in my paper.

The ultraproduct construction determines a monad on $\mathcal{E}$, as follows. Given a family $$ S = (S_x)_{x \in X} $$ of objects of $\mathcal{E}$, taking ultraproducts produces a new family $$ \Bigl( \prod\nolimits_{\mathcal{U}} S \Bigr)_{\text{ultrafilters } \mathcal{U} \text{ on } X} $$ of objects of $\mathcal{E}$, where $\prod\nolimits_{\mathcal{U}} S$ denotes the ultraproduct of $(S_x)_{x \in X}$ with respect to $\mathcal{U}$. So, it's plausible that the ultraproduct construction gives at least a functor $\mathbf{Fam}(\mathcal{E}) \to \mathbf{Fam}(\mathcal{E})$. In fact, it gives not just a functor but a monad on $\mathbf{Fam}(\mathcal{E})$, the ultraproduct monad for $\mathcal{E}$.

The theorem is that this is a codensity monad. Specifically, let $\mathbf{FinFam}(\mathcal{E})$ be the full subcategory of $\mathbf{Fam}(\mathcal{E})$ consisting of those objects $(S_x)_{x \in X}$ in which the indexing set $X$ is finite. Then:

Theorem The codensity monad of the inclusion functor $\mathbf{FinFam}(\mathcal{E}) \hookrightarrow \mathbf{Fam}(\mathcal{E})$ is the ultraproduct monad for $\mathcal{E}$.

Notice that the concept of ultrafilter isn't taken as given. Actually, the concept of ultrafilter also arises as a codensity monad. This is a 1971 theorem of Kennison and Gildenhuys (discussed in my paper):

Theorem (Kennison and Gildenhuys) The codensity monad of the inclusion functor $\mathbf{FinSet} \hookrightarrow \mathbf{Set}$ is the ultrafilter monad.

Here $\mathbf{FinSet}$ is the category of finite sets, and the ultrafilter monad is the monad on $\mathbf{Set}$ that sends a set $X$ to the set of ultrafilters on $X$.