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

A formula {\displaystyle \phi (x;y)} has the order property if there exists {\displaystyle a_{1},b_{1},a_{2},b_{2},\ldots } in {\displaystyle \mathbb {U} } such that {\displaystyle i<j\iff \models \phi (a_{i};b_{j})} for every {\displaystyle i,j}. {\displaystyle T} is said to be NOP (or stable) if no formula has the order property.

A formula {\displaystyle \phi (x;y)} has the strict order property if there exist {\displaystyle b_{1},b_{2},\ldots } such that {\displaystyle \phi (\mathbb {U} ;b_{1})\subsetneq \phi (\mathbb {U} ;b_{2})\subsetneq \phi (\mathbb {U} ;b_{3})\subsetneq \cdots } Taking {\displaystyle a_{i}} to be in {\displaystyle \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. {\displaystyle 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 {\displaystyle T} has no interpretable partial order with an infinite chain.

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

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

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

Theorem. {\displaystyle T} is NOP (stable) if and only if {\displaystyle T} is both NIP and NsOP.

Proof. We have already noted that NOP implies NIP and NsOP. Conversely, suppose {\displaystyle T} is NIP and NsOP.

Lemma. Suppose {\displaystyle T} is NsOP. Let {\displaystyle b_{1},b_{2},\ldots } be a {\displaystyle C}-indiscernible sequence. Let {\displaystyle \phi (x;y)} be a formula. Suppose there is {\displaystyle a} such that {\displaystyle \models \phi (a;b_{2})\wedge \neg \phi (a;b_{1})} Then there is some {\displaystyle a'\equiv _{C}a} such that {\displaystyle \models \phi (a';b_{1})\wedge \neg \phi (a';b_{2}).}

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

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

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

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

Replacing {\displaystyle \phi } with {\displaystyle \neg \phi }, we may assume that {\displaystyle S\setminus S'=\{j+1\}} and {\displaystyle S'\setminus S=\{j\}}. Let {\displaystyle C} be {\displaystyle \{b_{1},\ldots ,b_{j-1},b_{j+2},\ldots ,b_{n}\}}. Note that the sequence {\displaystyle 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 {\displaystyle C}-indiscernible. Also, {\displaystyle \phi (a;b_{j+1})} holds and {\displaystyle \phi (a;b_{j})} does not, because {\displaystyle j+1\in S} and {\displaystyle j\notin S}. By the previous lemma, we can find {\displaystyle a'\equiv _{C}a} such that {\displaystyle \phi (a';b_{j})} holds and {\displaystyle \phi (a';b_{j+1})} does not hold. If {\displaystyle i\in \{1,\ldots ,n\}} is not one of {\displaystyle j} or {\displaystyle j+1}, then {\displaystyle b_{i}\in C}, so {\displaystyle \phi (a;b_{i})} holds if and only if {\displaystyle \phi (a';b_{i})} holds, because {\displaystyle a'\equiv _{C}a}. Therefore, {\displaystyle \{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 {\displaystyle T} has the order property. Then there is {\displaystyle a_{1},b_{1},\ldots } such that {\displaystyle \models \phi (a_{i};b_{j})} if and only if {\displaystyle i<j}. Extracting an indiscernible sequence of length {\displaystyle \mathbb {Q} } from the sequence {\displaystyle a_{1}b_{1},a_{2}b_{2},\ldots }, we obtain an indiscernible sequence {\displaystyle \{(a_{i},b_{i})\}_{i\in \mathbb {Q} }} such that {\displaystyle \models \phi (a_{i};b_{j})} holds if and only if {\displaystyle i<j}. The {\displaystyle b_{i}} form an indiscernible sequence. For each {\displaystyle n} and each {\displaystyle 0\leq k\leq n}, we can find an {\displaystyle a} such that {\displaystyle |\{i\in \{1,\ldots ,n\}:\models \phi (a;b_{i})\}|=k} namely {\displaystyle a=a_{k+0.5}}. By the previous lemma, it follows that if {\displaystyle S} is any subset of {\displaystyle \{1,\ldots ,n\}}, then we can find an {\displaystyle a} such that {\displaystyle \{i\in \{1,\ldots ,n\}:\models \phi (a;b_{i})\}=S.} Now if {\displaystyle S} is any subset of {\displaystyle \mathbb {N} }, then by compactness we can find an {\displaystyle a_{S}} such that {\displaystyle \{i\in \mathbb {N} :\models \phi (a_{S};b_{i})\}=S.} Letting {\displaystyle \phi ^{\vee }(y;x)=\phi (x;y)}, the formula {\displaystyle \phi ^{\vee }} has the independence property, a contradiction. QED ::: ::: :::