Proof For the left to right direction let $(a^{\prime }_i)_{i < \omega }$ , $(b^{\prime }_i)_{i < \omega }$ and $\psi (x, y)$ witness the order property. By compactness we may elongate the sequences to $(a^{\prime }_i)_{i < \lambda }$ and $(b^{\prime }_i)_{i < \lambda }$ . Making sure that $\lambda $ is big enough, we can then by Lemma 2.6 base an indiscernible sequence $(a_i b_i)_{i < \omega }$ on $(a^{\prime }_i b^{\prime }_i)_{i < \lambda }$ . Now if $i < j < \omega $ then there are $i_0 < j_0 < \lambda $ such that $a_i b_j \equiv a^{\prime }_{i_0} b^{\prime }_{j_0}$ , and so $\models \varphi (a_i, b_j)$ follows from $\models \varphi (a^{\prime }_{i_0}, b^{\prime }_{j_0})$ . For the converse we prove the contrapositive, so let $j \leq i$ . Then there are $j_0 \leq i_0 < \lambda $ (with $j_0 = i_0$ iff $j = i$ ) such that $a_i b_j \equiv a^{\prime }_{i_0} b^{\prime }_{j_0}$ . Hence $\models \psi (a^{\prime }_{i_0}, b^{\prime }_{j_0})$ and so $\not \models \varphi (a_i, b_j)$ .

For the right to left direction we only need to find the negation $\psi (x, y)$ . As we have $\not \models \varphi (a_0, b_0)$ there must be some negation $\psi _1(x, y)$ of $\varphi (x, y)$ with $\models \psi _1(a_0, b_0)$ . By indiscernibility we have $\models \psi _1(a_i, b_i)$ for all $i < \omega $ . Similarly, using $\not \models \varphi (a_1, b_0)$ we find a negation $\psi _2(x, y)$ with $\models \psi _2(a_i, b_j)$ for all $j < i$ . Take $\psi (x, y)$ to be $\psi _1(x, y) \vee \psi _2(x, y)$ . As both of $\psi _1(x, y)$ and $\psi _2(x, y)$ are negations of $\varphi (x, y)$ we have that $\psi (x, y)$ is also a negation of $\varphi (x, y)$ . Furthermore, by construction $j \leq i$ implies $\models \psi (a_i, b_j)$ .

Proof Both are straightforward induction arguments. The key intuition being that $R_{\varphi , \psi }(\Sigma ) \geq n$ expresses that we can build a binary tree like in Definition 3.7 of height n and where every path is also consistent with $\Sigma $ .

Proof By Lemma 3.9 and compactness.

Proof The equivalence (iv) $\Leftrightarrow $ (v) is Lemma 3.10. The equivalence between (i), (ii), (v), and (vi) is exactly [Reference Ben-Yaacov3, Proposition 2.2].

$(\mathrm{i}) \Rightarrow (\mathrm{iii})$ We prove the contraposition. So let $\lambda $ be an arbitrary infinite cardinal. By a standard result there is a linear order I with a dense subset $I_0 \subseteq I$ such that $|I_0| = \lambda $ and $|I|> \lambda $ (see, e.g., [Reference Tent and Ziegler21, Exercise 8.2.8]). Let $\psi (x, y)$ be the negation of $\varphi (x, y)$ witnessing the order property. So by compactness there are $(a_i)_{i \in I}$ and $(b_i)_{i \in I}$ such that for all $i,j \in I$ :

$$ \begin{align*} &\models \varphi(a_i, b_j) & \text{if } i < j,\\ &\models \psi(a_i, b_j) & \text{if } i \geq j. \end{align*} $$

Set $B = (b_i)_{i \in I_0}$ , then as $I_0$ is dense in I we have that $\operatorname {\mathrm {tp}}_\varphi (a_i/B) \neq \operatorname {\mathrm {tp}}_\varphi (a_j/B)$ for any $i \neq j$ . So we find $|{\operatorname {S}}_\varphi (B)| \geq |I|> \lambda $ while $|B| \leq \lambda $ and we conclude that $\varphi $ is not $\lambda $ -stable.

$(\mathrm{iii}) \Rightarrow (\mathrm{i})$ This implication requires some more preparation, so we postpone it to Lemma 3.18.

Proof $(\mathrm{i}) \Rightarrow (\mathrm{ii})$ Let $\lambda $ be such that T is $\lambda $ -stable. Then whenever $|B| \leq \lambda $ we have for any $\varphi (x, y)$ that $|{\operatorname {S}}_\varphi (B)| \leq |{\operatorname {S}}_n(B)| \leq \lambda $ , where $n = |x|$ . So every formula is $\lambda $ -stable.

$(\mathrm{ii}) \Rightarrow (\mathrm{iii})$ Let $\lambda $ be such that $\lambda ^{|T|} = \lambda $ , and let $|B| \leq \lambda $ . As $\lambda ^{|T|} = \lambda $ we have that $\lambda> |T|$ . So for any $\varphi $ we have by Theorem 3.11 that $|{\operatorname {S}}_\varphi (B)| \leq (|B| + |T|)^{|T|} \leq \lambda ^{|T|} = \lambda $ . Every type is fully determined by its restrictions to $\varphi $ -types, as $\varphi $ ranges over all formulas in the theory. So there are at most $|T| \times \lambda = \lambda $ many types over B, as required.

$(\mathrm{iii}) \Rightarrow (\mathrm{i})$ Note that $(2^{|T|})^{|T|} = 2^{|T|}$ , so T is $2^{|T|}$ -stable and hence stable.

Proof To prove (i) we show that $p_1 \subseteq p_2$ , from which the result follows by symmetry. Let $\varphi (x, c) \in p_1$ . By the assumption on B, $\operatorname {\mathrm {tp}}_\psi (c/A)$ is realised by some $b \in B$ . As $p_1$ does not $(\psi , \varphi )$ -split over A we must then have $\varphi (x, b) \in p_1$ . We thus have $\varphi (x, b) \in p_2$ , because $p_1|_B = p_2|_B$ , and $\varphi (x, c) \in p_2$ follows from the fact that $p_2$ does not $(\psi , \varphi )$ -split over A.

For (ii) we can let B be such that $A \subseteq B \subseteq C$ and realising every $\psi $ -type over A that is realised in C, while also $|B| \leq |{\operatorname {S}}_\psi (A)| + |A|$ . By (i) then the number of types in ${\operatorname {S}}_\varphi (C)$ that do not $(\psi , \varphi )$ -split over A is bounded by $|{\operatorname {S}}_\varphi (B)| \leq 2^{|B| + |T|} \leq 2^{|{\operatorname {S}}_\psi (A)| + |A| + |T|}$ .

Finally, for (iii) we apply (ii) using that $|{\operatorname {S}}_\psi (A)| + |A| + |T| \leq 2^\lambda $ .

