View source for Ultraproduct

{{short description|Mathematical construction}}
The '''ultraproduct''' is a [[Mathematics|mathematical]] construction that appears mainly in [[Abstract algebra|abstract algebra]] and [[Mathematical logic|mathematical logic]], in particular in [[Model theory|model theory]] and [[Set theory|set theory]]. An ultraproduct is a [[Quotient|quotient]] of the [[Direct product|direct product]] of a family of [[Structure (mathematical logic)|structures]]. All factors need to have the same [[Philosophy:Signature (logic)|signature]]. The '''ultrapower''' is the special case of this construction in which all factors are equal.

For example, ultrapowers can be used to construct new [[Field (mathematics)|field]]s from given ones. The [[Hyperreal number|hyperreal number]]s, an ultrapower of the real numbers, are a special case of this.

Some striking applications of ultraproducts include very elegant proofs of the [[Compactness theorem|compactness theorem]] and the completeness theorem, Keisler's ultrapower theorem, which gives an algebraic characterization of the semantic notion of elementary equivalence, and the Robinson–Zakon presentation of the use of superstructures and their monomorphisms to construct nonstandard models of analysis, leading to the growth of the area of [[Nonstandard analysis|nonstandard analysis]], which was pioneered (as an application of the compactness theorem) by [[Biography:Abraham Robinson|Abraham Robinson]].

==Definition==

The general method for getting ultraproducts uses an index set <math>I,</math> a [[Structure (mathematical logic)|structure]] <math>M_i</math> (assumed to be non-empty in this article) for each element <math>i \in I</math> (all of the same [[Philosophy:Signature (logic)|signature]]), and an [[Ultrafilter (set theory)|ultrafilter]] <math>\mathcal{U}</math> on <math>I.</math> 

For any two elements <math>a_\bull = \left(a_i\right)_{i \in I}</math> and <math>b_\bull = \left(b_i\right)_{i \in I}</math> of the [[Cartesian product]] 
<math display=inline>{\textstyle\prod\limits_{i \in I}} M_i,</math> 
declare them to be {{em|<math>\mathcal{U}</math>-equivalent}}, written <math>a_\bull \sim b_\bull</math> or <math>a_\bull =_{\mathcal{U}} b_\bull,</math> if and only if the set of indices <math>\left\{i \in I : a_i = b_i\right\}</math> on which they agree is an element of <math>\mathcal{U};</math> in symbols,
<math display=block>a_\bull \sim b_\bull \; \iff \; \left\{i \in I : a_i = b_i\right\} \in \mathcal{U},</math>
which compares components only relative to the ultrafilter <math>\mathcal{U}.</math>  
This [[Binary relation|binary relation]] <math>\, \sim \,</math> is an [[Equivalence relation|equivalence relation]]<ref group=proof name=EquivalenceRelationProof /> on the Cartesian product <math>{\textstyle\prod\limits_{i \in I}} M_i.</math> 

The {{em|'''ultraproduct''' of <math>M_{\bull} = \left(M_i\right)_{i \in I}</math> modulo <math>\mathcal{U}</math>}} is the [[Quotient set|quotient set]] of <math>{\textstyle\prod\limits_{i \in I}} M_i</math> with respect to <math>\sim</math> and is therefore sometimes denoted by
<math>{\textstyle\prod\limits_{i \in I}} M_i \, / \, \mathcal{U}</math> or <math>{\textstyle\prod}_{\mathcal{U}} \, M_\bull.</math>

Explicitly, if the <math>\mathcal{U}</math>-[[Equivalence class|equivalence class]] of an element <math>a \in {\textstyle\prod\limits_{i \in I}} M_i</math> is denoted by
<math display=block>a_{\mathcal{U}} := \big\{x \in {\textstyle\prod\limits_{i \in I}} M_i \; : \; x \sim a\big\}</math>
then the ultraproduct is the set of all <math>\mathcal{U}</math>-equivalence classes
<math display=block>{\prod}_{\mathcal{U}} \, M_\bull \; = \; \prod_{i \in I} M_i \, / \, \mathcal{U} \; := \; \left\{a_{\mathcal{U}} \; : \; a \in {\textstyle\prod\limits_{i \in I}} M_i\right\}.</math>

