Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 25 / 6 / Solution

We prove the Ehrenfeucht-Mostowski theorem by ordered products of ultrafilters, without using Ramsey's theorem. Choose a Skolem expansion $M^{\ast }$ of the infinite structure and distinct elements $b_0,b_1,\dots$. Fix a nonprincipal ultrafilter $U$ on $\mathbb{N}$.

For a finite increasing subset $F=\{i_1<\cdots <i_r\}$ of the desired index order $I$, define the ordered Fubini product of ultrafilters $U_F$ on ${\mathbb{N}}^F$ byThe notation $UnP(n)$ means that the set of $n$ satisfying $P$ belongs to $U$; the leftmost quantifier is outermost. Upward closure and intersection follow successively at each coordinate, and applying complement at each step proves the ultrafilter dichotomy. Products are ordered; no false claim of symmetry is needed.

Put $M_F=(M^{\ast }{)}^{{\mathbb{N}}^F}/U_F$, with $M_{\varnothing }=M^{\ast }$. If $F\subseteq G$, pullback of a function by coordinate projection inducesFor a cylinder condition involving only coordinates in $F$, deleting the unused ultrafilter quantifiers makes its membership in $U_G$ exactly its membership in $U_F$. The Łoś theorem therefore makes ${\sigma }_{FG}$ an elementary embedding, not merely a homomorphism. The projection identities give ${\sigma }_{GH}{\sigma }_{FG}={\sigma }_{FH}$.

Take the directed limit of this system: elements from two stages are identified if their images agree at a common larger finite stage, and formulas are evaluated at such a stage. Elementary coherence makes this well-defined. It also makes each stage elementary in the limit: a formula uses finitely many parameters, and an existential witness at a later stage can be pulled back at the level of existential truth because the transition maps are elementary. Denote the limit by $N^{\ast }$.

For each $i\in I$, let $a_i$ be the limit image of the coordinate function $n_i\mapsto b_{n_i}$. These elements are distinct. For $i<j$, after fixing $n_i$, equality $b_{n_i}=b_{n_j}$ holds for at most one $n_j$, a set not in $U$; hence equality fails in the two-coordinate ultrapower and therefore in the limit.

For any increasing $i_1<\cdots <i_r$, Łoś evaluatesThe right-hand side depends on the formula and the number of increasing coordinates, not their particular indices. Thus $(a_i{)}_{i\in I}$ is order-indiscernible for every formula of the expanded language simultaneously; no preliminary homogeneous thinning is used. If elements of $M$ were named before expanding, the same computation gives indiscernibility over those names and the initial stage embeds the original structure into the limit.

The Skolem hull of these generators is elementary by the witness property. Transporting the generators by any order automorphism of $I$ transports every term, with well-definedness and relation preservation supplied by the formula equivalence just proved. The inverse transport supplies an inverse automorphism. The ordered-ultrapower construction gives the full Ehrenfeucht–Mostowski model and its order automorphisms without Ramsey's theorem.