Proof We prove the contrapositive, so we assume that $\varphi (x, y)$ is not stable. For convenience, set $\mu = 2^{2^{\lambda _T}}$ . As $\varphi $ is not $\mu $ -stable, we find some set A such that $|A| \leq \mu $ and ${\operatorname {S}}_\varphi (A)> \mu $ . We can thus find $(a_i)_{i < \mu ^+}$ such that $\operatorname {\mathrm {tp}}_\varphi (a_i / A) \neq \operatorname {\mathrm {tp}}_\varphi (a_j / A)$ for all $i \neq j < \mu ^+$ . We inductively build a continuous chain of sets $(A_i)_{i < \mu }$ with $A_0 = A$ such that for all $i < \mu $ :

1. (A1) $|A_i| \leq \mu $ ,

2. (A2) for every $B \subseteq A_i$ with $|B| \leq \lambda _T$ every type in ${\operatorname {S}}(B)$ (in finitely many variables) is realised in $A_{i+1}$ .

We can indeed do this because there are at most $\mu ^{\lambda _T} = \mu $ many subsets of $A_i$ that have cardinality at most $\lambda _T$ , and there are at most $2^{|B| + |T|} \leq 2^{\lambda _T} < \mu $ many types over such a parameter set B.

Set $\chi (y, x) := \varphi (x, y)$ . We now claim that there are cofinally many $i < \mu ^+$ such that for all $j < \lambda _T$ the type $\operatorname {\mathrm {tp}}_\varphi (a_i / A_j)\ (\chi , \varphi )$ -splits over each $B \subseteq A_j$ of cardinality at most $\lambda _T$ .

Using the claim we find some $i < \mu ^+$ such that $a_i \not \in \bigcup _{j < \lambda _T} A_j$ , because $\left | \bigcup _{j < \lambda _T} A_j \right | \leq \mu $ . So for all $j < \lambda _T \operatorname {\mathrm {tp}}_\varphi (a_i / A_j)\ (\chi , \varphi )$ -splits over every $B \subseteq A_j$ of cardinality at most $\lambda _T$ . By induction on $j < \lambda _T$ we define $b_j, b^{\prime }_j, c_j \in A_{2j+2}$ , such that:

1. (B1) writing $B_j = \{b_k, b^{\prime }_k, c_k : k < j\}$ , we have $B_j \subseteq A_{2j}$ ;

2. (B2) $\operatorname {\mathrm {tp}}_\chi (b_j/B_j) = \operatorname {\mathrm {tp}}_\chi (b^{\prime }_j/B_j)$ ,

3. (B3) $\models \varphi (a_i, b_j)$ and $\not \models \varphi (a_i, b^{\prime }_j)$ ,

4. (B4) $c_j \in A_{2j+1}$ is such that $\operatorname {\mathrm {tp}}(c_j / B_j b_j b^{\prime }_j) = \operatorname {\mathrm {tp}}(a_i/B_j b_j b^{\prime }_j)$ .

Let $j < \lambda _T$ and assume we have constructed $b_k, b^{\prime }_k, c_k$ for all $k < j$ . As $B_j \subseteq A_{2j}$ has cardinality at most $\lambda _T$ , we have that $\operatorname {\mathrm {tp}}_\varphi (a_i/A_{2j})\ (\chi , \varphi )$ -splits over $B_j$ . We can thus find $b_j, b^{\prime }_j \in A_{2j}$ such that $\operatorname {\mathrm {tp}}_\chi (b_j / B_j) = \operatorname {\mathrm {tp}}_\chi (b^{\prime }_j / B_j)$ while $\varphi (x, b_j) \in \operatorname {\mathrm {tp}}(a_i/A_{2j})$ and $\varphi (x, b^{\prime }_j) \not \in \operatorname {\mathrm {tp}}(a_i/A_{2j})$ . By construction of $A_{2j+1}$ , in particular by (A2), we can find $c_j \in A_{2j+1}$ realising $\operatorname {\mathrm {tp}}(a_i/B_j b_j b^{\prime }_j)$ .

Let $(d_j d^{\prime }_j e_j)_{j < \omega }$ be an indiscernible sequence based on $(b_j b^{\prime }_j c_j)_{j < \lambda _T}$ . We note the following two properties.

1. (C1) By (B2) we have for all $k < j < \lambda _T$ that $\models \chi (b_j, c_k)$ if and only if $\models \chi (b^{\prime }_j, c_k)$ , that is $\models \varphi (c_k, b_j)$ if and only if $\models \varphi (c_k, b^{\prime }_j)$ . So we must have $\models \varphi (e_k, d_j)$ if and only if $\models \varphi (e_k, d^{\prime }_j)$ for all $k < j < \omega $ .

2. (C2) By (B3) and (B4) we have for all $k \leq j < \lambda _T$ that $\models \varphi (c_j, b_k)$ and $\not \models \varphi (c_j, b^{\prime }_k)$ . So we must have $\models \varphi (e_j, d_k)$ and $\not \models \varphi (e_j, d^{\prime }_k)$ for all $k \leq j < \omega $ .

Based on (C1) we distinguish two cases, and show that in each case $\varphi (x, y)$ has the order property.

1. (1) The case where for all $k < j < \omega $ we have $\models \varphi (e_k, d^{\prime }_j)$ . By (C2) we have $\not \models \varphi (e_j, d^{\prime }_k)$ for all $k \leq j < \omega $ . We conclude by applying Proposition 3.6 to $(e_n, d^{\prime }_n)_{n < \omega }$ .

2. (2) The case where for all $k < j < \omega $ we have $\not \models \varphi (e_k, d_j)$ . By (C2) we have that $\models \varphi (e_j, d_k)$ for all $k \leq j < \omega $ . Write $\omega ^{\text {op}}$ for $\omega $ with the opposite order, then $(e_n, d_{n+1})_{n \in \omega ^{\text {op}}}$ is an indiscernible sequence such that $\models \varphi (e_k, d_j) \Leftrightarrow k <^{\text {op}} j$ . Applying compactness and an analogue of Proposition 3.6 we conclude that $\varphi (x,y)$ has the order property.

Proof Assume T has $\mathsf {SOP}_{3}$ , witnessed by formulas $\varphi _0(x, y)$ , $\varphi _1(x, y)$ and a negation $\psi (y_1, y_2)$ of $\exists x(\varphi _0(x, y_2) \wedge \varphi _1(x, y_1))$ . By compactness we find a sequence $(b_q)_{q \in \mathbb {Q}}$ such that:

1. (1) for all $t \in \mathbb {Q}$ the set $\{ \varphi _0(x,b_q) : q < t \} \cup \{\varphi _1(x,b_r):r \geq t\}$ is consistent,

2. (2) for all $q < r$ in $\mathbb {Q}$ we have $\models \psi (b_q,b_r)$ .

Consider $\chi (x, y_1, y_2) := \varphi _0(x, y_1) \wedge \varphi _1(x, y_2)$ . We inductively define a tree, indexed by $2^{<\omega }$ , which will witness that $\chi $ , and hence T, has $\mathsf {SOP}_{2}$ .