Although <math>\mathcal{U}</math> was assumed to be an ultrafilter, the construction above can be carried out more generally whenever <math>\mathcal{U}</math> is merely a [[Filter (set theory)|filter]] on <math>I,</math> in which case the resulting quotient set <math>{\textstyle\prod\limits_{i \in I}} M_i /  \, \mathcal{U}</math> is called a ''{{visible anchor|reduced product}}''.

When <math>\mathcal{U}</math> is a principal ultrafilter (which happens if and only if <math>\mathcal{U}</math> contains its [[Kernel (set theory)|kernel]] <math>\cap \, \mathcal{U}</math>) then the ultraproduct is isomorphic to one of the factors. 
And so usually, <math>\mathcal{U}</math> is not a principal ultrafilter, which happens if and only if <math>\mathcal{U}</math> is free (meaning <math>\cap \, \mathcal{U} = \varnothing</math>), or equivalently, if every cofinite subsets of <math>I</math> is an element of <math>\mathcal{U}.</math> 
Since every ultrafilter on a finite set is principal, the index set <math>I</math> is consequently also usually infinite.

The ultraproduct acts as a filter product space where elements are equal if they are equal only at the filtered components (non-filtered components are ignored under the equivalence). 
One may define a finitely additive [[Measure (mathematics)|measure]] <math>m</math> on the index set <math>I</math> by saying <math>m(A) = 1</math> if <math>A \in \mathcal{U}</math> and <math>m(A) = 0</math> otherwise.  Then two members of the Cartesian product are equivalent precisely if they are equal [[Almost everywhere|almost everywhere]] on the index set.  The ultraproduct is the set of equivalence classes thus generated.

[[Finitary]] [[Operation (mathematics)|operations]] on the Cartesian product <math>{\textstyle\prod\limits_{i \in I}} M_i</math> are defined pointwise (for example, if <math>+</math> is a binary function then <math>a_i + b_i = (a + b)_i</math>). 
Other [[Relation (mathematics)|relation]]s can be extended the same way:
<math display=block>R\left(a^1_{\mathcal{U}}, \dots, a^n_{\mathcal{U}}\right) ~\iff~ \left\{i \in I : R^{M_i}\left(a^1_i, \dots, a^n_i\right)\right\} \in \mathcal{U},</math>
where <math>a_{\mathcal{U}}</math> denotes the <math>\mathcal{U}</math>-equivalence class of <math>a</math> with respect to <math>\sim.</math> 
In particular, if every <math>M_i</math> is an [[Ordered field|ordered field]] then so is the ultraproduct.

===Ultrapower===

An ''ultrapower'' is an ultraproduct for which all the factors <math>M_i</math> are equal. 
Explicitly, the {{em|'''{{visible anchor|ultrapower}}''' of a set <math>M</math> modulo <math>\mathcal{U}</math>}} is the ultraproduct <math>{\textstyle\prod\limits_{i \in I}} M_i \, / \, \mathcal{U} = {\textstyle\prod}_{\mathcal{U}} \, M_\bull</math> of the indexed family <math>M_{\bull} := \left(M_i\right)_{i \in I}</math> defined by <math>M_i := M</math> for every index <math>i \in I.</math> 
The ultrapower may be denoted by <math>{\textstyle\prod}_{\mathcal{U}} \, M</math> or (since <math>{\textstyle\prod\limits_{i \in I}} M</math> is often denoted by <math>M^I</math>) by
<math display=block>M^I / \mathcal{U} ~:=~ \prod_{i \in I} M \, / \,\mathcal{U}\,</math>

