Is the ultraproduct concept fundamentally category-theoretic? - MathOverflow

Is the ultraproduct concept fundamentally category-theoretic?

2010-01-09T22:12:09Z

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 M_i 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 ΠM_i /U consists of equivalence classes [f]_U, where f is a function with domain J, with f(i) in M_i, 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 | M_i 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 M_i are the same model M, we arrive at the ultrapower M^J /U. In this case, there is a natural map from M into M^J /U, defined by x maps to [c_x]_U, where c_x 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.

Answer by Andrej Bauer for Is the ultraproduct concept fundamentally category-theoretic?

2010-01-10T07:43:39Z

This paper comes to mind:

Ultrasheaves and double negation. S. Awodey and J. Eliasson, Notre Dame Journal of Formal Logic 45(4), pp. 235--245 (2004). Available at http://www.andrew.cmu.edu/user/awodey/preprints/udn.pdf

Perhaps this is not quite what you are asking for, because the paper takes utrafilters as given, but it certainly gives a useful category-theoretic perspective.

Answer by François G. Dorais for Is the ultraproduct concept fundamentally category-theoretic?

2010-01-30T03:14:24Z

Andrej's answer was very helpful to me, but there is yet another (perhaps not completely unrelated) category theoretic view of ultraproducts that I am aware of. I am still hopeful that more category theorists will eventually step in and sort things out...

If $X$ is a discrete space then a sheaf $F:O(X)^{\mathrm{op}}\to Set$ must be such that $F(A) \cong \prod_{i \in A} F_i$ for some family of sets $(F_i)_{i \in X}$. This sheaf can be moved to a sheaf $F':O(\beta X)^{\mathrm{op}}\to Set$ . Viewing $\beta X$ as the space of ultrafilters on $X$, the stalk of $F'$ at a point $\mathcal{U} \in \beta X$ is precisely the ultraproduct $\prod_{i \in X} F_i/\mathcal{U}$ . (There is one subtle difference which occurs when some of the components $F_i$ are empty, in which case this ultraproduct can still be nonempty when $F(A)$ is nonempty for some $A \in \mathcal{U}$.)

From a more global point of view, the embedding $X \to \beta X$ induces a geometric morphism $Sh(X) \to Sh(\beta X)$. Similarly, a point of $\beta X$ can be identified with geometric morphism $\mathcal{U}:Set \to Sh(\beta X)$. The corresponding ultraproduct map is simply the composition $$Sh(X) \to Sh(\beta X) \xrightarrow{\mathcal{U}^*} Set,$$ where the last component is the inverse image part of $\mathcal{U}$. The corresponding ultrapower functor is the composite $$Set \xrightarrow{\Delta} Sh(X) \to Sh(\beta X) \xrightarrow{\mathcal{U}^*} Set,$$ where $\Delta$ is the diagonal functor.

Of course, there is nothing very special about discrete spaces in the above construction. The same construction exists for any completely regular Hausdorff space $X$ or, more generally, for a completely regular locale. (This makes sense even when the space/locale $X$ is not completely regular, but the map $X \to \beta X$ is not necessarily an embedding.) Of course, Łoś's Theorem takes a different form for this more general construction, the correct form of the theorem for a space/locale X can be found via the Kripke-Joyal semantics, for example.

Answer by Buschi Sergio for Is the ultraproduct concept fundamentally category-theoretic?

2010-05-28T16:55:05Z

Let $\Phi$ a filter on the set $I$ and let $X_i \in C\ i\in I$, and for $U \subset I$ let $X_U:=\prod_{i\in U} X_i$ . We have a natural functor $T : P(I)^{op} \to C$ (where $P(I)$ the order of ubset onf $I$) as: $T(U):=X_U$ and for $T(V\subset U) : X_U \to X_V$ the canonical proiection induced by $V \subset U$. Being $I$ the initial object of $P(I)$ and letting $X:=X_I$ follow a "lifting" of $T$ to a functor $T': P(I)^{op} \to X \downarrow C$ as $T'(U)= (T(U\subset I), X_U)$ and $T'(V\subset U)=T(V\subset U) $. For any $U \in \Phi$ let $\alpha_U, \beta_U : K_U \to X$ the kernel pair of $T'(U)$ we obtain a diagram of all these $\alpha_U, \beta_U$ morphisms and the natural $K_{V \subset U}: K_U\to K_V$ induced by $T(V \subset U)$. The colimit of this diagram is the ultrapower of $\prod_{i\in I} X_i$ respecto to $\Phi$. This colimit is the colimits in $X\downarrow C$ of the cokers of the kernel pairs.

But things are more simple too: observe that choise a retraction $r: I\to U$ os the inclusion $U\subset I$ we have a section $T(r): T(U)\to X$ on $T(U\subset I)$ give by $\pi_i\circ T(r) = \pi_{r(i)}$ then $T(U\subset I)$ being a retraction is a regular epimorphism (a coker of some pair), then is (well knowed fact) the coker of its Ker-pair $\alpha_U, \beta_U$. Then follow that the ultrapower is the colimit in $X\downarrow C$ of the diagram of $T(U\subset I)\ U\subset I$ as objects and $T(V\subset U)$ as morphisms.

Answer by Daniel Litt for Is the ultraproduct concept fundamentally category-theoretic?

2010-07-06T15:02:33Z

The other answers so far have generally taken ultrafilters as a given, or used the Stone-Cech compactification (which has a universal property in Top). I'd like to point out that the set of ultrafilters on a set $I$ has a categorical interpretation in Sets. In particular, consider the diagram in Sets consisting of finite partitions $X_i\subset 2^I$ of $I$, with an arrow $X_i\to X_j$ if $X_i$ is a refinement of $X_j$; the arrow sends a subset of $I$ in $X_i$ to the unique element of $X_j$ containing it. Then the set of ultrafilters on $I$ is the inverse limit of this diagram.

Answer by Peter Arndt for Is the ultraproduct concept fundamentally category-theoretic?

2010-07-06T16:50:09Z

For a short and painless description of how ultraproducts are colimits see page 6 of this article (it is equivalent, but I found it more readable than the descriptions given in the answers):

H. Mariano, F. Miraglia: Profinite structures are retracts of ultraproducts of finite structures

The article contains a nice application of this categorical description of ultraproducts...