Jump to content

Ultraproduct

From Wikipedia, the free encyclopedia
(Redirected from Łoś' theorem)

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]