$$ \begin{align*} c_\varnothing &= (b_0,b_1) , \\[-2pt] c_{\eta^\frown 0} &= (b_q,b_{\frac{2}{3}q + \frac{1}{3}r}) \quad\text{for } c_\eta=(b_q,b_r), \\[-2pt] c_{\eta^\frown 1} &= (b_{\frac{1}{3}q + \frac{2}{3}r}, b_r) \quad\text{for } c_\eta=(b_q,b_r). \end{align*} $$

Let moreover $\theta (y_1,y_2,y_3,y_4)$ denote the formula $\psi (y_4,y_1) \lor \psi (y_2, y_3)$ .

We claim that $\theta (y_1,y_2,y_3,y_4)$ is a negation of $\exists x (\chi (x,y_1,y_2) \wedge \chi (x,y_3,y_4))$ . Indeed, assume that $\theta (a,b,c,d)$ holds. Then either $\psi (d,a)$ holds or $\psi (b,c)$ holds. By definition of $\psi $ we have that in the first case $\exists x (\varphi _0(x,a) \wedge \varphi _1(x,d))$ does not hold, and in the second case $\exists x (\varphi _0(x, c) \wedge \varphi _1(x, b))$ . Either way, we have that $\exists x(\varphi _0(x,a) \wedge \varphi _1(x,d) \wedge \varphi _0(x, c) \wedge \varphi _1(x, b))$ “does not hold”. The claim now follows from the definition of $\chi $ .

We will now verify that $(c_\eta )_{\eta \in 2^{<\omega }}$ and $\theta $ witness that $\chi $ has $\mathsf {SOP}_{2}$ . For consistency along the branches, let $\sigma \in 2^\omega $ and $n < \omega $ . Then there are $0=q_0\leq \dots \leq q_n<r_n\leq \dots \leq r_0=1$ such that for $0 \leq i \leq n$ , $c_{\sigma |_i}=(b_{q_i},b_{r_i})$ . Taking $t = r_n$ in (1) above, we see that

$$\begin{align*}\{\varphi_0(x,b_{q_i}) : i \leq n\} \cup \{\varphi_1(x,b_{r_i}): i \leq n\} \end{align*}$$

is consistent. Thus $\{ \chi (x,c_{\sigma |_i}) : i < \omega \}$ is finitely consistent, and hence consistent.

Now let $\mu , \eta $ be incomparable. Then there are $q<r<s<t$ such that either $c_\mu =(b_q,b_r)$ and $c_\eta =(b_s,b_t)$ , or $c_\mu =(b_s,b_t)$ and $c_\eta =(b_q,b_r)$ . In both cases, since $r < s$ , we have $\models \psi (b_r,b_s)$ . That means both $\models \theta (b_q,b_r,b_s,b_t)$ and $\models \theta (b_s,b_t,b_q,b_r)$ , giving $\models \theta (c_\mu , c_\eta )$ in any case. This concludes the proof.

Proof One direction is obvious: if $(a_\eta )_{\eta \in \omega ^{<\omega }}$ and $\psi (y_1,y_2)$ witness $\mathsf {TP}_{1}$ of $\varphi $ , then $(a_\eta )_{\eta \in 2^{<\omega }}$ and $\psi (y_1,y_2)$ witness $\mathsf {SOP}_{2}$ of $\varphi $ .

For the converse, let us then assume that $\varphi (x,y)$ has $\mathsf {SOP}_{2}$ , witnessed by $(a_\eta )_{\eta \in 2^{<\omega }}$ and $\psi (y_1,y_2)$ . We inductively define a function $h:\omega ^{<\omega } \rightarrow 2^{< \omega }$ as

$$ \begin{align*} &h(\varnothing)=\varnothing , \\[-2pt] &h(\eta^\frown i)=h(\eta)^\frown (0)^{i \frown} 1 \quad\text{for } i<\omega. \end{align*} $$

Note that $\eta \preceq \mu $ implies $h(\eta ) \preceq h(\mu )$ and so for any $\sigma \in \omega ^\omega $ there is $\sigma ' \in 2^\omega $ such that $\{h(\sigma |_n) : n < \omega \} \subseteq \{\sigma '|_n : n < \omega \}$ .

Define a tree $(b_\eta )_{\eta \in \omega ^{<\omega }}$ by $b_\eta = a_{h(\eta )}$ . We verify that this tree witnesses $\mathsf {TP}_{1}$ for $\varphi (x, y)$ , with the same negation $\psi (y_1, y_2)$ .

For any $\sigma \in \omega ^\omega $ there is $\sigma ' \in 2^\omega $ such that

