Ultraproduct

The general method for getting ultraproducts uses an index set ${\displaystyle I,}$ a structure ${\displaystyle M_{i}}$ (assumed to be non-empty in this article) for each element ${\displaystyle i\in I}$ (all of the same signature), and an ultrafilter ${\displaystyle {\mathcal {U}}}$ on ${\displaystyle I.}$

For any two elements ${\displaystyle a_{\bullet }=\left(a_{i}\right)_{i\in I}}$ and ${\displaystyle b_{\bullet }=\left(b_{i}\right)_{i\in I}}$ of the Cartesian product ${\textstyle {\textstyle \prod \limits _{i\in I}}M_{i},}$ declare them to be ${\displaystyle {\mathcal {U}}}$-equivalent, written ${\displaystyle a_{\bullet }\sim b_{\bullet }}$ or ${\displaystyle a_{\bullet }=_{\mathcal {U}}b_{\bullet },}$ if and only if the set of indices ${\displaystyle \left\{i\in I:a_{i}=b_{i}\right\}}$ on which they agree is an element of ${\displaystyle {\mathcal {U}};}$ in symbols,

$${\displaystyle a_{\bullet }\sim b_{\bullet }\;\iff \;\left\{i\in I:a_{i}=b_{i}\right\}\in {\mathcal {U}},}$$

which compares components only relative to the ultrafilter ${\displaystyle {\mathcal {U}}.}$ This binary relation ${\displaystyle \,\sim \,}$ is an equivalence relation[proof 1] on the Cartesian product ${\displaystyle {\textstyle \prod \limits _{i\in I}}M_{i}.}$

The ultraproduct of ${\displaystyle M_{\bullet }=\left(M_{i}\right)_{i\in I}}$ modulo ${\displaystyle {\mathcal {U}}}$ is the quotient set of ${\displaystyle {\textstyle \prod \limits _{i\in I}}M_{i}}$ with respect to ${\displaystyle \sim }$ and is therefore sometimes denoted by ${\displaystyle {\textstyle \prod \limits _{i\in I}}M_{i}\,/\,{\mathcal {U}}}$ or ${\displaystyle {\textstyle \prod }_{\mathcal {U}}\,M_{\bullet }.}$

Explicitly, if the ${\displaystyle {\mathcal {U}}}$-equivalence class of an element ${\displaystyle a\in {\textstyle \prod \limits _{i\in I}}M_{i}}$ is denoted by

$${\displaystyle a_{\mathcal {U}}:={\big \{}x\in {\textstyle \prod \limits _{i\in I}}M_{i}\;:\;x\sim a{\big \}}}$$

then the ultraproduct is the set of all ${\displaystyle {\mathcal {U}}}$-equivalence classes

$${\displaystyle {\prod }_{\mathcal {U}}\,M_{\bullet }\;=\;\prod _{i\in I}M_{i}\,/\,{\mathcal {U}}\;:=\;\left\{a_{\mathcal {U}}\;:\;a\in {\textstyle \prod \limits _{i\in I}}M_{i}\right\}.}$$

Although ${\displaystyle {\mathcal {U}}}$ was assumed to be an ultrafilter, the construction above can be carried out more generally whenever ${\displaystyle {\mathcal {U}}}$ is merely a filter on ${\displaystyle I,}$ in which case the resulting quotient set ${\displaystyle {\textstyle \prod \limits _{i\in I}}M_{i}/\,{\mathcal {U}}}$ is called a reduced product.

When ${\displaystyle {\mathcal {U}}}$ is a principal ultrafilter (which happens if and only if ${\displaystyle {\mathcal {U}}}$ contains its kernel ${\displaystyle \cap \,{\mathcal {U}}}$) then the ultraproduct is isomorphic to one of the factors. And so usually, ${\displaystyle {\mathcal {U}}}$ is not a principal ultrafilter, which happens if and only if ${\displaystyle {\mathcal {U}}}$ is free (meaning ${\displaystyle \cap \,{\mathcal {U}}=\varnothing }$), or equivalently, if every cofinite subsets of ${\displaystyle I}$ is an element of ${\displaystyle {\mathcal {U}}.}$ Since every ultrafilter on a finite set is principal, the index set ${\displaystyle I}$ 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 ${\displaystyle m}$ on the index set ${\displaystyle I}$ by saying ${\displaystyle m(A)=1}$ if ${\displaystyle A\in {\mathcal {U}}}$ and ${\displaystyle m(A)=0}$ otherwise. Then two members of the Cartesian product are equivalent precisely if they are equal almost everywhere on the index set. The ultraproduct is the set of equivalence classes thus generated.

