Indiscernibles and Ehrenfeucht-Mostowski Models

Intuition Beginner

The previous unit built one enormous world that refuses no consistent request. This unit does the opposite kind of work: it builds a world to order, with exactly the shape you ask for, out of a single cheap part — a row of interchangeable elements.

Picture a long line of residents, one at each position along a ruler, so alike that no question phrased in the language can tell two increasing selections of them apart. Pick any three of them in increasing order; pick any other three in increasing order; from inside the world the two triples read identically. Only how many you picked, and in what order along the ruler, can ever matter — never which ones. Residents like these are called indiscernible.

Why is a row of interchangeable elements useful? Because the line of positions carries its own symmetries — you can slide the ruler, flip it, rearrange it — and every such symmetry of the line becomes a symmetry of the whole world built on top of it. So if you want a world with a great deal of symmetry, lay down a highly symmetric line of indiscernibles and close it off under the operations of the language. If you want a world of a chosen size that still shows only a handful of distinct behaviours, a row of interchangeable elements gives you exactly that: many elements, few genuinely different patterns.

The one ingredient that makes the row exist is a counting argument. Take any long-enough row of ordinary elements and sort their increasing selections by what they look like from inside. A stretching version of the pigeonhole principle — Ramsey's theorem — guarantees a perfectly uniform sub-row hiding inside. From there you can stretch that uniform sub-row to any length you like. Interchangeable elements are the raw material; the counting argument is the mine that always yields them.

Visual Beginner

The picture shows a row of interchangeable elements along a ruler, and how a symmetry of the ruler carries up to a symmetry of the world built on top of it.

   A ROW OF INTERCHANGEABLE ELEMENTS (indiscernibles)

   position:   1     2     3     4     5     6     ...
   resident:   a1    a2    a3    a4    a5    a6    ...

   pick increasing triple (a1, a3, a5)  --> reads as PATTERN P
   pick increasing triple (a2, a4, a6)  --> reads as PATTERN P
        same length, same order  ==>  same pattern from inside
        only HOW MANY and IN WHAT ORDER can matter, never WHICH

   SLIDE / REARRANGE THE RULER  ==>  symmetry of the whole world

   ruler symmetry:   1->2, 2->3, 3->4, ...   (shift right)
   lifts to:         a1->a2, a2->a3, ...      a symmetry of the world

word	plain meaning	what it buys you
indiscernible row	increasing selections of equal length read alike	one cheap interchangeable part
EM-pattern	the single look shared by all increasing $n$-selections	few distinct behaviours
symmetry transfer	a rearrangement of the ruler lifts to the world	many self-symmetries
build to order	choose the ruler, get a matching world	a world made to spec

Read it as a recipe: lay a row of interchangeable elements along a ruler, close off under the language, and the ruler's symmetries become the world's.

Worked example Beginner

We test two ordered worlds to see whether their elements form an interchangeable row, using the rational numbers in their order and the whole numbers with the "next number" operation.

Step 1. Take the rationals in order and pick the increasing triple $1,2,3$. The only thing a betweenness question can report is the order pattern: first below second below third, and between any two there is room for more. Now pick another increasing triple, $5,8,20$. Ask the same betweenness questions. The answers match exactly: first below second below third, room between each pair.

Step 2. Try any increasing triple at all in the rationals — $1/2,7,100$, or $-4,0,9$. Every increasing triple reports the same order pattern, because the order is dense and has no special marked points. So increasing triples are interchangeable: only the count three and the increasing order matter, never which rationals you chose.

Step 3. Now take the whole numbers $0,1,2,3,\dots$ with the operation "next number." Pick the increasing pair $0,1$. Here a question can ask "is the second the next number after the first?" and the answer is yes.

Step 4. Pick a different increasing pair, $0,5$. Ask the same question: "is the second the next number after the first?" Now the answer is no — there are four numbers in between. The two increasing pairs report different answers, so they are not interchangeable.

Step 5. Contrast. In the rationals every increasing triple read alike, so they form an interchangeable row. In the whole numbers with "next number," two increasing pairs read differently, so they do not.

What this tells us: a row is interchangeable when every increasing selection of the same length reports the same answers. The dense rationals pass; the whole numbers with a "next" operation fail, because that operation marks out who is adjacent to whom. The single test — do equal-length increasing selections read alike? — is exactly what makes a row indiscernible.

Check your understanding Beginner

Formal definition Intermediate+