$$\begin{align*}\{ \varphi(x, b_{\sigma|_n}) : n < \omega \} = \{ \varphi(x, a_{h(\sigma|_n)}) : n < \omega \} \subseteq \{ \varphi(x, a_{\sigma'|_n}) : n < \omega \}. \end{align*}$$

The rightmost set is consistent because $(a_\eta )_{\eta \in 2^{<\omega }}$ witnesses $\mathsf {SOP}_{2}$ for $\varphi (x, y)$ , so the leftmost set is consistent.

Let $\mu , \eta \in \omega ^{< \omega }$ be incomparable. Then there are $\gamma , \mu _0, \eta _0 \in \omega ^{<\omega }$ and $i\neq j < \omega $ such that $\mu =\gamma ^\frown i^\frown \mu _0$ and $\eta =\gamma ^\frown j ^\frown \eta _0$ . By definition of h, there are $\mu _1,\eta _1 \in 2^{<\omega }$ such that $h(\eta )=h(\gamma )^\frown (0)^{i \frown } 1 ^\frown \eta _1$ and $h(\mu )=h(\gamma )^\frown (0)^{j \frown } 1 ^\frown \mu _1$ . If $i<j$ then $h(\eta )$ has a $1$ in a place where $h(\mu )$ has a $0$ , and thus they are incomparable. Similarly, if $j < i$ then $h(\eta )$ and $h(\mu )$ are again incomparable. Hence, by definition of $\mathsf {SOP}_{2}$ , $\models \psi (a_{h(\eta )}, a_{h(\mu )})$ , and so $(b_\eta )_{\eta \in \omega ^{<\omega }}$ and $\psi $ witness $\mathsf {TP}_{1}$ of $\varphi $ .

Proof Suppose $\varphi (x,y)$ has $\mathsf {SOP}_{2}$ , witnessed by $(a_\eta )_{\eta \in 2^{<\omega }}$ and $\psi (y_1,y_2)$ . Let $\mu , \eta \in 2^{<\omega }$ , and $\mu ^\frown 0 \preceq \eta $ . Then $\mu ^\frown 1$ and $\eta $ are incomparable, so by $\mathsf {SOP}_{2}$ we have $\models \psi (a_{\mu ^\frown 1}, a_\eta )$ . Hence the second clause in the definition of $\mathsf {SOP}_{1}$ is satisfied. The first clause is the same as the first clause of the definition of $\mathsf {SOP}_{2}$ , and therefore $\varphi (x,y)$ has $\mathsf {SOP}_{1}$ , witnessed again by $(a_\eta )_{\eta \in \omega ^{<\omega }}$ and $\psi (y_1,y_2)$ .

Proof Suppose that $\varphi (x,y)$ has $\mathsf {SOP}_{1}$ , witnessed by $(a_\eta )_{\eta \in 2^{<\omega }}$ and $\psi (y_1,y_2)$ . We define $h:\omega ^{<\omega } \rightarrow 2^{< \omega }$ as in the proof of Proposition 5.3. Again, we define $(b_\eta )_{\eta \in \omega ^{<\omega }}$ by $b_\eta = a_{h(\eta )}$ , so that for any $\sigma \in \omega ^\omega $ , we get that $\{ \varphi (x, b_{\sigma |_n} : n < \omega \}$ is consistent.

Now let $\eta \in \omega ^{<\omega }$ and let $i < j < \omega $ . Then

$$\begin{align*}h(\eta)^\frown (0)^{i+1} \preceq h(\eta)^\frown (0)^{j \frown} 1=h(\eta ^\frown j). \end{align*}$$

We have that $h(\eta ^\frown i)=h(\eta )^\frown (0)^{i \frown }(1)$ and hence, by the second clause in the definition of $\mathsf {SOP}_{1}$ we have $\models \psi (a_{h(\eta ^\frown i)}, a_{h(\eta ^ \frown j)})$ . Hence $(b_\eta )_{\eta \in \omega ^{< \omega }}$ and $\psi $ witness $2$ - $\mathsf {TP}$ for $\varphi $ .

Proof Let $\kappa =|T|^+$ . We will find a set of parameters A and a set $B \subseteq A^\kappa $ such that:

1. (i) $|B|> |A|^{< \kappa } + 2^{2^\kappa }$ ;

2. (ii) if $B' \subseteq B$ and $|B'|> 2^\kappa $ then $\{ \varphi (x, b(\alpha )) : b \in B', \alpha < \kappa \}$ is inconsistent;

3. (iii) for any $b \in B$ we have that $\{ \varphi (x, b(\alpha )) : \alpha < \kappa \}$ is consistent.

Let $\lambda = \beth _\kappa (|T| + 2^\kappa )$ . By compactness we find a tree $(a_\eta )_{\eta \in \lambda ^{< \kappa }}$ such that for every $\sigma \in \lambda ^\kappa $ the set $\{ \varphi (x, a_{\sigma |_\alpha }) : \alpha < \kappa \}$ is consistent, but there exists $2 \leq k < \omega $ such that for any $\eta \in \lambda ^{<\kappa }$ the set $\{ \varphi (x, a_{\eta ^\frown i}) : i < \lambda \}$ is k-inconsistent. Because of this last property we may assume that for any $\eta \in \lambda ^{<\kappa }$ all the terms of $(a_{\eta ^\frown i})_{i < \lambda }$ are distinct.

Write $A = \{a_\eta : \eta \in \lambda ^{< \kappa }\}$ and for $\sigma \in \lambda ^\kappa $ we define $b_\sigma : \kappa \to A$ by $b_\sigma (\alpha ) = a_{\sigma |_\alpha }$ . We claim that this A together with $B = \{ b_\sigma : \sigma \in \lambda ^\kappa \}$ satisfies (i)–(iii).

1. (i) As $\operatorname {\mathrm {cf}}(\lambda ) = \kappa $ we have $|B| = \lambda ^\kappa> \lambda = \lambda ^{<\kappa } = |A|^{< \kappa }$ , and the required inequality follows. Here we use that for distinct $\sigma , \sigma ' \in \lambda ^\kappa $ we have $b_\sigma \neq b_{\sigma '}$ , which follows from our earlier assumption that the terms of $(a_{\eta ^\frown i})_{i < \lambda }$ are distinct for any $\eta \in \lambda ^{<\kappa }$ .

2. (ii) Let $B' \subseteq B$ be such that $\{ \varphi (x, b(\alpha )) : b \in B', \alpha < \kappa \}$ is consistent, we will show that $|B'| \leq 2^\kappa $ . Define $X = \{ \sigma \in \lambda ^\kappa : b_\sigma \in B' \}$ , so $\{ \varphi (x, a_{\sigma |_\alpha }) : \sigma \in X, \alpha < \kappa \}$ is consistent. By construction of $(a_\eta )_{\eta \in \lambda ^{< \kappa }}$ we then must have for all $\eta \in \lambda ^{<\kappa }$ that the branches in X pass through at most $k-1$ immediate successors of $\eta $ , that is,

   $$\begin{align*}|\{ i < \lambda : \text{there is } \sigma \in X \text{ such that } \eta^\frown i \preceq \sigma \}| < k. \end{align*}$$
   After re-indexing we then have that $X \subseteq k^\kappa $ and hence $|B'| = |X| \leq 2^\kappa $ .

3. (iii) This is just consistency of $\{ \varphi (x, a_{\sigma |_\alpha }) : \alpha < \kappa \}$ for every $\sigma \in \lambda ^\kappa $ .

With A and B be as above, let $\mu = |A|^{< \kappa } + 2^{2^\kappa }$ . We will find a cardinal $\kappa \leq \chi \leq 2^\kappa $ and a set $S \subseteq A^\chi $ such that:

1. (1) $|S| = \mu ^+$ ;

2. (2) for any distinct $s, s' \in S$ we have that $\{\varphi (x, s(\alpha )) : \alpha < \chi \} \cup \{\varphi (x, s'(\alpha )) : \alpha < \chi \}$ is inconsistent;

3. (3) for any $s \in S$ the set $\{\varphi (x, s(\alpha )) : \alpha < \chi \}$ is consistent;

4. (4) for any $s, s' \in S$ , viewing them as infinite tuples, we have $s \equiv s'$ .

First we may assume $|B| = \mu ^+$ . We inductively construct $U_i \subseteq B$ as follows: $U_i$ is a maximal subset such that $U_j \cap U_i = \emptyset $ for all $j < i$ and $\{\varphi (x, b(\alpha )) : b \in U_i, \alpha < \kappa \}$ is consistent. Note that the latter implies that $|U_i| \leq 2^\kappa $ by (ii), which together with (iii) allows us to continue the construction until we have constructed $\{U_i\}_{i < \mu ^+}$ . By the pigeonhole principle we may assume that all the $U_i$ have the same cardinality. For all $i <\mu ^+$ , let $A_i=\{b(\alpha ) :b \in U_i, \alpha <\kappa \}$ , $\chi =|A_i|=\kappa \cdot |U_i|$ , and $s_i \in A^\chi $ an enumeration of $A_i$ . If we let $S = \{s_i : i < \mu ^+\}$ then it satisfies (1)–(3), and by the pigeonhole principle we can replace S by a subset to also ensure (4).

