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 ::: ::: :::