Finitary operations on the Cartesian product ${\displaystyle {\textstyle \prod \limits _{i\in I}}M_{i}}$ are defined pointwise (for example, if ${\displaystyle +}$ is a binary function then ${\displaystyle a_{i}+b_{i}=(a+b)_{i}}$). Other relations can be extended the same way:

$${\displaystyle R\left(a_{\mathcal {U}}^{1},\dots ,a_{\mathcal {U}}^{n}\right)~\iff ~\left\{i\in I:R^{M_{i}}\left(a_{i}^{1},\dots ,a_{i}^{n}\right)\right\}\in {\mathcal {U}},}$$

where ${\displaystyle a_{\mathcal {U}}}$ denotes the ${\displaystyle {\mathcal {U}}}$-equivalence class of ${\displaystyle a}$ with respect to ${\displaystyle \sim .}$ In particular, if every ${\displaystyle M_{i}}$ is an ordered field then so is the ultraproduct.

Ultrapower

An ultrapower is an ultraproduct for which all the factors ${\displaystyle M_{i}}$ are equal. Explicitly, the ultrapower of a set ${\displaystyle M}$ modulo ${\displaystyle {\mathcal {U}}}$ is the ultraproduct ${\displaystyle {\textstyle \prod \limits _{i\in I}}M_{i}\,/\,{\mathcal {U}}={\textstyle \prod }_{\mathcal {U}}\,M_{\bullet }}$ of the indexed family ${\displaystyle M_{\bullet }:=\left(M_{i}\right)_{i\in I}}$ defined by ${\displaystyle M_{i}:=M}$ for every index ${\displaystyle i\in I.}$ The ultrapower may be denoted by ${\displaystyle {\textstyle \prod }_{\mathcal {U}}\,M}$ or (since ${\displaystyle {\textstyle \prod \limits _{i\in I}}M}$ is often denoted by ${\displaystyle M^{I}}$) by

$${\displaystyle M^{I}/{\mathcal {U}}~:=~\prod _{i\in I}M\,/\,{\mathcal {U}}\,}$$

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

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 ${\displaystyle \omega }$ given by ${\displaystyle \omega _{i}=i}$ 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 ${\displaystyle \psi }$ defined by ${\displaystyle \psi _{i}=2i.}$ Because ${\displaystyle \psi _{i}>\omega _{i}=i}$ for all ${\displaystyle i,}$ it follows that the equivalence class of ${\displaystyle \psi _{i}=2i}$ is greater than the equivalence class of ${\displaystyle \omega _{i}=i,}$ so that it can be interpreted as an infinite number which is greater than the one originally constructed. However, let ${\displaystyle \chi _{i}=i}$ for ${\displaystyle i}$ not equal to ${\displaystyle 7,}$ but ${\displaystyle \chi _{7}=8.}$ The set of indices on which ${\displaystyle \omega }$ and ${\displaystyle \chi }$ agree is a member of any ultrafilter (because ${\displaystyle \omega }$ and ${\displaystyle \chi }$ agree almost everywhere), so ${\displaystyle \omega }$ and ${\displaystyle \chi }$ belong to the same equivalence class.

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

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

Let ${\displaystyle \sigma }$ be a signature, ${\displaystyle {\mathcal {U}}}$ an ultrafilter over a set ${\displaystyle I,}$ and for each ${\displaystyle i\in I}$ let ${\displaystyle M_{i}}$ be a ${\displaystyle \sigma }$-structure. Let ${\displaystyle {\textstyle \prod }_{\mathcal {U}}\,M_{\bullet }}$ or ${\displaystyle {\textstyle \prod \limits _{i\in I}}M_{i}/{\mathcal {U}}}$ be the ultraproduct of the ${\displaystyle M_{i}}$ with respect to ${\displaystyle {\mathcal {U}}.}$ Then, for each ${\displaystyle a^{1},\ldots ,a^{n}\in {\textstyle \prod \limits _{i\in I}}M_{i},}$ where ${\displaystyle a^{k}=\left(a_{i}^{k}\right)_{i\in I},}$ and for every ${\displaystyle \sigma }$-formula ${\displaystyle \phi ,}$