For $s \in S$ we now define pairs $(v^s_\alpha , \psi ^s_\alpha )$ inductively on $\alpha < \delta _s$ , where $\delta _s$ is the first $\alpha $ for which $(v^s_\alpha , \psi ^s_\alpha )$ cannot be defined. We require:

1. (A) $v^s_\alpha \subseteq \chi $ is finite;

2. (B) there is $\{s_n\}_{n < \omega } \subseteq S$ with $s_n(j) = s(j)$ for all $n < \omega $ and all $j \in \bigcup _{\beta < \alpha } v^s_\beta $ ;

3. (C) $\psi ^s_\alpha ((y_\gamma )_{\gamma \in v^s_\alpha }, (y^{\prime }_\gamma )_{\gamma \in v^s_\alpha })$ is a negation of $\exists x \left ( \bigwedge _{\gamma \in v^s_\alpha } \varphi (x, y_\gamma ) \wedge \varphi (x, y^{\prime }_\gamma ) \right )$ ;

4. (D) for any distinct $n, m < \omega $ we have $\models \psi ^s_\alpha ((s_n(\gamma ))_{\gamma \in v^s_\alpha }, (s_m(\gamma ))_{\gamma \in v^s_\alpha })$ .

We will show that there is $s \in S$ such that $\delta _s \geq \kappa $ . Suppose for a contradiction that $\delta _s < \kappa $ for all $s \in S$ . There are $(\chi ^{< \omega } \cdot |T|)^{< \kappa } = \chi ^{<\kappa } \leq 2^\kappa \leq \mu $ many possible sequences $(v^s_\alpha , \psi ^s_\alpha )_{\alpha < \delta _s}$ . So by the pigeonhole principle there is $S_1 \subseteq S$ with $|S_1| = \mu ^+$ and for all $s,s' \in S_1$ we have $\delta _s = \delta _{s'}$ and $(v^s_\alpha , \psi ^s_\alpha )_{\alpha < \delta _s} = (v^{s'}_\alpha , \psi ^{s'}_\alpha )_{\alpha < \delta _{s'}}$ . Write $(v_\alpha , \psi _\alpha )_{\alpha < \delta } = (v^s_\alpha , \psi ^s_\alpha )_{\alpha < \delta _s}$ for some $s \in S_1$ . As $\delta < \kappa $ we have that $|\bigcup _{\beta < \delta } v_\beta | < \kappa $ . So as $|A|^{<\kappa } \leq \mu $ we can again apply the pigeonhole principle to find $S_2 \subseteq S_1$ with $|S_2| = \mu ^+$ and for any $s, s' \in S_2$ we have that $s(j) = s'(j)$ for all $j \in \bigcup _{\beta < \delta } v_\beta $ .

By (2) we have that any two distinct $s, s' \in S_2$ the set $\{\varphi (x, s(\alpha )) : \alpha < \chi \} \cup \{\varphi (x, s'(\alpha )) : \alpha < \chi \}$ is inconsistent. So we can assign a finite $u_{s,s'} \subseteq \chi $ and $\theta _{s,s'}((y_\gamma )_{\gamma \in u_{s,s'}}, (y^{\prime }_\gamma )_{\gamma \in u_{s,s'}})$ to each such a pair, such that $\theta _{s,s'}((y_\gamma )_{\gamma \in u_{s,s'}}, (y^{\prime }_\gamma )_{\gamma \in u_{s,s'}})$ is a negation of $\exists x \left ( \bigwedge _{\gamma \in u_{s,s'}} \varphi (x, y_\gamma ) \wedge \varphi (x, y^{\prime }_\gamma ) \right )$ and $\models \theta _{s,s'}((s(\gamma ))_{\gamma \in u_{s,s'}}, (s'(\gamma ))_{\gamma \in u_{s,s'}})$ . This defines a colouring function on $[S_2]^2$ with $(\chi ^{<\omega } \cdot |T|) = \chi $ many colours. As $\mu ^+ \geq (2^\chi )^+$ we can apply the Erdős–Rado theorem to find $S_3 \subseteq S_2$ with $|S_3| = \chi ^+$ such that $u = u_{s,s'}$ and $\theta = \theta _{s,s'}$ do not depend on the pair $s,s' \in S_3$ . However, for any $s \in S_3$ we could now have taken $(v^s_{\delta _s}, \psi ^s_{\delta _s})$ to be $(u, \theta )$ , contradicting the definition of $\delta _s$ . Indeed (A) and (C) follow immediately from the construction of u and $\theta $ . For (B) and (D) any $\{s_n\}_{n < \omega } \subseteq S_3$ suffices, which exists because $|S_3| = \chi ^+$ is infinite, then (B) follows because this is also a subset of $S_2$ and (D) follows from the construction of $\theta $ .

There is thus some $s \in S$ such that $\delta _s \geq \kappa $ . As $\kappa = |T|^+$ there is some $k'$ and $\psi (\bar {y}, \bar {y}') := \psi (y_1, \ldots , y_{k'}, y^{\prime }_1, \ldots , y^{\prime }_{k'})$ such that there are infinitely many $\alpha < \kappa $ with $|v^s_\alpha | = k'$ and $\psi ^s_\alpha = \psi $ (after renaming variables). For convenience we may as well assume that this happens for all $\alpha < \omega $ . We will show that $\varphi (x, y_1) \wedge \cdots \wedge \varphi (x, y_{k'})$ has $2$ - $\mathsf {TP}$ . The relevant negation will be $\psi $ , so we need to construct the tree $(c_\eta )_{\eta \in \omega ^{<\omega }}$ of parameters. For $\alpha < \omega $ we write $\bar {s}(\alpha )$ for the tuple $(s(\beta ))_{\beta \in v^s_\alpha }$ . We now construct $(c_\eta )_{\eta \in \omega ^{<\omega }}$ by induction on the length of $\eta \in \omega ^{<\omega }$ , such that for $\eta \in \omega ^n$ we have that $(c_{\eta |_\alpha })_{\alpha \leq n} \equiv (\bar {s}(\alpha ))_{\alpha \leq n}$ .

We can simply take $c_\emptyset = \bar {s}(0)$ . Now assuming we have constructed $c_{\eta }$ for $\eta \in \omega ^n$ , we will construct $c_{\eta ^\frown i}$ for all $i < \omega $ . By an automorphism we may assume $(c_{\eta |_\alpha })_{\alpha \leq n} = (\bar {s}(\alpha ))_{\alpha \leq n}$ . Let $(s_i)_{i < \omega }$ be as in (B) for $v^s_{n+1}$ . We set $c_{\eta ^\frown i} = \bar {s}_i(n+1)$ for all $i < \omega $ . Then we get

$$ \begin{align*}c_{\eta^\frown i} (c_{\eta|_\alpha})_{\alpha \leq n} = \bar{s}_i(n+1) (\bar{s}(\alpha))_{\alpha \leq n} = \bar{s}_i(n+1) (\bar{s}_i(\alpha))_{\alpha \leq n} \equiv \bar{s}(n+1) (\bar{s}(\alpha))_{\alpha \leq n}.\end{align*} $$

