FANDOM


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