Mathematical construction
The ultraproduct is a mathematical construction that appears mainly in abstract algebra and mathematical logic, in particular in model theory and set theory. An ultraproduct is a quotient of the direct product of a family of structures. All factors need to have the same 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 fields from given ones. The hyperreal numbers, 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 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, which was pioneered (as an application of the compactness theorem) by Abraham Robinson.
Definition
The general method for getting ultraproducts uses an index set
a structure
(assumed to be non-empty in this article) for each element
(all of the same signature), and an ultrafilter
on
For any two elements
and
of the Cartesian product
declare them to be
-equivalent, written
or
if and only if the set of indices
on which they agree is an element of
in symbols,
which compares components only relative to the ultrafilter
This binary relation
is an equivalence relation[proof 1] on the Cartesian product
The ultraproduct of
modulo
is the quotient set of
with respect to
and is therefore sometimes denoted by
or ![{\displaystyle {\textstyle \prod }_{\mathcal {U}}\,M_{\bullet }.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Explicitly, if the
-equivalence class of an element
is denoted by
then the ultraproduct is the set of all
-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\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Although
was assumed to be an ultrafilter, the construction above can be carried out more generally whenever
is merely a filter on
in which case the resulting quotient set
is called a reduced product.
When
is a principal ultrafilter (which happens if and only if
contains its kernel
) then the ultraproduct is isomorphic to one of the factors.
And so usually,
is not a principal ultrafilter, which happens if and only if
is free (meaning
), or equivalently, if every cofinite subset of
is an element of
Since every ultrafilter on a finite set is principal, the index set
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
on the index set
by saying
if
and
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
are defined pointwise (for example, if
is a binary function then
).
Other relations can be extended the same way:
where
denotes the
-equivalence class of
with respect to
In particular, if every
is an ordered field then so is the ultraproduct.
Ultrapower
An ultrapower is an ultraproduct for which all the factors
are equal.
Explicitly, the ultrapower of a set
modulo
is the ultraproduct
of the indexed family
defined by
for every index
The ultrapower may be denoted by
or (since
is often denoted by
) by![{\displaystyle M^{I}/{\mathcal {U}}~:=~\prod _{i\in I}M\,/\,{\mathcal {U}}\,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
For every
let
denote the constant map
that is identically equal to
This constant map/tuple is an element of the Cartesian product
and so the assignment
defines a map
The natural embedding of
into
is the map
that sends an element
to the
-equivalence class of the constant tuple ![{\displaystyle (m)_{i\in I}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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
given by
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
defined by
Because
for all
it follows that the equivalence class of
is greater than the equivalence class of
so that it can be interpreted as an infinite number which is greater than the one originally constructed. However, let
for
not equal to
but
The set of indices on which
and
agree is a member of any ultrafilter (because
and
agree almost everywhere), so
and
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
Properties of this ultrafilter
have a strong influence on (higher order) properties of the ultraproduct; for example, if
is
-complete, then the ultraproduct will again be well-founded. (See measurable cardinal for the prototypical example.)
Łoś's theorem
Ł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
such that the formula is true in
is a member of
More precisely:
Let
be a signature,
an ultrafilter over a set
and for each
let
be a
-structure.
Let
or
be the ultraproduct of the
with respect to
Then, for each
where
and for every
-formula ![{\displaystyle \phi ,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\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}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
The theorem is proved by induction on the complexity of the formula
The fact that
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.
Examples
Let
be a unary relation in the structure
and form the ultrapower of
Then the set
has an analog
in the ultrapower, and first-order formulas involving
are also valid for
For example, let
be the reals, and let
hold if
is a rational number. Then in
we can say that for any pair of rationals
and
there exists another number
such that
is not rational, and
Since this can be translated into a first-order logical formula in the relevant formal language, Łoś's theorem implies that
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
such that
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
above.
Direct limits of ultrapowers (ultralimits)
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,
and an ultrafilter,
form an ultrapower,
Then repeat the process to form
and so forth. For each
there is a canonical diagonal embedding
At limit stages, such as
form the direct limit of earlier stages. One may continue into the transfinite.
Ultraproduct monad
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
of finitely-indexed families of sets into the category
of all indexed families of sets. So in this sense, ultraproducts are categorically inevitable.[1]
Explicitly, an object of
consists of a non-empty index set
and an indexed family
of sets.
A morphism
between two objects consists of a function
between the index sets and a
-indexed family
of function
The category
is a full subcategory of this category of
consisting of all objects
whose index set
is finite.
The codensity monad of the inclusion map
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)}\,.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
See also
Notes
- ^ a b Leinster, Tom (2013). "Codensity and the ultrafilter monad" (PDF). Theory and Applications of Categories. 28: 332–370. arXiv:1209.3606. Bibcode:2012arXiv1209.3606L.
Proofs
- ^ Although
is assumed to be an ultrafilter over
this proof only requires that
be a filter on
Throughout, let
and
be elements of
The relation
always holds since
is an element of filter
Thus the reflexivity of
follows from that of equality
Similarly,
is symmetric since equality is symmetric. For transitivity, assume that
and
are elements of
it remains to show that
also belongs to
The transitivity of equality guarantees
(since if
then
and
). Because
is closed under binary intersections,
Since
is upward closed in
it contains every superset of
(that consists of indices); in particular,
contains
![{\displaystyle \blacksquare }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
References
- 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.).