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

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

for any

and

.

(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 is A-indiscernible if it is indiscernible after naming the elements of A, or equivalently, if

for any

and

.

More generally, we can allow the sequence of 's to have length other than . For any infinite totally ordered set , a sequence is A-indiscernible if

for any

and

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

• , i.e., the type of any two consecutive pairs is the same.
• , 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 for each . This is clear from the definition of indiscernibility.)
• .
• More generally, any infinite subsequence of an indiscernible sequence (of length ) has the same type as the original sequence. In fact, this condition characterizes indiscernible sequences (of length ), by an easy exercise.

## Examples

Example: In the structure (a model of DLO), any increasing sequence is indiscernible. In fact, by quantifier elimination in DLO, the type of a tuple over Ø is completely determined by the relative ordering of the 's. So if and , then

because both tuples and are strictly increasing.

Example: Consider the structure of as a ring (a model of ACF). Let be a sequence of transcendental complex numbers which are algebraically independent. (For example, could be the beginning of an enumeration of a transcendence basis of over .) Then is indiscernible. To see this, let and be two increasing sequences. Then is isomorphic to the rational function field in n variables, because the are algebraically independent. The same is true of . Consequently we can get an isomorphism

such that for each k. This condition is equivalent to the assertion that the two tuples in question have the same quantifier free type:

.

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 , 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

.

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

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 is said to be totally indiscernible if

,

for any , subject only to the condition that

and for .

An equivalent condition is that is indiscernible, and the sequence remains indiscernible after rearranging the order of the terms.

The condition for to be totally indiscernible doesn't depend on the ordering of I, and is really more of a property of the set , 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 in 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 , 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

is not indiscernible.

More generally, in a totally ordered structure, every totally indiscernible sequence must be constant. Indeed, if is totally indiscernible, then

, so

.

This is only possible if . But then indiscernibility gives for any , 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 , we can argue as follows. First note that there are no equilateral triangles in , in the sense that

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 .

