Łoś's theorem
   HOME

TheInfoList



OR:

The ultraproduct is a
mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
construction that appears mainly in
abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics), rings, field (mathematics), fields, module (mathe ...
and
mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...
, in particular in model theory and
set theory Set theory is the branch of mathematical logic that studies 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 mathematics, is mostly conce ...
. An ultraproduct is a
quotient In arithmetic, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to as the integer part of a ...
of the direct product of a family of
structures 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 ...
. All factors need to have the same
signature A signature (; from la, signare, "to sign") is a handwritten (and often stylized) 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. The writer of a ...
. The ultrapower is the special case of this construction in which all factors are equal. For example, ultrapowers can be used to construct new
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...
s from given ones. The
hyperreal number In mathematics, the system of hyperreal numbers is a way of treating infinite and infinitesimal (infinitely small but non-zero) quantities. The hyperreals, or nonstandard reals, *R, are an extension of the real numbers R that contains numbers ...
s, 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 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 generally ...
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 Abraham Robinson (born Robinsohn; October 6, 1918 – April 11, 1974) was a mathematician who is most widely known for development of nonstandard analysis, a mathematically rigorous system whereby infinitesimal and infinite numbers were reincorp ...
.


Definition

The general method for getting ultraproducts uses an index set ''I'', a structure ''M''''i'' for each element ''i'' of ''I'' (all of the same
signature A signature (; from la, signare, "to sign") is a handwritten (and often stylized) 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. The writer of a ...
), and an
ultrafilter In the 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 filter on P; that is, a proper filter on P that cannot be enlarged to a bigger proper filter o ...
''U'' on ''I''. One usually considers this in the case that ''I'' to be infinite and ''U'' contains all
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 it is countable, then one says the set is coco ...
subsets of ''I'', i.e. ''U'' is not a principal ultrafilter. In the principal case the ultraproduct is isomorphic to one of the factors. Algebraic operations on the Cartesian product :\prod_ M_i are defined pointwise (for example, if + is a binary function then a_i + b_i =(a + b)_i), and an equivalence relation is defined by a \sim b if :\left\\in U, and hence compares components only relative to the ultrafilter ''U''. The ultraproduct 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 a ...
with respect to \sim. The ultraproduct is therefore sometimes denoted by :\prod_M_i / U. and 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'' ∈ ''U'' and = 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. Other relations can be extended the same way: :R( ^1\dots, ^n \iff \left\\in U, where 'a''denotes the 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. The basic example of an ordered field is the field of real numbers, and every Dedekind-complete ordered fiel ...
, then so is the ultraproduct. An is an ultraproduct for which all the factors ''M''''i'' are equal: M^I/U=\prod_M/U.\, More generally, the construction above can be carried out whenever ''U'' is a
filter Filter, filtering or filters may refer to: Science and technology Computing * Filter (higher-order function), in functional programming * Filter (software), a computer program to process a data stream * Filter (video), a software component tha ...
on ''I''; the resulting model \prod_M_i / U is then called a .


Examples

The
hyperreal numbers In mathematics, the system of hyperreal numbers is a way of treating infinite and infinitesimal (infinitely small but non-zero) quantities. The hyperreals, or nonstandard reals, *R, are an extension of the real numbers R that contains 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 ''ω''''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 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 epsilon–delta ...
, 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 ''ψ''''i'' = 2''i''. Because ''ψ''''i'' > ''ω''''i'' = ''i'' for all ''i'', it follows that the equivalence class of ''ψ''''i'' = 2''i'' is greater than the equivalence class of ''ω''''i'' = ''i'', so that it can be interpreted as an infinite number which is greater than the one originally constructed. However, let ''χ''''i'' = ''i'' for ''i'' not equal to 7, but ''χ''7 = 8. 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 ''U''. Properties of this ultrafilter ''U'' have a strong influence on (higher order) properties of the ultraproduct; for example, if ''U'' is ''σ''-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 on a cardinal , or more generally on any set. For a cardinal , it can be described as a subdivisi ...
for the prototypical example.)


Łoś's theorem

Łoś's theorem, also called , is due to
Jerzy Łoś Jerzy Łoś (born 22 March 1920 in Lwów, Poland (now Lviv, Ukraine) – 1 June 1998 in Warsaw) () was a Polish mathematician, logician, economist, and philosopher. He is especially known for his work in model theory, in particular for " Łoś's th ...
(the surname is pronounced , approximately "wash"). It states that any
first-order In mathematics and other formal sciences, first-order or first order most often means either: * "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of high ...
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 ''U''. More precisely: Let σ be a signature, U an ultrafilter over a set I , and for each i \in I let M_ be a ''σ''-structure. Let M be the ultraproduct of the M_ with respect to U, that is, M = \prod_M_i/U. Then, for each a^, \ldots, a^ \in \prod M_ , where a^ = (a^k_i)_ , and for every ''σ''-formula \phi, : M \models \phi ^1_\ldots,_[a^n.html" ;"title="^1 \ldots, [a^n">^1 \ldots, [a^n \iff \ \in U. The theorem is proved by induction on the complexity of the formula \phi. The fact that 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 principle, transfer theorem for hyperreal number, 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 ''Rx'' 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 analysis, the Archimedean property, named after the ancient Greek mathematician Archimedes of Syracuse, is a property held by some algebraic structures, such as ordered or normed groups, and fields. The property, typica ...
of the reals, which states that there is no real number ''x'' such that ''x'' > 1, ''x'' > 1 + 1, ''x'' > 1 + 1 + 1, ... 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 Set theory is the branch of mathematical logic that studies 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 mathematics, is mostly conce ...
, 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, ''A''0, and an ultrafilter, ''D''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''ω, form the direct limit of earlier stages. One may continue into the transfinite.


See also

* * *


References

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