Equivalent definitions of stability[]

Fix some complete theory $T$ . Let $\mathbb {U}$ be a monster model for $T$ .

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

A formula $\phi (x;y)$ has the order property if there exist $a_{i}$ , $b_{i}$ for $i<\omega$ such that $\models \phi (a_{i};b_{j})$ if and only if $i<j$ . Equivalently, by compactness, for every $n$ , there exist $a_{i},b_{i}$ for $i<n$ such that $\models \phi (a_{i};b_{j})$ if and only if $i<j$ .

Let $\kappa \geq |T|$ be a cardinal. We say that $T$ is $\kappa$ -stable if there are at most $\kappa$ complete types over any set of size at most $\kappa$ . That is, if for every set $A\subset \mathbb {U}$ such that $|A|\leq \kappa$ , we have $|S_{n}(A)|\leq \kappa$ for every $n$ .

If $p(x)$ is a type over a set $A$ , we say that $p(x)$ is definable (over $A$ ) if for every formula $\phi (x;y)$ , there is some $A$ -formula $\psi (y)$ such that for each $a\in A$ , $\phi (x;a)\in p(x)\iff \models \psi (a)$

Theorem. The following are equivalent for $T$ a complete theory:

Every type over every set is definable
$T$ is $\kappa$ -stable for some $\kappa$
$T$ is $\kappa$ -stable for every infinite cardinal $\kappa \geq |T|$ such that $\kappa ^{|T|}=\kappa$ .
No formula has the order property.

