Fix some complete theory with monster model .

A formula has the order property if there exists in such that for every . is said to be NOP (or stable) if no formula has the order property.

A formula has the strict order property if there exist such that Taking to be in , one sees that any formula having the strict order property has the order property. 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 has no interpretable partial order with an infinite chain.

Proof. If is some interpretable poset, then is the quotient of some definable pre-order . The existence of an infinite chain implies that for each , we can find such that and . By compactness we can find an infinite sequence with for each . Let assert that and . Then , so has the strict order property.

Conversely, suppose that has the strict order property. Then there is a formula and with . Let be the sort of and let be the pre-order on given by . If is the quotient partial order, then has an infinite chain. QED

A formula has the independence property if there exist for and for such that for every , . If has the independence property, witnessed by and , then so has the order property. is said to be NIP (or dependent) if no formula has the independence property. Clearly NOP implies NIP.

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

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

Lemma. Suppose is NsOP. Let be a -indiscernible sequence. Let be a formula. Suppose there is such that Then there is some such that

Proof. Suppose not. Then is inconsistent with . By compactness, some finite subtype of is inconsistent with that formula. Therefore there is some and formula such that holds but is inconsistent. Let be the formula . Then is inconsistent. On the other hand, is consistent, being satisfied by .

This means that Since is -indiscernible, for each . So has the strict order property, a contradiction. QED

Lemma. Suppose is NsOP. Let be an indiscernible sequence. Let be a formula. Suppose that and are subsets of having the same cardinality. If there is an such that then there is such that

Proof. It suffices to consider the case where the symmetric difference of and is of the form , since we can get between any two subsets of of the same size via such steps. So is in one of and , and is in the other.

Replacing with , we may assume that and . Let be . Note that the sequence is -indiscernible. Also, holds and does not, because and . By the previous lemma, we can find such that holds and does not hold. If is not one of or , then , so holds if and only if holds, because . Therefore, QED

Now suppose for the sake of contradiction that has the order property. Then there is such that if and only if . Extracting an indiscernible sequence of length from the sequence , we obtain an indiscernible sequence such that holds if and only if . The form an indiscernible sequence. For each and each , we can find an such that namely . By the previous lemma, it follows that if is any subset of , then we can find an such that Now if is any subset of , then by compactness we can find an such that Letting , the formula has the independence property, a contradiction. QED ::: ::: :::