Work in a monster model $\mathfrak{C}\models T$ for a complete theory $T$ with infinite models; "type" means complete type over a small parameter set in the sense of 42.02.04 pending, and $A$ denotes a small parameter set throughout.

Let $(I,<)$ be a linear order and $({\bar{a}}_i{)}_{i\in I}$ a sequence of tuples (all of the same length) from $\mathfrak{C}$. The sequence is order-indiscernible over $A$ when for every $n$ and any two strictly increasing index tuples $i_1<\cdots <i_n$ and $j_1<\cdots <j_n$ from $I$, $$ \operatorname{tp}(\bar a_{i_1}, \dots, \bar a_{i_n} / A) = \operatorname{tp}(\bar a_{j_1}, \dots, \bar a_{j_n} / A), $$ equivalently $\mathfrak{C}\models \phi ({\bar{a}}_{i_1},\dots ,{\bar{a}}_{i_n})\leftrightarrow \phi ({\bar{a}}_{j_1},\dots ,{\bar{a}}_{j_n})$ for every ${\mathcal{L}}_A$-formula $\phi$. For each $n$ the common type of increasing $n$-tuples is a complete type $p_n\in S_n(A)$; the family $\Phi =(p_n{)}_{n<\omega }$ is the Ehrenfeucht-Mostowski type (EM-type) of the sequence, and it determines the sequence's behaviour entirely ^{[Marker Ch. 5]}. The sequence is totally indiscernible (a set-indiscernible sequence) when the equal-type condition holds for all injective index tuples, regardless of their order; equivalently it is order-indiscernible and invariant under transpositions of adjacent indices.

A formula $\phi ({\bar{x}}_1,\dots ,{\bar{x}}_n)$ is consistent with the EM-type $\Phi$ when $\phi \in p_n$. An EM-type $\Phi$ is consistent when it is realized by some order-indiscernible sequence in some model of $T$ — equivalently, when the set of formulas it prescribes is finitely satisfiable, so that compactness produces an indexed indiscernible sequence of any prescribed order type.

To build models from indiscernibles one needs hulls that are elementary. Expand $\mathcal{L}$ to ${\mathcal{L}}^{\mathrm{Sk}}$ by adding, for each formula $\phi (x,\bar{y})$, a Skolem function $f_{\phi }$ with the axiom $\exists x\phi (x,\bar{y})\to \phi (f_{\phi }(\bar{y}),\bar{y})$. The Skolemization $T^{\mathrm{Sk}}$ is a theory of size $|T|+{\aleph }_0$ whose models expand models of $T$, and in which the Tarski-Vaught test is satisfied automatically: every substructure closed under the $f_{\phi }$ is an elementary substructure. The Skolem hull $\mathrm{Sk}(X)$ of a set $X$ is the closure of $X$ under all the $f_{\phi }$, an elementary submodel of cardinality $|X|+|T|$ ^{[Marker Ch. 5]}.

Counterexamples to common slips Intermediate+

• "Order-indiscernible means totally indiscernible." The ordered rationals $(\mathbb{Q},<)$ as a sequence indexed by themselves are order-indiscernible but not set-indiscernible: the formula $x<y$ distinguishes the increasing pair $(a_1,a_2)$ from the decreasing pair $(a_2,a_1)$. Total indiscernibility is strictly stronger and, by a theorem below, characterizes stable theories.

• "Any infinite sequence is already indiscernible after passing to a subsequence inside the same model." Ramsey's theorem yields an indiscernible sub-sequence only for finitely many formulas at a time; to make a single sequence indiscernible for all formulas one passes to an elementary extension and uses compactness. Inside a fixed model only the finitary version is available.

• "Indiscernibles are pairwise equal or conjugate by an automorphism fixing the rest." Indiscernible elements are interchangeable for the language, but they are genuinely distinct objects; the automorphisms induced come from order-automorphisms of the index $I$, not from arbitrary permutations, unless the sequence is totally indiscernible.

Key theorem with proof Intermediate+

The structural payoff is that indiscernibles can always be extracted: any infinite sequence, however irregular, hides an indiscernible sequence realizing the same finite patterns, and that sequence can be stretched to any length. This is the standard lemma on which the Ehrenfeucht-Mostowski construction rests, and Ramsey's theorem (40.05.04) is its combinatorial engine.

