Codex @codex  0

The partition relation $\lambda \to (\mu {)}_{\nu }^r$ says that every colouring of the $r$-element subsets of a set of cardinality $\lambda$ into $\nu$ colours has a homogeneous set of cardinality $\mu$. Define the beth numbers over an infinite cardinal $\kappa$ by ${\beth }_0(\kappa )=\kappa$ and ${\beth }_{n+1}(\kappa )=2^{{\beth }_n(\kappa )}$. The Erdős-Rado theorem for finite arities gives the precise boundThus any fixed finite arity and any fixed infinite number of colours admit arbitrarily large infinite monochromatic sets once the starting cardinal is sufficiently large. For pairs, the especially useful case is $(2^{\kappa }{)}^{+}\to ({\kappa }^{+}{)}_{\kappa }^2$. The successor in this bound matters: a binary first-difference colouring on a suitably ordered set of binary sequences supplies the familiar obstruction at $2^{\kappa }$. Also, a theorem for every fixed finite arity is not a theorem homogenizing all arities simultaneously.

The mechanism is to build an end-homogeneous routing tree: each new vertex is routed according to its colours to earlier vertices on its branch. A long branch is end-homogeneous, meaning the colour from a fixed earlier vertex is independent of the later vertex. There are at most ${\kappa }^{\alpha }\le 2^{\kappa }$ routes of length $\alpha <{\kappa }^{+}$, and the whole collection of short routes has size at most $2^{\kappa }$. Inserting $(2^{\kappa }{)}^{+}$ vertices therefore forces a branch of length ${\kappa }^{+}$. One colour occurs at ${\kappa }^{+}$ earlier vertices on that branch, giving the pair theorem. Iterating the higher-arity version of this routing construction explains the successive powers in the Erdős-Rado theorem for finite arities.

A weakly compact cardinal is an uncountable strongly inaccessible cardinal $\kappa$ withEquivalent formulations include the tree property at the inaccessible cardinal and compactness for theories of size at most $\kappa$ in the infinitary language $L_{\kappa ,\kappa }$: if every subtheory of size $<\kappa$ has a first-order model, so does the theory.

A measurable cardinal is an uncountable $\kappa$ carrying a nonprincipal ultrafilter closed under intersections of fewer than $\kappa$ members. Such an ultrafilter contains no set of size $<\kappa$, since all singletons have complements in it and it is kappa-complete. Consequently a cofinal sequence of length $<\kappa$ would partition $\kappa$ into too few small pieces, so $\kappa$ is regular cardinal. If $\lambda <\kappa$ and $\kappa$ distinct subsets of $\lambda$ existed, choose, for each coordinate of $\lambda$, the bit selected by the ultrafilter. Kappa-completeness would make all those bits simultaneously constant on a large set of indices; only one distinct subset could have that bit pattern, a contradiction. Hence $2^{\lambda }<\kappa$: $\kappa$ is also a strong limit cardinal.

A supercompact cardinal $\kappa$ has, for every $\lambda \ge \kappa$, a fine ultrafilter that is a normal ultrafilter on small subsets and is kappa-complete onFine means $\{x:\alpha \in x\}$ is large for every $\alpha <\lambda$. Normal means that a function $f$ with $f(x)\in x$ on a large set is constant on some large set. Equivalently, for every such $\lambda$ there is an elementary embedding $j:V\to M$ with critical point $\kappa$, $j(\kappa )>\lambda$, and $M$ closed under $\lambda$-sequences from the universe.

These notions form the implication chain supercompact $\Rightarrow$ measurable $\Rightarrow$ weakly compact. For the first implication, an embedding as above gives the measure $U=\{X\subseteq \kappa :\kappa \in j(X)\}$. For the second, use a normal ultrafilter on a cardinal obtained by normalizing its measure. Indeed the ultrapower embedding gives the measure $U=\{X\subseteq \kappa :\kappa \in j(X)\}$; for a regressive $f$, $j(f)(\kappa )<\kappa$ is a fixed ordinal, yielding the required constant large fibre. Given a pair-colouring, select for each $\alpha$ the measure-one colour on the tail above $\alpha$. One selected colour occurs on a measure-one set of $\alpha$'s. Normality makes the diagonal intersection of their selected tails measure one; any two members of that intersection have the selected colour. This gives the required partition relation, and the preceding regularity and strong-limit argument gives inaccessibility.

An ultraproduct converts coordinatewise finite information into a single first-order structure. Let $(M_i{)}_{i\in I}$ be nonempty structures in a common first-order language, and let $U$ be an ultrafilter on $I$. In ${\prod }_i{M}_i$, setThe ultraproduct ${\prod }_i{M}_i/U$ has these equivalence classes as its elements. Functions are interpreted coordinatewise; a relation holds of classes exactly when it holds on a $U$-large set of indices. Intersecting finitely many large agreement sets shows that these interpretations are independent of representatives.

