nLab
ultraproduct

Idea

The ultraproduct construction is an important tool in model theory that permits to produce a new structure from an infinite family of structures. The construction has a decidedly ‘algebraic’ flavor and hence occurs naturally in applications of model theory to algebra.

It is closely related via the Łoś ultraproduct theorem? to the compactness theorem: suppose one is given a set of formulas SS in some first-order language and a family of structures such that any finite subset of formulas is modeled by all but a finite number of structures. Then an ultraproduct of those structures may be used to model the entire set SS.1

In slightly greater detail, given a family of structures of the same signature in the sense of model theory (or more specially, universal algebra), one can (assuming the ultrafilter principle, a weak form of the axiom of choice) use ultrafilters to form a certain congruence on the direct product and construct a quotient object, a new structure of the same signature, called an ultraproduct. As long as the ultrafilter is free (contains the filter of cofinite subsets), the last sentence of the preceding paragraph is validated.

An ultraproduct of some number of copies of the same structure is called an ultrapower.

Another important facet, somewhat reminiscent of Morita equivalence, is the Keisler-Shelah theorem?: Two structures are elementary equivalent 𝔄𝔅\mathfrak{A}\equiv\mathfrak{B} iff they have isomorphic ultrapowers: 𝔄 I/𝒰𝔅 I/𝒰\mathfrak{A}^I / \mathcal{U} \cong \mathfrak{B}^I / \mathcal{U} for some set II and ultrafilter 𝒰\mathcal{U}. This deep result says that the partially syntactic concept of elementary equivalence can be characterized in purely semantic form with the help of ultrapowers.

Definition

First we present the bare-bones set-theoretic construction; then we discuss structures and models.

Set-theoretic

Definition

Let XX be a set, and let UU be an ultrafilter on XX, which may be regarded as an element U:1βXU: 1 \to \beta X of the Stone-Cech compactification βX=hom Bool(2 X,2)\beta X = \hom_{Bool}(2^X, 2) with its usual topology. The ultrapower functor over UU is the functor

Set/XSh(X disc)i *Sh(βX)U *SetSet/X \simeq Sh(X_{disc}) \stackrel{i_\ast}{\to} Sh(\beta X) \stackrel{U^\ast}{\to} Set

where i *i_\ast is the direct image functor between categories of sheaves induced from the inclusion i:XβXi: X \to \beta X of XX as a discrete subspace, and the inverse image functor U *U^\ast is also known as the “taking the stalk” functor at the point UβXU \in \beta X.

Let us extract a more concrete description. Let {Y x:xX}\{Y_x: x \in X\} be an XX-indexed family of sets, which we can view as an object YXY \to X of Set/X\Set/X. We may view this object as a sheaf over XX as discrete space; as a presheaf, it takes an open set (an arbitrary subset AXA \subseteq X) to the set of sections over AA which is xAY x\prod_{x \in A} Y_x. The direct image functor i *i_\ast takes this presheaf to the presheaf which sends an arbitrary open set 𝒱βX\mathcal{V} \subseteq \beta X to xX𝒱Y x\prod_{x \in X \cap \mathcal{V}} Y_x, and then the stalk functor U *U^\ast sends this to the filtered colimit

colim 𝒱U xX𝒱Y xcolim_{\mathcal{V} \ni U} \prod_{x \in X \cap \mathcal{V}} Y_x

and since the basic opens 𝒱 A={UβX:AU}\mathcal{V}_A = \{U' \in \beta X: A \in U'\} with AUA \in U are cofinal in the system of open neighborhoods of UU (ordered by reverse inclusion), the colimit may be written more simply as

colim AU xAY xcolim_{A \in U} \prod_{x \in A} Y_x

and this is the ultraproduct, often written as xXY x/U\prod_{x \in X} Y_x/U.2 When all the fibers Y xY_x are the same set ZZ, this is written as Z X/UZ^X/U and called an ultrapower of ZZ.

Ultraproducts of structures

Now suppose each Y xY_x carries a structure specified by a signature; in other words, for each function symbol ff and predicate symbol RR of the signature there are specified operations and subsets

ω f:Y x ar(f)Y x,ρ RY x ar(R)\omega_f: Y_x^{ar(f)} \to Y_x, \qquad \rho_R \rightarrowtail Y_x^{ar(R)}