Here the second equality follows from (B) and the third equivalence follows from (4).

We are left to verify that the tree $(c_\eta )_{\eta \in \omega ^{<\omega }}$ is an instance of $2$ - $\mathsf {TP}$ . Indeed, for any $\eta \in \omega ^{<\omega }$ and $i < j < \omega $ we have $\models \psi (c_{\eta ^\frown i}, c_{\eta ^\frown j})$ by (D). Finally, for any $\sigma \in \omega ^\omega $ we have by the induction hypothesis that $(c_{\sigma |_\alpha })_{\alpha < \omega } \equiv (\bar {s}(\alpha ))_{\alpha < \omega }$ , so the required consistency follows from (3).

Proof Let $\kappa = \beth _{|T|^+}$ , then $\omega ^{<\kappa } = \kappa $ and $\kappa ^{|T|} = \kappa $ . To see the latter we note that for any $f: |T| \to \kappa $ , there is $\alpha < |T|^+$ such that the image of f is contained in $\beth _\alpha $ . Hence $\kappa ^{|T|} = \bigcup _{\alpha < |T|^+} \beth _\alpha ^{|T|}$ , and $\beth _\alpha ^{|T|} \leq \beth _{\alpha +1}$ , from which the equality follows.

We assume $\varphi (x,y)$ has $2$ - $\mathsf {TP}$ , so by compactness we find $(b_\eta )_{\eta \in \omega ^{< \kappa }}$ and a negation $\psi (y_1,y_2)$ of the formula $\exists x (\varphi (x, y_1) \wedge \varphi (x, y_2))$ witnessing $2$ - $\mathsf {TP}$ .

Let $B = \{ b_\eta : \eta \in \omega ^{< \kappa } \}$ . For $\sigma \in \omega ^\kappa $ let $a_\sigma $ be a realisation of $\{ \varphi (x, b_{\sigma |_\alpha }): \alpha < \kappa \}$ . Given distinct $\sigma _1, \sigma _2 \in \omega ^\kappa $ , we have $\operatorname {\mathrm {tp}}_\varphi (a_{\sigma _1}/B) \neq \operatorname {\mathrm {tp}}_\varphi (a_{\sigma _2}/B)$ . Indeed, let $\eta \in \omega ^{< \kappa }$ be such that $\eta \preceq \sigma _1, \sigma _2$ but there are $i \neq j < \omega $ such that $\eta ^\frown i \preceq \sigma _1$ and $\eta ^\frown j \preceq \sigma _2$ . Without loss of generality, assume $i < j$ . Then $\models \psi (b_{\eta ^\frown i}, b_{\eta ^\frown j})$ and so because we have $\models \varphi (a_{\sigma _1}, b_{\eta ^\frown i})$ and $\models \varphi (a_{\sigma _2}, b_{\eta ^\frown j})$ we cannot have $\models \varphi (a_{\sigma _2}, b_{\eta ^\frown i})$ .

We thus find $\omega ^\kappa> \kappa $ many types in ${\operatorname {S}}_\varphi (B)$ , while at the same time $(|B| + |T|)^{|T|} = (\omega ^{<\kappa } + |T|)^{|T|} = \kappa ^{|T|} = \kappa $ by our choice of $\kappa $ .

Proof By Proposition 5.8 and Theorem 3.11.

Proof Suppose that $\varphi (x,y)$ has k- $\mathsf {TP}_{2}$ , witnessed by $(a_{i,j})_{i,j < \omega }$ and $\psi (y_1,\ldots , y_k)$ . We construct $(b_\eta )_{\eta \in \omega ^{<\omega }}$ such that together with $\psi (y_1, \ldots , y_k)$ they witness k- $\mathsf {TP}$ . For $\eta \in \omega ^{<\omega }$ , let $\ell (\eta )$ be the length (domain) of $\eta $ and let $t(\eta )$ be the last element of $\eta $ and $t(\emptyset ) = 0$ . Define $b_\eta = a_{\ell (\eta ), t(\eta )}$ .

For any $\sigma \in \omega ^\omega $ we have that $\{ \varphi (x, b_{\sigma |_n}) : n < \omega \} = \{ \varphi (x, a_{n, t(\sigma |_n)}) : n < \omega \}$ is consistent. Let now $\eta \in \omega ^{< \omega }$ , and write $n = \ell (\eta ) +1$ . Then for any $i_1 < \cdots < i_k < \omega $ we have $\models \psi (a_{n, i_1}, \ldots , a_{n,i_k})$ . This is the same as $\models \psi (b_{\eta ^\frown i_1}, \ldots , b_{\eta ^\frown i_k})$ . Hence, $(b_\eta )_{\eta \in \omega ^{<\omega }}$ and $\psi (y_1, \ldots , y_k)$ witness $\varphi (x,y)$ having k- $\mathsf {TP}$ .

Proof Assume T has $2$ - $\mathsf {TP}_{2}$ witnessed by the formula $\varphi (x,y)$ , $(a_{i,j})_{i, j < \omega }$ and a negation $\psi (y_1,y_2)$ of the formula $\exists x (\varphi (x, y_1) \wedge \varphi (x, y_2))$ . Then for every $\sigma \in 2^\omega \subseteq \omega ^\omega $ , there exists $c_\sigma $ such that for all $i < \omega $ we have $\models \varphi (c_\sigma , a_{i, \sigma (i)})$ .

Consider the formulas $\chi (z_1 z_2, t) := \varphi (t, z_2) $ and $\xi (z_1 z_2, t) := \varphi (t, z_1) \land \psi (z_1, z_2) $ . Also for $i<\omega $ let $b_i$ be the tuple $(a_{i,0},\ a_{i,1})$ . We are going to show that $\chi $ has $\mathsf {IP}$ witnessed by $(b_i)_{i< \omega }$ , $(c_\sigma )_{\sigma \in 2^\omega }$ and $\xi $ .

First of all note that $\xi $ is indeed a negation of $\chi $ , since

$$\begin{align*}T \models \neg \exists z_1 z_2 t \ (\varphi(t, z_2) \land \varphi(t, z_1) \land \psi(z_1, z_2)). \end{align*}$$

Now take any $i < \omega $ and $\sigma \in 2^\omega $ . If $\sigma (i) = 1$ , then we have $\models \varphi (c_\sigma , a_{i, 1})$ and therefore $\models \chi (b_i, c_\sigma )$ . If $\sigma (i) = 0$ , then we have $\models \varphi (c_\sigma , a_{i, 0})$ as well as $\models \psi (a_{i,0}, a_{i, 1})$ and therefore $\models \xi (b_i, c_\sigma )$ . Hence, $(b_i)_{i< \omega }$ , $(c_\sigma )_{\sigma \in 2^\omega }$ and $\xi $ witness $\mathsf {IP}$ of $\chi $ and T has  $\mathsf {IP}$ .

