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


Fix some structure M. A sequence

{\displaystyle 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

{\displaystyle {\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

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


{\displaystyle 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 AM is some subset, we say that {\displaystyle a_{1},a_{2},\ldots } is A-indiscernible if it is indiscernible after naming the elements of A, or equivalently, if

{\displaystyle {\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

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


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

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

{\displaystyle {\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

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


{\displaystyle 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 = i1 and any j = j1, tp(ai/A) = tp(aj/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


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

{\displaystyle {\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 {\displaystyle (a_{i_{1}},a_{i_{2}},\ldots ,a_{i_{n}})} and {\displaystyle (a_{j_{1}},a_{j_{2}},\ldots ,a_{j_{n}})} are strictly increasing.

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

{\displaystyle 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 {\displaystyle 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:

{\displaystyle {\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 {\displaystyle (\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

{\displaystyle (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.,

{\displaystyle (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 {\displaystyle \{a_{i}\}_{i\in I}} is said to be totally indiscernible if

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

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

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

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

The condition for {\displaystyle \{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 {\displaystyle \{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 {\displaystyle t_{1},t_{2},\ldots } in {\displaystyle \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 {\displaystyle (\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

{\displaystyle 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 {\displaystyle a_{1},a_{2},\ldots } is totally indiscernible, then

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

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

This is only possible if {\displaystyle a_{1}=a_{2}}. But then indiscernibility gives {\displaystyle a_{i}=a_{j}} for any {\displaystyle 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 {\displaystyle \mathbb {Q} _{2}}, we can argue as follows. First note that there are no equilateral triangles in {\displaystyle \mathbb {Q} _{2}}, in the sense that

{\displaystyle \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 {\displaystyle v(x-y)>v(x-z)=v(y-z)}.

More formally, given an equilateral triangle {\displaystyle \{x,y,z\}}, we can scale it so that {\displaystyle v(x-y)=v(y-z)=v(x-z)=0} (or in terms of the 2-adic norm, {\displaystyle |x-y|_{2}=|x-z|_{2}=|y-z|_{2}=1}. Then each of the three differences is in {\displaystyle \mathbb {Z} _{2}} and has nonzero residue. There is only one nonzero residue, however, so {\displaystyle {\text{res}}(x-y)={\text{res}}(x-z)={\text{res}}(y-z)=1}. But this is absurd since {\displaystyle 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 {\displaystyle \mathbb {Q} _{2}}. This is a first order statement, so if K is any 2-closed field (any valued field elementarily equivalent to {\displaystyle \mathbb {Q} _{2}}), then

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

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

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

{\displaystyle \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 {\displaystyle a_{1},a_{2},\ldots } is an indiscernible sequence, so is the order-reversed sequence {\displaystyle \ldots ,a_{3},a_{2},a_{1}}. This works for A-indiscernible sequences of any length.

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

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

More precisely, if {\displaystyle f:J\to I} is an order-preserving bijection, then the map sending {\displaystyle a_{i}} to {\displaystyle 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 A0-indiscernible for every finite subset A0A.

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

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

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

If {\displaystyle \{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 {\displaystyle \Sigma (x_{1},x_{2},\ldots )} over A such that {\displaystyle a_{1},a_{2},\ldots } is A-indiscernible if and only if {\displaystyle M\models \Sigma (a_{1},a_{2},a_{3},\ldots )}. (Specifically, {\displaystyle \Sigma (x_{1},x_{2},\ldots )} consists of the formulas

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

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

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

If {\displaystyle \{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 {\displaystyle 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 {\displaystyle \omega +\omega }

{\displaystyle 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 {\displaystyle a_{1.5},a_{2.5},\ldots }, such that

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

is A-indiscernible.

More precisely, we have the following statement:

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

This can be stated a little more cleanly if we work in a monster. Theorem: Let {\displaystyle J} be an infinite totally ordered set, and let {\displaystyle I\subset J} be an infinite subset of {\displaystyle J}. If {\displaystyle \{a_{i}\}_{i\in I}} is A-indiscernible, then we can find {\displaystyle a_{j}} for {\displaystyle j\in J\setminus I} such that {\displaystyle \{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 {\displaystyle \{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 {\displaystyle a_{i}} and {\displaystyle a_{j}} have the same length and live in the same sorts, for {\displaystyle i\neq j}.) Let A be some set of parameters. The Ehrenfeucht-Mostowski type of the sequence {\displaystyle \{a_{i}\}_{i\in I}} over A is the set of all A-formulas

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

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

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

But it will not contain, for example

{\displaystyle 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 {\displaystyle \{b_{j}\}_{j\in J}} "realizes" the EM type of {\displaystyle \{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 {\displaystyle \{a_{i}\}_{i\in I}} is A-indiscernible if and only if its EM type is "complete," in the sense that for every formula {\displaystyle \phi (x_{1},\ldots ,x_{n})}, either {\displaystyle \phi } or {\displaystyle \neg \phi } is in the EM-type of {\displaystyle \{a_{i}\}_{i\in I}}.

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

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

{\displaystyle 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 {\displaystyle \phi (x_{1},\ldots ,x_{n})} such that

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

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

Observation: If {\displaystyle \{a_{i}\}_{i\in I}} and {\displaystyle \{b_{i}\}_{i\in I}} are two A-indiscernible sequences indexed by the same ordered set I, then {\displaystyle \{a_{i}\}_{i\in I}} and {\displaystyle \{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 {\displaystyle \{a_{i}\}_{i\in I}} be a small infinite sequence of elements of the monster. Let {\displaystyle J} be some small totally ordered set. Let A be a small subset of the monster. Then we can find an A-indiscernible sequence {\displaystyle \{b_{j}\}_{j\in J}} which realizes the EM type of {\displaystyle \{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 {\displaystyle \{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 {\displaystyle \Sigma ({\vec {x}})} in the variables {\displaystyle \{x_{j}\}_{j\in J}} consisting of the statements

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

for every {\displaystyle j_{1}<\cdots <j_{n}\in J} and every formula {\displaystyle \phi (x_{1},\ldots ,x_{n})} in the EM type (over A) of the original sequence {\displaystyle \{a_{i}\}_{i\in I}}. If we can realize this type, then we will have found a sequence {\displaystyle \{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 {\displaystyle \{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 {\displaystyle \Sigma ({\vec {x}})}, then by compactness or saturation, there must be some finite subset {\displaystyle \Sigma _{0}({\vec {x}})\subset \Sigma ({\vec {x}})} which is unsatisfiable. This finite subset must only refer to finitely many variable {\displaystyle x_{j_{1}},\ldots ,x_{j_{N}}} among the ones occurring in {\displaystyle {\vec {x}}}. Write {\displaystyle \Sigma _{0}({\vec {x}})} as {\displaystyle \Sigma _{0}(x_{j_{1}},\ldots ,x_{j_{N}})}. Since I is infinite, we can find {\displaystyle i_{1}<\cdots <i_{N}} in I. Then

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

essentially by definition of {\displaystyle \Sigma }. This contradicts the unsatisfiability of {\displaystyle \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 {\displaystyle a_{1},a_{2},\ldots } which is non-constant (i.e., {\displaystyle a_{i}\neq a_{j}} for some i and j.)

Proof: Let {\displaystyle b_{1},b_{2},\ldots } be some infinite sequence of distinct elements of M (from the same sort). The EM type of {\displaystyle \{b_{i}\}_{i\in \mathbb {N} }} contains the formula {\displaystyle x_{1}\neq x_{2}}, because no two elements are the same. Let {\displaystyle a_{1},a_{2},\ldots } be an indiscernible sequence extracted from the {\displaystyle b_{i}}'s. Then the EM type of {\displaystyle a_{1},a_{2},\ldots } must also contain the formula {\displaystyle x_{1}\neq x_{2}}. This implies that {\displaystyle 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 IJ be an infinite subset. Then given any indiscernible sequence {\displaystyle \{a_{i}\}_{i\in I}}, we can choose {\displaystyle a_{j}} for {\displaystyle j\in J\setminus I} such that {\displaystyle \{a_{j}\}_{j\in J}} is also indiscernbile. (Of course we can also do this with a parameter set A.)

Proof: Let {\displaystyle \{b_{j}\}_{j\in J}} be an indiscernible sequence of length J extraced from {\displaystyle \{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 {\displaystyle \{b_{i}\}_{i\in I}} of {\displaystyle \{b_{j}\}_{j\in J}}. Then all three sequences

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 {\displaystyle \{a_{i}\}_{i\in I}} has the same EM type and the same length as {\displaystyle \{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 {\displaystyle \sigma } (over Ø or a parameter set A) such that {\displaystyle \sigma (b_{i})=a_{i}} for each i. Now let {\displaystyle a_{j}=\sigma (b_{j})} for every {\displaystyle j\in J}. Then {\displaystyle \{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 {\displaystyle \{a_{i}\}_{i\in I}} is totally A-indiscernible if and only if its EM type includes

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

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

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

Lemma: Work in a monster. Let {\displaystyle \{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 dD such that {\displaystyle \{a_{i}\}_{i\in I}} is Ad-indiscernible. (Here, Ad denotes A ∪ {d}, as usual.)

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

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

Theorem: Work in a monster. Let {\displaystyle \{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 {\displaystyle \{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 dD 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 {\displaystyle \{D_{\alpha }\}_{\alpha <\lambda }} be some enumeration of the A-definable sets. Then we can recursively build an increasing sequence {\displaystyle A_{\alpha }} of small subsets such that {\displaystyle \{a_{i}\}_{iinI}} is {\displaystyle A_{\alpha }}-indiscernible for each {\displaystyle \alpha \leq \lambda }, and such that {\displaystyle A_{\alpha +1}} contains an element of {\displaystyle D_{\alpha }}. Specifically, we take

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

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

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

Now let M be the union {\displaystyle \bigcup _{n=1}^{\infty }A^{(n)}}. Again, we have that {\displaystyle \{a_{i}\}_{i\in I}} is M-indiscernible. And any M-definable set it {\displaystyle A^{(n)}}-definable, hence has at least one point in {\displaystyle 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 {\displaystyle \{a_{i}\}_{i\in I}} be A-indiscernible. Then {\displaystyle \{a_{i}\}_{i\in I}} is acl(A)-indiscernible.

Proof: We can elementarily embed everything in a monster. Then we are guaranteed some model MA such that {\displaystyle \{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 {\displaystyle \{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 {\displaystyle \{a_{i}\}_{i\in I}}, and an ordered set J, we want to find an indiscernible sequence {\displaystyle \{b_{j}\}_{j\in J}} realizing the EM type of {\displaystyle \{a_{i}\}_{i\in I}}.

Above, we gave a proof using compactness that worked whenever {\displaystyle \{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 {\displaystyle \{a_{i}\}_{i\in I}} be an infinite sequence (of small length). Let J be an ordered set (small). Then we can find {\displaystyle \{b_{j}\}_{j\in J}} not necessarily indiscernible, but realizing the EM type of {\displaystyle \{a_{i}\}_{i\in I}}.

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

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

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

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

by definition of {\displaystyle \Sigma ({\vec {x}})} and of the EM type of {\displaystyle \{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 {\displaystyle \omega }. That is, we only need to extract an indiscernible sequence {\displaystyle b_{1},b_{2},\ldots } from an (arbitrary) sequence {\displaystyle a_{1},a_{2},\ldots }.

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

Any realization of the partial type {\displaystyle \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 {\displaystyle \phi _{1},\ldots ,\phi _{m}}, we can satisfy the type {\displaystyle \Sigma _{\phi _{1},\ldots ,\phi _{m}}(x_{1},x_{2},\ldots )} consisting of the following statements.

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

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

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

{\displaystyle \{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 {\displaystyle \mathbb {N} }. That is, we can find {\displaystyle c_{1}<c_{2}<\cdots } and a color C such that for any {\displaystyle i_{1},\ldots ,i_{n}}, the color attached to {\displaystyle \{c_{i_{1}},\ldots ,c_{i_{n}}\}} is C. In particular, if {\displaystyle i_{1}<\cdots <i_{n}} and {\displaystyle j_{1}<\cdots <j_{n}}, then the same color is attached to {\displaystyle \{c_{i_{1}},\ldots ,c_{i_{n}}\}} as to {\displaystyle \{c_{j_{1}},\ldots ,c_{j_{n}}\}}. This means that for {\displaystyle 1\leq k\leq m}, we have

{\displaystyle \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

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

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

So each type {\displaystyle \Sigma _{\phi _{1},\ldots ,\phi _{m}}} is satisfiable. But any finite subset of {\displaystyle \Sigma } is contained in one of these, so {\displaystyle \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 {\displaystyle M'\succeq M} be an |M|+-saturated elementary extension of M. Consider the partial type {\displaystyle \Sigma (x)} over {\displaystyle M'}, where x is a variable in the sort I, consisting of the following formulas:

We claim that {\displaystyle \Sigma (x)} is consistent. Note that any element of {\displaystyle I(M)} will certainly satisfy the first type of statement, by definition of what {\displaystyle 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 {\displaystyle I(M)}. That is, we need to show that if {\displaystyle \alpha _{1},\ldots ,\alpha _{n}} are in {\displaystyle I(M)}, then some element of {\displaystyle I(M)} is greater than each {\displaystyle \alpha _{i}}. This is immediate from the fact that I has no greatest element.

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

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

{\displaystyle \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 {\displaystyle \alpha _{i}} has the same type over M. But this is clear, since each {\displaystyle \alpha _{i}} realized {\displaystyle p|M} (among other things).

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

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

or equivalently,

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


{\displaystyle \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

{\displaystyle \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,

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

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

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

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


{\displaystyle \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 {\displaystyle \phi (x_{1},\ldots ,x_{m})} over M. This means precisely that

{\displaystyle \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 {\displaystyle \alpha _{1},\alpha _{2},\ldots } is M-indiscernible, hence indiscernible. If {\displaystyle \alpha _{1}<\alpha _{2}<\cdots }, then we are done. Otherwise, {\displaystyle \alpha _{1}>\alpha _{2}>\cdots }. Consider the reversed sequence {\displaystyle \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 {\displaystyle b_{1},b_{2},\ldots } realizing the EM type of {\displaystyle \ldots ,\alpha _{3},\alpha _{2},\alpha _{1}}, which includes the statement {\displaystyle x_{1}<x_{2}}. Then {\displaystyle b_{1},b_{2},\ldots } is our desired increasing indiscernible sequence.


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 {\displaystyle a_{1},a_{2},\ldots } be a sequence from M. Then we can find an indiscernible sequence {\displaystyle b_{1},b_{2},\ldots } realizing the EM type of the sequence {\displaystyle 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 {\displaystyle \mathbb {N} }, as well as the binary order predicate on I and a unary function symbol f from I to M sending {\displaystyle i\in \mathbb {N} } to {\displaystyle a_{i}}. By the Lemma, we can find an elementary extension {\displaystyle N'\succeq N} containing an increasing indiscernible sequence {\displaystyle \alpha _{1},\alpha _{2},\ldots } in the sort I. Let {\displaystyle M'} be the reduct of {\displaystyle N'} to the original language of M. One easily checks that {\displaystyle M'\succeq M}. The function f is Ø-definable, so the sequence {\displaystyle f(\alpha _{1}),f(\alpha _{2}),\ldots } is an (Ø-)indiscernible sequence in {\displaystyle N'}. It lives in {\displaystyle M'}, and is indiscernible in the reduct {\displaystyle M'} (because there are fewer formulas for which to check indiscernibility). So we have an indiscernible sequence {\displaystyle \{f(\alpha _{i})\}_{i\in \mathbb {N} }} in {\displaystyle M'}, an elementary extension of M.

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

{\displaystyle 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 {\displaystyle \phi } to be in the EM type.) Since {\displaystyle N'\succeq N}, the above also holds in {\displaystyle N}. Now given {\displaystyle i_{1}<\cdots <i_{n}}, note that

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

so we must also have

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

Since {\displaystyle \phi } was a formula in the original language, it follows that

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

Consequently, {\displaystyle \phi } is in the EM type of {\displaystyle \{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[]

::: ::: :::