## Equivalent definitions of stability

Fix some complete theory . Let be a monster model for .

By default, "types" will be complete types. Types will be finitary types (-types for some ), unless stated otherwise.

A formula has the order property if there exist , for such that if and only if . Equivalently, by compactness, for every , there exist for such that if and only if .

Let be a cardinal. We say that is -stable if there are at most complete types over any set of size at most . That is, if for every set such that , we have for every .

If is a type over a set , we say that is definable (over ) if for every formula , there is some -formula such that for each ,

Theorem. The following are equivalent for a complete theory:

• Every type over every set is definable
• is -stable for some
• is -stable for every infinite cardinal such that .
• No formula has the order property.

We say that is stable if it satisfies these equivalent conditions.

There are a number of additional conditions which are also equivalent to stability:

• Every 1-type over every set is definable.
• Every type over every model is definable.
• Every 1-type over every model is definable.
• Every indiscernible sequence is totally indiscernible.
• No formula with a singleton has the order property.
• There is some such that for every set with , we have , where is the space of 1-types over . In other words, we have stability on the level of 1-types.
• For every with , if then .
• For every formula , there are only countably many -types over any countable set .
• For every formula and set , the space of -types over contains no perfect set, or equivalently, has Cantor-Bendixson rank less than .
• No formula has the independence property and no formula has the strict order property ( is both NIP and NSOP). The proof of this is purely combinatorial and has nothing to do with the rest of this article; it can be found here.
• is both NIP and simple

Below, we will prove all or most of these equivalences.

## [From definability of types to ΞΊ-stability]{#From_definability_of_types_to_β"UNIQ--postMath-00000043-QINU"β-stability .mw-headline}

Lemma 1. Suppose every 1-type over a model is definable. Suppose and has . Then .

Proof. By LΓΆwenheim-Skolem, we can find a model with . The restriction map is surjective, so it suffices to show . By assumption, every 1-type over is definable. A definition consists of a map which assigns to each formula an -formula . There are formulas and formulas over , so there are at most possible definitions. Consequently, there are at most -many 1-types over . QED

Lemma 2. Let be a cardinal. Suppose that for every set with we have . Then is -stable, i.e., for every set with and every , .

Proof. Let be a set of size at most . We need to show that there are at most -many -types over .

The rough idea here is that to specify , we need only specify , , , etc. At each step there are at most choices, so all together there are possibilities.

More rigorously, we proceed by induction on . The case is given. Suppose we know . For each -type over , choose some realization, and let be the set of all these realizations. For each in , there are at most -many 1-types over , by the assumption. For each 1-type over choose some representative realization and let be the set of representatives. So . Now if the , and so it suffices to show that every -type over is realized in . Let be an -type over , and let be a tuple realizing , where is a singleton and is an -tuple. As was a complete set of representatives of the -types over , there is some such that . Let send to . As is a complete set of representatives of the 1-types over , we can find some such that , or equivalently, . But then where the second follows because is an automorphism over . So , and is realized by someone in . This completes the inductive proof. QED

## From stability to the order property

If is a totally ordered set, by a Dedekind cut of we will mean a downward-closed subset , so if with , then .

Lemma 3. Let be a cardinal. Then there exists a totally ordered set of size at most with more than Dedekind cuts.

Proof. Let be the smallest cardinal such that . As , we have . Let be , the set of all strings of 0βs and 1βs of length less than . We will produce a Dedekind cut on for each element of , the set of strings of 0βs and 1βs of length .

Note that Let be the set of all functions from to , ordered lexicographically with . Embed into by taking a string and appending copies of to the end. We claim that the induced ordering on has more than -many Dedekind cuts. In fact, each element of (a set of size ) induces a distinct Dedekind cut on . To see this, let be two distinct strings from . Then and differ at some place, and we have for some . Now where we are viewing as an element of via the embedding . So and induce different Dedekind cuts on . QED

Lemma 4. Suppose is -stable for some . Then no formula has the order property.

Proof. By Lemma 3, we can find a totally ordered set such that but has more than Dedekind cuts.

Suppose has the order property. So there exist for such that holds if and only if . Let be an -indexed indiscernible sequence extracted from . So holds if and only if .

Now if is an ascending sequence in , then we can find some such that holds for and holds for . Namely, we take to be . By compactness, it follows that for each Dedekind cut of , we can find some such that holds for and doesnβt hold for .