For every <math>m \in M,</math> let <math>(m)_{i \in I}</math> denote the constant map <math>I \to M</math> that is identically equal to <math>m.</math> This constant map/tuple is an element of the Cartesian product <math>M^I = {\textstyle\prod\limits_{i \in I}} M</math> and so the assignment <math>m \mapsto (m)_{i \in I}</math> defines a map <math>M \to {\textstyle\prod\limits_{i \in I}} M.</math> 
The {{em|'''{{visible anchor|natural embedding}}''' of <math>M</math> into <math>{\textstyle\prod}_{\mathcal{U}} \, M</math>}} is the map <math>M \to {\textstyle\prod}_{\mathcal{U}} \, M</math> that sends an element <math>m \in M</math> to the <math>\mathcal{U}</math>-equivalence class of the constant tuple <math>(m)_{i \in I}.</math>

==Examples==

The hyperreal numbers are the ultraproduct of one copy of the real numbers for every natural number, with regard to an ultrafilter over the natural numbers containing all cofinite sets. Their order is the extension of the order of the real numbers. For example, the sequence <math>\omega</math> given by <math>\omega_i = i</math> defines an equivalence class representing a hyperreal number that is greater than any real number.

Analogously, one can define nonstandard integers, nonstandard complex numbers, etc., by taking the ultraproduct of copies of the corresponding structures.

As an example of the carrying over of relations into the ultraproduct, consider the sequence <math>\psi</math> defined by <math>\psi_i = 2 i.</math> Because <math>\psi_i > \omega_i = i</math> for all <math>i,</math> it follows that the equivalence class of <math>\psi_i = 2 i</math> is greater than the equivalence class of <math>\omega_i = i,</math> so that it can be interpreted as an infinite number which is greater than the one originally constructed. However, let <math>\chi_i = i</math> for <math>i</math> not equal to <math>7,</math> but <math>\chi_7 = 8.</math> The set of indices on which <math>\omega</math> and <math>\chi</math> agree is a member of any ultrafilter (because <math>\omega</math> and <math>\chi</math> agree almost everywhere), so <math>\omega</math> and <math>\chi</math> belong to the same equivalence class.

In the theory of [[Large cardinal|large cardinal]]s, a standard construction is to take the ultraproduct of the whole set-theoretic universe with respect to some carefully chosen ultrafilter <math>\mathcal{U}.</math> Properties of this ultrafilter <math>\mathcal{U}</math> have a strong influence on (higher order) properties of the ultraproduct; for example, if <math>\mathcal{U}</math> is <math>\sigma</math>-complete, then the ultraproduct will again be well-founded.  (See [[Measurable cardinal|measurable cardinal]] for the prototypical example.)

==Łoś's theorem==

Łoś's theorem, also called {{em|the fundamental theorem of ultraproducts}}, is due to [[Biography:Jerzy Łoś|Jerzy Łoś]] (the surname is pronounced {{IPA-pl|ˈwɔɕ|}}, approximately "wash"). It states that any first-order formula is true in the ultraproduct if and only if the set of indices <math>i</math> such that the formula is true in <math>M_i</math> is a member of <math>\mathcal{U}.</math> More precisely:

Let <math>\sigma</math> be a signature, <math>\mathcal{U}</math> an ultrafilter over a set <math>I,</math> and for each <math>i \in I</math> let <math>M_i</math> be a <math>\sigma</math>-structure. 
Let <math>{\textstyle\prod}_{\mathcal{U}} \, M_\bull</math> or <math>{\textstyle\prod\limits_{i \in I}} M_i / \mathcal{U}</math> be the ultraproduct of the <math>M_i</math> with respect to <math>\mathcal{U}.</math> 
Then, for each <math>a^1, \ldots, a^n \in {\textstyle\prod\limits_{i \in I}} M_i,</math> where <math>a^k = \left(a^k_i\right)_{i \in I},</math> and for every <math>\sigma</math>-formula <math>\phi,</math>
<math display=block>{\prod}_{\mathcal{U}} \, M_\bull \models \phi\left[a^1_{\mathcal{U}}, \ldots, a^n_{\mathcal{U}}\right] ~\iff~ \{i \in I : M_i \models \phi[a^1_i, \ldots, a^n_i]\} \in \mathcal{U}.</math>