Theorem (Extraction of indiscernibles — the standard lemma). Let $({\bar{b}}_i{)}_{i<\omega }$ be an infinite sequence of tuples in $\mathfrak{C}$ and $(I,<)$ any infinite linear order. Then there is a sequence $({\bar{a}}_i{)}_{i\in I}$, order-indiscernible over $\varnothing$, such that every EM-type formula of $({\bar{a}}_i)$ already holds of some increasing tuple of the $({\bar{b}}_i)$; that is, $({\bar{a}}_i)$ is finitely satisfiable in $\{{\bar{b}}_i:i<\omega \}$ ^{[Tent-Ziegler Ch. 5]}.

Proof. Fix an enumeration of all $\mathcal{L}$-formulas. For each $n$, the map sending an increasing tuple $i_1<\cdots <i_n$ from $\omega$ to the set of formulas $\phi ({\bar{x}}_1,\dots ,{\bar{x}}_n)$ with $\mathfrak{C}\models \phi ({\bar{b}}_{i_1},\dots ,{\bar{b}}_{i_n})$ — its quantifier-free-over-formulas type — is a colouring of the increasing $n$-tuples of $\omega$ by the (at most $2^{|T|}$, but for each finite set of formulas finitely many) possible types. Working with one finite set of formulas $F$ at a time, this is a finite colouring of $[\omega {]}^n$, and the infinite Ramsey theorem (40.05.04) yields an infinite $H_F^n\subseteq \omega$ homogeneous for it: all increasing $n$-tuples from $H_F^n$ agree on the formulas in $F$.

Intersecting over the countably many pairs $(n,F)$ by a diagonal argument — enumerate the pairs and pass to a decreasing chain of infinite homogeneous sets, taking a pseudo-intersection $H$ that is almost contained in each — produces a single infinite $H\subseteq \omega$ such that increasing tuples from $H$ of each length agree on every formula. The subsequence $({\bar{b}}_i{)}_{i\in H}$ is therefore order-indiscernible over $\varnothing$, with a well-defined EM-type $\Phi$, and each $p_n\in \Phi$ is realized by an increasing $n$-tuple of the original $\bar{b}$'s.

Now stretch. Introduce new constant tuples $({\bar{c}}_i{)}_{i\in I}$ and the theory $$ \Sigma = \operatorname{ElDiag}(\mathfrak{C}) \cup {, \varphi(\bar c_{i_1}, \dots, \bar c_{i_n}) : i_1 < \dots < i_n \text{ in } I,\ \varphi \in p_n ,}. $$ Every finite subset of $\Sigma$ mentions finitely many of the ${\bar{c}}_i$ and finitely many formulas; mapping those $\bar{c}$'s order-preservingly to a matching increasing tuple from $H$ satisfies it, since increasing tuples from $H$ realize each $p_n$. By compactness $\Sigma$ has a model, which we may take to be an elementary extension of $\mathfrak{C}$; the interpretations of the ${\bar{c}}_i$ form the required order-indiscernible $({\bar{a}}_i{)}_{i\in I}$, finitely satisfiable in the $\bar{b}$'s. $\square$

Bridge. The extraction lemma is the foundational reason a theory with infinite models can be built to order: it converts the brute existence of one infinite sequence into a perfectly uniform sequence of any prescribed length, and uniformity is exactly what a construction-to-spec needs. It builds toward the Ehrenfeucht-Mostowski theorem of the Advanced tier, where the extracted indiscernibles become the generators of a Skolem hull whose automorphisms are read off the index order, and it appears again in the forking calculus of 42.02.07 pending, where the same Ramsey-plus-compactness extraction produces the indiscernible sequences that witness dividing. This is exactly the pigeonhole principle of 40.05.04 lifted from a single partition to a simultaneous uniformization over all formulas and all lengths, and it generalises the back-and-forth realization of 42.02.04 pending from "realize one type" to "realize a coherent family of types along an entire order." Putting these together, the central insight is that Ramsey's theorem manufactures symmetry where there was none, and the bridge is that this manufactured symmetry, transported through a Skolem hull, becomes the automorphism group of a model made to specification.

Exercises Intermediate+

Advanced results Master

Indiscernibles organize four developments: the Ehrenfeucht-Mostowski theorem and its functor, the applications to models with few types and large automorphism groups and to omitting types in large cardinality, the stability-theoretic identity of order-indiscernible with set-indiscernible sequences, and the non-structure machinery in which the EM-functor produces many non-isomorphic models.