Let be the set . Then . On the other hand, if , then , because if , then holds and does not hold. There are more than -many βs, so there are more than -many types over , contradicting -stability. QED

## From the order property to definability

The missing link in the proof is that no formula having the order property implies the definability of types over models. This is where things get tricky.

### Step 1: Total indiscernibility

Lemma 5. Fix . Suppose that no formula has the order property with an -tuple of variables. Then every -indiscernible sequence of -tuples is totally -indiscernible.

Proof. Let be some -indiscernible sequence. Whether or not is totally -indiscernible is part of the Ehrenfeucht-Mostowski type over of the sequence, so we can replace with another -indiscernible sequence having the same EM type. Replacing with a -indexed -indiscernible sequence extracted from , we may assume that is (with the usual ordering).

Let , and . We claim that i.e., that we can swap two consecutive elements in the sequence without changing the type of the sequence.

If not, then where . Thus there is some -formula (with and both -tuples) such that holds and does not. Now is a -indiscernible sequence. Therefore, if , then holds if and doesnβt hold if . By density of , we can choose for such that . Now holds if and only if . Writing as for some tuple of parameters from , we have Consequently is a formula with the order property and is a tuple of length , contradicting the hypothesis.

Therefore the claim is proven, and we can swap any two consecutive elements of without changing the type over . This property remains true after performing the swap. Since every permutation can be written as a product of such swaps, it follows that every permutation of has the same type over . So the sequence is totally -indiscernible. QED

Lemma 6. Let be a formula without the order property, and be the length of the tuple . There is an integer , depending only on , such that for every totally -indiscernible sequence and every , one of the two sets has size at most .

Proof. If not, then for each we can find a totally indiscernible sequence and a such that holds for more than values of , and fails to hold for more than values of . Any permutation or infinite subset of a totally indiscernible sequence is still totally indiscernible. So we can pass to a countable subsequence and rearrange the sequence to be indexed by . We can reorder the terms so that holds for and doesnβt hold for .

Now since we can do this for each , by compactness we can find a totally indiscernible sequence and a such that holds if and only if .

By indiscernibility, for each we can find a such that . Then So has the order property, a contradiction. QED

### Step 2: Morley Sequences

Suppose that no formula with of length has the order property.

Let be an -type over which is -invariant for some small set . A Morley sequence for is a sequence such that for each , realizes restricted to . Observe that any subsequence of a Morley sequence is a Morley sequence.

Lemma. Any two Morley sequences of length have the same type over .

Proof. By induction on . For , we have both realizing . Then clearly . Suppose all Morley sequences of length have the same type over . Let and be two Morley sequences of length . By the inductive hypothesis, we can find such that for . Now realizes , so realizes . Since is -invariant, really realizes , which is the same type that realizes. Thus or equivalently Since we conclude that and have the same type over . QED

Lemma. Any Morley sequence is -indiscernible, hence totally -indiscernible by Lemma 5.

Proof. Let be a Morley sequence. It suffices to show that any two finite subsequences of the same length have the same type over . Since they are both Morley sequences, this follows from the previous lemma. QED

Lemma 7. Let be an infinite Morley sequence for . Let be the set of all formulas (with from ) such that for all but at most finitely many values of . Then is a consistent global type, which is definable (over some small set, not necessarily ). The type is called the average type of .

Proof. By the previous lemma, is totally indiscernible over , hence over . Therefore, by Lemma 6, we know that for every -formula , either holds for almost all , or holds for almost all .

First we check that is consistent. If not, then there exist -formulas in which are jointly inconsistent. But for each , at most finitely many fail to satisfy . Therefore, at most finitely many fail to satisfy . Since is infinite, at least one satisfies . So is consistent.

Lemma 6 ensures that is complete, i.e., that or is in for every -formula .

Definability comes from the number in Lemma 6. Specifically, for each formula we need to show that is definable. Lemma 6 gives us a number depending on (but not on ) such that for every , either

• for all but at most values of , in which case ; OR
• for no more than values of , in which case .

Consequently, we can determine whether belongs in by checking for values of , and doing a majority vote. If are distinct values of , then we get and so is the -definition of . QED