More formally, given an equilateral triangle , we can scale it so that (or in terms of the 2-adic norm, . Then each of the three differences is in and has nonzero residue. There is only one nonzero residue, however, so . But this is absurd since , and 1 + 1 is 0, not 1.

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

.

Now let be a totally indiscernible sequence in K. Because the valuation is ultrametric, the triangle must be isoceles. Because any permutation of the tuple must have the same type as , the triangle is forced to be equilateral. This then forces . As in the ordered case, this forces the entire sequence to be constant.

In the case of for , one can instead show that

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 is an indiscernible sequence, so is the order-reversed sequence . This works for A-indiscernible sequences of any length.

If is an indiscernible sequence, then so is any infinite subsequence , with . In fact, has the same type as the original indiscernible sequence. In general, if is an A-indiscernible sequence and is an infinite subset, then is also A-indiscernible, and if J and I are order-isomorphic, then has the same type over A as the original indiscernible sequence :

More precisely, if is an order-preserving bijection, then the map sending to 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 is indiscernible, then we can clump consecutive terms together without losing indiscernibility. Specifically, the following sequences are indiscernible:

• .
• and so on

If f is an A-definable function, and is A-indiscernible, then so is .

Any constant sequence is indiscernible. If fails to be non-constant, then it must contain no repeats, that is, for any . (If not, then for some . Then indiscernibility implies that for any , we have . This forces the sequence to be constant.)

If 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 over A such that is A-indiscernible if and only if . (Specifically, consists of the formulas

for every formula , every a from A, and every and .)

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

If 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 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

.

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 , such that

is A-indiscernible.

More precisely, we have the following statement:

Theorem: Let be an infinite totally ordered set, and let be an infinite subset of . Let M be a structure, and be an A-indiscernible sequence indexed by . Then there is an elementary extension in which there is an A-indiscernible sequence such that for .

This can be stated a little more cleanly if we work in a monster. Theorem: Let be an infinite totally ordered set, and let be an infinite subset of . If is A-indiscernible, then we can find for such that 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 be some infinite sequence of tuples from M, not assumed to have any indiscernibility properties. (But we should probably assume that and have the same length and live in the same sorts, for .) Let A be some set of parameters. The Ehrenfeucht-Mostowski type of the sequence over A is the set of all A-formulas

such that for every . We write EM type as shorthand for "Ehrenfeucht-Mostowski type."

For example, if we consider the sequence in the structure (as a model of RCF), then the EM type will contain statements like

• (because every element of the sequence is at least 0)
• (because the sequence is increasing)

But it will not contain, for example

, because while this holds for consecutive terms, it does not hold for non-consecutive terms.

We can say that some other sequence "realizes" the EM type of 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 is A-indiscernible if and only if its EM type is "complete," in the sense that for every formula , either or is in the EM-type of .

Proof: First suppose that is A-indiscernible. Let be a formula over A. Let be n distinct elements of I, in sorted order. (We can find such because I is infinite.) Then either or . If the former happens, then is in the EM type of the sequence over A, because of A-indiscernibility. If the latter happens, then is in the EM type over A, again by A-indiscernibility.

Conversely, suppose that is an infinite sequence with a "complete" EM type. Then for and we want to show that

.

But if this failed, there would be an A-formula such that

and .

But then is not in the EM type, because of , and is not in the EM type, because of . QED.

Observation: If and are two A-indiscernible sequences indexed by the same ordered set I, then and 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 be a small infinite sequence of elements of the monster. Let be some small totally ordered set. Let A be a small subset of the monster. Then we can find an A-indiscernible sequence which realizes the EM type of 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 is already A-indiscernible, this theorem is an easy application of compactness. Specifically, we write down the (infinitary) partial type in the variables consisting of the statements

for every and every formula in the EM type (over A) of the original sequence . If we can realize this type, then we will have found a sequence 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 must also be complete, making this sequence be indiscernible. Then we are done.

If, on the other hand, we cannot realize this partial type , then by compactness or saturation, there must be some finite subset which is unsatisfiable. This finite subset must only refer to finitely many variable among the ones occurring in . Write as . Since I is infinite, we can find in I. Then

essentially by definition of . This contradicts the unsatisfiability of . 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 which is non-constant (i.e., for some i and j.)

Proof: Let be some infinite sequence of distinct elements of M (from the same sort). The EM type of contains the formula , because no two elements are the same. Let be an indiscernible sequence extracted from the 's. Then the EM type of must also contain the formula . This implies that 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 , we can choose for such that is also indiscernbile. (Of course we can also do this with a parameter set A.)

Proof: Let be an indiscernible sequence of length J extraced from . These two sequences have the same EM type (over Ø, or over whatever parameter set we may want to use). Consider the subsequence of . 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 has the same EM type and the same length as , 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 (over Ø or a parameter set A) such that for each i. Now let for every . Then 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 is totally A-indiscernible if and only if its EM type includes

for any A-formula and any permutation of .

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

Lemma: Work in a monster. Let 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 is Ad-indiscernible. (Here, Ad denotes A ∪ {d}, as usual.)

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

Since is Ae-indiscernible, is -indiscernible. And, since D is A-definable and fixes A, the element is in D. Take . QED.

Theorem: Work in a monster. Let be an infinite sequence (of small length), indiscernible over some (small) set A. Then there is a small model M containing A, such that 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 be some enumeration of the A-definable sets. Then we can recursively build an increasing sequence of small subsets such that is -indiscernible for each , and such that contains an element of . Specifically, we take

• if is a limit ordinal. The sequence is -indiscernible because it is indiscernible over any finite subset of .
• for some , such that the indiscernibility is maintained. We can find such a by the Lemma.

Now the limit is a small subset with the property that the original sequence is -indiscernible, and every A-definable set contains at least one point in . Repeating this process times, we obtain

such that the original sequence is -indiscernible for each n, and such that each -definable set has points in .

Now let M be the union . Again, we have that is M-indiscernible. And any M-definable set it -definable, hence has at least one point in . 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 be A-indiscernible. Then is acl(A)-indiscernible.

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

Above, we gave a proof using compactness that worked whenever was already indiscernible to begin with (so we were really just changing the length of the sequence). The same proof yields

Lemma: Let be an infinite sequence (of small length). Let J be an ordered set (small). Then we can find not necessarily indiscernible, but realizing the EM type of .

Proof: This amounts to realizing the partial type consisting of the formulas

for every and every in the EM type of . By compactness, it suffices to realize a finite subset . But one can easily see that if we take , then

,

by definition of and of the EM type of . QED.

On account of this lemma, the problem of extracting indiscernible sequences reduces down to the case where the index sets are always . That is, we only need to extract an indiscernible sequence from an (arbitrary) sequence .

One proof of this uses Ramsey's Theorem from combinatorics, together with compactness. Given , write down the partial type consisting of the following statements:

• for every n, every formula , and every and .
• for every formula in the EM type of the sequence .

Any realization of the partial type 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 , we can satisfy the type consisting of the following statements.

• for and every and .
• for every formula in the EM type of the sequence .

Here, denotes the number of free variables occurring in . By adding on dummy variables at the end, it is safe to assume that doesn't depend on i.

So basically expresses the desired EM type plus "indiscernibility with respect to the formulas in ."

Now we "color" each of the n-element subsets of with one of colors. Specifically, the "color" attached to is

.

By Ramsey's Theorem, we can find an infinite homogeneous subset of . That is, we can find and a color C such that for any , the color attached to is C. In particular, if and , then the same color is attached to as to . This means that for , we have

.

So the subsequence

of the original sequence satisfies the "indiscernibility with respect to <\math>\{\phi_1, \ldots, \phi_m\}[/itex]" condition. As a subsequence of , it also satisfies the EM type of . Therefore, it satisfies .

So each type is satisfiable. But any finite subset of is contained in one of these, so 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 be an |M|+-saturated elementary extension of M. Consider the partial type over , where x is a variable in the sort I, consisting of the following formulas:

• , whenever and is a formula.
• for every . (Here, I(M) denotes the interpretation of I in M, or equivalently, .)

We claim that is consistent. Note that any element of will certainly satisfy the first type of statement, by definition of what means. By compactness, it therefore suffices to show that any finite collection of statements of the second type is realized by someone in . That is, we need to show that if are in , then some element of is greater than each . This is immediate from the fact that I has no greatest element.

Now let p(x) be a complete type over extending the consistent partial type . Build a sequence recursively by letting be any realization of p restricted to . We can find a realization of this type in because we assumed to be |M|+-saturated.

We claim that is not just indiscernible, but even M-indiscernible. To do this, we prove by induction on n that if and , then

.

The base case of n = 1 amounts to showing that each has the same type over M. But this is clear, since each realized (among other things).

For the inductive step, suppose we know the claim for all , and consider . Given and , we first find some k such that . Then realizes p restricted to . In particular, realizes . So does , so

or equivalently,

.

Similarly,

.

So it suffices to show that

.

By the inductive hypothesis,

.

Now if is any formula over M, then the formula

is in , hence in , and hence in . In particular, satisfies it.

So

holds for every formula over M. This means precisely that

,

completing the inductive step.

So we conclude that is M-indiscernible, hence indiscernible. If , then we are done. Otherwise, . Consider the reversed sequence . 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 realizing the EM type of , which includes the statement . Then 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 be a sequence from M. Then we can find an indiscernible sequence realizing the EM type of the sequence .

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

It remains to check that this sequence realizes the EM type of the original sequence . Let be a formula in that EM type. Then

(This is a restatement of what it means for to be in the EM type.) Since , the above also holds in . Now given , note that

,

so we must also have

.

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

.

Consequently, is in the EM type of . This completes the proof. QED.