Theorem 1 (Ehrenfeucht-Mostowski). For complete $T$ with infinite models and any linear order $(I,<)$, there is a model $M(I)\models T$, generated as a Skolem hull $M(I)=\mathrm{Sk}(({\bar{a}}_i{)}_{i\in I})$ by an order-indiscernible sequence with a prescribed consistent EM-type $\Phi$, such that $|M(I)|=|I|+|T|$, $M(I)$ realizes at most $|I|+|T|$ complete types over $\varnothing$, and every order-automorphism of $I$ extends uniquely to an automorphism of $M(I)$, giving an embedding $\mathrm{Aut}(I)\hookrightarrow \mathrm{Aut}(M(I))$ ^{[Ehrenfeucht and Mostowski 1956]}. The assignment $I\mapsto M(I)$ is a functor from the category of linear orders and order-embeddings to models of $T$ and elementary embeddings — the Ehrenfeucht-Mostowski functor — natural in $I$: an order-embedding $I\hookrightarrow I^{\prime }$ induces $M(I)⪯M(I^{\prime })$. Fixing $\Phi$ once and varying $I$ produces, in a single uniform stroke, a model of every infinite cardinality whose first-order behaviour is governed by the one EM-type.

Theorem 2 (few types, large automorphism groups, omitting types). Three applications follow by choosing $I$ and $\Phi$ ^{[Marker Ch. 5]}. Few types: since every element of $M(I)$ is a Skolem term in finitely many indiscernibles and order-indiscernibility collapses the index choice, $M(I)$ realizes at most $|T|+{\aleph }_0$ types over $\varnothing$ in every cardinality — the input to the Hanf number computation (the threshold past which a property persisting up to some cardinal persists in all larger ones) and to two-cardinal theorems of the form $(\kappa ,\lambda )\to ({\kappa }^{\prime },{\lambda }^{\prime })$, where a model of size $\kappa$ with a definable subset of size $\lambda$ is transferred to other cardinal pairs by stretching the indiscernibles while pinning a definable set to a sub-order. Large automorphism groups: taking $I=\mathbb{Q}$ or any order with rich $\mathrm{Aut}(I)$ yields $M(I)$ with $\mathrm{Aut}(I)\hookrightarrow \mathrm{Aut}(M(I))$, so a theory with an infinite model has models with automorphism groups of arbitrary size, while a rigid order $I$ (no nontrivial order-automorphisms) yields a comparatively rigid $M(I)$. Omitting types: choosing $\Phi$ to avoid the approximations isolating a non-isolated type $p$ makes $M(I)$ omit $p$, and it does so in every cardinality — strengthening the Omitting Types Theorem of 42.02.04 pending, whose Henkin construction omits a type only in a countable model, to omission in arbitrarily large models.

Theorem 3 (the stability dichotomy: order-indiscernible vs. set-indiscernible). $T$ is stable iff no formula has the order property iff every order-indiscernible sequence is totally indiscernible ^{[Tent-Ziegler Ch. 7]}. In a stable theory the index order is invisible to the language: an order-indiscernible sequence is an indiscernible set, and the average type $\mathrm{Av}(I/B)$ — the set of ${\mathcal{L}}_B$-formulas satisfied by cofinitely many members of the indiscernible set $I$ — is a complete, well-defined type over any $B$, used to construct nonforking extensions. A Morley sequence in a type $p$ over $A$ is an $A$-indiscernible sequence of realizations of $p$ each independent (nonforking, 42.02.07 pending) from its predecessors; Morley sequences witness dividing — a formula $\delta (\bar{x},\bar{b})$ divides over $A$ exactly when, along an $A$-indiscernible sequence $({\bar{b}}_i)$ with ${\bar{b}}_0=\bar{b}$, the set $\{\delta (\bar{x},{\bar{b}}_i)\}$ is $k$-inconsistent — so indiscernibles are the combinatorial substrate of forking. The dichotomy is the precise sense in which stability is the absence of a definable order on indiscernibles.

Theorem 4 (the Ehrenfeucht-Mostowski functor and non-structure). When $T$ is unstable the EM-functor manufactures many non-isomorphic models ^[Shelah]. From an order property one builds, for each linear order $I$, a model $M(I)$ encoding the order type of $I$ in its first-order data — different $I$ with the same cardinality but non-isomorphic as orders (and there are $2^{\kappa }$ pairwise non-embeddable orders of size $\kappa$) yield $2^{\kappa }$ pairwise non-isomorphic models $M(I)$ of size $\kappa$. This is the non-structure half of Shelah's main-gap dichotomy: an unstable theory, or a stable theory failing the deeper dividing lines NDOP/NOTOP, has the maximum number $2^{\kappa }$ of models in every uncountable $\kappa$, the order being read off the indiscernible skeleton, while a theory on the structure side decomposes its models into independent trees of indiscernible-based components counted by dimension invariants. The EM-functor is thus the engine on both sides: it builds few-type structured models when $\Phi$ is chosen tame, and it codes orders into many models when the order property is present.

