## FANDOM

78 Pages

Fix some complete theory $T$ with monster model $\mathbb{U}$.

A formula $\phi(x;y)$ has the order property if there exists $a_1, b_1, a_2, b_2, \ldots$ in $\mathbb{U}$ such that $i < j \iff \models \phi(a_i;b_j)$ for every $i, j$. $T$ is said to be NOP (or stable) if no formula has the order property.

A formula $\phi(x;y)$ has the strict order property if there exist $b_1, b_2, \ldots$ such that $\phi(\mathbb{U};b_1) \subsetneq \phi(\mathbb{U};b_2) \subsetneq \phi(\mathbb{U};b_3) \subsetneq \cdots$ Taking $a_i$ to be in $\phi(\mathbb{U};b_{i+1}) \setminus \phi(\mathbb{U};b_i)$, one sees that any formula having the strict order property has the order property. $T$ is said to be NsOP if no formula has the strict order property. Clearly NOP implies NsOP.

Remark. An equivalent condition to NsOP is that $T$ has no interpretable partial order with an infinite chain.

Proof. If $(P,\le)$ is some interpretable poset, then $P$ is the quotient of some definable pre-order $(P',\le)$. The existence of an infinite chain implies that for each $n$, we can find $b_1, \ldots, b_n$ such that $b_1 \le \cdots \le b_n$ and $b_n \not \le b_{n-1} \not \le \cdots \not \le b_1$. By compactness we can find an infinite sequence $b_1 \le b_2 \le \cdots$ with $b_i \not \ge b_{i+1}$ for each $i$. Let $\phi(x;y)$ assert that $x, y \in P'$ and $x \le y$. Then $\phi(\mathbb{U};b_1) \subsetneq \phi(\mathbb{U};b_2) \subsetneq \cdots$, so $T$ has the strict order property.

Conversely, suppose that $T$ has the strict order property. Then there is a formula $\phi(x;y)$ and $b_1, b_2, \ldots$ with $\phi(\mathbb{U};b_i) \subsetneq \phi(\mathbb{U};b_{i+1})$. Let $P'$ be the sort of $y$ and let $\le$ be the pre-order on $P'$ given by $b_1 \le b_2 \iff \phi(\mathbb{U};b_1) \le \phi(\mathbb{U};b_2)$. If $(P,\le)$ is the quotient partial order, then $P$ has an infinite chain. QED

A formula $\phi(x;y)$ has the independence property if there exist $a_i$ for $i \in \mathbb{N}$ and $b_S$ for $S \in \mathbb{N}$ such that $i \in S \iff \models \phi(a_i;b_S)$ for every $i$, $S$. If $\phi(x;y)$ has the independence property, witnessed by $a_i$ and $b_S$, then $\models \phi(a_i;b_{1,\ldots,j-1}) \iff i < j$ so $\phi$ has the order property. $T$ is said to be NIP (or dependent) if no formula has the independence property. Clearly NOP implies NIP.

Theorem. $T$ is NOP (stable) if and only if $T$ is both NIP and NsOP.

Proof. We have already noted that NOP implies NIP and NsOP. Conversely, suppose $T$ is NIP and NsOP.

Lemma. Suppose $T$ is NsOP. Let $b_1, b_2, \ldots$ be a $C$-indiscernible sequence. Let $\phi(x;y)$ be a formula. Suppose there is $a$ such that $\models \phi(a;b_2) \wedge \neg \phi(a;b_1)$ Then there is some $a' \equiv_C a$ such that $\models \phi(a';b_1) \wedge \neg \phi(a';b_2).$

Proof. Suppose not. Then $\operatorname{tp}(a/C)$ is inconsistent with $\phi(x;b_1) \wedge \neg \phi(x;b_2)$. By compactness, some finite subtype of $\operatorname{tp}(a/C)$ is inconsistent with that formula. Therefore there is some $c \in C$ and formula $\psi(x;z)$ such that $\psi(a;c)$ holds but $\psi(x;c) \wedge \phi(x;b_1) \wedge \neg \phi(x;b_2)$ is inconsistent. Let $\phi'(x;y,z)$ be the formula $\phi(x;y) \wedge \psi(x;z)$. Then $\phi'(x;b_1,c) \wedge \neg \phi'(x;b_2,c)$ is inconsistent. On the other hand, $\phi'(x;b_2,c) \wedge \neg \phi'(x;b_1,c)$ is consistent, being satisfied by $a$.

This means that $\phi'(\mathbb{U};b_1,c) \subsetneq \phi'(\mathbb{U};b_2,c).$ Since $b_1, b_2, \ldots$ is $c$-indiscernible, $\phi'(\mathbb{U};b_i,c) \subsetneq \phi'(\mathbb{U};b_{i+1},c)$ for each $i$. So $T$ has the strict order property, a contradiction. QED

Lemma. Suppose $T$ is NsOP. Let $\{b_i\}_{i \in \mathbb{Q}}$ be an indiscernible sequence. Let $\phi(x;y)$ be a formula. Suppose that $S$ and $S'$ are subsets of $\{1,\ldots,n\}$ having the same cardinality. If there is an $a$ such that $S = \{i \in \{1,\ldots,n\} : \models \phi(a;b_i)\}$ then there is $a'$ such that $S' = \{i \in \{1,\ldots,n\} : \models \phi(a';b_i)\}$

