Roughly speaking, an indiscernible sequence is an infinite sequence of elements which is very homogeneous, in the sense that

Any two elements have the same type
More generally, any two subsequences of the same length have the same type.

Definitions[]

Fix some structure M. A sequence

$a_{1},a_{2},\ldots$

of elements of M (or more generally, tuples from M) is said to be indiscernible if any two subsequences of the same length have the same type, i.e., if

${\text{tp}}(a_{i_{1}}a_{i_{2}}\cdots a_{i_{n}}/\emptyset )={\text{tp}}(a_{j_{1}}a_{j_{2}}\cdots a_{j_{n}}/\emptyset )$

for any

$i_{1}<i_{2}<\cdots <i_{n}<\omega$

and

$j_{1}<j_{2}<\cdots <j_{n}<\omega$ .

(Here, we are using the standard notational abbreviation in which concatenation of tuples is written multiplicatively.)

More generally, if A ⊆ M is some subset, we say that $a_{1},a_{2},\ldots$ is A-indiscernible if it is indiscernible after naming the elements of A, or equivalently, if

${\text{tp}}(a_{i_{1}}a_{i_{2}}\cdots a_{i_{n}}/A)={\text{tp}}(a_{j_{1}}a_{j_{2}}\cdots a_{j_{n}}/A)$

for any

$i_{1}<i_{2}<\cdots <i_{n}<\omega$

and

$j_{1}<j_{2}<\cdots <j_{n}<\omega$ .

More generally, we can allow the sequence of $a_{i}$ 's to have length other than $\omega$ . For any infinite totally ordered set $(I,<)$ , a sequence $\{a_{i}\}_{i\in I}$ is A-indiscernible if

${\text{tp}}(a_{i_{1}}a_{i_{2}}\cdots a_{i_{n}}/A)={\text{tp}}(a_{j_{1}}a_{j_{2}}\cdots a_{j_{n}}/A)$

for any

$i_{1}<i_{2}<\cdots <i_{n}$

and

$j_{1}<j_{2}<\cdots <j_{n}$

in I. Again, this just means that any two subsequences of the same length have the same type (over A).

Remark: In the case n = 1, the definition of "A-indiscernible" implies that for any i = i₁ and any j = j₁, tp(a_i/A) = tp(a_j/A). In other words, any two elements of an indiscernible sequence must have the same type. However, the condition of indiscernibility is much stronger than this. For example, it also implies that

$a_{i}a_{i+1}\equiv _{A}a_{j}a_{j+1}$ , i.e., the type of any two consecutive pairs is the same.
$a_{1}a_{2}a_{3}\cdots \equiv _{A}a_{2}a_{3}a_{4}\cdots$ , i.e., we can shift the entire sequence to the left and its type doesn't change. (To verify this statement, it suffices to show that ${\text{tp}}(a_{i_{1}}\cdots a_{i_{n}}/A)={\text{tp}}(a_{i_{1}+1}\cdots a_{i_{n}+1}/A)$ for each $i_{1}<\cdots <i_{n}$ . This is clear from the definition of indiscernibility.)
$a_{1}a_{2}a_{3}\cdots \equiv _{A}a_{2}a_{4}a_{6}a_{8}\cdots$ .
More generally, any infinite subsequence of an indiscernible sequence (of length $\omega$ ) has the same type as the original sequence. In fact, this condition characterizes indiscernible sequences (of length $\omega$ ), by an easy exercise.

Examples[]

Example: In the structure $(\mathbb {Q} ,<)$ (a model of DLO), any increasing sequence $a_{1}<a_{2}<\cdots$ is indiscernible. In fact, by quantifier elimination in DLO, the type of a tuple $(x_{1},x_{2},\ldots ,x_{n})$ over Ø is completely determined by the relative ordering of the $x_{i}$ 's. So if $i_{1}<\cdots <i_{n}$ and $j_{1}<\cdots <j_{n}$ , then

${\text{tp}}(a_{i_{1}}a_{i_{2}}\cdots a_{i_{n}}/\emptyset )={\text{tp}}(a_{j_{1}}a_{j_{2}}\cdots a_{j_{n}}/\emptyset )$

because both tuples $(a_{i_{1}},a_{i_{2}},\ldots ,a_{i_{n}})$ and $(a_{j_{1}},a_{j_{2}},\ldots ,a_{j_{n}})$ are strictly increasing.

Example: Consider the structure of $\mathbb {C}$ as a ring (a model of ACF). Let $t_{1},t_{2},\ldots$ be a sequence of transcendental complex numbers which are algebraically independent. (For example, $t_{1},t_{2},\ldots$ could be the beginning of an enumeration of a transcendence basis of $\mathbb {C}$ over $\mathbb {Q}$ .) Then $t_{1},t_{2},\ldots$ is indiscernible. To see this, let $i_{1}<\cdots <i_{n}$ and $j_{1}<\cdots <j_{n}$ be two increasing sequences. Then $\mathbb {Q} (t_{i_{1}},\ldots ,t_{i_{n}})\subset \mathbb {C}$ is isomorphic to the rational function field in n variables, because the $t_{i_{1}},\ldots ,t_{i_{n}}$ are algebraically independent. The same is true of $\mathbb {Q} (t_{j_{1}},\ldots ,t_{j_{n}})$ . Consequently we can get an isomorphism

$f:\mathbb {Q} (t_{i_{1}},t_{i_{2}},\ldots ,t_{i_{n}}){\stackrel {\sim }{\to }}\mathbb {Q} (t_{j_{1}},t_{j_{2}},\ldots ,t_{j_{n}})$

such that $f(t_{i_{k}})=t_{j_{k}}$ for each k. This condition is equivalent to the assertion that the two tuples in question have the same quantifier free type:

