Stable theory is NIP

Question

I am working through some model theory material, and my source notes state that any theory with the independence property is unstable. It is stated as a fact, but I cannot see why it should be true. I have looked at other sources and cannot seem to find a proof for this, so perhaps it is trivial and I am missing something? Please advise as to how I could observe why this statement is true. Thank you.

Answer 1

Show that if $\phi(x, y)$ has the independence property, then it has the order property (there are $(a_i : i < \omega)$ and $(b_i : i < \omega)$ such that $\phi(a_i, b_j)$ if and only if $i < j$). Now a theory is stable if and only if no formula has the order property. If you are using a different definition of stability, you can try to show that it is equivalent to this.

Answer 2

By phrasing the order property and the independence property in the right way, we can see that the order property is just a weak form of the independence property.

Fix a theory $T$. Assume we have some formula $\varphi(x,y)$, where $x$ and $y$ might be tuples of variables.

$\varphi(x,y)$ has the order property if it is consistent with $T$ that there are $(a_i)_{i<\omega}$ and $(b_i)_{i < \omega}$ such that $M \models \varphi(a_i,b_j)$ iff $i < j$.

$\varphi(x,y)$ has the independence property if it is consistent with $T$ that there are $(a_i)_{i < \omega}$ and $(b_S)_{S \subseteq \omega}$ such that $M \models \varphi(a_i,b_S)$ iff $i \in S$.

By setting $b_j = b_{\{i | i < j\}}$, we can see that the independence property implies the order property directly.

Answer 3

Recall the definitions:

Independence property: $\phi(x,y)$ have the independence property if there are sequences $\langle a_i:i\in\omega\rangle,\langle b_W:W\subseteq \omega\rangle$ such that $\phi(a_i,b_W)$ holds if and only if $i\in W$.

Order property: $\phi(x,y)$ has the order property if there are sequences $\langle a_i:i<\omega\rangle,\langle c_j:j<\omega\rangle$ such that $\phi(a_i,c_j)$ holds if and only if $i<j$.

Stability: We say that $\phi(x,y)$ is unstable if it has the order property.

To show that a property with the independence property is unstable: suppose that $\phi(x,y)$ has the independence property witnessed by the tuples $\langle a_i:i<\omega\rangle$ and $\langle b_W:W\subseteq \omega\rangle$, and simply take the sequences $\langle a_i:i<\omega\rangle$ and $c_j=b_{\{0,1,\ldots,j-1\}}$. Notice that from the independence property we have:

\begin{align*} \models\phi(a_i,c_j) \Leftrightarrow \models\phi(a_i,b_{\{0,\ldots,j-1\}})\Leftrightarrow i\in \{0,\ldots,j-1\}\Leftrightarrow i<j \end{align*}

which shows that $\phi(x,y)$ is unstable.