Theories with Infinite Models have Models with Order Indiscernibles

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $T$ be an $\mathcal{L}$-theory with infinite models.

Let $(I, <)$ be an infinite strict linearly ordered set.


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


Proof

We will construct the claimed model using the Compactness Theorem.


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

Let $T^*$ be the $\mathcal{L}^*$-theory obtained by adding to $T$ the $\mathcal{L}^*$-sentences:

$c_i \neq c_j$ for each $i\neq j$ in $I$, and
$\phi (c_{i_1},\dots,c_{i_n}) \leftrightarrow \phi (c_{j_1},\dots,c_{j_n})$ for each $n\in \mathbb N$, each $\mathcal{L}$-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 $\mathcal{L}$-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 $\mathcal{M}$ be an infinite model of $T$ (which exists by assumption).
Let $X$ be any infinite subset of the universe of $\mathcal{M}$ such that $X$ is linearly ordered by some relation $\prec$.


Define a partition $P$ of $X^{(m)} = \{X'\subseteq X : |X'|=m\}$ into $2^k$ components $S_A$ for each $A\subseteq\{1,2,\dots,k\}$ by
$\{x_1, \dots, x_m\} \in S_A \iff x_1 \prec \cdots \prec x_m \text{ and } A = \{i : \mathcal{M} \models \phi_i (x_1, \dots, x_m)\}$.
By Infinite Ramsey's Theorem, there is an infinite subset $Y\subseteq X$ such that each element of $Y^{(m)} = \{Y'\subseteq Y : |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 $\mathcal{M}$, 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,\dots, k$ and any pair of chains $i_1 < \cdots < i_n$ and $j_1 < \cdots < j_n$ in $I_\Delta$, we thus have:
$\mathcal{M}\models \phi_h (y_{f(i_1)}, \dots, y_{f(i_n)})$ iff $h \in A$ iff $\mathcal{M}\models \phi_h (y_{f(j_1)}, \dots, y_{f(j_n)})$
and hence
$\mathcal{M}\models \phi_h (y_{f(i_1)}, \dots, y_{f(i_n)}) \longleftrightarrow \phi_h (y_{f(j_1)}, \dots, y_{f(j_n)})$
So, if we interpret each $c_i$ for $i\in I_\Delta$ as $y_{f(i)}$, we will have $\mathcal{M}\models \psi_h$ for each $h=1,\dots,k$.


Thus, we have shown that $\mathcal{M}$ can be extended to an $\mathcal{L}^*$-structure which models $\Delta$.


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


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


Let $\mathcal{N}$ be any model of $T^*$.

Let $n_i$ be the interpretation of $c_i$ in $\mathcal{N}$ for each $i\in I$.

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


$\blacksquare$