${\text{qftp}}((t_{i_{1}},\ldots ,t_{i_{n}})/\emptyset )={\text{qftp}}((t_{j_{1}},\ldots ,t_{j_{n}})/\emptyset )$ .

Then because of quantifier elimination in ACF, it follows that they actually have the same type. Consequently the sequence is indiscernible.

Non-example: Let M be the structure $(\mathbb {Z} ,s)$ , where s is a unary function symbol interpreted as s(x) = x + 1. The sequence 1, 2, 3, ... is not indiscernible in this structure. Any two elements of this sequence have the same type over Ø, and it is also true that

$(1,2,3,\ldots )\equiv _{\emptyset }(2,3,4,\ldots )$ .

Both of these facts hold because s is an automorphism of M. However, indiscernibility fails because, e.g.,

$(1,2)\not \equiv _{\emptyset }(1,3)$

Indeed, the tuple (1,3) satisfies the formula y = s(s(x)), but the tuple (1,2) does not. So they do not have the same type over the empty set, and the sequence is not indiscernible.

Totally Indiscernible Sequences[]

A sequence $\{a_{i}\}_{i\in I}$ is said to be totally indiscernible if

$a_{i_{1}}a_{i_{2}}\cdots a_{i_{n}}\equiv _{\emptyset }a_{j_{1}}a_{j_{2}}\cdots a_{j_{n}}$ ,

for any $i_{1},\ldots ,i_{n},j_{1},\ldots ,j_{n}$ , subject only to the condition that

$i_{k}\neq i_{k'}$ and $j_{k}\neq j_{k'}$ for $k\neq k'$ .

An equivalent condition is that $\{a_{i}\}_{i\in I}$ is indiscernible, and the sequence remains indiscernible after rearranging the order of the terms.

The condition for $\{a_{i}\}_{i\in I}$ to be totally indiscernible doesn't depend on the ordering of I, and is really more of a property of the set $\{a_{i}:i\in I\}$ , so the terminology indiscernible set is sometimes used in stead of "totally indiscernible sequence."

Of course we can also add a parameter set A, and speak of "totally A-indiscernible sequences," or equivalently, "A-indiscernible sets."

Example: The example of an independent sequence of transcendentals $t_{1},t_{2},\ldots$ in $\mathbb {C}$ is totally indiscernible. Indeed, any reordering of this sequence will still be an independent sequence of transcendentals, and so will remain indiscernible by the argument given above.

More generally, it turns out that in any stable theory, every indiscernible sequence is totally indiscernible. We do not prove this here.

A closely related source of totally indiscernible sequences is the Morley sequence of a generically stable type in an NIP theory.

Non-example: In the structure $(\mathbb {Q} ,\leq )$ , the sequence 1, 2, 3, ... is indiscernible, as we discussed above. However, this sequence is not totally indiscernible. For instance, the tuple (1,2) does not have the same type as (2,1), because the former satisfies the formula x < y , while the latter does not. In terms of rearranging the sequence, the sequence fails to be totally indiscernible, because the reordering

$2,1,3,4,5,\ldots$

is not indiscernible.

More generally, in a totally ordered structure, every totally indiscernible sequence must be constant. Indeed, if $a_{1},a_{2},\ldots$ is totally indiscernible, then

${\text{tp}}(a_{1}a_{2}/\emptyset )={\text{tp}}(a_{2}a_{1}/\emptyset )$ , so

$a_{1}\leq a_{2}\iff a_{2}\leq a_{1}$ .

This is only possible if $a_{1}=a_{2}$ . But then indiscernibility gives $a_{i}=a_{j}$ for any $i<j$ , so the sequence must be constant.

Another example of a theory in which totally indiscernible sequences are scarce is the p-adics (the theories of p-closed fields.) For example, in the case of the 2-adics $\mathbb {Q} _{2}$ , we can argue as follows. First note that there are no equilateral triangles in $\mathbb {Q} _{2}$ , in the sense that

$\mathbb {Q} _{2}\models \forall x,y,z:v(x-y)=v(x-z)=v(y-z)\rightarrow x=y=z$

Indeed, looking at the binary expansions of x, y, and z, we can find the rightmost digit (bit) at which any two of x, y, and z differ. Two of x, y and z must agree because there are only two binary digits. If x and y agree, and z differs, this means that $v(x-y)>v(x-z)=v(y-z)$ .