Proof Suppose $\varphi (x, y)$ has $\mathsf {IP}$ , witnessed by $(a_i)_{i < \omega }$ , $(c_\sigma )_{\sigma \in 2^\omega }$ and $\psi (x,y)$ . We use the same $\psi (x,y)$ and $(a_i)_{i < \omega }$ to show that $\varphi (x,y)$ has $\mathsf {OP}$ . Let $\sigma _j \in 2^\omega $ be defined by

$$\begin{align*}\sigma_j(i) = \begin{cases} 1 & \text{if }i<j, \\ 0 & \text{if }i \geq j. \end{cases} \end{align*}$$

Then we get

$$ \begin{align*} &\models \varphi(a_i, c_{\sigma_j}) \quad\text{if} \ i < j, \\ &\models \psi(a_i, c_{\sigma_j}) \quad\text{if} \ i \geq j. \end{align*} $$

Therefore, $\varphi (x,y)$ has $\mathsf {OP}$ , witnessed by $(a_i)_{i < \omega }$ , $(c_{\sigma _j})_{j < \omega }$ and $\psi (x,y)$ .

Proof If $p(x, b)$ divides then let $(b_i)_{i < \omega }$ be an indiscernible sequence witnessing this. By compactness there is $\varphi (x, b) \in p(x, b)$ and some $k < \omega $ such that $\{\varphi (x, b_1), \ldots , \varphi (x, b_k)\}$ is inconsistent. So there is a negation $\psi (y_1, \ldots , y_k)$ of $\exists x(\varphi (x, y_1) \wedge \cdots \wedge \varphi (x, y_k))$ with $\models \psi (b_1, \ldots , b_k)$ . It then follows by C-indiscernibility that for all $i_1 < \cdots < i_k < \omega $ we have $\models \psi (b_{i_1}, \ldots , b_{i_k})$ .

Conversely, suppose that $\varphi (x, b) \in p(x, b)\ \psi $ -divides over C. Let $(b_i)_{i < \omega }$ be the infinite sequence witnessing this. By compactness we may elongate $(b_i)_{i < \omega }$ to $(b_i)_{i < \lambda }$ for suitably large $\lambda $ . Then by Lemma 2.6 we find an indiscernible sequence $(b^{\prime }_i)_{i < \omega }$ based on $(b_i)_{i < \lambda }$ . In particular, there are $i_1 < \cdots < i_k < \lambda $ such that $b^{\prime }_1 \ldots b^{\prime }_k \equiv _C b_{i_1} \ldots b_{i_k}$ . As we have $\models \psi (b_{i_1}, \ldots , b_{i_k})$ , we thus have $\models \psi (b^{\prime }_1, \ldots , b^{\prime }_k)$ . So $\{\varphi (x, b^{\prime }_1), \ldots , \varphi (x, b^{\prime }_k)\}$ is inconsistent and therefore $\bigcup _{i < \omega } p(x, b^{\prime }_i)$ is inconsistent. We conclude that $p(x, b)$ divides over C.

Fact 6.6 [Reference Dobrowolski and Kamsma7, Lemma 2.20].

Let T be a thick theory and M a $\lambda _T$ -saturated e.c. model, then $a \equiv _M a'$ implies $a \equiv ^{\text {Ls}}_M a'$ .

Fact 6.7 [Reference Dobrowolski and Kamsma7, Theorem 9.1].

Let T be a thick theory. Then T is $\mathsf {NSOP}_{1}$ if and only if there exists an automorphism invariant ternary relation on subsets, only allowing e.c. models in the base, satisfying the following properties $:$

• Finite Character: if for all finite $b_0 \subseteq b$ then .

• Existence: for any e.c. model M.

• Monotonicity: implies .

• Symmetry: implies .

• Chain Local Character: let a be a finite tuple and $\kappa> |T|$ be regular, then for every continuous chain $(M_i)_{i < \kappa }$ , with $|M_i| < \kappa $ for all i, there is $i_0 < \kappa $ such that , where $M = \bigcup _{i < \kappa } M_i$ .

• Independence Theorem: if , and with $a \equiv ^{\text {Ls}}_M a'$ then there is $a"$ such that $a"b \equiv ^{\text {Ls}}_M ab$ , $a"c \equiv ^{\text {Ls}}_M a'c$ and .

• Extension: if then for any c there is $a' \equiv _{Mb} a$ such that .

• Transitivity: if and with $M \subseteq N$ then .

Furthermore, in this case is given by non-Kim-dividing.

Fact 6.8 [Reference Ben-Yaacov3, Theorem 1.51] and [Reference Ben-Yaacov4, Theorem 1.15].

Let T be a thick theory. Then T is simple if and only if there exists an automorphism invariant ternary relation on subsets, only allowing e.c. models in the base, satisfying all the properties from Fact 6.7 as well as $:$

• Base-Monotonicity: if and $M \subseteq N \subseteq B$ , with N an e.c. model, then .

Furthermore, in this case is given by non-dividing.

In this fact we may restrict the base of further to $\kappa $ -saturated e.c. models for some fixed $\kappa $ .

Fact 6.9 [Reference Ben-Yaacov3, Theorem 2.8].

Let T be a thick theory. Then T is stable if and only if it is simple and dividing independence satisfies Stationarity over $\lambda _T$ -saturated e.c. models $:$ whenever M is a $\lambda _T$ -saturated e.c. model, , and $a \equiv _M a'$ then $a \equiv _{Mb} a'$ .

Proof If T is stable then Kim-dividing is the same as dividing by the canonicity parts of Facts 6.7 and 6.8, so by Fact 6.9 we have Stationarity over $\lambda _T$ -saturated e.c. models for Kim-dividing.

By the other direction of Fact 6.9 it suffices to prove that Stationarity for implies that T is simple. By Fact 6.8 it is then enough to prove that satisfies Base-Monotonicity, where we may in fact restrict ourselves in the base to $\lambda _T$ -saturated e.c. models. So let M be a $\lambda _T$ -saturated e.c. model such that , and let N be a ( $\lambda _T$ -saturated) e.c. model such that $M \subseteq N \subseteq B$ . By Existence we have , so by Extension we find $a' \equiv _N a$ with . By Monotonicity applied to we find and so . We then apply Transitivity to find . As $a \equiv _M a'$ we can apply Stationarity to find $a \equiv _B a'$ and so we conclude , as required.

Proof Standard, but we give the proof for completeness. By Existence we have . So by repeatedly applying Extension we find, for some big enough $\lambda $ , a sequence $(a^{\prime }_i)_{i < \lambda }$ with $a^{\prime }_i \equiv _M a$ and for all $i < \lambda $ . Then using Lemma 2.6 we base an M-indiscernible sequence $(a_i)_{i < \omega }$ on $(a^{\prime }_i)_{i < \lambda }$ , and by an automorphism we may assume $a_0 = a$ . By Finite Character it is then enough to verify that for any $i_1 < \cdots < i_n < \omega $ we have , which follows because there are $j_1 < \cdots < j_n < \lambda $ such that $a_{i_1} \ldots a_{i_n} \equiv _M a^{\prime }_{j_1} \ldots a^{\prime }_{j_n}$ .

