indiscernible sequence?
Morley sequence?
Ramsey theorem?
Erdos-Rado theorem?
Ehrenfeucht-Fraïssé games (back-and-forth games)
Hrushovski construction?
generic predicate?
In model theory, an ultrapower of a structure with respect to an ultrafilter is a common method for creating new structures, with applications to nonstandard arithmetic and nonstandard analysis. It is a standard construction for constructing models which embody infinite and infinitesimal quantities, as in Abraham Robinson’s nonstandard analysis.
An ultrapower is a special case of ultraproduct; see the description under the sheaf-theoretic interpretation below.
Let $X$ be a set, and let $\mathcal{U}$ be an ultrafilter on $X$; that is, a collection of subsets such that
If $A \in \mathcal{U}$ and $A \subseteq B \subseteq X$, then $B \in \mathcal{U}$,
If $A, B \in \mathcal{U}$, then $A \cap B \in \mathcal{U}$,
$\emptyset \notin \mathcal{U}$,
For every set $A \subseteq X$, either $A$ belongs to $\mathcal{U}$ or its complement $\neg A$ belongs to $\mathcal{U}$.
(The first three axioms are the defining axioms for a filter, and the last is satisfied for maximal filters, aka ultrafilters.)
Let $Y$ be a model of a (finitary, single-sorted) first-order theory $T$ (given by a signature $\Sigma$ together with a set of axioms in the language generated by $\Sigma$). Then the ultrapower
is the set of $\sim$-equivalence classes $[f]$ on the set of functions $f \in hom(X, Y)$, where $f \sim g$ if and only if
The ultrapower is a structure of $\Sigma$ under the evident pointwise definitions: for each $n$-ary function symbol $\phi$, define
and observe that $f_1 \sim g_1, \ldots, f_n \sim g_n$ implies that $\phi(f_1, \ldots, f_n) \sim \phi(g_1, \ldots, g_n)$, so that the interpretation of $\phi$ descends to equivalence classes. Similarly, for each $n$-ary relation symbol $R$, say $\vdash R([f_1], \ldots, [f_n])$ if
for any chosen representatives $f_1, \ldots, f_n$. Note that the well-definedness of the interpretations of functions and relations depends only on the filter axioms.
That the ultrapower is a model of the theory is a consequence of Los's theorem. (Here one needs all of the ultrafilter conditions, in particular one needs condition 4 in order to accommodate satisfaction of formulas involving instances of negation.)
An ultrafilter $\mathcal{U}$ on a set $X$ may be regarded as a point in the Stone-Cech compactification $\beta X$ of the discrete space $X_d$, and ultrapowers may be interpreted as a special case of taking stalks.
Namely, let $i: X_d \hookrightarrow \beta X$ be the inclusion. This is a continuous function; hence it induces a geometric morphism $i_*$ between the sheaf toposes over these spaces. Then, under the composite
the set $Y$ is taken to the ultrapower $Y^X/\mathcal{U}$.
An object of $Set/X$ is just an $X$-indexed collection $Y_x$ of sets, and the more general ultraproduct $\prod_x Y_x/\mathcal{U}$ is the value obtained by applying the composite
to the object $\langle Y_x \rangle_{x \in X}$.
For any filter $\mathcal{U}$ on a set $X$, we can form the 2-colimit of the pseudofunctor
Each $F(i: U \subseteq V): Set/V \to Set/U$ is the logical morphism of toposes given by the pullback functor $i^*$. The 2-colimit is itself a topos denoted $Set/\mathcal{U}$, in fact a 2-valued topos if $\mathcal{U}$ is an ultrafilter, and the functor defined by
defines a logical morphism.
If $\mathcal{U}$ is a principal ultrafilter, then the ultrapower of $Y$ is isomorphic to $Y$ again. Thus the interest in ultrapowers relies on the existence of non-principal ultrafilters, which requires some sort of choice principle.
An important application is to $Y = \mathbb{R}$ as a model of the theory of ordered fields. If $\mathcal{U}$ is a non-principal ultrafilter on the set of natural numbers $\mathbb{N}$, then the model $\mathbb{R}^{\mathbb{N}}/\mathcal{U}$ provides a model for nonstandard analysis (in the sense promulgated by Abraham Robinson). There are in particular infinitesimal elements in the ultrapower, for example the $\sim$-equivalence class of the sequence $\langle 1/n \rangle_{n \in \mathbb{N}} \in \mathbb{R}^{\mathbb{N}}$.
At the same time, the ultrapower is elementarily equivalent to $\mathbb{R}$, so that the sentences true for $\mathbb{R}$ in the first-order theory of ordered fields coincide with the sentences that are true for the ultrapower. This principle assures us that any conclusions adduced with the help of infinitesimals in the ultrapower are still valid in the standard model $\mathbb{R}$; in some cases, however, the arguments based on infinitesimals may offer more perspicuous proofs.