数学 On Model Theory

Stability theory is the most important part of model theory, which was studied by Saharon Shelah.

Without special explanation, we let $T$ be a complete countable $L$-theory that has infinite models. $\mathcal{M}$ denotes the monster model and its universe of $T$. $\kappa,\lambda$ are used to denote infinite cardinals.

Definition and Results

We say the theory $T$ is $\kappa$-stable (or stable in $\kappa$) if for any subset $A\subset\mathcal{M}$,

$$|A|\le\kappa\Rightarrow|S(A)|\le\kappa.$$

It is called stable if there is a cardinal where it is stable, and it’s called superstable if there is a cardinal $\kappa$ such that for all $\lambda>\kappa$, $T$ is $\lambda$-stable. A structure $\mathfrak{M}$ is called $\kappa$-stable if $\mathrm{Th}(\mathfrak{M})$ is $\kappa$-stable.

The definition can be replaced by a $1$-type version, which is to say that a theory $T$ is $\kappa$-stable if for any subset $A\subset\mathcal{M}$, $|A|\le\kappa\Rightarrow|S_1(A)|\le\kappa$. To show this, we suppose the alternative definition holds but the original definition fails. Since $S(A)=\bigcup_{i\in\omega}S_i(A)$, there must be some $i$ such that $|S_i(A)|>\kappa$. If $i=1$, then the contradiction completes the proof. Otherwise, we can find without loss of generality that $|S_i(A)|>\kappa$ but $|S_{i-1}(A)|\le\kappa$. Now, for a $p(x_1,\ldots,x_i)\in S_i(A)$, we can define $p^*(x_1,\ldots,x_{i-1})=\{\exists x_i\varphi(x_1,\ldots,x_i); \varphi\in p\}$. Consider an arbitrary $\Gamma\subset S_i(A)$ such that $|\Gamma|>\kappa$. By the Pigeonhole principle, there is a $q\in S_{i-1}(A)$ such that

$$|\{p\in\Gamma\mid p^*\subset q\}|>\kappa.$$

Finally, we choose a solution $a_1,\ldots,a_{i-1}\in\mathcal{M}$ of $q$. For each $p\in\Gamma$, $p(a_1,\ldots,a_{i-1},x_i)$ defines a $1$-type on $A\cup\{a_1,\ldots,a_{i-1}\}$. By choosing a formula $\varphi\in p_1$ while $\neg\varphi\in p_2$, we can find out that if $p_1\neq p_2$, then $p_1(a_1,\ldots,a_{i-1},x_i)\neq p_2(a_1,\ldots,a_{i-1},x_i)$. Hence,

$$|S_1(A\cup\{a_1,\ldots,a_{i-1}\})|=|\Gamma|>\kappa,$$

which contradicts the assumption that for any subset $A\subset\mathcal{M}$, $|A|\le\kappa\Rightarrow|S_1(A)|\le\kappa$.

If you read the definitions carefully, you must be confused why there isn’t a definition that a theory is stable for all cardinals. The following theorem explains.

($\omega$-Stable) If the theory $T$ is $\omega$-stable, then it is $\kappa$-stable for any $\kappa$.

The proof of this theorem is quite complex, so it is omitted here by the low cost-performance ratio. But one should realize the relation between these stabilities.

$$\omega\text{-stable}\Rightarrow\text{superstable}\Rightarrow\text{stable}$$

Such property is so strong that a lot of properties can be deduced directly from it. Let me show one. If the theory $T$ is $\omega$-stable, then there is a countable model $\mathfrak{A}$ which is saturated.

To prove this, we choose an arbitrary countable model $\mathfrak{M}_0$, then construct a chain of elementary extensions inductively. Suppose $\mathfrak{M}_i$ is constructed and it is countable. Since $T$ is $\omega$-stable, then the set $S=\bigcup\{S(A); A\text{ is a finite subset of }M_i\}$ is countable. Then for each $p\in S$, we introduce some irrelevant constants $\bar a_p\in\mathcal{M}$ to satisfy $p$. Now the set $M_i\cup\{\bar a_p\}$ is countable. By the Löwenheim-Skolem theorem, there is a countable elementary extension $\mathfrak{M}_{i+1}$ of $\mathfrak{M}_i$. Finally, we take $\mathfrak{A}=\bigcup_{i\in\omega}\mathfrak{M}_i$. By Tarski’s chain lemma, it is an elementary extension of $\mathfrak{M}_0$, and you might see that it is $\omega$-saturated, which is saturated by definition.