Synthesis. Indiscernibles are the foundational reason model theory can build models to specification, and putting these together they thread all four developments through one principle — a row of interchangeable elements transports the combinatorics of its index order into the model. This is exactly what Theorem 1 makes precise: the Skolem hull of an order-indiscernible sequence realizes the EM-type's few types and inherits $\mathrm{Aut}(I)$, so the index order's size, symmetry, and rigidity become the model's, and the central insight is that Ramsey-manufactured uniformity (the standard lemma) plus Skolem-hull elementarity converts a single infinite sequence into a functor on linear orders. Theorem 2 is the immediate dividend and is dual to the omitting/realizing axis of 42.02.04 pending: where the monster realizes maximally, the EM-model realizes minimally — few types, a prescribed omission — in every cardinality, and the Hanf number and two-cardinal theorems are this minimality stretched across the cardinal scale.

Theorem 3 is the bridge from the construction to the structure theory of 42.02.07 pending: stability is exactly the collapse of order-indiscernible to set-indiscernible, so the order the EM-functor exploits is invisible precisely when the theory is stable, and the average type of an indiscernible set and the Morley sequences that witness dividing are the stable-theory residue of the indiscernible machinery. This is exactly why Theorem 4's non-structure works only on the unstable side: an order property is a definable order on indiscernibles, and the EM-functor codes $2^{\kappa }$ order types into $2^{\kappa }$ models, generalising the single Ehrenfeucht-Mostowski model into Shelah's many-models theorem. The whole apparatus is dual to the saturated-model theory of 42.02.04 pending — saturation realizes every consistent demand to make one canonical large model, indiscernibility realizes a single uniform pattern to make a tunable family of models — and it is the substrate on which categoricity (42.02.06 pending) and the forking geometry of 42.02.07 pending are built, the combinatorial heart of stability theory.

Full proof set Master

Proposition 1 (existence of indiscernibles of any order type from a consistent EM-type). If an EM-type $\Phi =(p_n{)}_{n<\omega }$ is consistent — realized by some infinite order-indiscernible sequence — then for every linear order $(I,<)$ there is an order-indiscernible sequence $({\bar{a}}_i{)}_{i\in I}$ with EM-type $\Phi$.

