Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 20 / 8 / Solution

Let $M^{\ast }$ be a full Skolem expansion of an infinite structure $M$, choose distinct $b_n\in M$ for $n\in \mathbb{N}$, and extend the cofinite filter to a nonprincipal ultrafilter $U$ on $\mathbb{N}$. For a finite 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$ bywhere $UnP(n)$ means $\{n:P(n)\}\in U$. These nested tests decide complements and preserve intersections by induction on $r$, so $U_F$ is indeed an ultrafilter. For the empty set use the one-point index set and its principal ultrafilter.

Put $M_F=(M^{\ast }{)}^{{\mathbb{N}}^F}/U_F$. If $F\subseteq G$, projection of coordinates inducesA truth test independent of a coordinate is unchanged by its dummy ultrafilter quantifier. Consequently pullback preserves exactly the $U_F$-large subsets, proving that the map is well defined and injective. The Łoś theorem, applied to every formula rather than just to equality, proves that it is an elementary embedding. Projections compose, so these elementary maps form a coherent directed system.

Take its directed limit of elementary embeddings $N^{\ast }$. Explicitly identify two stage elements when their images agree at a common larger stage, and interpret functions and relations there. For an existential formula true in the limit, its parameters and a witness occur at a common stage; elementarity then pulls truth back to the stage of the original parameters. This verifies that all stage maps into the limit are elementary.

Let $a_i$ be the image in this limit of the coordinate class $[n\mapsto b_n]\in M_{\{i\}}$. These elements are distinct: in $U_{\{i,j\}}$, equality would require $n_i=n_j$, whose inner-coordinate section is a singleton and hence not in the nonprincipal $U$. For $i_1<\cdots <i_r$, the truth of any expanded-language formula on $(a_{i_1},\dots ,a_{i_r})$ is exactlyThis expression depends on the formula and the tuple length, not on the chosen increasing indices. Thus $(a_i{)}_{i\in I}$ is an order-indiscernible sequence. The empty-coordinate stage embeds $M^{\ast }$ elementarily into $N^{\ast }$.

Their Skolem hull is elementary by the witness-function argument, and an order automorphism of $I$ extends to it by transporting the generators in every term. Equality and relation preservation follow from the displayed uniform truth test, and the inverse order automorphism gives the inverse map. Therefore this proves the Ehrenfeucht-Mostowski theorem through ultrapowers and their directed limit, with no Ramsey-theoretic step.