= 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^*$ 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^*$, using separate names for its elements. Require $c_i\neq c_j$ for distinct indices, and for each formula $\varphi$ in the Skolem language require
$$
\varphi(c_{i_1},\ldots,c_{i_k})\leftrightarrow\varphi(c_{j_1},\ldots,c_{j_k})
$$
whenever both index tuples are strictly increasing. These are the <order-indiscernible sequence> requirements.
Every finite fragment is satisfiable in $M^*$. Choose a countably infinite sequence of distinct elements of $M^*$. 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^*$. By the <compactness theorem> proved in Question 5, the full set of requirements has a model $N^*$, 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^*\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\preceq N^*$; its reduct is a model of $\operatorname{Th}(M)$. For infinite $I$, its <cardinality> is at most $\max(|I|,|L^*|,\aleph_0)$ and at least $|I|$.
For an <order automorphism> $\alpha:I\to I$, define
$$
\widehat\alpha\bigl(t(c_{i_1},\ldots,c_{i_k})\bigr)=t(c_{\alpha(i_1)},\ldots,c_{\alpha(i_k)}).
$$
Rewrite 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{\operatorname{Aut}(I)\hookrightarrow\operatorname{Aut}(H^*)}$, with uniqueness in the Skolem expansion. This uniqueness need not hold in the unexpanded reduct.
Back to article page