Definability

To characterize stability, it’s easy for us to think of the characterization of types. Stability is nothing more than “the types won’t ‘split’ into too many pieces”, therefore we need a way to describe types. It is the definability of a type $p(x)$.

Given a set $B$ of tuples of constants, we say it is definable on $A_0\subset A\subset\mathcal{M}$ if there is a formula $\theta(\bar x)\in L(A_0)$ such that

$$\bar b\in B\Leftrightarrow\mathcal{M}\models\theta(\bar b).$$

Now consider a type $p(\bar x)\in S(A)$. We may consider whether an $L(A)$-formula $\varphi(\bar x)\in p(\bar x)$. We may detach all parameters from it, and then it is degenerated to an $L$-formula $\psi(\bar x,\bar y)$. Consider the set

$$B=\{\bar b\in A\mid \psi(\bar x,\bar b)\in p(\bar x)\}.$$

If it is definable on $A_0$, we say $\psi(\bar x,\bar y)$ is definable on $A_0$. If every $L$-formula $\psi(\bar x,\bar y)$ is definable on $A_0$, then we say the $L(A)$-formula is definable on $A_0$.

Refining the definition: let $A_0\subset A$. The type $p(\bar x)\in S(A)$ is definable on $A_0$ if for all formulas $\varphi(\bar x,\bar y)$, there is an $L(A_0)$-formula $\theta_\varphi(\bar y)$ such that

$$\forall\bar a\in A,\quad\varphi(\bar x,\bar a)\in p(\bar x)\Leftrightarrow\mathcal{M}\models\theta_\varphi(\bar a).$$

If we take $A_0=A$, we simply say $p$ is definable.

(Char.A) If every type is definable, then $T$ is a stable theory.

This proof is easy. Take $\lambda$ to be a cardinal such that $\lambda^\omega=\lambda$ (for example, $2^\omega$). We can prove that $T$ is $\lambda$-stable. For an arbitrary type $p(\bar x)$ on set $A\subset\mathcal{M}$ where $|A|\le\lambda$ and $L$-formula $\varphi(\bar x,\bar y)$, we can define the set

$$p|\varphi=\{\varphi(\bar x,\bar a)\mid \bar a\in\mathcal{M},\varphi(\bar x,\bar a)\in p\}\cup\{\neg\varphi(\bar x,\bar a)\mid \bar a\in\mathcal{M},\neg\varphi(\bar x,\bar a)\in p\}.$$

Since $\varphi$ is definable on $A$, we can rewrite $p|\varphi$ by the corresponding $L(A)$-formula $\theta_\varphi(\bar y)$ as

$$p|\varphi=\{\varphi(\bar x,\bar a)\mid \bar a\in\mathcal{M},\mathcal{M}\models\theta_\varphi(\bar a)\}\cup\{\neg\varphi(\bar x,\bar a)\mid \bar a\in\mathcal{M},\mathcal{M}\not\models\theta_\varphi(\bar a)\}.$$

Now, $|S(A)|\le(|L|+|A|+\omega)^{|L|+\omega}=\lambda^\omega=\lambda$. Hence $T$ is stable.

Binary Tree

The set $p|\varphi$ points out how we actually see a type. The formula $\theta_\varphi(\bar y)$ actually gives a $0$/$1$ criterion to a sequence of parameters $\bar a_i,i<\omega$. If there are only finitely many boolean patterns for parameters, we will find the type is definable easily. Therefore, it’s necessary to study this.

Think. Given a set of formulas $\Sigma(\bar x)$ and a formula $\varphi(\bar x,\bar y)$, a binary tree gives the possibilities of boolean values of given parameters of $\bar y$ and the result of adding each layer into $\Sigma$ to make it a type.