$${\displaystyle {\prod }_{\mathcal {U}}\,M_{\bullet }\models \phi \left[a_{\mathcal {U}}^{1},\ldots ,a_{\mathcal {U}}^{n}\right]~\iff ~\{i\in I:M_{i}\models \phi [a_{i}^{1},\ldots ,a_{i}^{n}]\}\in {\mathcal {U}}.}$$

The theorem is proved by induction on the complexity of the formula ${\displaystyle \phi .}$ The fact that ${\displaystyle {\mathcal {U}}}$ is an ultrafilter (and not just a filter) is used in the negation clause, and the axiom of choice is needed at the existential quantifier step. As an application, one obtains the transfer theorem for hyperreal fields.

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

Beginning with a structure, ${\displaystyle A_{0}}$ and an ultrafilter, ${\displaystyle {\mathcal {D}}_{0},}$ form an ultrapower, ${\displaystyle A_{1}.}$ Then repeat the process to form ${\displaystyle A_{2},}$ and so forth. For each ${\displaystyle n}$ there is a canonical diagonal embedding ${\displaystyle A_{n}\to A_{n+1}.}$ At limit stages, such as ${\displaystyle A_{\omega },}$ form the direct limit of earlier stages. One may continue into the transfinite.

The ultrafilter monad is the codensity monad of the inclusion of the category of finite sets into the category of all sets.[1]

Similarly, the ultraproduct monad is the codensity monad of the inclusion of the category ${\displaystyle \mathbf {FinFam} }$ of finitely-indexed families of sets into the category ${\displaystyle \mathbf {Fam} }$ of all indexed families of sets. So in this sense, ultraproducts are categorically inevitable.[1] Explicitly, an object of ${\displaystyle \mathbf {Fam} }$ consists of a non-empty index set ${\displaystyle I}$ and an indexed family ${\displaystyle \left(M_{i}\right)_{i\in I}}$ of sets. A morphism ${\displaystyle \left(N_{i}\right)_{j\in J}\to \left(M_{i}\right)_{i\in I}}$ between two objects consists of a function ${\displaystyle \phi :I\to J}$ between the index sets and a ${\displaystyle J}$-indexed family ${\displaystyle \left(\phi _{j}\right)_{j\in J}}$ of function ${\displaystyle \phi _{j}:M_{\phi (j)}\to N_{j}.}$ The category ${\displaystyle \mathbf {FinFam} }$ is a full subcategory of this category of ${\displaystyle \mathbf {Fam} }$ consisting of all objects ${\displaystyle \left(M_{i}\right)_{i\in I}}$ whose index set ${\displaystyle I}$ is finite. The codensity monad of the inclusion map ${\displaystyle \mathbf {FinFam} \hookrightarrow \mathbf {Fam} }$ is then, in essence, given by

$${\displaystyle \left(M_{i}\right)_{i\in I}~\mapsto ~\left(\prod _{i\in I}M_{i}\,/\,{\mathcal {U}}\right)_{{\mathcal {U}}\in U(I)}\,.}$$

• Compactness theorem
• Extender (set theory) – in set theory, a system of ultrafilters representing an elementary embedding witnessing large cardinal propertiesPages displaying wikidata descriptions as a fallback
• Löwenheim–Skolem theorem – Existence and cardinality of models of logical theories
• Transfer principle – That all statements of some language that are true for some structure are true for another structure
• Ultrafilter – Maximal proper filter

Proofs

• Bell, John Lane; Slomson, Alan B. (2006) [1969]. Models and Ultraproducts: An Introduction (reprint of 1974 ed.). Dover Publications. ISBN 0-486-44979-3.
• Burris, Stanley N.; Sankappanavar, H.P. (2000) [1981]. A Course in Universal Algebra (Millennium ed.).