Ultraproduct

(Redirected from Ultraproducts)

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

edit

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  

Explicitly, if the  -equivalence class of an element   is denoted by   then the ultraproduct is the set of all  -equivalence classes  

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

edit

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  

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  

Examples

edit

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

edit

Ł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    

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

edit

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)

edit

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

edit

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  

See also

edit

Notes

edit
  1. ^ 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

  1. ^ 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    

References

edit