Proof. It suffices to consider the case where the symmetric difference of $S$ and $S'$ is of the form $\{j,j+1\}$, since we can get between any two subsets of $\{1,\ldots,n\}$ of the same size via such steps. So $j$ is in one of $S$ and $S'$, and $j+1$ is in the other.

Replacing $\phi$ with $\neg \phi$, we may assume that $S \setminus S' = \{j+1\}$ and $S' \setminus S = \{j\}$. Let $C$ be $\{b_1,\ldots,b_{j-1},b_{j+2},\ldots,b_n\}$. Note that the sequence $b_j, b_{j+1}, b_{j+2-1/2}, b_{j+2-1/3}, b_{j+2-1/4}, b_{j+2 - 1/5}, \ldots$ is $C$-indiscernible. Also, $\phi(a;b_{j+1})$ holds and $\phi(a;b_j)$ does not, because $j+1 \in S$ and $j \notin S$. By the previous lemma, we can find $a' \equiv_C a$ such that $\phi(a';b_j)$ holds and $\phi(a';b_{j+1})$ does not hold. If $i \in \{1,\ldots,n\}$ is not one of $j$ or $j+1$, then $b_i \in C$, so $\phi(a;b_i)$ holds if and only if $\phi(a';b_i)$ holds, because $a' \equiv_C a$. Therefore, $\{i \in \{1,\ldots,n\} : \models \phi(a';b_i)\} = S \setminus \{j+1\} \cup \{j\} = S'.$ QED

Now suppose for the sake of contradiction that $T$ has the order property. Then there is $a_1, b_1, \ldots$ such that $\models \phi(a_i;b_j)$ if and only if $i < j$. Extracting an indiscernible sequence of length $\mathbb{Q}$ from the sequence $a_1b_1, a_2b_2, \ldots$, we obtain an indiscernible sequence $\{(a_i,b_i)\}_{i \in \mathbb{Q}}$ such that $\models \phi(a_i;b_j)$ holds if and only if $i < j$. The $b_i$ form an indiscernible sequence. For each $n$ and each $0 \le k \le n$, we can find an $a$ such that $|\{i \in \{1, \ldots, n\} : \models \phi(a;b_i)\}| = k$ namely $a = a_{k + 0.5}$. By the previous lemma, it follows that if $S$ is any subset of $\{1,\ldots,n\}$, then we can find an $a$ such that $\{i \in \{1, \ldots, n\} : \models \phi(a;b_i)\} = S.$ Now if $S$ is any subset of $\mathbb{N}$, then by compactness we can find an $a_S$ such that $\{i \in \mathbb{N} : \models \phi(a_S;b_i)\} = S.$ Letting $\phi^\vee(y;x) = \phi(x;y)$, the formula $\phi^\vee$ has the independence property, a contradiction. QED