Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 26 / 6 / Solution

The Ehrenfeucht-Mostowski theorem asserts that an infinite first-order structure has, for any prescribed total order $I$, an elementary extension containing distinct order-indiscernibles $(c_i{)}_{i\in I}$. After a Skolem expansion, the Skolem hull of those generators is a model of the original complete theory. Every order automorphism of $I$ extends to a unique automorphism of this specified Skolem hull in the expanded language.

Choose a Skolem expansion $M^{\ast }$ of the original infinite structure: for each existential formula, select a witness function, including nullary functions when needed. Add constants $c_i$ for $i\in I$ and the elementary diagram of a structure of $M^{\ast }$, using separate names for its elements. Require $c_i\ne c_j$ for distinct indices, and for each formula $\phi$ in the Skolem language requirewhenever both index tuples are strictly increasing. These are the order-indiscernible sequence requirements.

Every finite fragment is satisfiable in $M^{\ast }$. Choose a countably infinite sequence of distinct elements of $M^{\ast }$. The fragment mentions only finitely many formulas and arities. Color increasing $k$-tuples of that sequence by the finite vector of truth values of its relevant $k$-ary formulas. The Ramsey theorem supplies an infinite homogeneous subsequence; repeat for the finitely many arities. Assign the finitely many named $c_i$ to distinct elements of the final homogeneous subsequence in increasing index order. The fixed finite part of the elementary diagram of a structure already holds in $M^{\ast }$. By the compactness theorem proved in Question 5, the full set of requirements has a model $N^{\ast }$, giving the required elementary extension and order-indiscernible sequence.

Let $H$ comprise all values of Skolem-language terms in finitely many $c_i$. It is closed under the witness functions. If $N^{\ast }\models \exists x\psi (x,\bar{h})$ for parameters in $H$, the specified witness function supplies a witness in $H$. Induction on formulas therefore gives $H⪯N^{\ast }$; its reduct is a model of $\mathrm{Th}(M)$. For infinite $I$, its cardinality is at most $\max (|I|,|L^{\ast }|,{\aleph }_0)$ and at least $|I|$.

For an order automorphism $\alpha :I\to I$, defineRewrite any finite list of indices in increasing order, allowing a term to repeat or omit variables. The order-indiscernible sequence property transfers every equality between terms and every relation among their values, making this definition well defined and elementary. Applying ${\alpha }^{-1}$ gives its inverse. All of $H$ is generated by the $c_i$ and the named Skolem functions, so an automorphism extending $\alpha$ must have precisely this action. Thus $\boxed{\mathrm{Aut}(I)\hookrightarrow \mathrm{Aut}(H^{\ast })}$, with uniqueness in the Skolem expansion. This uniqueness need not hold in the unexpanded reduct.