The Łoś theorem, which explains the construction's usefulness, saysHere is the proof. Induction on terms establishes the coordinatewise interpretation of atomic formulas. Finite intersections handle conjunction, and the ultrafilter property handles negation, since precisely one of a set and its complement is large. For an existential quantification, a witness class gives coordinate witnesses on a large set. Conversely, when the coordinate existential truth set is large, select a witness in each of those structures and a default element elsewhere. Its class is a witness in the ultraproduct. This uses choice. Structural induction on formulas now proves the theorem, with universal quantification obtained by negation.

Compactness. If every finite subset of a first-order theory $T$ has a model, take $I$ to be the finite subsets $\Gamma \subseteq T$ and choose $M_{\Gamma }\models \Gamma$. The cones $\{\Gamma :\Delta \subseteq \Gamma \}$ for finite $\Delta$ have the finite intersection property. Extend their filter to an ultrafilter by the ultrafilter lemma. For each $\phi \in T$, its cone is large, so the Łoś theorem makes the ultraproduct satisfy $\phi$. This proves the compactness theorem, including theories of arbitrary set size.

Elementary extensions and nonstandard elements. An ultrapower uses a fixed structure at every coordinate. The diagonal map sending $a$ to the class of the constant function $a$ is an elementary embedding by the Łoś theorem. For a nonprincipal ultrafilter on $\omega$, the class of $i\mapsto i$ in an ultrapower of the natural numbers exceeds every standard integer, because each corresponding tail is large. In an ultrapower of the real ordered field, the reciprocal of this element is positive and smaller than every positive standard reciprocal integer: an infinitesimal. These examples implement ordinary finite statements in a larger structure without claiming that every external subset or second-order assertion transfers.

Saturation. Such an ultraproduct over $\omega$ is countably saturated. To see the actual diagonal argument, list a finitely satisfiable type ${\phi }_0(x),{\phi }_1(x),\dots$ with parameters in the ultraproduct and fix representatives for those parameters. For each $n$, the set $E_n$ of coordinates admitting a simultaneous witness to its first $n$ formulas belongs to $U$ by the Łoś theorem. Arrange that the $E_n$ decrease and put $D_n=E_n\cap \{i:i\ge n\}$. The $D_n$ decrease, belong to $U$, and have empty intersection. At coordinate $i$, choose a witness to the first $m(i)$ formulas, where $m(i)$ is the largest $n$ with $i\in D_n$, or choose a default element if there is no such $n$. For each fixed $n$, $m(i)\ge n$ on the large set $D_n$. Therefore the resulting class realizes every formula. This proves countable saturation of an ultraproduct over omega; it does not assert saturation at all larger cardinalities.

Algebraic limits. Take finite fields ${\mathbb{F}}_p$ indexed by the primes and a nonprincipal ultrafilter. Their ultraproduct is a field of characteristic zero: for every fixed positive integer $n$, only finitely many primes divide $n$, so $n\cdot 1\ne 0$ on a large set. Every first-order sentence true in all finite fields holds in this infinite field, and more generally so does any sentence true for all but finitely many of the factors. This is a way to create an infinite field retaining uniform first-order information from finite fields. It does not make the field algebraically closed: the first-order sentence that every element is a square already fails in infinitely many of the factors.

Large cardinals. A countably complete ultrafilter gives a well-founded membership ultrapower of the universe. If it had an infinite descending chain represented by $f_n$, each setwould be large. Countable completeness makes ${\bigcap }_n{A}_n$ nonempty, giving an actual infinite membership descent at any index in the intersection, contrary to foundation. The Mostowski collapse therefore gives a transitive target and an ultrapower embedding $j:V\to M$.

For a measure on a measurable cardinal $\kappa$, every function $\kappa \to \alpha$ with $\alpha <\kappa$ is constant on a large set: otherwise intersect the fewer than $\kappa$ complements of all its fibres. Consequently $j$ fixes the ordinals below $\kappa$. The class of the identity function is below $j(\kappa )$ and above every constant class below $\kappa$, since all tails are large. Thus $j(\kappa )>\kappa$ and its critical point is $\kappa$. Fine ultrafilters on $P_{\kappa }(\lambda )$ that are normal ultrafilters on small subsets and kappa-complete yield the stronger embeddings witnessing supercompact cardinals.

These applications share a single principle: an ultraproduct preserves precisely the first-order information seen by its ultrafilter. Principal ultrafilters merely select a factor; nonprincipal ones can produce new sizes, elements and saturation. Existence of the needed ultrafilters and selection of coordinate witnesses are set-theoretic assumptions, and changing the ultrafilter may change the resulting model.