Spencinar: Morley's categoricity theorem, part 1

Unfortunately, I missed posting about some interesting lectures given at the Very Informal Gathering, and the Southern California logic meeting at Caltech. We'll return with this series of posts following Spencer Unger's talks at the first two seminars of the quarter. There may be a larger amount of errors than usual in my transcription because of my limited knowledge of model theory. Basic model theory will be helpful to follow these notes, but I'll do my best to fill in the definitions. The notation follows Marker's text closely.

A general question is:
Given a first order theory $T$, what can we say about the number of non-isomorphic models of $T$ of size $\lambda$, as $\lambda$ varies through the cardinals?

This is addressed by Shelah's classification theory. Historically, the first step was Morley's categoricity theorem (1965) which states:

• If $T$ is a first-order theory in a countable language and $T$ is categorical in some uncountable cardinal, then it is categorical in all uncountable cardinals.

The proof of this theorem, which was the content of the lectures, involves the ideas of stability, indiscernibles, saturated models, and splitting types. It's somewhat different from the one I recall from the basic model theory class I took many years ago.

To begin with, we can define a rank $R$ on sets of formulas (i.e., types) with parameters in some large saturated model $\mathcal{C}$ (the "monster model"). Let $p$ be a set of formulas. Then, working in $\mathcal{C}$,

• $R(p)=-1$ if $p$ is not satisfiable.
• $R(p)\ge 0$ if $p$ is satisfiable.
• $R(p)\ge \alpha+1$ if for any finite $p_0\subseteq p$, there is a formula $\psi$ such that $R(p_0\cup\{\psi\})\ge \alpha$ and $R(p\cup\{\neg \psi\})\ge \alpha$.

The rank $R(p)$ is then defined inductively to be the minimum value so that all of the above conditions are satisfied. Note: this isn't what is known as Morley rank. Andrew Marks noticed that this rank is the Cantor-Bendixson rank on the Stone space of complete types.

Some properties of the rank:

• (Monotonicity) If $p\vdash q$ then $R(p)\le R(q)$.
• (Finite character) For every $p$, there is a finite $p_0\subseteq p$ so that $R(p)=R(p_0)$. 
• Proof: If $R(p)=\alpha$, there is a finite $p_0$ witnessing $R(p)\not\ge \alpha+1$, and monotonicity gives the reverse inequality.
• (Invariance) If $f$ is an automorphism of $\mathcal{C}$, then $R(p)=R(f(p))$.
• Proof is by induction on the rank.

Definition: $T$ is $\lambda$-stable if for any $A\subseteq C$ of size $\lambda$, $|S^n(A)|\le \lambda$. Here $S^n(A)$ is the set of complete $n$-types over $A$, that is, maximal satisfiable sets of formulas with parameters over $A$ and free variables $x_1,\ldots, x_n$.

Theorem: Let $T$ be a theory in a countable language. Then $T$ is $\aleph_0$-stable iff $R(\{\bar{x}=\bar{x}\})<\infty$, i.e., has some ordinal value. In fact, if these equivalent conditions hold, then $R(\{\bar{x}=\bar{x}\})<\omega_1$.

Proof: Suppose $R(\{\bar{x}=\bar{x}\})\ge \omega_1$. We will inductively construct a complete binary tree whose nodes are finite sets of formulas $p_\eta$ for $\eta\in 2^{<\omega}$ and whose branches will give $2^{\aleph_0}$ many different complete types, contradicting stability. For the construction, we will maintain that $R(p_\eta)\ge\omega_1$.

Let $p_\emptyset=\{\bar{x}=\bar{x}\}$. Given $p_\eta$, there are formulas $\psi_{\eta,i}(\bar{x},\bar{a}_{\eta,i})$ for each $i<\omega_1$ witnessing that $R(p_\eta)\ge i+1$. Using the fact that the language of $T$  is countable together with $\aleph_0$-stability, there are $\psi$ and $t$ so that for an unbounded set of $i<\omega_1$, $\psi=\psi_{\eta,i}$ and $t=\mathrm{tp}(\bar{a}_{\eta,i})$ (the set of all formulas satisfied by $\bar{a}_{\eta,i}$, over the finitely many parameters in $p_\eta$). Pick $a_\eta$ realizing $t$. Then define 

• $p_{\eta\circ 0}=p_\eta\cup\{\psi(\bar{x},\bar{a}_\eta)\}$
• $p_{\eta\circ 1}=p_\eta\cup\{\neg\psi(\bar{x},\bar{a}_\eta)\}$

Using invariance of rank under automorphisms and the fact that in $\mathcal{C}$ for any two tuples realizing the same type there exists an automorphism sending one to the other, the ranks of these sets of formulas are at least $i$ for an unbounded set of $i<\omega_1$, so they must be $\ge\omega_1$, allowing the construction to continue. The branches of the tree we construct can be extended to complete types, and the construction ensures that each of these complete types is distinct (for two different branches, look at the first place of disagreement).

For the converse, assume $R(\bar{x}=\bar{x})<\infty$ and $T$ is not stable. Then there are $A\subseteq \mathcal{C}$, $|A|\le \lambda$ such that there are distinct $\{p_i:i<\lambda^+\}\subseteq S^n(A)$. By assumption, for any $i<\lambda^+$, there is $\alpha_i$ so that $R(p_i)=\alpha_i$. By finite character, there is $q_i\subseteq p_i$ finite with $R(q_i)=R(p_i)=\alpha_i$. By counting, $|\{q_i:i<\lambda^+\}|\le \omega$. Let $i\neq j$ be such that $q_i=q_j$, so $p_i,p_j$ are different completions of $q_i=q_j$. This means there is a formula $\psi$ with $\neg\psi\in p_i$ and $\psi\in p_j$. This gives $R(q_j)\ge R(p_j)+1$, a contradiction to the choice of $q_j$. $\Box$.