Ultraproduct

From Wikipedia, the free encyclopedia

An ultraproduct is a mathematical construction, a generalization of the ultrapower, which is used in abstract algebra to construct new fields from given ones, and in model theory, a branch of mathematical logic. In particular, it can be used in a "purely semantic" proof of the compactness theorem of first-order logic. One well-known use of ultraproducts is the construction of the hyperreal numbers by taking the ultraproduct of countably infinitely many copies of the field of real numbers.

The general method for getting ultraproducts uses an index set I, a structure M_i for each element i of I, and an ultrafilter U on I (the usual choice is for I to be infinite and U to contain all cofinite subsets of I).

Algebraic operations on the cartesian product

$\prod_{i \in I} M_i$

are defined in the usual way (for example, for a binary function +, (a + b) _i = a_i + b_i ), and an equivalence relation is defined by a ~ b if and only if

$\left\{ i \in I: a_i = b_i \right\}\in U,$

and the ultraproduct is the quotient set with regard to ~. The ultraproduct is therefore sometimes denoted by

$\prod_{i\in I}M_i / U .$

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 on the index set. The ultraproduct is the set of equivalence classes thus generated.

Other relations can be extended the same way: a R b if and only if

$\left\{ i \in I: a_i\,R\,b_i \right\}\in U.$

In particular, if every F_i is an ordered field, then so is the ultraproduct.

1 Łoś' theorem
2 Examples
3 See also
4 References

[edit] Łoś' theorem

Łoś' theorem (due to Jerzy Łoś; the surname is pronounced, approximately, "wash") 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 U. More precisely:

Let $U$ be an ultrafilter over a set $I$ , and for each $i \in I$ let $M i$ be a first order model. Let $M$ be the ultraproduct of the $M i$ with respect to $U$ , that is, $M = \prod_{ i\in I }M_i/U.$

Then, for each $a^{1}, \ldots, a^{n} \in \prod M_{i}$ , where $a^{k} = (a^{k}_{i})_{i \in I}$ , and for every formula $φ$

$M \models \phi[[a^1], \ldots, [a^n]]$ if and only if $\{ i \in I : M_{i} \models \phi[a^1_{i}, \ldots, a^n_{i} ] \} \in U$ .

The theorem is proved by induction on the complexity of the formula $φ$ . 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.

[edit] 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.

Analogously, one can define nonstandard complex numbers by taking the ultraproduct of copies of the field of complex numbers.

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 for the prototypical example.)