We say that $T$ 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 $\phi (x;y)$ with $x$ a singleton has the order property.
There is some $\kappa \geq |T|$ such that for every set $A$ with $|A|\leq \kappa$ , we have $|S_{1}(A)|\leq \kappa$ , where $S_{1}(A)$ is the space of 1-types over $A$ . In other words, we have stability on the level of 1-types.
For every $\kappa \geq |T|$ with $\kappa ^{|T|}=\kappa$ , if $|A|\leq \kappa$ then $|S_{1}(A)|\leq \kappa$ .
For every formula $\phi (x;y)$ , there are only countably many $\phi$ -types over any countable set $A$ .
For every formula $\phi (x;y)$ and set $A$ , the space $S_{\phi }(A)$ of $\phi$ -types over $A$ contains no perfect set, or equivalently, has Cantor-Bendixson rank less than $\infty$ .
No formula has the independence property and no formula has the strict order property ( $T$ 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.
$T$ is both NIP and simple

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

[From definability of types to $\kappa$ -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 $\kappa ^{|T|}=\kappa \geq |T|$ and $A\subset \mathbb {U}$ has $|A|\leq \kappa$ . Then $|S_{1}(A)|\leq \kappa$ .

Proof. By Löwenheim-Skolem, we can find a model $M\supseteq A$ with $|M|\leq |A|+|T|\leq \kappa$ . The restriction map $S_{1}(M)\to S_{1}(A)$ is surjective, so it suffices to show $|S_{1}(M)|\leq \kappa$ . By assumption, every 1-type over $M$ is definable. A definition consists of a map which assigns to each formula $\phi (x;y)$ an $M$ -formula $\psi (y)$ . There are $|T|$ formulas and $\kappa +|T|=\kappa$ formulas over $M$ , so there are at most $\kappa ^{|T|}=\kappa$ possible definitions. Consequently, there are at most $\kappa$ -many 1-types over $M$ . QED

Lemma 2. Let $\kappa \geq |T|$ be a cardinal. Suppose that for every set $A\subset \mathbb {U}$ with $|A|\leq \kappa$ we have $|S_{1}(A)|\leq \kappa$ . Then $T$ is $\kappa$ -stable, i.e., for every set $A\subset \mathbb {U}$ with $|A|\leq \kappa$ and every $n$ , $|S_{n}(A)|\leq \kappa$ .

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

The rough idea here is that to specify $\operatorname {tp} (a_{1}a_{2}\cdots a_{n}/A)$ , we need only specify $\operatorname {tp} (a_{n}/A)$ , $\operatorname {tp} (a_{n-1}/Aa_{n})$ , $\operatorname {tp} (a_{n-2}/Aa_{n}a_{n-1})$ , etc. At each step there are at most $\kappa$ choices, so all together there are $\kappa ^{n}=\kappa$ possibilities.

More rigorously, we proceed by induction on $n$ . The case $n=1$ is given. Suppose we know $|S_{n-1}(A)|\leq \kappa$ . For each $(n-1)$ -type over $A$ , choose some realization, and let $B$ be the set of all these realizations. For each $b$ in $B$ , there are at most $\kappa$ -many 1-types over $Ab$ , by the assumption. For each 1-type over $Ab$ choose some representative realization and let $C_{b}$ be the set of representatives. So $|C_{b}|\leq \kappa$ . Now if $D=\{(c,b):b\in B,~c\in C_{b}\}$ the $|D|\leq \kappa \times \kappa =\kappa$ , and so it suffices to show that every $n$ -type over $A$ is realized in $D$ . Let $p$ be an $n$ -type over $A$ , and let $(c',b')$ be a tuple realizing $p$ , where $c'$ is a singleton and $b'$ is an $(n-1)$ -tuple. As $B$ was a complete set of representatives of the $(n-1)$ -types over $A$ , there is some $b\in B$ such that $b\equiv _{A}b'$ . Let $\sigma \in \operatorname {Aut} (\mathbb {U} /A)$ send $b'$ to $b$ . As $C_{b}$ is a complete set of representatives of the 1-types over $Ab$ , we can find some $c\in C_{b}$ such that $c\equiv _{Ab}\sigma (c')$ , or equivalently, $(c,b)\equiv _{A}(\sigma (c'),b)$ . But then $(c,b)\equiv _{A}(\sigma (c'),b)=\sigma ((c',b'))\equiv _{A}(c',b'),$ where the second $\equiv _{A}$ follows because $\sigma$ is an automorphism over $A$ . So $p=\operatorname {tp} (c'b'/A)=\operatorname {tp} (cb/A)$ , and $p$ is realized by someone in $D$ . This completes the inductive proof. QED

From stability to the order property[]

If $(S,<)$ is a totally ordered set, by a Dedekind cut of $S$ we will mean a downward-closed subset $T\subset S$ , so if $s,s'\in S$ with $s<s'$ , then $s'\in T\implies s\in T$ .

Lemma 3. Let $\kappa$ be a cardinal. Then there exists a totally ordered set $(S,<)$ of size at most $\kappa$ with more than $\kappa$ Dedekind cuts.

Proof. Let $\lambda$ be the smallest cardinal such that $2^{\lambda }>\kappa$ . As $2^{\kappa }>\kappa$ , we have $\lambda \leq \kappa$ . Let $S$ be $2^{<\lambda }$ , the set of all strings of 0’s and 1’s of length less than $\lambda$ . We will produce a Dedekind cut on $S$ for each element of $2^{\lambda }=\{0,1\}^{\lambda }$ , the set of strings of 0’s and 1’s of length $\lambda$ .

Note that $\left|2^{<\lambda }\right|\leq \sum _{\alpha <\lambda }2^{|\alpha |}\leq \sum _{\alpha <\lambda }\kappa \leq \lambda \times \kappa =\kappa .$ Let $T$ be the set of all functions from $\lambda$ to $\{0,*,1\}$ , ordered lexicographically with $0<*<1$ . Embed $S$ into $T$ by taking a string $s$ and appending $\lambda$ copies of $*$ to the end. We claim that the induced ordering on $S$ has more than $\kappa$ -many Dedekind cuts. In fact, each element of $\{0,1\}^{\lambda }$ (a set of size $2^{\lambda }>\kappa$ ) induces a distinct Dedekind cut on $S$ . To see this, let $w<w'$ be two distinct strings from $\{0,1\}^{\lambda }\subset T$ . Then $w$ and $w'$ differ at some place, and we have $w=v0u$ $w'=v1u'$ for some $v,u,u'$ . Now $w<v<w'$ where we are viewing $v\in S$ as an element of $T$ via the embedding $S\hookrightarrow T$ . So $w$ and $w'$ induce different Dedekind cuts on $S$ . QED

Lemma 4. Suppose $T$ is $\kappa$ -stable for some $T$ . Then no formula $\phi (x;y)$ has the order property.

Proof. By Lemma 3, we can find a totally ordered set $(S,<)$ such that $|S|\leq \kappa$ but $S$ has more than $\kappa$ Dedekind cuts.

Suppose $\phi (x;y)$ has the order property. So there exist $a_{i},b_{i}$ for $i<\omega$ such that $\phi (a_{i};b_{j})$ holds if and only if $i<j$ . Let $\langle c_{s}d_{s}\rangle _{s\in S}$ be an $S$ -indexed indiscernible sequence extracted from $\langle a_{i}b_{i}\rangle _{i<\omega }$ . So $\phi (c_{s};d_{s'})$ holds if and only if $s<s'$ .

Now if $s_{1}<\cdots <s_{n}<t_{1}<\cdots <t_{m}$ is an ascending sequence in $S$ , then we can find some $b\in \mathbb {U}$ such that $\phi (a_{s_{i}};b)$ holds for $1\leq i\leq n$ and $\neg \phi (a_{t_{i}};b)$ holds for $1\leq i\leq m$ . Namely, we take $b$ to be $b_{t_{1}}$ . By compactness, it follows that for each Dedekind cut $D$ of $S$ , we can find some $b_{D}\in \mathbb {U}$ such that $\phi (a_{s};b_{D})$ holds for $s\in D$ and doesn’t hold for $s\notin D$ .

Let $A$ be the set $\{a_{s}:s\in S\}$ . Then $|A|\leq |S|\leq \kappa$ . On the other hand, if $D\neq D'$ , then $b_{D}\not \equiv _{A}b_{D'}$ , because if $s\in D\setminus D'$ , then $\phi (a_{s};b_{D})$ holds and $\phi (a_{s};b_{D'})$ does not hold. There are more than $\kappa$ -many $D$ ’s, so there are more than $\kappa$ -many types over $A$ , contradicting $\kappa$ -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 $n<\omega$ . Suppose that no formula $\phi (x;y)$ has the order property with $x$ an $n$ -tuple of variables. Then every $A$ -indiscernible sequence of $n$ -tuples is totally $A$ -indiscernible.

Proof. Let $\langle a_{i}\rangle _{i\in I}$ be some $A$ -indiscernible sequence. Whether or not $e_{i}$ is totally $A$ -indiscernible is part of the Ehrenfeucht-Mostowski type over $A$ of the sequence, so we can replace $a_{i}$ with another $A$ -indiscernible sequence having the same EM type. Replacing $a_{i}$ with a $\mathbb {Q}$ -indexed $A$ -indiscernible sequence extracted from $\langle a_{i}\rangle _{i\in I}$ , we may assume that $I$ is $\mathbb {Q}$ (with the usual ordering).

Let $x_{1}<\cdots <x_{n}\in \mathbb {Q}$ , and $1\leq i<n$ . We claim that $a_{x_{1}}\cdots a_{x_{n}}\equiv _{A}a_{x_{1}}\cdots a_{x_{i-1}}a_{x_{i+1}}a_{x_{i}}a_{x_{i+2}}\cdots a_{x_{n}},$ i.e., that we can swap two consecutive elements in the sequence $(a_{x_{1}},\ldots ,a_{x_{n}})$ without changing the type of the sequence.

If not, then $a_{x_{i}}a_{x_{i+1}}\not \equiv _{B}a_{x_{i+1}}a_{x_{i}}$ where $B=Aa_{x_{1}}\cdots a_{x_{i-1}}a_{x_{i+2}}\cdots a_{x_{n}}$ . Thus there is some $B$ -formula $\phi (x;y)$ (with $x$ and $y$ both $n$ -tuples) such that $\phi (a_{x_{i}},a_{x_{i+1}})$ holds and $\phi (a_{x_{i+1}},a_{x_{i}})$ does not. Now $\langle a_{x}:x_{i-1}<x<x_{i+2}\rangle$ is a $B$ -indiscernible sequence. Therefore, if $y,z\in (x_{i-1},x_{i+2})$ , then $\phi (a_{y},a_{z})$ holds if $y<z$ and doesn’t hold if $z>y$ . By density of $\mathbb {Q}$ , we can choose $y_{i},z_{i}$ for $i<\omega$ such that $x_{i-1}<z_{1}<y_{1}<z_{2}<y_{2}<z_{3}<y_{3}<\cdots <x_{i+2}$ . Now $\phi (a_{y_{i}};a_{z_{j}})$ holds if and only if $i<j$ . Writing $\phi (x;y)$ as $\psi (x;y,b)$ for $b$ some tuple of parameters from $B$ , we have $\models \psi (a_{y_{i}};a_{z_{j}}b)\iff i<j$ Consequently $\psi (x;-)$ is a formula with the order property and $x$ is a tuple of length $n$ , contradicting the hypothesis.

Therefore the claim is proven, and we can swap any two consecutive elements of $a_{1}a_{2}\cdots a_{n}$ without changing the type over $A$ . 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 $a_{1}a_{2}\cdots a_{n}$ has the same type over $A$ . So the sequence is totally $A$ -indiscernible. QED

Lemma 6. Let $\phi (x;y)$ be a formula without the order property, and $n$ be the length of the tuple $x$ . There is an integer $N$ , depending only on $\phi (x;y)$ , such that for every totally $\emptyset$ -indiscernible sequence $\{a_{i}:i\in I\}$ and every $b$ , one of the two sets $\{i\in I:\mathbb {U} \models \phi (a_{i};b)\}$ $\{i\in I:\mathbb {U} \models \neg \phi (a_{i};b)\}$ has size at most $N$ .

Proof. If not, then for each $N$ we can find a totally indiscernible sequence $\{a_{i}:i\in I\}$ and a $b$ such that $\phi (a_{i};b)$ holds for more than $N$ values of $i$ , and fails to hold for more than $N$ values of $i$ . 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 $\mathbb {Z}$ . We can reorder the terms so that $\phi (a_{i};b)$ holds for $i=-1,\ldots ,-(N+1)$ and doesn’t hold for $i=0,\ldots ,N$ .

Now since we can do this for each $N$ , by compactness we can find a totally indiscernible sequence $\{a_{i}:i\in \mathbb {Z} \}$ and a $b$ such that $\phi (a_{i};b)$ holds if and only if $i<0$ .

By indiscernibility, for each $j$ we can find a $\sigma _{j}\in \operatorname {Aut} (\mathbb {U} )$ such that $\sigma _{j}(a_{i})=a_{i+j}$ . Then $\models \phi (a_{i};\sigma _{j}(b))\iff \models \phi (\sigma _{j}^{-1}(a_{i});b)\iff \models \phi (a_{i-j};b)\iff i-j<0$ So $\phi (x;y)$ has the order property, a contradiction. QED

Step 2: Morley Sequences[]

Suppose that no formula $\phi (x;y)$ with $x$ of length $n$ has the order property.

Let $p(x)$ be an $n$ -type over $\mathbb {U}$ which is $\operatorname {Aut} (\mathbb {U} /A)$ -invariant for some small set $A$ . A Morley sequence for $p$ is a sequence $\langle a_{i}\rangle _{i\in I}$ such that for each $i$ , $a$ realizes $p$ restricted to $A\cup \{a_{j}:j<i\}$ . Observe that any subsequence of a Morley sequence is a Morley sequence.

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

Proof. By induction on $m$ . For $m=1$ , we have $a_{1},b_{1}$ both realizing $p|A$ . Then clearly $a_{1}\equiv _{A}b_{1}$ . Suppose all Morley sequences of length $m-1$ have the same type over $A$ . Let $a_{1},\ldots ,a_{m}$ and $b_{1},\ldots ,b_{m}$ be two Morley sequences of length $M$ . By the inductive hypothesis, we can find $\sigma \in \operatorname {Aut} (\mathbb {U} /A)$ such that $\sigma (b_{i})=a_{i}$ for $i<m$ . Now $b_{m}$ realizes $p|Ab_{1}b_{2}\cdots b_{m-1}$ , so $\sigma (b_{m})$ realizes $\sigma (p)|Aa_{1}\cdots a_{m-1}$ . Since $p$ is $\operatorname {Aut} (\mathbb {U} /A)$ -invariant, $\sigma (b_{m})$ really realizes $p|Aa_{1}\cdots a_{m-1}$ , which is the same type that $a_{m}$ realizes. Thus $a_{m}\equiv _{Aa_{1}\cdots a_{m-1}}\sigma (b_{m})$ or equivalently $a_{1}a_{2}\cdots a_{m}\equiv _{A}a_{1}a_{2}\cdots a_{m-1}\sigma (b_{m})=\sigma (b_{1}b_{2}\cdots b_{m}).$ Since $\sigma (b_{1}b_{2}\cdots b_{m})\equiv _{A}b_{1}b_{2}\cdots b_{m}$ we conclude that $a_{1}\cdots a_{m}$ and $b_{1}\cdots b_{m}$ have the same type over $A$ . QED

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

Proof. Let $\langle a_{i}\rangle _{i\in I}$ be a Morley sequence. It suffices to show that any two finite subsequences of the same length have the same type over $A$ . Since they are both Morley sequences, this follows from the previous lemma. QED

Lemma 7. Let $\langle a_{i}\rangle _{i\in I}$ be an infinite Morley sequence for $p$ . Let $q(x)$ be the set of all formulas $\phi (x;b)$ (with $b$ from $\mathbb {U}$ ) such that $\mathbb {U} \models \phi (a_{i};b)$ for all but at most finitely many values of $i$ . Then $q(x)$ is a consistent global type, which is definable (over some small set, not necessarily $A$ ). The type $q$ is called the average type of $\langle a_{i}\rangle _{i\in I}$ .

Proof. By the previous lemma, $\langle a_{i}\rangle _{i\in I}$ is totally indiscernible over $A$ , hence over $\emptyset$ . Therefore, by Lemma 6, we know that for every $\mathbb {U}$ -formula $\phi (x;b)$ , either $\phi (a_{i};b)$ holds for almost all $i$ , or $\neg \phi (a_{i};b)$ holds for almost all $i$ .

First we check that $q(x)$ is consistent. If not, then there exist $\mathbb {U}$ -formulas $\phi _{1}(x),\ldots ,\phi _{n}(x)$ in $q(x)$ which are jointly inconsistent. But for each $1\leq j\leq n$ , at most finitely many $a_{i}$ fail to satisfy $\phi _{j}(x)$ . Therefore, at most finitely many $a_{i}$ fail to satisfy $\bigwedge _{j=1}^{n}\phi _{j}(x)$ . Since $I$ is infinite, at least one $i$ satisfies $\bigwedge _{j=1}^{n}\phi _{j}(x)$ . So $q(x)$ is consistent.

Lemma 6 ensures that $q(x)$ is complete, i.e., that $\phi (x)$ or $\neg \phi (x)$ is in $q(x)$ for every $\mathbb {U}$ -formula $\phi (x)$ .

Definability comes from the number $N$ in Lemma 6. Specifically, for each formula $\phi (x;y)$ we need to show that $\{b\in \mathbb {U} :\phi (x;b)\in q(x)\}$ is definable. Lemma 6 gives us a number $N=N_{\phi }$ depending on $\phi$ (but not on $b$ ) such that for every $b$ , either

$\mathbb {U} \models \phi (a_{i};b)$ for all but at most $N_{\phi }$ values of $i$ , in which case $\phi (x;b)\in q(x)$ ; OR
$\mathbb {U} \models \phi (a_{i};b)$ for no more than $N_{\phi }$ values of $i$ , in which case $\neg \phi (x;b)\in q(x)$ .

Consequently, we can determine whether $\phi (x;b)$ belongs in $q(x)$ by checking $\phi (a_{i};b)$ for $2N_{\phi }+1$ values of $i$ , and doing a majority vote. If $i_{1},\ldots ,i_{2N_{\phi }+1}$ are $2N_{\phi }+1$ distinct values of $i$ , then we get $\phi (x;b)\in q(x)\iff \mathbb {U} \models \bigvee _{S\subset 2N_{\phi }+1,~|S|\geq N_{\phi }+1}\bigwedge _{i\in S}\phi (a_{i};b),$ and so $\bigvee _{S\subset 2N_{\phi }+1,~|S|\geq N_{\phi }+1}\bigwedge _{i\in S}\phi (a_{i};x)$ is the $\phi$ -definition of $q$ . 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 $\phi (x;y)$ with $x$ of length $n$ has the order property, and that $p(x)$ is a global $n$ -type which is $A$ -invariant.

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

Proof. Let $q'$ and $q$ be the average types of $I'$ and $I$ . If $\phi (x)\in q'(x)$ , then $\phi (a)$ holds for all but finitely many $a$ in $I'$ . In particular, $\phi (a)$ also holds for all but finitely many $a$ in $I$ , so $\phi (x)\in q(x)$ . Thus $q'\subset q$ . Since $q'$ and $q$ are complete types, they must be equal. QED

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

Proof. Recursively build a sequence $a_{1},a_{2},\ldots$ by letting $a_{i}$ realize $p$ restricted to $A\cup I\cup I'\cup \{a_{j}:j<i\}$ . Let $J$ be the sequence of all the $a_{i}$ ’s. Then the concatenations $IJ$ and $I'J$ are Morley sequences. By the previous lemma, $Av(I)=Av(IJ)=Av(J)=Av(I'J)=Av(I')$ , where $Av(I)$ denotes the average type of a Morley sequence $I$ . QED

So there is a unique global type $q(x)$ which is the average type of any Morley sequence of $p(x)$ .

Lemma 8. $q=p$

Proof. Let $\phi (x;b)$ be a formula in $p(x)$ . We will show that $\phi (x;b)\in q(x)$ . This suffices because $p(x)$ and $q(x)$ are complete types (over the monster). Let $a_{1},a_{2},\ldots$ be a sequence built up recursively by letting $a_{i}$ realize the restriction of $p$ to $Ab\cup \{a_{j}:j<i\}$ . Then $a_{1},a_{2},\ldots$ is a Morley sequence for $p$ . The formula $\phi (x;b)$ is in the restriction of $p$ to $Ab$ , so $a_{i}$ satisfies it for every $i$ . That is, $\phi (a_{i};b)$ holds for every $i$ . It follows that $\phi (x;b)$ is in the average type of $a_{1},a_{2},\ldots$ , but this average type is $q(x)$ . QED

Combining this with Lemma 7, we get

Lemma 9. Suppose that no formula $\phi (x;y)$ with $x$ of length $n$ has the order property. Let $p(x)$ be a global $n$ -type. Suppose that $p(x)$ is $A$ -invariant for some small set $A$ . Then $p$ is $A$ -definable, i.e., for every formula $\phi (x;y)$ the set $\{b\in \mathbb {U} :\phi (x;b)\in p(x)\}$ is an $A$ -definable subset of $\mathbb {U}$ .

Proof. Lemma 8, $p$ is the average type of any Morley sequence. By Lemma 7, it follows that $p$ is definable over some set. So for each formula $\phi (x;y)$ , the set $\{b\in \mathbb {U} :\phi (x;b)\in p(x)\}$ is definable. But it is also $\operatorname {Aut} (\mathbb {U} /A)$ -invariant, so it must be $A$ -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 $\phi (x;y)$ with $x$ of length $n$ has the order property. Then every $n$ -type $p(x)$ over a model $M$ is $M$ -definable.

Proof. Let $\Sigma (x)$ be the global partial type which consists of all formulas of the form $\phi (x;b)\leftrightarrow \phi (x;c)$ for $b\equiv _{M}c$ . Note that any element of $M$ satisfies $\Sigma (x)$ . If $p_{0}(x)$ is a finite subset of $p(x)$ , then $p_{0}(x)$ is satisfiable in $M$ , hence so is $p_{0}(x)\cup \Sigma (x)$ . It follows that $p(x)\cup \Sigma (x)$ is consistent. Let $p'(x)$ be a global type extending $p(x)\cup \Sigma (x)$ . Then whenever $b\equiv _{M}c$ , we have $\phi (x;b)\in p'(x)\iff \phi (x;c)\in p'(x).$ Therefore $p'(x)$ is $\operatorname {Aut} (\mathbb {U} /M)$ -invariant, hence $M$ -definable by Lemma 9. But $p(x)$ is the restriction of $p'(x)$ from $\mathbb {U}$ to $M$ , so it is also $M$ -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): $T$ is $\kappa$ -stable for all $\kappa \geq |T|$ with $\kappa ^{|T|}=\kappa$ .
(b'): same as (c) but for 1-types rather than n-types
(c): $T$ is $\kappa$ -stable for some $\kappa$ .
(c'): same as (d) but for 1-types rather than n-types
(d): No formula $\phi (x;y)$ has the order property.
(d’): No formula $\phi (x;y)$ with $x$ 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: $(c)\implies (d)\implies (d')\implies (a')\implies (b')\iff (b)$ $(c)\implies (d)\implies (a)\implies (a')\implies (b')\iff (b)$ From left to right:

(c) $\implies$ (d) is by Lemma 4.
(d) $\implies$ (d') is obvious.
(d) $\implies$ (a) is by Lemma 10.
(d') $\implies$ (a') is by Lemma 10.
(a) $\implies$ (a') is obvious.
(a') $\implies$ (b') is by Lemma 1.

It remains to show that (b) $\implies$ (c). Suppose $T$ is $\kappa$ -stable for every $\kappa \geq |T|$ such that $\kappa ^{|T|}=\kappa$ . Let $\kappa =2^{|T|}$ . Then $\kappa ^{|T|}=2^{|T|^{2}}=2^{|T|}=\kappa$ , so $T$ is $\kappa$ -stable. In particular, $T$ is $\kappa$ -stable for at least one $\kappa$ . QED

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

Additional equivalent conditions[]

At this point, one easy equivalence is:

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

Proof. If $T$ is stable, then for every $n$ , no formula $\phi (x;y)$ with $x$ of length $n$ has the order property. By Lemma 5, every indiscernible sequence is totally indiscernible. Conversely, suppose that $T$ is not stable. Then some formula $\phi (x;y)$ has the order property. Let $a_{i},b_{i}$ for $i<\omega$ witness this, so that $\phi (a_{i};b_{j})$ holds if and only if $i<j$ . Let $\langle c_{i}d_{i}\rangle _{i<\omega }$ be an indiscernible sequence extracted from $\langle a_{i}b_{i}\rangle _{i<\omega }$ . Then $\phi (c_{i};d_{j})$ holds if and only if $i<j$ , because this was expressed in the Ehrenfeucht-Mostowski type of $\langle a_{i}b_{i}\rangle _{i<\omega }$ . But now $\phi (c_{2};d_{3})$ holds and $\phi (c_{2};d_{1})$ does not, indicating that $(c_{2}d_{2},c_{3}d_{3})$ and $(c_{2}d_{2},c_{1}d_{1})$ do not have the same type, so the sequence $\langle c_{i}d_{i}\rangle _{i<\omega }$ is not totally indiscernible, in spite of being indiscernible. QED

Lemma. Let $T$ be a countable stable theory, and $\phi (x;y)$ be a formula. Then over any countable set $A$ , there are at most countably many $\phi$ -types.

Proof. Since $T$ is countable, by Löwenheim-Skolem we can find a countable model $M$ containing $A$ . Then $S_{\phi }(M)$ surjects onto $S_{\phi }(A)$ , so it suffices to show that $S_{\phi }(M)$ is countable. If $p\in S_{\phi }(M)$ , we can extend $p$ to a complete type $p'\in S(M)$ . The type $p'$ is $M$ -definable, by stability. Let $\psi (y;m)$ be the $\phi$ -definition of $p'$ , with $m$ a tuple from $M$ . Then for $b\in M$ , $\phi (x;b)\in p(x)\iff \phi (x;b)\in p'(x)\iff \models \psi (b;m).$ The $\phi$ -type $p(x)$ is therefore determined by the formula $\psi (y;m)$ . Since $T$ and $M$ are countable, there are only countably many possibilities for $\psi (y;m)$ . Hence there are only countably many possibilities for $p$ . 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. $T$ is stable if and only if the following holds: for every formula $\phi (x;y)$ and every countable set, $A$ , the space of $\phi$ -types $S_{\phi }(A)$ is countable.

Proof. Suppose $T$ is stable. Then we can find a countable reduct $T'$ of $T$ in which $\phi (x;y)$ is still definable. The space of $\phi$ -types of $A$ is the same after passing to this reduct, so it is countable.

Conversely, suppose that $T$ is unstable. Let $\phi (x;y)$ be a formula having the order property, witnessed by $a_{i},b_{i}$ . Extract an indiscernible sequence $\langle c_{i}d_{i}\rangle _{i\in \mathbb {Q} }$ of length $\mathbb {Q}$ from $a_{1}b_{1},a_{2}b_{2},\ldots$ . So $\phi (c_{x};d_{y})$ holds if and only if $x\leq y$ . By compactness, for each real number $r\in \mathbb {R}$ , we can find a $d_{r}$ such that $x<r\iff \models \phi (c_{x};d_{r})$ Then each $d_{r}$ has a distinct $\phi$ -type over the countable set $\{c_{x}:x\in \mathbb {Q} \}$ , so there are uncountably many $\phi$ -types over this set. QED

[Cantor-Bendixson Rank in the space of $\phi$ -types]{#Cantor-Bendixson_Rank_in_the_space_of_‘"`UNIQ--postMath-000002A5-QINU`"’-types .mw-headline}[]

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

$S(B)$ has Cantor-Bendixson rank $\infty$
$S(B)$ contains a perfect set
There exist $b_{w}\in B$ for $w\in \{0,1\}^{<\omega }$ such that $b_{w}\neq 0$ for each $w$ and such that $b_{w0}\cap b_{w1}=0$ and $b_{w0}\cup b_{w1}=b_{w}$ for each $w$ .

The first two conditions are equivalent essentially by definition of Cantor-Bendixson rank. If a perfect set $P\subset S(B)$ exists, then we can inductively choose $b,b_{0},b_{1},b_{00},\ldots$ as follows:

Take $b$ to be any clopen set in $S(B)$ intersecting $P$ .
Given $b_{w}$ intersecting $P$ , the set $P\cap b_{w}$ is still perfect, and hence contains at least two points $x_{0},x_{1}$ . If $U$ is a clopen neighborhood containing $x_{0}$ and not $x_{1}$ , then let $b_{w0}=b_{w}\cap U$ and $b_{w1}=b_{w}\setminus U$ .

Then each $b_{w}$ intersects $P$ , hence is non-empty.

Conversely, given $b_{w}\neq 0$ such that $b_{w0}\cap b_{w1}=0$ and $b_{w0}\cup b_{w1}=b_{w}$ , the Cantor-Bendixson rank must be $\infty$ . If not, then for each $w$ , we can find a $w'\in \{w0,w1\}$ such that $b_{w'}$ has lower CB rank than $b_{w}$ , or has the same rank and lower degree. In this way, we obtain a sequence $b_{w},b_{w'},b_{w''},\ldots$ with descending $rank\cdot \omega +degree$ . But there are no infinite descending sequences of ordinal numbers.

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

Now suppose that $T$ is a stable theory, $\mathbb {U}$ is a monster model of $T$ , and $\phi (x;y)$ is a formula. Let $B$ be the boolean algebra generated by $\phi$ -formulas over $\mathbb {U}$ , so $S_{\phi }(\mathbb {U} )=S(B)$ . Then $B$ is stable. If not, then some countable subalgebra $B_{0}\subset B$ is unstable. Then $B_{0}$ consists of boolean combinations of $\phi$ -formulas over some countable set of parameters $A$ . If $B_{1}$ is the boolean algebra generated by all $\phi$ -formulas over $A$ , then $B_{0}\subset B_{1}\subset B$ , and $B_{1}$ is unstable. That is, $S(B_{1})=S_{\phi }(A)$ contains a perfect set. But then $S_{\phi }(A)$ is uncountable (by the Cantor-Bendixson theorem), contradicting one of our criteria for stability in the previous section.

Since $B$ is stable, we see that $S_{\phi }(\mathbb {U} )$ has Cantor-Bendixson rank less than $\infty$ , or equivalently, contains no perfect set. The same holds for $S_{\phi }(A)$ for any subset $A\subset \mathbb {U}$ .

Conversely, if $T$ is a theory such that $S_{\phi }(A)$ contains no perfect set for any $A\subset \mathbb {U}$ and formula $\phi (x;y)$ , then $T$ is stable. Indeed, since $S_{\phi }(A)$ is a Polish space for countable $A$ , $S_{\phi }(A)$ must be countable by the Cantor-Bendixson theorem, and therefore $T$ is stable. So we have proven:

Theorem. A theory $T$ is stable if and only if $S_{\phi }(A)$ contains no perfect set, for every set $A$ and formula $\phi (x;y)$ .

Definability of types over arbitrary sets[]

Lemma. Assume $T$ is stable. Let $A$ be a small subset of $\mathbb {U}$ , $p(x)$ be a complete type over $A$ , and $\phi (x;y)$ be a formula. Then there exists a global $\phi$ -type $q(x)\in S_{\phi }(\mathbb {U} )$ which is consistent with $p(x)$ and which has finite orbit under $\operatorname {Aut} (\mathbb {U} /A)$ .

Proof. Let $X\subset S_{\phi }(\mathbb {U} )$ be the closed subset of $S_{\phi }(\mathbb {U} )$ consisting of the global $\phi$ -types which are consistent with $p$ . By stability, $S_{\phi }(\mathbb {U} )$ contains no perfect set; therefore neither does $X$ . The boolean space $X$ therefore has Cantor-Bendixson rank less than $\infty$ . Let $q$ be any point in $X$ with maximal Cantor-Bendixson rank. If $\sigma \in \operatorname {Aut} (\mathbb {U} /A)$ , then by symmetry, $\sigma (q)$ is another point of maximal Cantor-Bendixson rank. But there are only finitely many points of maximal Cantor-Bendixson rank in $X$ . So $q$ has finitely many conjugates. QED

Theorem. A theory $T$ 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 $T$ is stable.

Conversely, suppose $T$ is stable, and $A$ is a set. Let $p(x)$ be a complete type over $A$ . Let $\phi (x;y)$ be a formula. Let $q(x)$ be a complete $\phi$ -type over $\mathbb {U}$ extending $p$ , with finitely many conjugates over $A$ . Then $q(x)$ is definable, so there is some $\mathbb {U}$ -definable set $D$ such that for all $a$ , $\phi (x;a)\in q(x)\iff a\in D.$ Now if $a\in A$ and $\sigma \in \operatorname {Aut} (\mathbb {U} /A)$ , then $\phi (x;a)\in p(x)\iff \phi (x;\sigma (a))\in q(x)\iff \phi (x;a)\in \sigma (q)\iff a\in \sigma (D).$ Since $q$ has finitely many conjugates over $A$ , so does $D$ . If $D'$ is the intersection of all the conjugates of $D$ , then $D'$ is a definable set, which is $A$ -invariant, hence $A$ -definable. And for $a\in A$ , $\phi (x;a)\in p(x)\iff a\in D'$ . So $p(x)$ has a $\phi$ -definition. As $\phi$ was arbitrary, $p(x)$ is $A$ -definable. QED

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

Theorem. Assume $T$ is stable. Let $D$ be a definable set (over some parameters). Then $D$ is stably embedded, i.e., if $D'$ is a definable subset of $D^{n}$ for some $n$ , then $D'\cap D^{n}=D''\cap D^{n}$ for some $D''$ definable over parameters from $D$ .

Proof. Let $D'$ be cut out by a formula $\phi (b;y)$ , with $b$ some element from the monster. The type of $b$ over $D(\mathbb {U} )$ is definable over $D(\mathbb {U} )$ . In particular, for the formula $\phi (x;y)$ , there is some $D(\mathbb {U} )$ -formula $\psi (z)$ such that for every $a$ from $D(\mathbb {U} )$ , we have $a\in D'\iff \models \phi (b;a)\iff \phi (x;a)\in \operatorname {tp} (b/D(\mathbb {U} ))\iff \models \psi (a).$ So if $D''$ is the set cut out by $\psi (z)$ , then $a\in D'\iff a\in D''$ . This holds for $a\in D^{n}$ , so $D'\cap D^{n}=D''\cap D^{n}$ , where $D''=\psi (\mathbb {U} )$ is definable with parameters from $D(\mathbb {U} )$ . QED ::: ::: :::