# Theories with Infinite Models have Models with Order Indiscernibles

## Theorem

Let $T$ be an $\LL$-theory with infinite models.

Let $\struct {I, <$ be an infinite strict linearly ordered set.

There is a model $\MM \models T$ containing an order indiscernible set $\set {x_i : i \in I}$.

## Proof

We will construct the claimed model using the Compactness Theorem.

Let $LL^*$ be the language obtained by adding constant symbols $c_i$ to $\LL$ for each $i \in I$.

Let $T^*$ be the $\LL^*$-theory obtained by adding to $T$ the $\LL^*$-sentences:

- $c_i \ne c_j$ for each $i \ne j$ in $I$

and:

- $\map \phi {c_{i_1}, \dotsc, c_{i_n} } \leftrightarrow \map \phi {c_{j_1}, \dotsc, c_{j_n} }$ for each $n \in \N$, each $\LL$-formula $\phi$ with $n$ free variables, and each pair of chains $i_1 < \cdots < i_n$ and $j_1 < \cdots < j_n$ in $I$.

For future reference, we will refer to these last sentences using as those which **assert indiscernibility with respect to $\phi$**.

If we can find a model of $T^*$, then its interpretations of the constants $c_i$ for $i\in I$ will be order indiscernibles.

Suppose $\Delta$ is a finite subset of $T^*$.

- We will show that there is a model of $\Delta$ using the Infinite Ramsey's Theorem.

- Let $I_\Delta$ be the finite subset of $I$ containing those $i$ for which $c_i$ occurs in some sentence in $\Delta$.
- Let $\psi_1, \dots, \psi_k$ be the finitely many $\LL$-formulas in $\Delta$ which assert indiscernibility with respect to $\phi_1, \dots, \phi_k$.
- Let $m$ be the maximum number of free variables in the formulas $\phi_1, \dots, \phi_k$.
- Let $\MM$ be an infinite model of $T$ (which exists by assumption).
- Let $X$ be any infinite subset of the universe of $\MM$ such that $X$ is linearly ordered by some relation $\prec$.

- Define a partition $P$ of $X^{\paren m} = \set {X' \subseteq X: \card {X'} = m}$ into $2^k$ components $S_A$ for each $A \subseteq \set {1, 2, \dotsc, k}$ by:
- $\set {x_1, \dots, x_m} \in S_A \iff x_1 \prec \cdots \prec x_m \text { and } A = \set {i: \MM \models \map {\phi_i} {x_1, \dotsc, x_m} }$

- By Infinite Ramsey's Theorem, there is an infinite subset $Y\subseteq X$ such that each element of $Y^{\paren m} = \set {Y' \subseteq Y: \card {Y'} = m}$ is in the same component $S_A$ of $P$.

- Note that $Y$ is indexed by some infinite subset $J_Y$ of $J$ and hence still linearly ordered by $\prec$.

- We now show that the constants $c_i$ for $i \in I_\Delta$ can be interpreted as elements of $Y$ in $\MM$, and that the sentences $\psi_1, \dots, \psi_k$ will be satisfied using this interpretation.

- Since $I_\Delta$ is finite and linearly ordered, and $J_Y$ is infinite and linearly ordered, there is clearly an increasing function $f:I_\Delta \to J_Y$.

- For each $h = 1, \dotsc, k$ and any pair of chains $i_1 < \cdots < i_n$ and $j_1 < \cdots < j_n$ in $I_\Delta$, we thus have:
- $\MM \models \map {\phi_h} {y_{\map f {i_1} }, \dotsc, y_{\map f {i_n} } }$ if and only if $h \in A$ if and only if $\MM \models \map {\phi_h} {y_{\map f {j_1} }, \dotsc, y_{\map f {j_n} } }$

- and hence:
- $\MM \models \map {\phi_h} {y_{\map f {i_1} }, \dotsc, y_{\map f {i_n} } } \iff \map {\phi_h} {y_{\map f {j_1} }, \dotsc, y_{\map f {j_n} } }$

- So, if we interpret each $c_i$ for $i \in I_\Delta$ as $y_{\map f i}$, we will have $\MM \models \psi_h$ for each $h = 1, \dotsc, k$.

- Thus, we have shown that $\MM$ can be extended to an $\LL^*$-structure which models $\Delta$.

Hence all finite subsets $\Delta$ of $T^*$ are satisfiable.

By the Compactness Theorem, we have that $T^*$ is satisfiable.

Let $\NN$ be any model of $T^*$.

Let $n_i$ be the interpretation of $c_i$ in $\NN$ for each $i \in I$.

Then $\set {n_i: i \in I}$ is easily seen to be an order indiscernible set, since $T^*$ was defined to include sentences guaranteeing such.

$\blacksquare$