### [Step 3: p is the average type of its Morley sequences]{#Step_3:_β"UNIQ--postMath-000001C6-QINU"β_is_the_average_type_of_its_Morley_sequences .mw-headline}

Continue to assume that no formula with of length has the order property, and that is a global -type which is -invariant.

Lemma. If is a Morley sequence for and is an infinite subsequence, then (which is also a Morley sequence) has the same average type as .

Proof. Let and be the average types of and . If , then holds for all but finitely many in . In particular, also holds for all but finitely many in , so . Thus . Since and are complete types, they must be equal. QED

Lemma. If and are two infinite Morley sequences for , then they have the same average type.

Proof. Recursively build a sequence by letting realize restricted to . Let be the sequence of all the βs. Then the concatenations and are Morley sequences. By the previous lemma, , where denotes the average type of a Morley sequence . QED

So there is a unique global type which is the average type of any Morley sequence of .

Lemma 8.

Proof. Let be a formula in . We will show that . This suffices because and are complete types (over the monster). Let be a sequence built up recursively by letting realize the restriction of to . Then is a Morley sequence for . The formula is in the restriction of to , so satisfies it for every . That is, holds for every . It follows that is in the average type of , but this average type is . QED

Combining this with Lemma 7, we get

Lemma 9. Suppose that no formula with of length has the order property. Let be a global -type. Suppose that is -invariant for some small set . Then is -definable, i.e., for every formula the set is an -definable subset of .

Proof. Lemma 8, is the average type of any Morley sequence. By Lemma 7, it follows that is definable over some set. So for each formula , the set is definable. But it is also -invariant, so it must be -definable. QED

Finally, we can deduce the definability of types (over models) from the absence of formulas with the order property:

Lemma 10. Suppose that no formula with of length has the order property. Then every -type over a model is -definable.

Proof. Let be the global partial type which consists of all formulas of the form for . Note that any element of satisfies . If is a finite subset of , then is satisfiable in , hence so is . It follows that is consistent. Let be a global type extending . Then whenever , we have Therefore is -invariant, hence -definable by Lemma 9. But is the restriction of from to , so it is also -definable. QED

## The first few definitions of stability

We have now reached the following:

Theorem. The following are equivalent:

(a)
Every type over a model is definable.
(a')
Every 1-type over a model is definable.
(b)
is -stable for all with .
(b')
same as (c) but for 1-types rather than n-types
(c)
is -stable for some .
(c')
same as (d) but for 1-types rather than n-types
(d)
No formula has the order property.
(dβ)
No formula with a singleton has the order property.

Proof. Clearly (c) implies (c'), and Lemma 2 gives the converse. Similarly, (b) and (b') are equivalent.

We have the following sequence of implications: From left to right:

• (c) (d) is by Lemma 4.
• (d) (d') is obvious.
• (d) (a) is by Lemma 10.
• (d') (a') is by Lemma 10.
• (a) (a') is obvious.
• (a') (b') is by Lemma 1.

It remains to show that (b) (c). Suppose is -stable for every such that . Let . Then , so is -stable. In particular, is -stable for at least one . QED

We say that is stable if it satisfies one of these equivalent conditions.

At this point, one easy equivalence is:

Theorem. is stable if and only if every indiscernible sequence is totally indiscernible.

Proof. If is stable, then for every , no formula with of length has the order property. By Lemma 5, every indiscernible sequence is totally indiscernible. Conversely, suppose that is not stable. Then some formula has the order property. Let for witness this, so that holds if and only if . Let be an indiscernible sequence extracted from . Then holds if and only if , because this was expressed in the Ehrenfeucht-Mostowski type of . But now holds and does not, indicating that and do not have the same type, so the sequence is not totally indiscernible, in spite of being indiscernible. QED

Lemma. Let be a countable stable theory, and be a formula. Then over any countable set , there are at most countably many -types.

Proof. Since is countable, by LΓΆwenheim-Skolem we can find a countable model containing . Then surjects onto , so it suffices to show that is countable. If , we can extend to a complete type . The type is -definable, by stability. Let be the -definition of , with a tuple from . Then for , The -type is therefore determined by the formula . Since and are countable, there are only countably many possibilities for . Hence there are only countably many possibilities for . QED

Observe that any reduct of a stable theory is still stable. One way to see this is to observe that there are fewer formulas to check against the order property. Alternatively, one can note that there are fewer types in a reduct than in the original structure.

Theorem. is stable if and only if the following holds: for every formula and every countable set, , the space of -types is countable.

Proof. Suppose is stable. Then we can find a countable reduct of in which is still definable. The space of -types of is the same after passing to this reduct, so it is countable.

Conversely, suppose that is unstable. Let be a formula having the order property, witnessed by . Extract an indiscernible sequence of length from . So holds if and only if . By compactness, for each real number , we can find a such that Then each has a distinct -type over the countable set , so there are uncountably many -types over this set. QED

## [Cantor-Bendixson Rank in the space of Ο-types]{#Cantor-Bendixson_Rank_in_the_space_of_β"UNIQ--postMath-000002A5-QINU"β-types .mw-headline}

Recall that if is a boolean algebra, and is the stone space of ultrafilters on , then the following conditions are equivalent:

• has Cantor-Bendixson rank
• contains a perfect set
• There exist for such that for each and such that and for each .

The first two conditions are equivalent essentially by definition of Cantor-Bendixson rank. If a perfect set exists, then we can inductively choose as follows:

• Take to be any clopen set in intersecting .
• Given intersecting , the set is still perfect, and hence contains at least two points . If is a clopen neighborhood containing and not , then let and .

Then each intersects , hence is non-empty.

Conversely, given such that and , the Cantor-Bendixson rank must be . If not, then for each , we can find a such that has lower CB rank than , or has the same rank and lower degree. In this way, we obtain a sequence with descending . But there are no infinite descending sequences of ordinal numbers.

By abuse of terminology, let us say that is "unstable" if one of the above conditions holds, and "stable" otherwise. From the third condition, one sees that if is stable, so is any subalgebra . Conversely, if every countable subalgebra is stable, then is stable.

Now suppose that is a stable theory, is a monster model of , and is a formula. Let be the boolean algebra generated by -formulas over , so . Then is stable. If not, then some countable subalgebra is unstable. Then consists of boolean combinations of -formulas over some countable set of parameters . If is the boolean algebra generated by all -formulas over , then , and is unstable. That is, contains a perfect set. But then is uncountable (by the Cantor-Bendixson theorem), contradicting one of our criteria for stability in the previous section.

Since is stable, we see that has Cantor-Bendixson rank less than , or equivalently, contains no perfect set. The same holds for for any subset .

Conversely, if is a theory such that contains no perfect set for any and formula , then is stable. Indeed, since is a Polish space for countable , must be countable by the Cantor-Bendixson theorem, and therefore is stable. So we have proven:

Theorem. A theory is stable if and only if contains no perfect set, for every set and formula .

## Definability of types over arbitrary sets

Lemma. Assume is stable. Let be a small subset of , be a complete type over , and be a formula. Then there exists a global -type which is consistent with and which has finite orbit under .

Proof. Let be the closed subset of consisting of the global -types which are consistent with . By stability, contains no perfect set; therefore neither does . The boolean space therefore has Cantor-Bendixson rank less than . Let be any point in with maximal Cantor-Bendixson rank. If , then by symmetry, is another point of maximal Cantor-Bendixson rank. But there are only finitely many points of maximal Cantor-Bendixson rank in . So has finitely many conjugates. QED

Theorem. A theory is stable if and only if every type over every set is definable.

Proof. Clearly if every type over every set is definable, then every type over a model is definable, so is stable.

Conversely, suppose is stable, and is a set. Let be a complete type over . Let be a formula. Let be a complete -type over extending , with finitely many conjugates over . Then is definable, so there is some -definable set such that for all , Now if and , then Since has finitely many conjugates over , so does . If is the intersection of all the conjugates of , then is a definable set, which is -invariant, hence -definable. And for , . So has a -definition. As was arbitrary, is -definable. QED

From this, we get the stable embeddedness of all definable sets (what Poizat calls the "Parameter Separation Theorem").

Theorem. Assume is stable. Let be a definable set (over some parameters). Then is stably embedded, i.e., if is a definable subset of for some , then for some definable over parameters from .

Proof. Let be cut out by a formula , with some element from the monster. The type of over is definable over . In particular, for the formula , there is some -formula such that for every from , we have So if is the set cut out by , then . This holds for , so , where is definable with parameters from . QED ::: ::: :::