The theorem is proved by induction on the complexity of the formula <math>\phi.</math> The fact that <math>\mathcal{U}</math> is an ultrafilter (and not just a filter) is used in the negation clause, and the [[Axiom of choice|axiom of choice]] is needed at the existential quantifier step.  As an application, one obtains the [[Transfer principle|transfer theorem]] for [[Hyperreal number|hyperreal fields]].

===Examples===

Let <math>R</math> be a unary relation in the structure <math>M,</math> and form the ultrapower of <math>M.</math> Then the set <math>S = \{x \in M : R x\}</math> has an analog <math>{}^* S</math> in the ultrapower, and first-order formulas involving <math>S</math> are also valid for <math>{}^* S.</math> For example, let <math>M</math> be the reals, and let <math>R x</math> hold if <math>x</math> is a rational number. Then in <math>M</math> we can say that for any pair of rationals <math>x</math> and <math>y,</math> there exists another number <math>z</math> such that <math>z</math> is not rational, and <math>x < z < y.</math> Since this can be translated into a first-order logical formula in the relevant formal language, Łoś's theorem implies that <math>{}^* S</math> has the same property. That is, we can define a notion of the hyperrational numbers, which are a subset of the hyperreals, and they have the same first-order properties as the rationals.

Consider, however, the [[Archimedean property]] of the reals, which states that there is no real number <math>x</math> such that <math>x > 1, \; x > 1 + 1, \; x > 1 + 1 + 1, \ldots</math> for every inequality in the infinite list. Łoś's theorem does not apply to the Archimedean property, because the Archimedean property cannot be stated in first-order logic. In fact, the Archimedean property is false for the hyperreals, as shown by the construction of the hyperreal number <math>\omega</math> above.

==Direct limits of ultrapowers (ultralimits)==

In [[Model theory|model theory]] and [[Set theory|set theory]], the [[Direct limit|direct limit]] of a sequence of ultrapowers is often considered. In [[Model theory|model theory]], this construction can be referred to as an '''ultralimit''' or '''limiting ultrapower'''.

Beginning with a structure, <math>A_0</math> and an ultrafilter, <math>\mathcal{D}_0,</math> form an ultrapower, <math>A_1.</math> Then repeat the process to form <math>A_2,</math> and so forth. For each <math>n</math> there is a canonical diagonal embedding <math>A_n \to A_{n+1}.</math> At limit stages, such as <math>A_\omega,</math> form the direct limit of earlier stages. One may continue into the transfinite.

==Ultraproduct monad==