Proof From Theorem 1.1 we already know that $\mathsf {IP}$ and $\mathsf {SOP}_{1}$ imply $\mathsf {OP}$ , i.e., instability. For the other direction we will prove that any thick unstable $\mathsf {NSOP}_{1}$ theory has $\mathsf {IP}$ .

As T is unstable we have by Proposition 6.10 that there is a $\lambda _T$ -saturated e.c. model M such that Stationarity over M fails. That is, there are $a_0, a_1, b$ such that , and $a_0 \equiv _M a_1$ while $a_0 \not \equiv _{Mb} a_1$ . Write $p_0(x, y) = \operatorname {\mathrm {tp}}(a_0 b / M)$ and $p_1(x, y) = \operatorname {\mathrm {tp}}(a_1 b / M)$ . Use Lemma 6.12 to find an -Morley sequence $(b_i)_{i < \omega }$ with $b_0 = b$ . We will now construct $(a_\eta )_{\eta \in 2^{< \omega }}$ by induction on the length (domain) of $\eta $ , such that for $\eta \in 2^n$ :

1. (1) $\models p_{\eta (i)}(a_\eta , b_i)$ for all $i < n$ ,

2. (2) ,

3. (3) $a_\eta \equiv ^{\text {Ls}}_M a_0 \equiv ^{\text {Ls}}_M a_1$ .

For $a_{\langle 0 \rangle }$ and $a_{\langle 1 \rangle }$ we can just take $a_0$ and $a_1$ , respectively, where (3) is satisfied by Fact 6.6 and the fact that M is $\lambda _T$ -saturated. Now assume that $(a_\eta )_{\eta \in 2^{\leq n}}$ has been constructed and let $\eta \in 2^{n+1}$ . As $b_n \equiv ^{\text {Ls}}_M b_0 = b$ we can find $a'$ such that $a' b_n \equiv ^{\text {Ls}}_M a_{\eta (n)} b$ . We also have , and , so by Independence Theorem we find the required $a_\eta $ , where (1)–(3) are easily verified using the induction hypothesis and the application of Independence Theorem.

By (1) and compactness we now find $(a_\sigma )_{\sigma \in 2^\omega }$ such that $a_\sigma \models \bigcup _{i < \omega } p_{\sigma (i)}(x, b_i)$ for every $\sigma \in 2^\omega $ . As $p_0(x, y)$ and $p_1(x, y)$ are distinct, there is $\varphi (x, y) \in p_1(x, y)$ such that $\varphi (x, y) \not \in p_0(x, y)$ . So there is a negation $\psi (x, y)$ of $\varphi (x, y)$ with $\psi (x, y) \in p_0(x, y)$ . Now for any $\sigma \in 2^\omega $ and $i < \omega $ we have

$$\begin{align*}\begin{array}{rcccl} \sigma(i) = 1 & \implies & \models p_1(a_\sigma, b_i) & \implies & \models \varphi(a_\sigma, b_i), \\ \sigma(i) = 0 & \implies & \models p_0(a_\sigma, b_i) & \implies & \models \psi(a_\sigma, b_i). \end{array} \end{align*}$$

Any parameters from M contained in $\varphi (x, y)$ or $\psi (x, y)$ can be assumed to be part of the $b_i$ ’s, so we see that the formula $\theta (y, x) := \varphi (x, y)$ has $\mathsf {IP}$ .

Proof From Theorem 1.1 we know that if T has $\mathsf {SOP}_{1}$ or $\mathsf {TP}_{2}$ then it has $\mathsf {TP}$ . We will prove the converse by proving that a thick non-simple $\mathsf {NSOP}_{1}$ theory has $\mathsf {TP}_{2}$ . This uses that simplicity is equivalent to $\mathsf {NTP}$ , which is exactly Theorem 6.14.

Assume then that T is thick, non-simple, and $\mathsf {NSOP}_{1}$ . By Facts 6.7 and 6.8 we have that an $\mathsf {NSOP}_{1}$ theory is simple iff satisfies Base-Monotonicity. We have that always satisfies Base-Monotonicity by definition: if $\operatorname {\mathrm {tp}}(a/B)$ does not divide over M and $M \subseteq N$ are e.c. models contained in B then $\operatorname {\mathrm {tp}}(a/B)$ does not divide over N. Hence we must have . It follows easily from the definition of Kim-dividing (see, for example, [Reference Dobrowolski and Kamsma7, Remark 4.12]) that , so there must be $a, b, M$ with while . Write $p(x, b) = \operatorname {\mathrm {tp}}(a/Mb)$ and let $J = (b_j)_{j < \omega }$ be an M-indiscernible sequence with $b_0 = b$ such that $\bigcup _{j < \omega } p(x, b_j)$ is inconsistent. So there is $\varphi (x, y) \in p(x, y)$ together with a negation $\psi (y_1, \ldots , y_k)$ of $\exists x(\varphi (x, y_1) \wedge \cdots \wedge \varphi (x,y_k))$ such that for all $j_1 < \cdots < j_k < \omega $ we have $\models \psi (b_{j_1}, \ldots , b_{j_k})$ . We claim that $\varphi $ has k- $\mathsf {TP}_{2}$ , as witnessed by $\psi $ .

By Lemma 6.12 we find an -Morley sequence $(J_i)_{i < \omega }$ with $J_0 = J$ . For $i < \omega $ we write $J_i = (c_{i,j})_{j < \omega }$ . This yields an array $(c_{i,j})_{i,j < \omega }$ such that the following hold.

1. (1) For all $\sigma \in \omega ^\omega $ the set $\{\varphi (x, c_{i,\sigma (i)}) : i < \omega \}$ is consistent. First note that for any $i < \omega $ we have $c_{i,\sigma (i)} \equiv ^{\text {Ls}}_M c_{i,0} \equiv ^{\text {Ls}}_M c_{0, 0} = b$ . So $(c_{i,\sigma (i)})_{i < \omega }$ is an -independent sequence, all having the same Lascar strong type as b over M, hence by the usual inductive application of compactness and Independence Theorem we get that $\{\varphi (x, c_{i,\sigma (i)}) : i < \omega \}$ is consistent.

2. (2) For all $i < \omega $ and $j_1 < \cdots < j_k < \omega $ we have $\models \psi (c_{i,j_1}, \ldots , c_{i,j_k})$ . This follows because $J_i$ is an M-automorphic copy of $J_0 = J$ .

Any parameters from M contained in $\varphi $ or $\psi $ can be assumed to be part of the $c_{i,j}$ ’s, so we conclude that $\varphi $ does indeed have k- $\mathsf {TP}_{2}$ .