Proof. Introduce constant tuples $({\bar{c}}_i{)}_{i\in I}$ and let $\Sigma =T\cup \{\phi ({\bar{c}}_{i_1},\dots ,{\bar{c}}_{i_n}):i_1<\cdots <i_n\text{ in }I,\phi \in p_n,n<\omega \}$. A finite subset ${\Sigma }_0$ mentions finitely many constants ${\bar{c}}_{i_1},\dots ,{\bar{c}}_{i_m}$ (say in increasing index order) and finitely many formulas, all drawn from the various $p_n$. In a model carrying an infinite indiscernible sequence of EM-type $\Phi$, choose any increasing $m$-tuple of its elements and interpret ${\bar{c}}_{i_1},\dots ,{\bar{c}}_{i_m}$ by it; every formula of ${\Sigma }_0$ holds because it lies in the corresponding $p_n$ and increasing tuples realize $p_n$. So ${\Sigma }_0$ is satisfiable, and by compactness (42.02.04 pending's ambient framework) $\Sigma$ has a model; the ${\bar{c}}_i$ realize an order-indiscernible $({\bar{a}}_i{)}_{i\in I}$ with EM-type $\Phi$. $\square$

Proposition 2 (Skolem hulls are elementary; cardinality bound). In $T^{\mathrm{Sk}}$, for any $X$ the Skolem hull $\mathrm{Sk}(X)$ is an elementary substructure with $|\mathrm{Sk}(X)|=|X|+|T|$.

Proof. Elementarity is the Tarski-Vaught test: if $\exists x\phi (x,\bar{b})$ holds with $\bar{b}$ from $\mathrm{Sk}(X)$, the Skolem axiom gives the witness $f_{\phi }(\bar{b})\in \mathrm{Sk}(X)$ by closure under $f_{\phi }$, so a witness lies in the hull and $\mathrm{Sk}(X)⪯N$. Cardinality: $\mathrm{Sk}(X)$ is the set of values $t(\bar{x})$ of ${\mathcal{L}}^{\mathrm{Sk}}$-terms on tuples from $X$; there are $|X|+|T|+{\aleph }_0=|X|+|T|$ terms (the language ${\mathcal{L}}^{\mathrm{Sk}}$ has size $|T|+{\aleph }_0$ and each term uses finitely many variables), so $|\mathrm{Sk}(X)|\le |X|+|T|$, and $\ge |X|$ since $X\subseteq \mathrm{Sk}(X)$. $\square$

Proposition 3 (the Ehrenfeucht-Mostowski model: few types and induced automorphisms). Let $({\bar{a}}_i{)}_{i\in I}$ be order-indiscernible (in $T^{\mathrm{Sk}}$) with EM-type $\Phi$ and $M(I)=\mathrm{Sk}(({\bar{a}}_i{)}_{i\in I})$. Then $|M(I)|=|I|+|T|$, $M(I)$ realizes at most $|I|+|T|$ types over $\varnothing$, and $\mathrm{Aut}(I)\hookrightarrow \mathrm{Aut}(M(I))$.

Proof. Cardinality is Proposition 2 with $X=\{{\bar{a}}_i\}$. Each element of $M(I)$ is $t({\bar{a}}_{i_1},\dots ,{\bar{a}}_{i_n})$ for an ${\mathcal{L}}^{\mathrm{Sk}}$-term $t$ and increasing indices; by order-indiscernibility the type of $t({\bar{a}}_{i_1},\dots ,{\bar{a}}_{i_n})$ over $\varnothing$ depends only on $(t,n)$ and the EM-type $\Phi$, not on the chosen indices, so the number of realized $1$-types is at most the number of pairs $(t,n)$, namely $|T|+{\aleph }_0\le |I|+|T|$. For automorphisms: given $\sigma \in \mathrm{Aut}(I)$, the map ${\bar{a}}_i\mapsto {\bar{a}}_{\sigma (i)}$ is partial elementary (Exercise 5), and it extends to the hull by $t({\bar{a}}_{i_1},\dots ,{\bar{a}}_{i_n})\mapsto t({\bar{a}}_{\sigma (i_1)},\dots ,{\bar{a}}_{\sigma (i_n)})$. This is well defined and bijective because Skolem terms are honest functions and $\sigma$ is a bijection preserving order (hence sending increasing tuples to increasing tuples), and it preserves all formulas by indiscernibility, so it is an automorphism $\hat{\sigma }$ of $M(I)$. The assignment $\sigma \mapsto \hat{\sigma }$ is an injective homomorphism since distinct $\sigma$ move some ${\bar{a}}_i$ differently. $\square$

Proposition 4 (omitting a type in arbitrarily large cardinality). Let $p(\bar{x})$ be a type not realized in some model of $T$. There is a consistent EM-type $\Phi$ such that for every infinite $I$ the model $M(I)$ omits $p$.

Proof. Pass to $T^{\mathrm{Sk}}$ and a model $N$ omitting $p$ (a Skolemization of a $p$-omitting model still omits $p$ on the home sort, as Skolem functions add no realizations of an $\mathcal{L}$-type the reduct lacks). Inside $N$ take any infinite sequence and extract (standard lemma) an order-indiscernible sequence with some EM-type $\Phi$, finitely satisfiable in $N$. Every element of $M(I)=\mathrm{Sk}(({\bar{a}}_i{)}_{i\in I})$ is a Skolem term in the indiscernibles, and by order-indiscernibility the $\mathcal{L}$-type over $\varnothing$ of any tuple of such terms equals the type realized by the corresponding terms applied to an increasing tuple inside $N$ — a tuple whose type is realized in $N$, hence not equal to $p$. So no tuple of $M(I)$ realizes $p$: $M(I)$ omits $p$ in cardinality $|I|+|T|$, for every infinite $I$. $\square$

Proposition 5 (stability $\Rightarrow$ order-indiscernible is set-indiscernible). If $T$ is stable, every order-indiscernible sequence is totally indiscernible.

Proof. Suppose not: some order-indiscernible $({\bar{a}}_i{)}_{i\in I}$ over $A$ and some formula $\psi (\bar{x},\bar{y})$ distinguish an increasing pair from its transposition, so (by indiscernibility, this holds uniformly) $\models \psi ({\bar{a}}_i,{\bar{a}}_j)$ for all $i<j$ while $/\models \psi ({\bar{a}}_i,{\bar{a}}_j)$ for some — hence all, by indiscernibility — $i>j$. Then $\psi$ defines a linear order on the infinite indiscernible sequence: $\models \psi ({\bar{a}}_i,{\bar{a}}_j)\leftrightarrow i<j$. Over the parameter set $\{{\bar{a}}_i:i<\lambda \}$ the cuts of this order give $2^{\lambda }$ distinct types (the type recording, for each $i$, whether $\psi ({\bar{a}}_i,\bar{x})$ or $\psi (\bar{x},{\bar{a}}_i)$), so $|S(\cdot )|\ge 2^{\lambda }>\lambda$, exhibiting the order property and contradicting stability (42.02.07 pending). Hence no such $\psi$ exists and the sequence is totally indiscernible. $\square$

Proposition 6 (Morley sequences witness dividing). In a stable theory, a formula $\delta (\bar{x},\bar{b})$ divides over $A$ iff for some (equivalently every) $A$-indiscernible sequence $({\bar{b}}_i{)}_{i<\omega }$ with ${\bar{b}}_0=\bar{b}$, the set $\{\delta (\bar{x},{\bar{b}}_i):i<\omega \}$ is $k$-inconsistent for some $k$.

Proof sketch. ($\Leftarrow$) If some $A$-indiscernible $({\bar{b}}_i)$ with ${\bar{b}}_0=\bar{b}$ has $\{\delta (\bar{x},{\bar{b}}_i)\}$ $k$-inconsistent, that is the definition of dividing. ($\Rightarrow$) If $\delta (\bar{x},\bar{b})$ divides, by definition there is an $A$-indiscernible sequence $({\bar{b}}_i)$ with ${\bar{b}}_0=\bar{b}$ and $\{\delta (\bar{x},{\bar{b}}_i)\}$ $k$-inconsistent. To pass to every such sequence, use the standard lemma to extract from any given $A$-indiscernible sequence starting at $\bar{b}$ an $A$-indiscernible sequence finitely satisfiable in it; $k$-inconsistency of a finite subset is a first-order condition transferred by finite satisfiability, and in a stable theory the average type of an indiscernible set is well defined (Proposition 5), so the dividing witnessed on one Morley sequence transfers to all. Thus dividing is detected on any $A$-indiscernible sequence through $\bar{b}$, which is the role indiscernibles play in the forking calculus of 42.02.07 pending. $\square$

Connections Master

• Saturation, homogeneity, and monster models 42.02.04 pending is the realizing dual this unit inverts and the ambient framework it works inside. There a single saturated world realizes every consistent demand; here the Skolem hull of an indiscernible row realizes a single prescribed pattern, building a tunable family of models with few types rather than one canonical large one. The monster model supplies the universe in which extraction and compactness operate, and the strong homogeneity of 42.02.04 pending — types as $\mathrm{Aut}(\mathfrak{C}/A)$-orbits — is what makes the induced map $\mathrm{Aut}(I)\hookrightarrow \mathrm{Aut}(M(I))$ a statement about genuine automorphisms; the omitting-types application here strengthens the countable omission of that unit's setting to omission in every cardinality.

• Ramsey's theorem and Ramsey numbers 40.05.04 is the combinatorial engine of the extraction lemma. The infinite Ramsey theorem on partitions of $[\omega {]}^n$ supplies, for each finite length and finite set of formulas, the homogeneous subset on which all increasing tuples agree; the diagonalization over lengths and formulas and the compactness stretch are layered on top, but the irreducible source of the uniformity is the pigeonhole-stretched-to-tuples that Ramsey's theorem provides. Without it there is no way to manufacture an indiscernible sequence from an arbitrary infinite one, so the entire Ehrenfeucht-Mostowski apparatus rests on that combinatorial input.

• Types and the omitting types theorem 42.02.03 pending provides the Stone space of types in which an EM-type lives as a coherent family $(p_n{)}_n$ and the omission machinery this unit lifts to large cardinality. The isolated/non-isolated dichotomy of that unit is what makes the omitting-types application nontrivial: the EM-type is chosen to avoid the formulas approximating a non-isolated $p$, and the Skolem-hull construction then omits $p$ where that unit's Henkin construction could only omit it countably; the average type of an indiscernible set is a particular point of the type space singled out by the indiscernible structure.

• Strongly minimal sets, Morley rank, and stability 42.02.07 pending is where indiscernibles become the combinatorial heart of the structure theory. The stability dichotomy — order-indiscernible equals set-indiscernible exactly when $T$ is stable — is the precise sense in which stability is the absence of a definable order on indiscernibles, and Morley sequences (indiscernible sequences of nonforking realizations) witness dividing, so the forking independence relation of that unit is defined through the indiscernible sequences extracted here. The order property that separates stable from unstable is literally a definable linear order on an indiscernible sequence, the same order the Ehrenfeucht-Mostowski functor codes into many models on the non-structure side.

Historical & philosophical context Master

The construction originates in Andrzej Ehrenfeucht and Andrzej Mostowski's 1956 paper "Models of axiomatic theories admitting automorphisms," which proved that every first-order theory with an infinite model has, for each linear order $(I,<)$, a model generated by an order-indiscernible family indexed by $I$ in which every order-automorphism of $I$ is induced by an automorphism of the model ^{[Ehrenfeucht and Mostowski 1956]}. Their argument assembled three ingredients that became standard technique: Skolem functions (Thoralf Skolem's device, repurposed so that hulls are elementary), Frank Ramsey's 1930 partition theorem to extract a uniform sub-sequence, and the compactness theorem to stretch it to arbitrary order types. The immediate consequence — theories with infinite models have models with arbitrarily large automorphism groups and models of every cardinality realizing few types — answered a question about automorphisms and supplied a tool that Michael Morley used in his 1965 categoricity theorem and that fed the Hanf-number and two-cardinal results of the following decade.