More formally, given an equilateral triangle $\{x,y,z\}$ , we can scale it so that $v(x-y)=v(y-z)=v(x-z)=0$ (or in terms of the 2-adic norm, $|x-y|_{2}=|x-z|_{2}=|y-z|_{2}=1$ . Then each of the three differences is in $\mathbb {Z} _{2}$ and has nonzero residue. There is only one nonzero residue, however, so ${\text{res}}(x-y)={\text{res}}(x-z)={\text{res}}(y-z)=1$ . But this is absurd since $1={\text{res}}(x-z)={\text{res}}(x-y)+{\text{res}}(y-z)=1+1$ , and 1 + 1 is 0, not 1.

So there are no equilateral triangles in $\mathbb {Q} _{2}$ . This is a first order statement, so if K is any 2-closed field (any valued field elementarily equivalent to $\mathbb {Q} _{2}$ ), then

$K\models \forall x,y,z:v(x-y)=v(y-z)=v(x-z)\rightarrow x=y=z$ .

Now let $x_{1},x_{2},\ldots$ be a totally indiscernible sequence in K. Because the valuation is ultrametric, the triangle $\{x_{1},x_{2},x_{3}\}$ must be isoceles. Because any permutation of the tuple $(x_{1},x_{2},x_{3})$ must have the same type as $(x_{1},x_{2},x_{3})$ , the triangle is forced to be equilateral. This then forces $x_{1}=x_{2}=x_{3}$ . As in the ordered case, this forces the entire sequence to be constant.

In the case of $\mathbb {Q} _{p}$ for $p>2$ , one can instead show that

$\mathbb {Q} _{p}\models \forall x_{1},\ldots ,x_{p+1}:\left(\bigwedge _{i<j,k<\ell }v(x_{i}-x_{j})=v(x_{k}-x_{\ell })\right)\rightarrow \left(\bigwedge _{i,j}x_{i}=x_{j}\right)$

again by looking at the base p expansion and using the pigeonhole principle at the rightmost digit where things begin to differ. This statement must then persist in all p-closed fields, and then one can make a similar argument to show that any totally indiscernible sequence must be constant.

Manipulating Indiscernible Sequences[]

We list some basic facts about indiscernible sequences which are relatively easy to verify from the definitions.

If $a_{1},a_{2},\ldots$ is an indiscernible sequence, so is the order-reversed sequence $\ldots ,a_{3},a_{2},a_{1}$ . This works for A-indiscernible sequences of any length.

If $a_{1},a_{2},\ldots$ is an indiscernible sequence, then so is any infinite subsequence $a_{i_{1}},a_{i_{2}},\ldots$ , with $i_{1}<i_{2}<\cdots$ . In fact, $a_{i_{1}},a_{i_{2}},\ldots$ has the same type as the original indiscernible sequence. In general, if $\{a_{i}\}_{i\in I}$ is an A-indiscernible sequence and $J\subset I$ is an infinite subset, then $\{a_{i}\}_{i\in J}$ is also A-indiscernible, and if J and I are order-isomorphic, then $\{a_{i}\}_{i\in J}$ has the same type over A as the original indiscernible sequence $\{a_{i}\}_{i\in I}$ :

$\{a_{i}\}_{i\in J}\equiv _{A}\{a_{i}\}_{i\in I}$

More precisely, if $f:J\to I$ is an order-preserving bijection, then the map sending $a_{i}$ to $a_{f(i)}$ and sending A to itself is a partial elementary map.

To check that an infinite sequence is indiscernible, it suffices to check that every countable subsequence is indiscernible.

To check that a sequence is A-indiscernible, it suffices to check that it is A₀-indiscernible for every finite subset A₀ ⊆ A.

If $a_{1},a_{2},\ldots$ is indiscernible, then we can clump consecutive terms together without losing indiscernibility. Specifically, the following sequences are indiscernible:

$a_{1}a_{2},a_{3}a_{4},a_{5}a_{6},\ldots$
$a_{1}a_{2}a_{3},a_{4}a_{5}a_{6},a_{7}a_{8}a_{9},\ldots$ .
and so on

If f is an A-definable function, and $\{a_{i}\}_{i\in I}$ is A-indiscernible, then so is $\{f(a_{i})\}_{i\in I}$ .

Any constant sequence $a,a,a,\ldots$ is indiscernible. If $a_{1},a_{2},\ldots$ fails to be non-constant, then it must contain no repeats, that is, $a_{i}\neq a_{j}$ for any $i\neq j$ . (If not, then $a_{i}=a_{j}$ for some $i<j$ . Then indiscernibility implies that for any $i<j$ , we have $a_{i}=a_{j}$ . This forces the sequence to be constant.)

If $\{a_{i}\}_{i\in I}$ is A-indiscernible, it remains A-indiscernible upon passing to any elementary extension.

Any sequence having the same type over A as an A-indiscernible sequence is itself A-indiscernible. The property of being A-indiscernible is type-definable, in the sense that there is a partial type $\Sigma (x_{1},x_{2},\ldots )$ over A such that $a_{1},a_{2},\ldots$ is A-indiscernible if and only if $M\models \Sigma (a_{1},a_{2},a_{3},\ldots )$ . (Specifically, $\Sigma (x_{1},x_{2},\ldots )$ consists of the formulas

$\phi (x_{i_{1}},\ldots ,x_{i_{n}},a)\iff \phi (x_{j_{1}},\ldots ,x_{j_{n}},a)$

for every formula $\phi (z_{1},\ldots ,z_{n},y)$ , every a from A, and every $i_{1}<i_{2}<\cdots <i_{n}<\omega$ and $j_{1}<j_{2}<\cdots <\omega$ .)

If a sequence is A-indiscernible, it is also B-indiscernible for every B ⊆ A.

If $\{a_{i}\}_{i\in I}$ is A-indiscernible, then it is also acl(A)-indiscernible, where acl(A) denotes the algebraic closure of A. We will prove this later after discussing extraction of indiscernible sequences.

All of the above claims also work for totally indiscernible sequences (rather than indiscernible sequences). In many of the cases, this can be seen by the characterization of totally indiscernible sequences as those sequences which remain indiscernible after re-ordering.

Extending Indiscernible Sequences[]

Let $a_{1},a_{2},\ldots$ be an A-indiscernible sequence in the structure M. By passing to an elementary extension, or assuming that M is sufficiently saturated, we can extend this A-indiscernible sequence to an A-indiscernible sequence of length $\omega +\omega$

$a_{1},a_{2},\ldots ,a_{\omega },a_{\omega +1},\ldots$ .

In fact, we can extend the sequence to whatever length we like. We can even extend it to the left, or add new elements in between preexisting ones. For example, we can also find $a_{1.5},a_{2.5},\ldots$ , such that

$a_{1},a_{1.5},a_{2},a_{2.5},\ldots$

is A-indiscernible.

More precisely, we have the following statement:

Theorem: Let $J$ be an infinite totally ordered set, and let $I\subset J$ be an infinite subset of $J$ . Let M be a structure, and $\{a_{i}\}_{i\in I}$ be an A-indiscernible sequence indexed by $I$ . Then there is an elementary extension $M'\succeq M$ in which there is an A-indiscernible sequence $\{b_{j}\}_{j\in J}$ such that $b_{i}=a_{i}$ for $i\in I$ .

This can be stated a little more cleanly if we work in a monster. Theorem: Let $J$ be an infinite totally ordered set, and let $I\subset J$ be an infinite subset of $J$ . If $\{a_{i}\}_{i\in I}$ is A-indiscernible, then we can find $a_{j}$ for $j\in J\setminus I$ such that $\{a_{j}\}_{j\in J}$ is A-indiscernible.

These theorems also hold with indiscernibility replaced by total indiscernibility.

We will prove these claims after discussing extraction of indiscernible sequences.

Extracting Indiscernible Sequences[]

Let $\{a_{i}\}_{i\in I}$ be some infinite sequence of tuples from M, not assumed to have any indiscernibility properties. (But we should probably assume that $a_{i}$ and $a_{j}$ have the same length and live in the same sorts, for $i\neq j$ .) Let A be some set of parameters. The Ehrenfeucht-Mostowski type of the sequence $\{a_{i}\}_{i\in I}$ over A is the set of all A-formulas

$\phi (x_{1},\ldots ,x_{n})$

such that $M\models \phi (a_{i_{1}},\ldots ,a_{i_{n}})$ for every $i_{1}<\cdots <i_{n}$ . We write EM type as shorthand for "Ehrenfeucht-Mostowski type."

For example, if we consider the sequence $0,1,2,3,\ldots$ in the structure $\mathbb {R}$ (as a model of RCF), then the EM type will contain statements like

$x_{1}\geq 0$ (because every element of the sequence is at least 0)
$x_{2}>x_{1}$ (because the sequence is increasing)

But it will not contain, for example

$x_{2}=x_{1}+1$ , because while this holds for consecutive terms, it does not hold for non-consecutive terms.

We can say that some other sequence $\{b_{j}\}_{j\in J}$ "realizes" the EM type of $\{a_{i}\}_{i\in I}$ over A if every formula in the EM type of the latter sequence is also in the EM type of the former sequence.

Observation: An infinite sequence $\{a_{i}\}_{i\in I}$ is A-indiscernible if and only if its EM type is "complete," in the sense that for every formula $\phi (x_{1},\ldots ,x_{n})$ , either $\phi$ or $\neg \phi$ is in the EM-type of $\{a_{i}\}_{i\in I}$ .

Proof: First suppose that $\{a_{i}\}_{i\in I}$ is A-indiscernible. Let $\phi (x_{1},\ldots ,x_{n})$ be a formula over A. Let $i_{1}<\cdots <i_{n}$ be n distinct elements of I, in sorted order. (We can find such $i_{k}$ because I is infinite.) Then either $M\models \phi (a_{i_{1}},\ldots ,a_{i_{n}})$ or $M\models \neg \phi (a_{i_{1}},\ldots ,a_{i_{n}})$ . If the former happens, then $\phi$ is in the EM type of the sequence over A, because of A-indiscernibility. If the latter happens, then $\neg \phi$ is in the EM type over A, again by A-indiscernibility.

Conversely, suppose that $\{a_{i}\}_{i\in I}$ is an infinite sequence with a "complete" EM type. Then for $i_{1}<\cdots <i_{n}$ and $j_{1}<\cdots <j_{n}$ we want to show that

$a_{i_{1}}\cdots a_{i_{n}}\equiv _{A}a_{j_{1}}\cdots a_{j_{n}}$ .

But if this failed, there would be an A-formula $\phi (x_{1},\ldots ,x_{n})$ such that

$M\models \phi (a_{i_{1}},\ldots ,a_{i_{n}})$ and $M\models \neg \phi (a_{j_{1}},\ldots ,a_{j_{n}})$ .

But then $\phi$ is not in the EM type, because of $a_{j_{1}}\cdots a_{j_{n}}$ , and $\neg \phi$ is not in the EM type, because of $a_{i_{1}}\cdots a_{i_{n}}$ . QED.

Observation: If $\{a_{i}\}_{i\in I}$ and $\{b_{i}\}_{i\in I}$ are two A-indiscernible sequences indexed by the same ordered set I, then $\{a_{i}\}_{i\in I}$ and $\{b_{i}\}_{i\in I}$ have the same type over A if and only if they have the same Ehrenfeucht-Mostowski type over A.

Indeed, the EM type of an indiscernible sequence completely specifies the type of any subsequence, and these data combine to yield the type of the entire sequence.

At any rate, the fundamental theorem about extracting indiscernible sequences is the following. For simplicity, work in a monster model.

Theorem: Let $\{a_{i}\}_{i\in I}$ be a small infinite sequence of elements of the monster. Let $J$ be some small totally ordered set. Let A be a small subset of the monster. Then we can find an A-indiscernible sequence $\{b_{j}\}_{j\in J}$ which realizes the EM type of $\{a_{i}\}_{i\in I}$ over A.

Without working in the monster, it is necessary to pass to an elementary extension to find such a sequence.

In the case where $\{a_{i}\}_{i\in I}$ is already A-indiscernible, this theorem is an easy application of compactness. Specifically, we write down the (infinitary) partial type $\Sigma ({\vec {x}})$ in the variables $\{x_{j}\}_{j\in J}$ consisting of the statements

$\phi (x_{j_{1}},\ldots ,x_{j_{n}})$

for every $j_{1}<\cdots <j_{n}\in J$ and every formula $\phi (x_{1},\ldots ,x_{n})$ in the EM type (over A) of the original sequence $\{a_{i}\}_{i\in I}$ . If we can realize this type, then we will have found a sequence $\{b_{j}\}_{j\in J}$ whose EM type extends the EM type of the original sequence. But since the EM type of the original sequence was complete, the EM type of the $\{b_{j}\}_{j\in J}$ must also be complete, making this sequence be indiscernible. Then we are done.

If, on the other hand, we cannot realize this partial type $\Sigma ({\vec {x}})$ , then by compactness or saturation, there must be some finite subset $\Sigma _{0}({\vec {x}})\subset \Sigma ({\vec {x}})$ which is unsatisfiable. This finite subset must only refer to finitely many variable $x_{j_{1}},\ldots ,x_{j_{N}}$ among the ones occurring in ${\vec {x}}$ . Write $\Sigma _{0}({\vec {x}})$ as $\Sigma _{0}(x_{j_{1}},\ldots ,x_{j_{N}})$ . Since I is infinite, we can find $i_{1}<\cdots <i_{N}$ in I. Then

$\models \Sigma _{0}(a_{i_{1}},\ldots ,a_{i_{N}})$

essentially by definition of $\Sigma$ . This contradicts the unsatisfiability of $\Sigma _{0}$ . QED.

The Theorem on extracting indiscernible sequence has a number of useful consequences:

Corollary: Nontrivial indiscernible sequences exist, in infinite structures. More precisely, let M be an infinite structure (or more precisely, a structure containing an infinite sort). Then, in some elementary extension of M, we can find an indiscernible sequence $a_{1},a_{2},\ldots$ which is non-constant (i.e., $a_{i}\neq a_{j}$ for some i and j.)

Proof: Let $b_{1},b_{2},\ldots$ be some infinite sequence of distinct elements of M (from the same sort). The EM type of $\{b_{i}\}_{i\in \mathbb {N} }$ contains the formula $x_{1}\neq x_{2}$ , because no two elements are the same. Let $a_{1},a_{2},\ldots$ be an indiscernible sequence extracted from the $b_{i}$ 's. Then the EM type of $a_{1},a_{2},\ldots$ must also contain the formula $x_{1}\neq x_{2}$ . This implies that $a_{i}\neq a_{j}$ for i < j. QED.

Corollary: We can extend indiscernible sequences. Working in a monster model, let J be a small totally ordered set (an abstract set, not a subset of the monster). Let I ⊆ J be an infinite subset. Then given any indiscernible sequence $\{a_{i}\}_{i\in I}$ , we can choose $a_{j}$ for $j\in J\setminus I$ such that $\{a_{j}\}_{j\in J}$ is also indiscernbile. (Of course we can also do this with a parameter set A.)

Proof: Let $\{b_{j}\}_{j\in J}$ be an indiscernible sequence of length J extraced from $\{a_{i}\}_{i\in I}$ . These two sequences have the same EM type (over Ø, or over whatever parameter set we may want to use). Consider the subsequence $\{b_{i}\}_{i\in I}$ of $\{b_{j}\}_{j\in J}$ . Then all three sequences

$\{a_{i}\}_{i\in I}$
$\{b_{j}\}_{j\in J}$
$\{b_{i}\}_{i\in I}$

realize the same EM type. (The EM type of the third sequence must extend the EM type of the second sequence. But since the second sequence already has a complete EM type, the EM type of the third sequence must agree with it.)

Now since the first sequence $\{a_{i}\}_{i\in I}$ has the same EM type and the same length as $\{b_{i}\}_{i\in I}$ , they must have the same type, by one of the observations above.

In particular, by strong homogeneity of the monster, we can find an automorphism $\sigma$ (over Ø or a parameter set A) such that $\sigma (b_{i})=a_{i}$ for each i. Now let $a_{j}=\sigma (b_{j})$ for every $j\in J$ . Then $\{a_{j}\}_{j\in J}$ is indiscernible, because it is the image of an indiscernible sequence under an automorphism. QED.

We can also extend totally indiscernible sequences, in a manner similar to the Corollary just discussed. This essentially holds because the total indiscernibility is witnessed by the EM type: an A-indiscernible sequence $\{a_{i}\}_{i\in I}$ is totally A-indiscernible if and only if its EM type includes

$\phi (x_{1},\ldots ,x_{n})\iff \phi (x_{\pi (1)},\ldots ,x_{\pi (n)})$

for any A-formula $\phi (x_{1},\ldots ,x_{n})$ and any permutation $\pi$ of $\{1,\ldots ,n\}$ .

Finally, we show as promised that A-indiscernibility implies acl(A)-indiscernibility.

Lemma: Work in a monster. Let $\{a_{i}\}_{i\in I}$ be an infinite sequence (of small length), indiscernible over some small set A. Let D be a non-empty A-definable set. Then there exists some d ∈ D such that $\{a_{i}\}_{i\in I}$ is Ad-indiscernible. (Here, Ad denotes A ∪ {d}, as usual.)

Proof: Let e be any element of D. Let $\{b_{i}\}_{i\in I}$ be an Ae-indiscernible sequence extracted from $\{a_{i}\}_{i\in I}$ . The EM type of $\{b_{i}\}_{i\in I}$ over A must extend the EM type of $\{a_{i}\}_{i\in I}$ over A, which was already complete. So the two sequences $\{a_{i}\}_{i\in I}$ and $\{b_{i}\}_{i\in I}$ have the same type over A (as they have the same EM type and the same length). Let $\sigma$ be an automorphism of the monster over A, sending $b_{i}$ to $a_{i}$ for each i.

Since $\{b_{i}\}_{i\in I}$ is Ae-indiscernible, $\{\sigma (b_{i})\}_{i\in I}=\{a_{i}\}_{i\in I}$ is $A\sigma (e)$ -indiscernible. And, since D is A-definable and $\sigma$ fixes A, the element $\sigma (e)$ is in D. Take $d=\sigma (e)$ . QED.

Theorem: Work in a monster. Let $\{a_{i}\}_{i\in I}$ be an infinite sequence (of small length), indiscernible over some (small) set A. Then there is a small model M containing A, such that $\{a_{i}\}_{i\in I}$ is indiscernible over A. (Since we are working in the monster, a "model" is a small elementary substructure of the monster.)

Proof: If A is not a model, then by the Tarski-Vaught criterion, there is some non-empty A-definable set D such that no element of D is in A. By the Lemma, we can find some element d ∈ D such that the sequence remains indiscernible over A if we add d to A. By repeating this process infinitely many times, we can enlarge A to be a model.

More rigorously, let $\{D_{\alpha }\}_{\alpha <\lambda }$ be some enumeration of the A-definable sets. Then we can recursively build an increasing sequence $A_{\alpha }$ of small subsets such that $\{a_{i}\}_{iinI}$ is $A_{\alpha }$ -indiscernible for each $\alpha \leq \lambda$ , and such that $A_{\alpha +1}$ contains an element of $D_{\alpha }$ . Specifically, we take

$A_{0}=A$
$A_{\alpha }=\bigcup _{\beta <\alpha }A_{\beta }$ if $\alpha$ is a limit ordinal. The sequence is $A_{\alpha }$ -indiscernible because it is indiscernible over any finite subset of $A_{\alpha }$ .
$A_{\alpha +1}=A_{\alpha }d_{\alpha }$ for some $d_{\alpha }\in D_{\alpha }$ , such that the indiscernibility is maintained. We can find such a $d_{\alpha }$ by the Lemma.

Now the limit $A':=A_{\lambda }$ is a small subset with the property that the original sequence $\{a_{i}\}_{i\in I}$ is $A'$ -indiscernible, and every A-definable set contains at least one point in $A'$ . Repeating this process $\omega$ times, we obtain

$A\subset A'\subset A''\subset \cdots \subset A^{(n)}\subset \cdots$

such that the original sequence $\{a_{i}\}_{i\in I}$ is $A^{(n)}$ -indiscernible for each n, and such that each $A^{(n)}$ -definable set has points in $A^{(n+1)}$ .

Now let M be the union $\bigcup _{n=1}^{\infty }A^{(n)}$ . Again, we have that $\{a_{i}\}_{i\in I}$ is M-indiscernible. And any M-definable set it $A^{(n)}$ -definable, hence has at least one point in $M\supseteq A^{(n)}$ . But this latter condition means that M is a model (i.e., an elementary substructure of the monster), by the Tarski-Vaught criterion. QED.

Corollary: Let $\{a_{i}\}_{i\in I}$ be A-indiscernible. Then $\{a_{i}\}_{i\in I}$ is acl(A)-indiscernible.

Proof: We can elementarily embed everything in a monster. Then we are guaranteed some model M ⊇ A such that $\{a_{i}\}_{i\in I}$ is M-indiscernible. But acl(A) is the same computed in our original model as in the monster, as in M. In particular, acl(A) ⊆ M, so $\{a_{i}\}_{i\in I}$ is acl(A)-indiscernible. QED.

Proof of Existence of Indiscernible Sequences[]

Work in a monster model. Assume for the sake of simplicity that our base set of parameters A is the empty set Ø. Given an infinite sequence $\{a_{i}\}_{i\in I}$ , and an ordered set J, we want to find an indiscernible sequence $\{b_{j}\}_{j\in J}$ realizing the EM type of $\{a_{i}\}_{i\in I}$ .

Above, we gave a proof using compactness that worked whenever $\{a_{i}\}_{i\in I}$ was already indiscernible to begin with (so we were really just changing the length of the sequence). The same proof yields

Lemma: Let $\{a_{i}\}_{i\in I}$ be an infinite sequence (of small length). Let J be an ordered set (small). Then we can find $\{b_{j}\}_{j\in J}$ not necessarily indiscernible, but realizing the EM type of $\{a_{i}\}_{i\in I}$ .

Proof: This amounts to realizing the partial type $\Sigma ({\vec {x}})$ consisting of the formulas

$\phi (x_{j_{1}},\ldots ,x_{j_{n}})$

for every $j_{1}<\cdots <j_{n}\in J$ and every $\phi (x_{1},\ldots ,x_{n})$ in the EM type of $\{a_{i}\}_{i\in I}$ . By compactness, it suffices to realize a finite subset $\Sigma _{0}(x_{j_{1}},\ldots ,x_{j_{N}})\subset \Sigma ({\vec {x}})$ . But one can easily see that if we take $i_{1}<\cdots <i_{N}inI$ , then

$\models \Sigma _{0}(a_{i_{1}},\ldots ,a_{i_{N}})$ ,

by definition of $\Sigma ({\vec {x}})$ and of the EM type of $\{a_{i}\}_{i\in I}$ . QED.

On account of this lemma, the problem of extracting indiscernible sequences reduces down to the case where the index sets are always $\omega$ . That is, we only need to extract an indiscernible sequence $b_{1},b_{2},\ldots$ from an (arbitrary) sequence $a_{1},a_{2},\ldots$ .

One proof of this uses Ramsey's Theorem from combinatorics, together with compactness. Given $a_{1},a_{2},\ldots$ , write down the partial type $\Sigma (x_{1},x_{2},\ldots )$ consisting of the following statements:

$\phi (x_{j_{1}},\ldots ,x_{j_{n}})\iff \phi (x_{i_{1}},\ldots ,x_{i_{n}})$ for every n, every formula $\phi (y_{1},\ldots ,y_{n})$ , and every $j_{1}<\cdots <j_{n}$ and $i_{1}<\cdots <i_{n}$ .
$\psi (x_{1},x_{2},\ldots ,x_{n})$ for every formula $\psi$ in the EM type of the sequence $a_{1},a_{2},\ldots$ .

Any realization of the partial type $\Sigma$ will be an indiscernible sequence realizing the desired EM type. By compactness, it suffices to check finite satisfiability of this type. More precisely, it suffices to check that for any given $\phi _{1},\ldots ,\phi _{m}$ , we can satisfy the type $\Sigma _{\phi _{1},\ldots ,\phi _{m}}(x_{1},x_{2},\ldots )$ consisting of the following statements.

$\phi _{i}(x_{j_{1}},\ldots ,x_{j_{n_{i}}})\iff \phi _{i}(x_{i_{1}},\ldots ,x_{i_{n_{i}}})$ for $1\leq i\leq m$ and every $j_{1}<\cdots <j_{n_{i}}$ and $i_{1}<\cdots <i_{n_{i}}$ .
$\psi (x_{1},x_{2},\ldots ,x_{n})$ for every formula $\psi$ in the EM type of the sequence $a_{1},a_{2},\ldots$ .

Here, $n_{i}$ denotes the number of free variables occurring in $\phi _{i}=\phi _{i}(y_{1},\ldots ,y_{n_{i}})$ . By adding on dummy variables at the end, it is safe to assume that $n_{i}$ doesn't depend on i.

So $\Sigma _{\phi _{1},\ldots ,\phi _{m}}$ basically expresses the desired EM type plus "indiscernibility with respect to the formulas in $\{\phi _{1},\ldots ,\phi _{m}\}$ ."

Now we "color" each of the n-element subsets of $\mathbb {N}$ with one of $2^{m}$ colors. Specifically, the "color" attached to $\{i_{1},\ldots ,i_{n}\}\subset \mathbb {N}$ is

$\{k\leq m:\models \phi _{k}(a_{i_{1}},\ldots ,a_{i_{n}})\}\subset \{1,\ldots ,m\}$ .

By Ramsey's Theorem, we can find an infinite homogeneous subset of $\mathbb {N}$ . That is, we can find $c_{1}<c_{2}<\cdots$ and a color C such that for any $i_{1},\ldots ,i_{n}$ , the color attached to $\{c_{i_{1}},\ldots ,c_{i_{n}}\}$ is C. In particular, if $i_{1}<\cdots <i_{n}$ and $j_{1}<\cdots <j_{n}$ , then the same color is attached to $\{c_{i_{1}},\ldots ,c_{i_{n}}\}$ as to $\{c_{j_{1}},\ldots ,c_{j_{n}}\}$ . This means that for $1\leq k\leq m$ , we have

$\models \phi _{k}(a_{c_{i_{1}}},\ldots ,a_{c_{i_{n}}})\iff \phi _{k}(a_{c_{j_{1}}},\ldots ,a_{c_{j_{n}}})$ .

So the subsequence

$a_{c_{1}},a_{c_{2}},\ldots$

of the original sequence $a_{1},a_{2},\ldots$ satisfies the "indiscernibility with respect to <\math>\{\phi_1, \ldots, \phi_m\}</math>" condition. As a subsequence of $a_{1},a_{2},\ldots$ , it also satisfies the EM type of $a_{1},a_{2},\ldots$ . Therefore, it satisfies $\Sigma _{\phi _{1},\ldots ,\phi _{m}}$ .

So each type $\Sigma _{\phi _{1},\ldots ,\phi _{m}}$ is satisfiable. But any finite subset of $\Sigma$ is contained in one of these, so $\Sigma$ is finite satisfiable. QED.

Another proof, more model-theoretic than combinatorial, uses the machinery of global invariant types. Without developing that machinery (and the machinery of monster models), we describe the proof.

Lemma: Let M be a structure containing a sort I with a total ordering <, such that I has no greatest element. Then in some elementary extension of M, we can find an indiscernible increasing sequence in I.

Proof: Let $M'\succeq M$ be an |M|⁺-saturated elementary extension of M. Consider the partial type $\Sigma (x)$ over $M'$ , where x is a variable in the sort I, consisting of the following formulas:

$\phi (x,a)\iff \phi (x,b)$ , whenever $a\equiv _{M}b$ and $\phi (x;y)$ is a formula.
$x>\alpha$ for every $\alpha \in I(M)$ . (Here, I(M) denotes the interpretation of I in M, or equivalently, $I\cap M$ .)

We claim that $\Sigma (x)$ is consistent. Note that any element of $I(M)$ will certainly satisfy the first type of statement, by definition of what $a\equiv _{M}b$ means. By compactness, it therefore suffices to show that any finite collection of statements of the second type is realized by someone in $I(M)$ . That is, we need to show that if $\alpha _{1},\ldots ,\alpha _{n}$ are in $I(M)$ , then some element of $I(M)$ is greater than each $\alpha _{i}$ . This is immediate from the fact that I has no greatest element.

Now let p(x) be a complete type over $M'$ extending the consistent partial type $\Sigma (x)$ . Build a sequence $\alpha _{1},\alpha _{2},\ldots \in M'$ recursively by letting $\alpha _{n}$ be any realization of p restricted to $M\cup \{\alpha _{1},\ldots ,\alpha _{n-1}\}$ . We can find a realization of this type in $M'$ because we assumed $M'$ to be |M|⁺-saturated.

We claim that $\alpha _{1},\alpha _{2},\ldots$ is not just indiscernible, but even M-indiscernible. To do this, we prove by induction on n that if $i_{1}<\cdots <i_{n}$ and $j_{1}<\cdots <j_{n}$ , then

$\alpha _{i_{1}}\cdots \alpha _{i_{n}}\equiv _{M}\alpha _{j_{1}}\cdots \alpha _{j_{n}}$ .

The base case of n = 1 amounts to showing that each $\alpha _{i}$ has the same type over M. But this is clear, since each $\alpha _{i}$ realized $p|M$ (among other things).

For the inductive step, suppose we know the claim for all $n<m$ , and consider $n=m$ . Given $i_{1}<\cdots <i_{m}$ and $j_{1}<\cdots <j_{m}$ , we first find some k such that $k>max(i_{m},j_{m})$ . Then $\alpha _{k}$ realizes p restricted to $M\cup \{\alpha _{1},\ldots ,\alpha _{k}\}$ . In particular, $\alpha _{k}$ realizes $p\upharpoonright M\cup \{\alpha _{j_{1}},\ldots ,\alpha _{j_{m-1}}\}$ . So does $\alpha _{j_{m}}$ , so

$\alpha _{k}\equiv _{M\alpha _{j_{1}}\cdots \alpha _{j_{m-1}}}\alpha _{j_{m}}$

or equivalently,

$\alpha _{j_{1}}\cdots \alpha _{j_{m-1}}\alpha _{k}\equiv _{M}\alpha _{j_{1}}\cdots \alpha _{j_{m}}$ .

Similarly,

$\alpha _{i_{1}}\cdots \alpha _{i_{m-1}}\alpha _{k}\equiv _{M}\alpha _{i_{1}}\cdots \alpha _{i_{m}}$ .

So it suffices to show that

$\alpha _{j_{1}}\cdots \alpha _{j_{m-1}}\alpha _{k}\equiv _{M}\alpha _{i_{1}}\cdots \alpha _{i_{m-1}}\alpha _{k}$ .

By the inductive hypothesis,

$\alpha _{j_{1}}\cdots \alpha _{j_{m-1}}\equiv _{M}\alpha _{i_{1}}\cdots \alpha _{i_{m-1}}$ .

Now if $\phi (x_{1},\ldots ,x_{m})$ is any formula over M, then the formula

$\phi (\alpha _{i_{1}},\ldots ,\alpha _{i_{m-1}},x)\iff \phi (\alpha _{j_{1}},\ldots ,\alpha _{j_{m-1}},x)$

is in $\Sigma (x)$ , hence in $p(x)$ , and hence in $p\upharpoonright M\cup \{\alpha _{1},\ldots ,\alpha _{k-1}\}$ . In particular, $\alpha _{k}$ satisfies it.

$\phi (\alpha _{i_{1}},\ldots ,\alpha _{i_{m-1}},\alpha _{k})\iff \phi (\alpha _{j_{1}},\ldots ,\alpha _{j_{m-1}},\alpha _{k})$

holds for every formula $\phi (x_{1},\ldots ,x_{m})$ over M. This means precisely that

$\alpha _{j_{1}}\cdots \alpha _{j_{m-1}}\alpha _{k}\equiv _{M}\alpha _{i_{1}}\cdots \alpha _{i_{m-1}}\alpha _{k}$ ,

completing the inductive step.

So we conclude that $\alpha _{1},\alpha _{2},\ldots$ is M-indiscernible, hence indiscernible. If $\alpha _{1}<\alpha _{2}<\cdots$ , then we are done. Otherwise, $\alpha _{1}>\alpha _{2}>\cdots$ . Consider the reversed sequence $\ldots ,\alpha _{3},\alpha _{2},\alpha _{1}$ . This is also indiscernible. By the Lemma at the beginning of this section, we can pass to an even bigger elementary extension and find an indiscernible sequence $b_{1},b_{2},\ldots$ realizing the EM type of $\ldots ,\alpha _{3},\alpha _{2},\alpha _{1}$ , which includes the statement $x_{1}<x_{2}$ . Then $b_{1},b_{2},\ldots$ is our desired increasing indiscernible sequence.

QED.

Now to prove the Theorem on the ability to extract indiscernible sequences, it remains to prove the following:

Lemma: Let M be some model. Let $a_{1},a_{2},\ldots$ be a sequence from M. Then we can find an indiscernible sequence $b_{1},b_{2},\ldots$ realizing the EM type of the sequence $a_{1},a_{2},\ldots$ .

Proof: Consider the expansion of M to a new structure N in which we have added a sort I interpreted as $\mathbb {N}$ , as well as the binary order predicate on I and a unary function symbol f from I to M sending $i\in \mathbb {N}$ to $a_{i}$ . By the Lemma, we can find an elementary extension $N'\succeq N$ containing an increasing indiscernible sequence $\alpha _{1},\alpha _{2},\ldots$ in the sort I. Let $M'$ be the reduct of $N'$ to the original language of M. One easily checks that $M'\succeq M$ . The function f is Ø-definable, so the sequence $f(\alpha _{1}),f(\alpha _{2}),\ldots$ is an (Ø-)indiscernible sequence in $N'$ . It lives in $M'$ , and is indiscernible in the reduct $M'$ (because there are fewer formulas for which to check indiscernibility). So we have an indiscernible sequence $\{f(\alpha _{i})\}_{i\in \mathbb {N} }$ in $M'$ , an elementary extension of M.

It remains to check that this sequence realizes the EM type of the original sequence $a_{1},a_{2},\ldots$ . Let $\phi (x_{1},\ldots ,x_{n})$ be a formula in that EM type. Then

$N\models \forall x_{1},\ldots ,x_{n}\in I:x_{1}<x_{2}<\cdots <x_{n}\Rightarrow \phi (f(x_{1}),\ldots ,f(x_{n}))$

(This is a restatement of what it means for $\phi$ to be in the EM type.) Since $N'\succeq N$ , the above also holds in $N$ . Now given $i_{1}<\cdots <i_{n}$ , note that

$N'\models \alpha _{i_{1}}<\alpha _{i_{2}}<\cdots <\alpha _{i_{n}}$ ,

so we must also have

$N'\models \phi (f(\alpha _{i_{1}}),f(\alpha _{i_{2}}),\ldots ,f(\alpha _{i_{n}})$ .

Since $\phi$ was a formula in the original language, it follows that

$M'\models \phi (f(\alpha _{i_{1}}),\ldots ,f(\alpha _{i_{n}})$ .

Consequently, $\phi$ is in the EM type of $\{f(\alpha _{i})\}_{i\in \mathbb {N} }$ . This completes the proof. QED.

[Extraction using Erdős–Rado]{#Extraction_using_Erdős–Rado .mw-headline}[]

Applications of Indiscernible Sequences[]

::: ::: :::