Łoś's Theorem
   HOME

TheInfoList



OR:

The ultraproduct is a
mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
construction that appears mainly in
abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures, which are set (mathematics), sets with specific operation (mathematics), operations acting on their elements. Algebraic structur ...
and
mathematical logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
, in particular in
model theory In mathematical logic, model theory is the study of the relationship between theory (mathematical logic), formal theories (a collection of Sentence (mathematical logic), sentences in a formal language expressing statements about a Structure (mat ...
and
set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory – as a branch of mathema ...
. An ultraproduct is a
quotient In arithmetic, a quotient (from 'how many times', pronounced ) is a quantity produced by the division of two numbers. The quotient has widespread use throughout mathematics. It has two definitions: either the integer part of a division (in th ...
of the
direct product In mathematics, a direct product of objects already known can often be defined by giving a new one. That induces a structure on the Cartesian product of the underlying sets from that of the contributing objects. The categorical product is an abs ...
of a family of structures. All factors need to have the same
signature A signature (; from , "to sign") is a depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. Signatures are often, but not always, Handwriting, handwritt ...
. 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 number In mathematics, hyperreal numbers are an extension of the real numbers to include certain classes of infinite and infinitesimal numbers. A hyperreal number x is said to be finite if, and only if, , x, for some integer n
s, an ultrapower of the
real numbers In mathematics, a real number is a number that can be used to measurement, measure a continuous variable, continuous one-dimensional quantity such as a time, duration or temperature. Here, ''continuous'' means that pairs of values can have arbi ...
, are a special case of this. Some striking applications of ultraproducts include very elegant proofs of the
compactness theorem In mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model. This theorem is an important tool in model theory, as it provides a useful (but generall ...
and the
completeness theorem Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies ...
, 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 The history of calculus is fraught with philosophical debates about the meaning and logical validity of fluxions or infinitesimal numbers. The standard way to resolve these debates is to define the operations of calculus using (ε, δ)-definitio ...
, which was pioneered (as an application of the compactness theorem) by Abraham Robinson.


Definition

The general method for getting ultraproducts uses an index set I, a
structure A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such as ...
M_i (assumed to be non-empty in this article) for each element i \in I (all of the same
signature A signature (; from , "to sign") is a depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. Signatures are often, but not always, Handwriting, handwritt ...
), and an
ultrafilter In the Mathematics, mathematical field of order theory, an ultrafilter on a given partially ordered set (or "poset") P is a certain subset of P, namely a Maximal element, maximal Filter (mathematics), filter on P; that is, a proper filter on P th ...
\mathcal on I. For any two elements a_\bull = \left(a_i\right)_ and b_\bull = \left(b_i\right)_ of the
Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets and , denoted , is the set of all ordered pairs where is an element of and is an element of . In terms of set-builder notation, that is A\times B = \. A table c ...
M_i, declare them to be , written a_\bull \sim b_\bull or a_\bull =_ b_\bull, if and only if the set of indices \left\ on which they agree is an element of \mathcal; in symbols, a_\bull \sim b_\bull \; \iff \; \left\ \in \mathcal, which compares components only relative to the ultrafilter \mathcal. This
binary relation In mathematics, a binary relation associates some elements of one Set (mathematics), set called the ''domain'' with some elements of another set called the ''codomain''. Precisely, a binary relation over sets X and Y is a set of ordered pairs ...
\, \sim \, is an
equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric, and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. A simpler example is equ ...
on the Cartesian product M_i. The is the
quotient set In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
of M_i with respect to \sim and is therefore sometimes denoted by M_i \, / \, \mathcal or _ \, M_\bull. Explicitly, if the \mathcal-
equivalence class In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
of an element a \in M_i is denoted by a_ := \big\ then the ultraproduct is the set of all \mathcal-equivalence classes _ \, M_\bull \; = \; \prod_ M_i \, / \, \mathcal \; := \; \left\. Although \mathcal was assumed to be an ultrafilter, the construction above can be carried out more generally whenever \mathcal is merely a filter on I, in which case the resulting quotient set M_i / \, \mathcal is called a '. When \mathcal is a
principal ultrafilter In the mathematical field of set theory, an ultrafilter on a set X is a ''maximal filter'' on the set X. In other words, it is a collection of subsets of X that satisfies the definition of a filter on X and that is maximal with respect to incl ...
(which happens if and only if \mathcal contains its kernel \cap \, \mathcal) then the ultraproduct is isomorphic to one of the factors. And so usually, \mathcal is not a
principal ultrafilter In the mathematical field of set theory, an ultrafilter on a set X is a ''maximal filter'' on the set X. In other words, it is a collection of subsets of X that satisfies the definition of a filter on X and that is maximal with respect to incl ...
, which happens if and only if \mathcal is free (meaning \cap \, \mathcal = \varnothing), or equivalently, if every
cofinite In mathematics, a cofinite subset of a set X is a subset A whose complement in X is a finite set. In other words, A contains all but finitely many elements of X. If the complement is not finite, but is countable, then one says the set is cocounta ...
subset of I is an element of \mathcal. Since every ultrafilter on a finite set is principal, the index set 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 m on the index set I by saying m(A) = 1 if A \in \mathcal and m(A) = 0 otherwise. Then two members of the Cartesian product are equivalent precisely if they are equal
almost everywhere In measure theory (a branch of mathematical analysis), a property holds almost everywhere if, in a technical sense, the set for which the property holds takes up nearly all possibilities. The notion of "almost everywhere" is a companion notion to ...
on the index set. The ultraproduct is the set of equivalence classes thus generated.
Finitary In mathematics and logic, an operation is finitary if it has finite arity, i.e. if it has a finite number of input values. Similarly, an infinitary operation is one with an infinite number of input values. In standard mathematics, an operat ...
operations on the Cartesian product M_i are defined pointwise (for example, if + is a binary function then a_i + b_i = (a + b)_i). Other relations can be extended the same way: R\left(a^1_, \dots, a^n_\right) ~\iff~ \left\ \in \mathcal, where a_ denotes the \mathcal-equivalence class of a with respect to \sim. In particular, if every M_i is an
ordered field In mathematics, an ordered field is a field together with a total ordering of its elements that is compatible with the field operations. Basic examples of ordered fields are the rational numbers and the real numbers, both with their standard ord ...
then so is the ultraproduct.


Ultrapower

An ''ultrapower'' is an ultraproduct for which all the factors M_i are equal. Explicitly, the is the ultraproduct M_i \, / \, \mathcal = _ \, M_\bull of the indexed family M_ := \left(M_i\right)_ defined by M_i := M for every index i \in I. The ultrapower may be denoted by _ \, M or (since M is often denoted by M^I) by M^I / \mathcal ~:=~ \prod_ M \, / \,\mathcal\, For every m \in M, let (m)_ denote the constant map I \to M that is identically equal to m. This constant map/tuple is an element of the Cartesian product M^I = M and so the assignment m \mapsto (m)_ defines a map M \to M. The is the map M \to _ \, M that sends an element m \in M to the \mathcal-equivalence class of the constant tuple (m)_.


Examples

The hyperreal numbers are the ultraproduct of one copy of the
real numbers In mathematics, a real number is a number that can be used to measurement, measure a continuous variable, continuous one-dimensional quantity such as a time, duration or temperature. Here, ''continuous'' means that pairs of values can have arbi ...
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 \omega given by \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 \psi defined by \psi_i = 2 i. Because \psi_i > \omega_i = i for all i, it follows that the equivalence class of \psi_i = 2 i is greater than the equivalence class of \omega_i = i, so that it can be interpreted as an infinite number which is greater than the one originally constructed. However, let \chi_i = i for i not equal to 7, but \chi_7 = 8. The set of indices on which \omega and \chi agree is a member of any ultrafilter (because \omega and \chi agree almost everywhere), so \omega and \chi belong to the same equivalence class. In the theory of
large cardinal In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers. Cardinals with such properties are, as the name suggests, generally very "large" (for example, bigger than the least ...
s, a standard construction is to take the ultraproduct of the whole set-theoretic universe with respect to some carefully chosen ultrafilter \mathcal. Properties of this ultrafilter \mathcal have a strong influence on (higher order) properties of the ultraproduct; for example, if \mathcal is \sigma-complete, then the ultraproduct will again be well-founded. (See
measurable cardinal In mathematics, a measurable cardinal is a certain kind of large cardinal number. In order to define the concept, one introduces a two-valued measure (mathematics), measure on a cardinal ''κ'', or more generally on any set. For a cardinal ''κ'', ...
for the prototypical example.)


Łoś's theorem

Łoś's theorem, also called , is due to Jerzy Łoś (the surname is pronounced , approximately "wash"). It states that any first-order formula is true in the ultraproduct if and only if the set of indices i such that the formula is true in M_i is a member of \mathcal. More precisely: Let \sigma be a signature, \mathcal an ultrafilter over a set I, and for each i \in I let M_i be a \sigma-structure. Let _ \, M_\bull or M_i / \mathcal be the ultraproduct of the M_i with respect to \mathcal. Then, for each a^1, \ldots, a^n \in M_i, where a^k = \left(a^k_i\right)_, and for every \sigma-formula \phi, _ \, M_\bull \models \phi\left ^1_, \ldots, a^n_\right~\iff~ \ \in \mathcal. The theorem is proved by induction on the complexity of the formula \phi. The fact that \mathcal is an ultrafilter (and not just a filter) is used in the negation clause, and the
axiom of choice In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of non-empty sets, it is possible to construct a new set by choosing one element from e ...
is needed at the existential quantifier step. As an application, one obtains the transfer theorem for hyperreal fields.


Examples

Let R be a unary relation in the structure M, and form the ultrapower of M. Then the set S = \ has an analog ^* S in the ultrapower, and first-order formulas involving S are also valid for ^* S. For example, let M be the reals, and let R x hold if x is a rational number. Then in M we can say that for any pair of rationals x and y, there exists another number z such that z is not rational, and x < z < y. Since this can be translated into a first-order logical formula in the relevant formal language, Łoś's theorem implies that ^* S 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 In abstract algebra and mathematical analysis, analysis, the Archimedean property, named after the ancient Greek mathematician Archimedes of Syracuse, Italy, Syracuse, is a property held by some algebraic structures, such as ordered or normed g ...
of the reals, which states that there is no real number x such that x > 1, \; x > 1 + 1, \; x > 1 + 1 + 1, \ldots 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 \omega above.


Direct limits of ultrapowers (ultralimits)

In
model theory In mathematical logic, model theory is the study of the relationship between theory (mathematical logic), formal theories (a collection of Sentence (mathematical logic), sentences in a formal language expressing statements about a Structure (mat ...
and
set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory – as a branch of mathema ...
, the
direct limit In mathematics, a direct limit is a way to construct a (typically large) object from many (typically smaller) objects that are put together in a specific way. These objects may be groups, rings, vector spaces or in general objects from any cate ...
of a sequence of ultrapowers is often considered. In
model theory In mathematical logic, model theory is the study of the relationship between theory (mathematical logic), formal theories (a collection of Sentence (mathematical logic), sentences in a formal language expressing statements about a Structure (mat ...
, this construction can be referred to as an ultralimit or limiting ultrapower. Beginning with a structure, A_0 and an ultrafilter, \mathcal_0, form an ultrapower, A_1. Then repeat the process to form A_2, and so forth. For each n there is a canonical diagonal embedding A_n \to A_. At limit stages, such as A_\omega, 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. Similarly, the is the codensity monad of the inclusion of the category \mathbf of finitely-indexed families of sets into the category \mathbf of all indexed families of sets. So in this sense, ultraproducts are categorically inevitable. Explicitly, an object of \mathbf consists of a non-empty
index set In mathematics, an index set is a set whose members label (or index) members of another set. For instance, if the elements of a set may be ''indexed'' or ''labeled'' by means of the elements of a set , then is an index set. The indexing consists ...
I and an
indexed family In mathematics, a family, or indexed family, is informally a collection of objects, each associated with an index from some index set. For example, a family of real numbers, indexed by the set of integers, is a collection of real numbers, wher ...
\left(M_i\right)_ of sets. A morphism \left(N_i\right)_ \to \left(M_i\right)_ between two objects consists of a function \phi : I \to J between the index sets and a J-indexed family \left(\phi_j\right)_ of function \phi_j : M_ \to N_j. The category \mathbf is a full subcategory of this category of \mathbf consisting of all objects \left(M_i\right)_ whose index set I is finite. The codensity monad of the inclusion map \mathbf \hookrightarrow \mathbf is then, in essence, given by \left(M_i\right)_ ~\mapsto~ \left(\prod_ M_i \, / \, \mathcal\right)_ \, .


See also

* * * * *


Notes

Proofs


References

* * {{Mathematical logic Mathematical logic Model theory Nonstandard analysis Theorems in the foundations of mathematics Universal algebra