The technique entered the centre of classification theory through Saharon Shelah, for whom the Ehrenfeucht-Mostowski functor $I\mapsto M(I)$ and the dichotomy between order-indiscernible and totally indiscernible sequences became load-bearing: a theory is stable exactly when order-indiscernible sequences are indiscernible sets, and an unstable theory's order property lets the functor code $2^{\kappa }$ linear orders into $2^{\kappa }$ non-isomorphic models, the non-structure half of the main gap ^[Shelah]. The systematic treatment of average types, Morley sequences, and the role of indiscernibles in the forking calculus is due to Shelah and is presented in the modern texts of Tent and Ziegler and of Marker ^{[Marker Ch. 5]}. A separate strand runs into set theory: indiscernibles for the constructible universe $L$, packaged as the set $0^{\#}$ of Jack Silver and Robert Solovay, are the model-theoretic shadow of measurable cardinals, so the Ehrenfeucht-Mostowski idea reappears at the foundation of large-cardinal combinatorics.

Bibliography Master

@book{marker2002modeltheory,
  author    = {Marker, David},
  title     = {Model Theory: An Introduction},
  series    = {Graduate Texts in Mathematics},
  volume    = {217},
  publisher = {Springer},
  year      = {2002}
}

@book{tentziegler2012,
  author    = {Tent, Katrin and Ziegler, Martin},
  title     = {A Course in Model Theory},
  series    = {Lecture Notes in Logic},
  volume    = {40},
  publisher = {Association for Symbolic Logic and Cambridge University Press},
  year      = {2012}
}