The ultrafilter monad is the [[Codensity monad|codensity monad]] of the inclusion of the category of finite sets into the [[Category of sets|category of all sets]].<ref name="Leinster2013">{{cite journal|last=Leinster|first=Tom|year=2013|title=Codensity and the ultrafilter monad|journal=Theory and Applications of Categories|volume=28|pages=332–370|bibcode=2012arXiv1209.3606L|arxiv=1209.3606|url=http://www.tac.mta.ca/tac/volumes/28/13/28-13.pdf}}</ref> 

Similarly, the {{visible anchor|Ultraproduct monad|text=ultraproduct monad}} is the codensity monad of the inclusion of the category <math>\mathbf{FinFam}</math> of [[Indexed family|finitely-indexed]] [[Family of sets|families of sets]] into the category <math>\mathbf{Fam}</math> of all [[Indexed family|indexed]] families of sets. So in this sense, ultraproducts are categorically inevitable.<ref name="Leinster2013">{{cite journal|last=Leinster|first=Tom|year=2013|title=Codensity and the ultrafilter monad|journal=Theory and Applications of Categories|volume=28|pages=332–370|bibcode=2012arXiv1209.3606L|arxiv=1209.3606|url=http://www.tac.mta.ca/tac/volumes/28/13/28-13.pdf}}</ref> 
Explicitly, an object of <math>\mathbf{Fam}</math> consists of a non-empty [[Index set|index set]] <math>I</math> and an [[Indexed family|indexed family]] <math>\left(M_i\right)_{i \in I}</math> of sets. 
A morphism <math>\left(N_i\right)_{j \in J} \to \left(M_i\right)_{i \in I}</math> between two objects consists of a function <math>\phi : I \to J</math> between the index sets and a <math>J</math>-indexed family <math>\left(\phi_j\right)_{j \in J}</math> of function <math>\phi_j : M_{\phi(j)} \to N_j.</math> 
The category <math>\mathbf{FinFam}</math> is a full subcategory of this category of <math>\mathbf{Fam}</math> consisting of all objects <math>\left(M_i\right)_{i \in I}</math> whose index set <math>I</math> is finite. 
The codensity monad of the inclusion map <math>\mathbf{FinFam} \hookrightarrow \mathbf{Fam}</math> is then, in essence, given by
<math display=block>\left(M_i\right)_{i \in I} ~\mapsto~ \left(\prod_{i \in I} M_i \, / \, \mathcal{U}\right)_{\mathcal{U} \in U(I)} \, .</math>

==See also==

* {{annotated link|Compactness theorem}}
* {{annotated link|Extender (set theory)}}
* {{annotated link|Löwenheim–Skolem theorem}}
* {{annotated link|Transfer principle}}
* {{annotated link|Ultrafilter}}

==Notes==

{{reflist}}

'''Proofs'''

{{reflist|group=proof|refs=
<ref name=EquivalenceRelationProof>Although <math>\mathcal{U}</math> is assumed to be an ultrafilter over <math>I,</math> this proof only requires that <math>\mathcal{U}</math> be a filter on <math>I.</math> Throughout, let <math>a_\bull = \left(a_i\right)_{i \in I}, b_\bull = \left(b_i\right)_{i \in I},</math> and <math>c_\bull = \left(c_i\right)_{i \in I}</math> be elements of <math>{\textstyle\prod\limits_{i \in I}} M_i.</math> The relation <math>a_\bull\,\sim\,a_\bull</math> always holds since <math>\{i \in I : a_i = a_i\} = I</math> is an element of filter <math>\mathcal{U}.</math> Thus the [[Reflexive relation|reflexivity]] of <math>\,\sim\,</math> follows from that of equality <math>\,=.\,</math> Similarly, <math>\,\sim\,</math> is [[Symmetric relation|symmetric]] since equality is symmetric. For [[Transitive relation|transitivity]], assume that <math>R = \{i : a_i := b_i\}</math> and <math>S := \{i : b_i = c_i\}</math> are elements of <math>\mathcal{U};</math> it remains to show that <math>T := \{i : a_i = c_i\}</math> also belongs to <math>\mathcal{U}.</math> The transitivity of equality guarantees <math>R \cap S \subseteq T</math> (since if <math>i \in R \cap S</math> then <math>a_i = b_i</math> and <math>b_i = c_i</math>). Because <math>\mathcal{U}</math> is closed under binary intersections, <math>R \cap S \in \mathcal{U}.</math> Since <math>\mathcal{U}</math> is upward closed in <math>I,</math> it contains every superset of <math>R \cap S</math> (that consists of indices); in particular, <math>\mathcal{U}</math> contains <math>T.</math> <math>\blacksquare</math></ref>
}}

==References==

* {{cite book| last=Bell | first=John Lane |author2=Slomson, Alan B.| year=2006 | title=Models and Ultraproducts: An Introduction | edition=reprint of 1974 | orig-year=1969 | publisher=[[Social:Dover Publications|Dover Publications]] | isbn=0-486-44979-3}}
* {{cite book| last=Burris | first =Stanley N. |author2=Sankappanavar, H.P.| title=A Course in Universal Algebra | orig-year=1981 | year=2000 | url=http://www.thoralf.uwaterloo.ca/htdocs/ualg.html | edition=Millennium}}

{{Mathematical logic}}

[[Category:Mathematical logic]]
[[Category:Model theory]]
[[Category:Nonstandard analysis]]
[[Category:Theorems in the foundations of mathematics]]
[[Category:Universal algebra]]

{{Sourceattribution|Ultraproduct}}