$$\Sigma(\bar x) \left\{\begin{matrix} \varphi(\bar x,\bar y_\emptyset) \left\{\begin{matrix} \varphi(\bar x,\bar y_{0})\left\{\begin{matrix} \varphi(\bar x,\bar y_{00})\cdots x_{000}\text{ is the solution of this branch}\\ \neg\varphi(\bar x,\bar y_{01})\cdots x_{001}\text{ is the solution of this branch}\\ \end{matrix}\right.\\ \neg\varphi(\bar x,\bar y_{1})\left\{\begin{matrix} \varphi(\bar x,\bar y_{10})\cdots x_{010}\text{ is the solution of this branch}\\ \neg\varphi(\bar x,\bar y_{11})\cdots x_{011}\text{ is the solution of this branch}\\ \end{matrix}\right.\\ \end{matrix}\right. \\ \neg\varphi(\bar x,\bar y_\emptyset) \left\{\begin{matrix} \varphi(\bar x, \bar y_{0})\left\{\begin{matrix} \varphi(\bar x,\bar y_{00})\cdots x_{100}\text{ is the solution of this branch}\\ \neg\varphi(\bar x,\bar y_{01})\cdots x_{101}\text{ is the solution of this branch}\\ \end{matrix}\right.\\ \neg\varphi(\bar x,\bar y_{1})\left\{\begin{matrix} \varphi(\bar x,\bar y_{10})\cdots x_{110}\text{ is the solution of this branch}\\ \neg\varphi(\bar x,\bar y_{11})\cdots x_{111}\text{ is the solution of this branch}\\ \end{matrix}\right.\\ \end{matrix}\right. \end{matrix}\right.$$

Formalizing such idea, we get the following definition.

Let $\Sigma(\bar x)$ be a satisfiable set of $L(\mathcal{M})$-formulas, and $\varphi(\bar x,\bar y)$ be an $L$-formula. For each $n\in\omega$, consider a set of variables

$$\{\bar x_\nu\mid \nu\in{}^n2\}\cup\{\bar y_\eta\mid \eta\in{}^{n>}2\}.$$

$\Sigma_n$ is the union of the following sets, which is the $n$-th layer of the binary tree:

1. $\bigcup_{\nu\in{}^n2}\Sigma(\bar x_\nu)$,
2. $\{\varphi(\bar x_\nu,\bar y_{\nu|k}); \nu\in{}^n2,k<n,\nu(k)=0\}$,
3. $\{\neg\varphi(\bar x_\nu,\bar y_{\nu|k}); \nu\in{}^n2,k<n,\nu(k)=1\}$.

We call $\Sigma_n$ the $\varphi$-binary tree with height $n$ from $\Sigma$. In the case when $\Sigma$ is empty, we simply say it’s a $\varphi$-tree with height $n$.

The greatest $n$ that makes $\Sigma_n$ satisfiable is written as $\operatorname{R}(\Sigma,\varphi,2)=n$, called the $(\varphi,2)$-rank of $\Sigma$. If there is no greatest one, we simply write $\omega$.

A simple fact is that when $\Gamma\subset\Sigma$ are two sets of formulas, $\operatorname{R}(\Gamma,\varphi,2)\ge\operatorname{R}(\Sigma,\varphi,2)$. And you can always find a finite subset $\Pi$ of $\Sigma$ to make $\operatorname{R}(\Pi,\varphi,2)=\operatorname{R}(\Sigma,\varphi,2)$. To show this, think of $\mathcal{M}$ as the monster model which makes any finitely satisfiable set of formulas satisfiable.

By this definition, we have a characterization of definability.

(Char.B) If for each $L$-formula $\varphi(\bar x,\bar y)$, the satisfiable $\varphi$-tree has a finite height, namely $\operatorname{R}(\bar x=\bar x,\varphi,2)<\omega$, then all types $p$ are definable.

Let $p\in S(A)$ be a type and $\varphi(\bar x,\bar y)$ be an $L$-formula. Let $n=\operatorname{R}(p,\varphi,2)<\omega$. Then there is a formula $\psi\in p$ such that $\operatorname{R}(\psi,\varphi,2)=n$.

We claim that for each $\bar a \in A$,

$$\varphi(\bar x,\bar a )\in p\Leftrightarrow\operatorname{R}(\psi(\bar x)\wedge\varphi(\bar x,\bar a),\varphi(\bar x,\bar y),2)\ge n.$$

The $\Rightarrow$ part is obvious. Now assume $\varphi(\bar x,\bar a)\not\in p$. Since $p$ is a type, $\neg\varphi(\bar x,\bar a)\in p$, then $\operatorname{R}(\psi\wedge\neg\varphi(\bar x,\bar a),\varphi,2)\ge n$. At the same time, $\operatorname{R}(\psi(\bar x)\wedge\varphi(\bar x,\bar a),\varphi,2)\ge n$. Now we can insert $\varphi(\bar x,\bar a)$ and $\neg\varphi(\bar x,\bar y)$ in front of the binary tree starting from $\psi$, and this gives a $\varphi$-tree starting from $\psi$ with height $n+1$ and satisfiable. This implies $\operatorname{R}(\psi,\varphi,2)=n+1$, which is a contradiction to the fact that $\operatorname{R}(\psi,\varphi,2)=n$. Hence the $\Leftarrow$ part is proved.

Now, we denote the $\varphi$-tree starting from $\psi\wedge\varphi(\bar x,\bar a)$ as $\Gamma(\bar a)$ with height $n$. Then $\operatorname{R}(\psi(\bar x)\wedge\varphi(\bar x,\bar a),\varphi,2)\ge n$ is equivalent to saying $\mathcal{M}\models\Gamma(\bar a)$. Now take

$$\theta_\varphi(\bar a)=\exists\{\bar x_\nu,\bar y_\eta\mid \nu\in{}^n2,\eta\in{}^{n>}2\}\bigwedge_{\gamma\in\Gamma}\gamma.$$

We have $\varphi(\bar x,\bar a)\in p\Leftrightarrow\theta_\varphi(\bar a)$. Hence $p$ is definable.

Order Property

Order property is an important thing in model theory. We say a theory $T$ has the order property if there is an $L$-formula $\varphi(\bar x,\bar y)$ and a sequence of elements $(\bar a_i)_{i\in\omega}\in\mathcal{M}$ such that

$$i<j\Leftrightarrow\mathcal{M}\models\varphi(a_i,a_j).$$

A simple example is taking $a_i=i$ and letting $\varphi(i,j)$ be $i<j$, which is an order. This definition seems lovely, but unlike most other properties, we actually do not want this property. It may cause chaos in a theory. The following proposition explains.

(Char.C) If $T$ doesn’t have the order property, then every formula $\varphi$ has $\operatorname{R}(\bar x=\bar x,\varphi,2)<\omega$.

We define some temporary notations. Let $X=\{\bar x_\nu; \nu\in{}^\omega2\}$, $Y=\{\bar y_\eta; \eta\in{}^{\omega>}2\}$, and

$$\Sigma(X,Y)=\{\varphi(\bar x_\nu,\bar y_{\nu|k})\mid \nu\in{}^\omega2,k<\omega,\nu(k)=0\}\cup\{\neg\varphi(\bar x_\nu,\bar y_{\nu|k})\mid \nu\in{}^\omega2,k<\omega,\nu(k)=1\}.$$

Before we give the proof of (Char.C), we give a lemma first. Let $\Gamma(x)$ be a set of $L(A)$-formulas. If $\bigcup_{\nu\in{}^\omega 2}\Gamma(\bar x_\nu)\cup\Sigma(X,Y)$ is satisfiable, then we can find a type $r(\bar y)\in S(A)$ such that $\bigcup_{\nu\in{}^\omega 2}\Gamma(\bar x_\nu)\cup\Sigma(X,Y)\cup\bigcup_{\eta\in{}^{\omega>}2}r(\bar y_\eta)$ is also satisfiable.

Choose a set of constants $D=\{d_\eta\}_{\eta\in{}^{\omega>}2}$ in $\mathcal{M}$ which makes $\bigcup_{\nu\in{}^\omega 2}\Gamma(\bar x_\nu)\cup\Sigma(X,D)$ satisfiable. Now, for each $L(A)$-formula $\psi(\bar y)$, there are only two possibilities:

1. There is an $\eta\in{}^{\omega>}2$ that makes $\{\bar d_\iota; \eta\subset\iota,\mathcal{M}\models\psi(d_\iota)\}$ finite (the tree stops somewhere).
2. For all $\eta\in{}^{\omega>}2$, $\{\bar d_\iota; \eta\subset\iota,\mathcal{M}\models\psi(d_\iota)\}$ is infinite.

If it’s 1, then $\bigcup_{\nu\in{}^\omega 2}\Gamma(\bar x_\nu)\cup\Sigma(X,Y)\cup\{\neg\psi(\bar y_\eta); \eta\in{}^{\omega>}2\}$ is satisfiable. Otherwise, $\bigcup_{\nu\in{}^\omega 2}\Gamma(\bar x_\nu)\cup\Sigma(X,Y)\cup\{\psi(\bar y_\eta); \eta\in{}^{\omega>}2\}$ is satisfiable. Now, if the situation is 1, then we put $\neg\psi(\bar y)$ into $r(\bar y)$; otherwise we put $\psi(\bar y)$ into $r(\bar y)$. By enumeration, type $r(\bar y)$ is constructed. By compactness, $\bigcup_{\nu\in{}^\omega 2}\Gamma(\bar x_\nu)\cup\Sigma(X,Y)\cup\bigcup_{\eta\in{}^{\omega>}2}r(\bar y_\eta)$ is satisfiable.

Now, we prove (Char.C) by contradiction. Assume there is a formula $\varphi$ that has $\operatorname{R}(\bar x=\bar x,\varphi,2)=\omega$.

Since $\Sigma(X,Y)$ is satisfiable, we find solutions $\bar a_0,\bar b_0,\bar b'_0$ to $\bar x_\nu,\bar y_\emptyset,\bar y_0$, where $\nu(0)=0$, $\nu(1)=1$. Intuitively, $\bar a_0$ is the solution of the branch after $\neg\varphi(\bar x,\bar y_1)$, therefore we have $\mathcal{M}\models\varphi(\bar a_0,\bar b_0)\wedge\neg\varphi(\bar a_0,\bar b'_0)$. Hence,

1. $\mathcal{M}\models\varphi(\bar a_0,\bar b_0)\not\leftrightarrow\varphi(\bar a_0,\bar b'_0)$,
2. $\Sigma(X,Y)\cup\{\varphi(\bar x_\nu,\bar b_0)\not\leftrightarrow\varphi(\bar x_\nu,\bar b'_0); \nu\in{}^\omega2\}$ is satisfiable.

Now, we construct sequences of $\bar a_n,\bar b_n,\bar b'_n$ recursively. If the sequences for $i<n$ are already constructed and

1. $\mathcal{M}\models\varphi(\bar a_i,\bar b_j)\leftrightarrow\varphi(\bar a_i,\bar b'_j)\Leftrightarrow i<j$,
2. $\Sigma(X,Y)\cup\{\varphi(\bar x_\nu,\bar b_i)\not\leftrightarrow\varphi(\bar x_\nu,\bar b'_i); \nu\in{}^\omega2\}$ is satisfiable,

then by the lemma, we can construct a type $r(\bar y)$ that makes

$$\Sigma(X,Y)\cup\{\varphi(\bar x_\nu,\bar b_i)\not\leftrightarrow\varphi(\bar x_\nu,\bar b'_i)\mid \nu\in{}^\omega2\}\cup\bigcup_{\eta\in{}^{\omega>}2}r(\bar y_\eta)$$

satisfiable. Now we take solutions $\bar a_{n},\bar b_{n},\bar b'_{n}$ to $\bar x_\nu,\bar y_\emptyset,\bar y_0$. It’s easy to verify that this satisfies the previous two demands. Therefore, $\mathcal{M}\models\varphi(\bar a_i,\bar b_j)\leftrightarrow\varphi(\bar a_i,\bar b'_j)\Leftrightarrow i<j$.

Now, we concatenate the three sequences as one as $c_n=a_n{}^\frown b_n{}^\frown b'_n$, and let

$$\psi(c_i,c_j)=\varphi(c_i|_{a_n},c_j|_{b_n})\leftrightarrow\varphi(c_i|_{a_n},c_j|_{b'_n}).$$

This gives an order property of $T$, which is a contradiction. Hence (Char.C) is proved.

Characterization

(Char.A), (Char.B) and (Char.C) give the sufficiency part of the characterization of stability, but we need more, which is the following theorem.

(Shelah’s Characterization of Stability) The following four are equivalent:

1. $T$ is stable.
2. $T$ doesn’t have the order property.
3. For each $L$-formula $\varphi$, $\operatorname{R}(\bar x=\bar x,\varphi,2)<\omega$.
4. All types $p$ are definable.

The theorems (Char.A), (Char.B) and (Char.C) are 4$\Rightarrow$1, 3$\Rightarrow$4 and 2$\Rightarrow$3 respectively. Now we prove 1$\Rightarrow$2 to complete the loop.

We prove by contraposition. Assume $T$ has the order property, which is given by $\varphi(\bar x,\bar y)$ and $\{\bar a_i\}_{i\in\omega}$.

Let $\kappa$ be an arbitrary cardinal and $\lambda$ be the least cardinal such that $\kappa^\lambda>\kappa$. Take $(D,<)$ to be a dense well-ordering without endpoints where $|D|=\kappa$. Choose a set of constants $\{a_\eta\}_{\eta\in{}^{\lambda>}D}$. There is a lexicographic order on it. Define the set

$$\Sigma=\{\varphi(a_\eta,a_{\eta'})\mid \eta<\eta'\}\cup\{\neg\varphi(a_\eta,a_{\eta'})\mid \eta\ge \eta'\}.$$

It is finitely satisfiable by using $\{a_i\}_{i\in\omega}$. Therefore, it can be satisfied by a set of elements in $\mathcal{M}$ and we simply denote these elements by $\{a_\eta\}_{\eta\in{}^{\lambda>}D}$, which is a harmless abuse of notation. This gives a PRO version of the order property, which means

$$\mathcal{M}\models\varphi(\bar a_\eta,\bar a_{\eta'})\Leftrightarrow\eta<\eta'.$$

Now, for each $\nu\in{}^\lambda D$, we define the set

$$\Gamma_\nu(\bar x)=\{\varphi(\bar x,a_\eta)\mid \eta\in{}^{\lambda>}D,\eta>\nu\}\cup\{\neg\varphi(\bar x,a_\eta)\mid \eta\in{}^{\lambda>}D,\eta<\nu\}.$$

We claim that it is finitely satisfiable. Take arbitrary finitely many indices

$$\eta_1<\cdots<\eta_k<\nu<\eta_{k+1}<\cdots<\eta_n.$$

Since ${}^{\lambda>}D$ is dense, we can find an $\eta_0$ between $\eta_k$ and $\eta_{k+1}$. Then the corresponding finite subset of $\Gamma_\nu(\bar x)$ is satisfiable.

Now, since $\kappa^{<\lambda}=\kappa$ (by the minimality of $\lambda$), we have $|A|=\kappa$ where $A=\{a_\eta; \eta\in{}^{\lambda>}D\}$. For each $\nu\in{}^\lambda D$, $\Gamma_\nu$ can be extended to a type $p_\nu\in S(A)$. Meanwhile, for different $\nu$ and $\nu'$, the corresponding types are different. Therefore, we have $|S(A)|\ge|{}^\lambda D|>\kappa$, which means $T$ is not $\kappa$-stable.

Hence, $T$ is not stable.

This wraps up the proof, as well as this post.