where arar denotes arity (constants being considered function symbols of arity zero). Then of course the products aAY x\prod_{a \in A} Y_x carry structures canonically induced from those on the Y xY_x. As all of the function symbols ff and predicate symbols RR have finite arity, and since the taking of filtered colimits commutes with finite limits in SetSet, we get a canonically induced structure on the ultraproduct xXY x/U\prod_{x \in X} Y_x/U. More briefly: since U *i *U^\ast i_\ast preserves finite limits, it takes an XX-indexed finitary structure Y xY_x in Set/XSet/X to a finitary structure of the same type in SetSet.

Intuitively (and adopting language used by Lawvere), what is going on is that we have a variable structure varying over some domain XX, and we consider a point UU of its compactification βX\beta X as some kind of “ideal point at infinity”, and then we “freeze” (or localize) the variation by passing to germs of the variation at that point UU.

Notice that if we replace the word “ultrafilter” by the word “filter”, the general structural facts mentioned here would remain true. That is to say: if FF is a filter consisting of subsets of XX, then the colimit colim AF xAcolim_{A \in F} \prod_{x \in A} (with such AA ordered by reverse inclusion) is still directed or filtered, and we would still get a structure of given finitary type by passing to the colimit. Here, instead of ultrapowers and ultraproducts, one speaks of reduced powers and reduced products.

Ultraproducts of models

To be written.

Examples

The hyperreal numbers (wikipedia) and nonstandard integers in nonstandard analysis are obtained as countable ultrapowers with help of free ultrafilters on \mathbb{N}. Such ultrafilters contain all cofinite? subsets of integers, but not only them. See wikipedia:ultraproduct.

From Michael Barr’s Models of Sketches

Unlike limits and colimits, an ultraproduct is not defined by any universal mapping property. Of course, if the category has limits and (filtered) colimits, then it has ultraproducts constructed as colimits of products … But usually the category of models of a coherent theory (such as the theory of fields) lacks products and hence does not have categorical ultraproducts.

References

Standard references in model theory for ultraproducts are

  • J. L. Bell, A. B. Slomson, Models and Ultraproducts: An Introduction , North-Holland Amsterdam 1969. (Dover reprint)

  • P. C. Eklof, Ultraproducts for Algebraists , pp.105-137 in Barwise (ed.), Handbook of Mathematical Logic , Elsevier Amsterdam 1977.

For a more recent textbook treatment see

  • Wilfrid Hodges, Model Theory , Cambridge University Press 1993. (sec. 9.5)

The categorical perspective on ultraproducts goes back to

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

  • S. Fakir, L. Haddad, Objets cohérents et ultraproduits dans les catégories , Journal of Algebra 21 (1972) pp.410–421.

For the vacuum engineering point of view of ‘freezing variation’ 3 in the context of non-standard analysis see

  • F. William Lawvere, Variable sets etendu and variable structure in topoi , Lecture notes University of Chicago 1975.

The following papers are relevant for understanding the ultraproduct construction via codensity monads:

  • D. P. Ellerman, Sheaves of structures and generalized ultraproducts , Annals of Mathematical Logic 7 (1974) pp.163–195.

  • J. F. Kennison, Triples and compact sheaf representation , JPAA 20 (1981) pp.13-38.

  • Tom Leinster, Codensity and the Ultrafilter Monad , TAC 28 no. 13 (2013) pp.332-370. (tac)

See also

  • M. Makkai, Ultraproducts and categorical logic , Lectures Notes in Math. 1130, Springer 1985, pp. 222–309.


  1. Due to the outstanding importance of the compactness theorem, it is possible to prove ‘almost all’ results in model theory by the use of ultraproducts. This approach to model theory is pursued in Bell-Slomson (1969). For contrast, compare with the more sober view of Hodges (1993).

  2. The quotient notation is traditional but (ever so slightly) misleading. If all the Y xY_x are inhabited sets, then all the maps xAY x xBY x\prod_{x \in A} Y_x \to \prod_{x \in B} Y_x (BAB \subseteq A) are quotient maps and the ultraproduct is a quotient of the full product xXY x\prod_{x \in X} Y_x; there the notation is apt. If one of the Y xY_x is empty, then the full product is empty and thus the ultraproduct is not such a quotient. But it is useful to allow for empty models (when they exist)! The correct definition which works for all cases is as we have it: a filtered colimit over restricted products.

  3. This perspective was apparently inspired by joined work with Miles Tierney on the use of forcing in the context of the continuum hypothesis in early topos theory.

Revised on July 12, 2015 16:18:56 by Thomas Holder (89.204.138.179)