nLab Łoś ultraproduct theorem

Contents

Contents

Idea

The Łoś ultraproduct theorem characterizes the first-order theory of an ultraproduct of \mathcal{L}-structures (for \mathcal{L} some signature). It generalizes the transfer principle from nonstandard analysis, by replacing the hyperreals *^*\mathbb{R} with an ultraproduct and formulas from the standard reals \mathbb{R} with formulas which are true on an “ultrafilter-large” subset of factors of the ultraproduct.

Definition

The theorem is usually given in this form:

Theorem

let (A i) iI(A_i)_{i \in I} be a family of nonempty \mathcal{L}-structures, and let 𝒰\mathcal{U} be an ultrafilter on II. Let *A^* A be the ultraproduct of A iA_i with respect to 𝒰\mathcal{U}. Since each A iA_i was nonempty, *A^* A is the quotient of the product iIA i\prod_{i \in I} A_i by the equivalence relation which identifies sequences which coincide on a subset of indices belonging to 𝒰\mathcal{U}. Let (a i) iI(a_i)_{i \in I} be such a sequence, and let [(a i)][(a_i)] denote its equivalence class. Then for each \mathcal{L}-formula φ(x)\varphi(x),

*Aφ([a i]){jI|A jφ(a j)}𝒰.^* A \models \varphi([a_i]) \iff \{j \in I | A_j \models \varphi(a_j)\} \in \mathcal{U}.

The above follows from a more fundamental fact:

Proposition

Any functor

[𝒰]:Set ISet[\mathcal{U}] : \mathbf{Set}^I \to \mathbf{Set}

which specifies a choice of ultraproduct (and hence comparison maps, since ultraproducts are colimits) is elementary (logical in the terminology of Makkai-Reyes, i.e. a pretopos morphism.)

Proof

Recall that the ultraproduct sends the family of sets A iA_i to the colimit of s isA is \mapsto \prod_{i \in s} A_i, indexed by sU ops \in U^op. U opU^op (the opposite category of the sub-poset U𝒫(I)U \subseteq \mathcal{P}(I)) is filtered because UU is a filter.

A functor is a pretopos morphism precisely when it preserves finite limits, initial objects, disjoint sums, and quotients by internal equivalence relations.

Finite limits: a ss-indexed product of JJ-indexed limits is a JJ-indexed limit of ss-indexed products, and finite limits commute with filtered colimits.

Initial objects: a ss-indexed product of empty sets is empty (as each ss is nonempty by properness of UU), and a colimit of empty sets is empty.

Disjoint sums: a ss-indexed product of disjoint sums i:s(A 0i+A 1i)\prod_{i:s} (A_{0i} + A_{1i}) is a disjoint sum of products f:s2 i:sA f(i)i\sum_{f : s \to 2} \prod_{i:s} A_{f(i)i}. For any (f,a)(f,a) in this set, there is a UU-large subset tst \subset s such that the restriction of ff to tt is constantly bb (b{0,1}b \in \{0,1\}). Therefore the restriction map identifies (f,a)(f,a) with (const b,a| t)(const_b,a|_t), and the U opU^op-indexed colimit of the f:s2 i:sA f(i)i\sum_{f : s \to 2} \prod_{i:s} A_{f(i)i} is equivalent to the U opU^op-indexed colimit of the b:2 i:sA bi= i:sA 0i+ i:sA 1i\sum_{b : 2} \prod_{i:s} A_{bi} = \prod_{i:s} A_{0i} + \prod_{i:s} A_{1i}, and colimits commute with colimits.

Quotients: Given X iX_i and equivalence relations E iX i×X iE_i \to X_i \times X_i, a ss-indexed product of quotients i:s(X i/E i)\prod_{i:s} (X_i / E_i) is a quotient of products ( i:sX i)/( i:sE i)(\prod_{i:s} X_i) / (\prod_{i:s} E_i) (because the natural map from the latter to the former is an iso, using the axiom of choice), and colimits commute with colimits.

Now we can show the theorem:

Proof of theorem

Since the ultraproduct functor is elementary, then the process of taking points M(X)M(X) of a definable set XX inside models MM commutes with taking ultraproducts. In symbols,

( iIM i/𝒰)(X)( iIM i(X)/𝒰).\left(\prod_{i \in I} M_i / \mathcal{U}\right) (X) \simeq \left(\prod_{i \in I} M_i(X) / \mathcal{U}\right).

Since this is a filtered colimit, a sequence x¯\overline{x} satisfies that its germ [x¯][\overline{x}] is in iIM i/𝒰(X)\prod_{i \in I} M_i / \mathcal{U}(X) if and only if there is some J𝒰J \in \mathcal{U} such that the restriction of x¯\overline{x} to JJ is in jJM j(X)\prod_{j \in J} M_j(X). i.e. if x jM j(X)x_j \in M_j(X) for each jJj \in J.

Examples

An immediate consequence of the Łoś theorem is the transfer principle for the hyperreals.

The compactness theorem also follows quickly from the Łoś theorem, so anything that you build using compactness can be realized a bit more concretely as an ultraproduct.

Remarks

The proposition should be interpreted as saying that Set simultaneously carries a pretopos structure and an ultracategory structure, and that these two structures commute. Indeed, one can view Set as a dualizing object for a generalized Stone duality between pretoposes and ultracategories; this is the starting point of Makkai duality.

There is an analogous statement for ultraproducts of structures in continuous logic.

References

  • Hisashi Aratake, Sheaves of Structures, Heyting-Valued Structures, and a Generalization of Łoś’s Theorem , arXiv:2012.04317 (2020). (abstract)

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

Last revised on May 17, 2022 at 17:51:54. See the history of this page for a list of all contributions to it.