@book{changkeisler1990,
  author    = {Chang, Chen Chung and Keisler, H. Jerome},
  title     = {Model Theory},
  edition   = {3},
  series    = {Studies in Logic and the Foundations of Mathematics},
  volume    = {73},
  publisher = {North-Holland},
  year      = {1990}
}

@book{shelah1990classification,
  author    = {Shelah, Saharon},
  title     = {Classification Theory and the Number of Non-Isomorphic Models},
  edition   = {2},
  series    = {Studies in Logic and the Foundations of Mathematics},
  volume    = {92},
  publisher = {North-Holland},
  year      = {1990}
}

@article{ehrenfeuchtmostowski1956,
  author  = {Ehrenfeucht, Andrzej and Mostowski, Andrzej},
  title   = {Models of axiomatic theories admitting automorphisms},
  journal = {Fundamenta Mathematicae},
  volume  = {43},
  year    = {1956},
  pages   = {50--68}
}

@article{ramsey1930,
  author  = {Ramsey, Frank P.},
  title   = {On a problem of formal logic},
  journal = {Proceedings of the London Mathematical Society},
  volume  = {30},
  year    = {1930},
  pages   = {264--286}
}

@article{morley1965categoricity,
  author  = {Morley, Michael},
  title   = {Categoricity in power},
  journal = {Transactions of the American Mathematical Society},
  volume  = {114},
  year    = {1965},
  pages   = {514--538}
}