DIVIDING LINES BETWEEN POSITIVE THEORIES

Abstract

We generalise the properties $\mathsf {OP}$, $\mathsf {IP}$, k-$\mathsf {TP}$, $\mathsf {TP}_{1}$, k-$\mathsf {TP}_{2}$, $\mathsf {SOP}_{1}$, $\mathsf {SOP}_{2}$, and $\mathsf {SOP}_{3}$ to positive logic, and prove various implications and equivalences between them. We also provide a characterisation of stability in positive logic in analogy with the one in full first-order logic, both on the level of formulas and on the level of theories. For simple theories there are the classically equivalent definitions of not having $\mathsf {TP}$ and dividing having local character, which we prove to be equivalent in positive logic as well. Finally, we show that a thick theory T has $\mathsf {OP}$ iff it has $\mathsf {IP}$ or $\mathsf {SOP}_{1}$ and that T has $\mathsf {TP}$ iff it has $\mathsf {SOP}_{1}$ or $\mathsf {TP}_{2}$, analogous to the well-known results in full first-order logic where $\mathsf {SOP}_{1}$ is replaced by $\mathsf {SOP}$ in the former and by $\mathsf {TP}_{1}$ in the latter. Our proofs of these final two theorems are new and make use of Kim-independence.

1 Introduction

Model-theoretic dividing lines are used to measure how “tame” logical theories are. The most important such dividing lines can be formulated in terms of combinatorial properties. For example, a theory is stable if it does not have the order property. These various properties form an intricate diagram of implications and equivalences.

Positive logic is a generalisation of full first-order logic, and allows for the treatment of e.c. models of a non-companiable inductive theory [10], hyperimaginaries (e.g., the $(-)^{\text {heq}}$ construction, see [7, Subsection 10C]), continuous logic [5] and more [11]. Some of these dividing lines have recently been studied in positive logic [3, 7, 8, 10, 15, 18], and for some of them there is a positive version of the corresponding combinatorial property. However, these definitions and the implications between them that we know from full first-order logic are currently developed ad hoc, leaving gaps in the overall picture. For example, simplicity theory has been developed in positive logic [3, 15], but simplicity in positive logic has so far only been defined in terms of local character for dividing and is nowhere equated to the usual definition of not having the tree property. The main goal of this paper is to provide the definitions of and implications between the most important dividing lines in terms of combinatorial properties, while also proving equivalences with other characterisations of these dividing lines.

1.1 Main results

In full first-order logic stable formulas are characterised in various ways, for example, as those that do not have have $\mathsf {OP}$ (the order property) or by counting types. We recover this characterisation in positive logic in Theorem 3.11, tying together previous work on stability in positive logic from [3, 18]. Subsequently, we obtain the usual equivalence of definitions for a stable theory in Theorem 3.15: either through type counting or by the lack of $\mathsf {OP}$ .

Our first main result in the unstable setting is the implication diagram between the various combinatorial properties we consider. See the start of Section 5 for a discussion about the strictness of implications, and implications that are missing compared to full first-order logic.

Theorem 1.1. The following implications between properties hold for a positive theory T.

Like stable theories, simple theories can be defined in different ways, which are equivalent in full first-order logic. This includes defining simplicity in terms of local character for dividing, as is done in previous studies of simplicity in positive logic [3], or as those theories not having $\mathsf {TP}$ . We prove that these are equivalent in positive logic as well in Theorem 6.14.

Finally, we recall the following two famous theorems from full first-order logic. Here $\mathsf {SOP}$ stands for the strict order property, a property that we do not consider in this paper but that implies $\mathsf {SOP}_{3}$ (see also Remark 7.4).

Theorem 1.2 [19, Theorem II.4.7].

A full first-order theory T has $\mathsf {OP}$ iff it has $\mathsf {IP}$ or $\mathsf {SOP}$ .

Theorem 1.3 [19, Theorem III.7.11] ¹ .

A full first-order theory T has $\mathsf {TP}$ iff it has $\mathsf {TP}_{1}$ or $\mathsf {TP}_{2}$ .

We will prove the following versions of these theorems for positive logic.

Theorem 1.4. A thick theory T has $\mathsf {OP}$ iff it has $\mathsf {IP}$ or $\mathsf {SOP}_{1}$ . Equivalently: T is stable iff it is $\mathsf {NIP}$ and $\mathsf {NSOP}_{1}$ .

Theorem 1.5. A thick theory T has $\mathsf {TP}$ iff it has $\mathsf {SOP}_{1}$ or $\mathsf {TP}_{2}$ . Equivalently: T is simple iff it is $\mathsf {NSOP}_{1}$ and $\mathsf {NTP}_{2}$ .

For an in-depth discussion about why we use $\mathsf {NSOP}_{1}$ we refer to Remark 6.13. It is worth mentioning however that our proofs are completely different from the proofs of the original two theorems. Using recent developments on Kim-independence in $\mathsf {NSOP}_{1}$ theories we give proofs based on independence relations. Thickness is a mild assumption that is automatically satisfied in full first-order logic, see also Definition 6.4 and the discussion before it.

1.2 Overview

We start with the basics for positive logic in Section 2. We deal with the different characterisations of stable formulas and stable theories in Section 3. We then collect all the definitions of the various combinatorial properties we consider in Section 4. In Section 5 we prove the implications between the various properties, i.e., we prove Theorem 1.1. In Section 6 we consider interactions between independence relations and some of the combinatorial properties, obtaining the equivalence of definitions for a simple theory and proving Theorems 1.4 and 1.5. Finally, Section 7 discusses and asks some natural questions.

2 Preliminaries of positive logic

We only recall the definitions and facts about positive logic that we need, for a more extensive treatment and discussion, see [2, 16] and for a more survey-like overview, see [7, Section 2].

Definition 2.1. Fix a signature ${\mathcal {L}}$ . A positive formula in ${\mathcal {L}}$ is one that is obtained from combining atomic formulas using $\wedge $ , $\vee $ , $\top $ , $\bot $ , and $\exists $ . An h-inductive sentence is a sentence of the form $\forall x(\varphi (x) \to \psi (x))$ , where $\varphi (x)$ and $\psi (x)$ are positive formulas. A positive theory is a set of h-inductive sentences.

Whenever we say “formula” or “theory” we will mean “positive formula” and “positive theory” respectively, unless explicitly stated otherwise. This also means that every formula and theory we consider will be implicitly assumed to be positive.

Remark 2.2. We can study full first-order logic as a special case of positive logic. This is done through a process called Morleyisation. For this we add a relation symbol $R_\varphi (x)$ to our language for every full first-order formula $\varphi (x)$ . Then we have our theory (inductively) express that $R_\varphi (x)$ and $\varphi (x)$ are equivalent. This way every first-order formula is (equivalent to) a relation symbol, and thus in particular to a positive formula.

We are generally only interested in existentially closed models. These can be characterised in various ways, but the one that matters for us is the following.

Definition 2.3. A negation of a formula $\varphi (x)$ is a formula $\psi (x)$ such that $T \models \neg \exists x(\varphi (x) \wedge \psi (x))$ . Equivalently, $\psi (x)$ implies $\neg \varphi (x)$ modulo T.

Definition 2.4. We call a model M of a theory T existentially closed or e.c. if whenever $M \not \models \varphi (a)$ then there is a negation $\psi (x)$ of $\varphi (x)$ with $M \models \psi (a).$

Following our earlier convention about dropping the “positive” everywhere, a (positive) type will be a set of (positive) formulas, over some parameter set B, satisfied by some tuple a in some e.c. model M:

$$\begin{align*}\operatorname{\mathrm{tp}}(a/B) = \{ \varphi(x, b) : M \models \varphi(a, b) \text{ and } b \in B \}. \end{align*}$$

Throughout we will assume that our theories have the joint continuation property or JCP (that is, for any two models $M_1$ and $M_2$ there is a model N with homomorphisms $M_1 \rightarrow N \leftarrow M_2$ ). This is the positive version of working in a complete theory, and we can always extend a theory T to a theory with JCP by taking the set of all h-inductive sentences that are true in some e.c. model of T. Under the JCP assumption we can work in a monster model, and these can be constructed for positive theories using the usual techniques. We let the reader fix their favourite notion of smallness (e.g., fix a big enough cardinal $\kappa $ , and let “small” mean $< \kappa $ ). We recall the properties of a monster model $\mathfrak {M}$ :

• • existentially closed, $\mathfrak {M}$ is an e.c. model;

• • very homogeneous, for any small $a, b, C$ we have $\operatorname {\mathrm {tp}}(a/C) = \operatorname {\mathrm {tp}}(b/C)$ iff there is $f \in \operatorname {\mathrm {Aut}}(\mathfrak {M}/C)$ with $f(a) = b$ (we will also write $a \equiv _C b$ );

• • very saturated, any finitely satisfiable small set of formulas $\Sigma $ over $\mathfrak {M}$ is satisfiable in $\mathfrak {M}$ .

As usual, we will omit the monster model from notation. For example, we write $\models \varphi (a)$ instead of $\mathfrak {M} \models \varphi (a)$ .

We finish this section with the definition of indiscernible sequences and a lemma for finding such sequences. The construction of indiscernible sequences using Ramsey’s theorem fails in positive logic, but the construction using the Erdős–Rado theorem goes through and gives in fact a stronger result.

Definition 2.5. A sequence $(a_i)_{i \in I}$ (for some linear order I) is C-indiscernible if for any $i_1 < \cdots < i_n$ and $j_1 < \cdots < j_n$ in I we have $a_{i_1} \ldots a_{i_n} \equiv _C a_{j_1} \ldots a_{j_n}$ .

Lemma 2.6 [3, Lemma 1.2].

Let C be any parameter set, $\kappa $ any cardinal, and let $\lambda = \beth _{(2^{|T| + |C| + \kappa })^+}$ . Then for any sequence $(a_i)_{i < \lambda }$ of $\kappa $ -tuples there is a C-indiscernible sequence $(b_i)_{i < \omega }$ such that for all $n < \omega $ there are $i_1 < \cdots < i_n < \lambda $ with $b_1 \ldots b_n \equiv _C a_{i_1} \ldots a_{i_n}$ .

Definition 2.7. For a theory T we write $\lambda _T = \beth _{(2^{|T|})^+}$ .

Remark 2.8. Since inequality may not be positively definable, there may be infinite bounded positively definable sets in our monster. In fact, the cardinality of the e.c. models of a positive theory might be bounded (such a theory is called bounded), which results in a monster model that is itself “small”. An extreme example is the empty theory in the empty language, whose e.c. models are singletons, and so the monster is a singleton. However, there is no need for special treatment for these cases. It just means that if we speak about a sequence (or otherwise indexed set) of parameters $(a_i)_{i < \lambda }$ where $\lambda $ is larger than the cardinality of the monster, we will have duplicates in this sequence. Particularly, the only indiscernible sequences in bounded theories (or, more generally, in bounded positively definable sets) are the constant ones.

3 Positive stability

In this section we begin our treatment of dividing lines in positive theories from stability. We introduce the order property (Definition 3.5), the first example of the combinatorial properties which will be discussed in the next sections. Theorem 3.11 provides a characterisation of stable formulas in the positive context, analogous to the various characterising properties that are well known from full first-order logic. The techniques used in this section are adapted from [3, 9, 17, 18], as well as from the standard techniques used for full first-order theories. There is also work on stability in the positive setting in [1, Chapter 4], see Remark 3.19 for more details.

Definition 3.1. Let $\varphi (x, y)$ be a formula. For a and a parameter set B, we write

$$\begin{align*}\operatorname{\mathrm{tp}}_\varphi(a/B) = \{ \varphi(x, b) : \, \models \varphi(a, b) \text{ where } b \in B \}. \end{align*}$$

A $\varphi $ -type over B is a set of formulas of the form $\operatorname {\mathrm {tp}}_\varphi (a/B)$ for some a. So it is the restriction of a maximal type over B to just the $\varphi $ -formulas. We write ${\operatorname {S}}_\varphi (B)$ for the set of $\varphi $ -types over B.

Example 3.2. A $\varphi $ -type is not necessarily maximal. For example, consider the theory T with inequality and two disjoint unary predicates P and Q. The e.c. models of T are then simply two disjoint infinite sets. Let M be such an e.c. model and let $a \in P(M)$ and $b \in Q(M)$ . Let $\varphi (x)$ be the formula $P(x)$ : then $\operatorname {\mathrm {tp}}_\varphi (a) = \{ \varphi (x) \}$ , while $\operatorname {\mathrm {tp}}_\varphi (b) = \emptyset $ .

Definition 3.3. Let $\lambda $ be an infinite cardinal. A formula $\varphi (x, y)$ is $\lambda $ -stable if $|B| \leq \lambda $ implies $|{\operatorname {S}}_\varphi (B)| \leq \lambda $ . We call $\varphi (x, y)$ stable if it is $\lambda $ -stable for some $\lambda $ .

The following is taken from [3, Definition 2.1].

Definition 3.4. Let $p(x)$ be a type over B and let $\varphi (x, y)$ be a formula. A $\varphi $ -definition of $p(x)$ over C is a partial type ${\operatorname {d}}_p \varphi (y)$ over C with $|{\operatorname {d}}_p \varphi (y)| \leq |T|$ such that

$$\begin{align*}\varphi(x, b) \in p(x) \quad \Longleftrightarrow \quad \models {\operatorname{d}}_p \varphi(b). \end{align*}$$

We say that $p(x)$ is $\varphi $ -definable (over C) if it has a $\varphi $ -definition over C. If $p(x)$ is $\varphi $ -definable over B we just say it is $\varphi $ -definable.

Definition 3.5. A formula $\varphi (x,y)$ has the order property ( $\mathsf {OP}$ ) if there are sequences $(a_i)_{i < \omega }$ and $(b_i)_{i < \omega }$ and a negation $\psi (x,y)$ of $\varphi (x,y)$ such that for all $i, j < \omega $ , we have

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

Note that by compactness the exact shape of the linear order in the order property (Definition 3.5) does not matter. That is, we can replace $\omega $ with any infinite linear order. In fact, we can use this trick to state the order property in terms of indiscernible sequences, getting rid of the negation $\psi (x, y)$ .

Proposition 3.6. A formula $\varphi (x, y)$ has the order property iff there is an indiscernible sequence $(a_i b_i)_{i < \omega }$ such that

$$\begin{align*}\models \varphi(a_i, b_j) \quad \Longleftrightarrow \quad i < j. \end{align*}$$

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)$ .

Definition 3.7. A formula $\varphi (x, y)$ is said to have the binary tree property if there is a negation $\psi (x, y)$ of $\varphi (x, y)$ together with $(b_\eta )_{2^{< \omega }}$ such that for every $\sigma \in 2^\omega $ the set

$$\begin{align*}\{ \chi_{\sigma(n)}(x, b_{\sigma|_n}) : n < \omega \} \end{align*}$$

is consistent, where $\chi _0 := \varphi $ and $\chi _1 := \psi $ .

Definition 3.8 ([3, Definition 2.1], simplified).

For contradictory formulas $\varphi (x, y)$ and $\psi (x, y)$ we define the $(\varphi , \psi )$ -rank $R_{\varphi , \psi }(-)$ as follows. The input is a set of formulas (possibly with parameters) in free variables x. Then $R_{\varphi , \psi }(-)$ is the least function into the ordinals (together with ${-}1$ and $\infty $ ) such that:

• • $R_{\varphi , \psi }(\Sigma ) \geq 0$ if $\Sigma (x)$ is consistent;

• • $R_{\varphi , \psi }(\Sigma ) \geq \alpha + 1$ if there is some b such that $R_{\varphi , \psi }(\Sigma \cup \{\varphi (x, b)\}) \geq \alpha $ and $R_{\varphi , \psi }(\Sigma \cup \{\psi (x, b)\}) \geq \alpha $ ;

• • $R_{\varphi , \psi }(\Sigma ) \geq \ell $ if $R_{\varphi , \psi }(\Sigma ) \geq \alpha $ for all $\alpha < \ell $ , where $\ell $ is a limit ordinal.

Lemma 3.9. Let $\varphi (x, y)$ and $\psi (x, y)$ be contradictory formulas.

1. (i) If $\Sigma (x)$ implies $\Sigma '(x)$ then $R_{\varphi , \psi }(\Sigma ) \leq R_{\varphi , \psi }(\Sigma ')$ .

2. (ii) The property $R_{\varphi , \psi }(\Sigma ) \geq n$ is type-definable by

   $$\begin{align*}\exists (y_\eta)_{\eta \in 2^{< n}} \left( \bigwedge_{\sigma \in 2^n} \exists x \left( \Sigma(x) \wedge \bigwedge_{k < n} \chi_{\sigma(k)}(x, y_{\sigma|_k}) \right) \right), \end{align*}$$
   where $\chi _0$ and $\chi _1$ are $\varphi $ and $\psi $ respectively. In particular, if $\Sigma $ is finite $($ i.e., a formula $)$ , then this is just a formula.

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 $ .

Lemma 3.10. A formula $\varphi (x, y)$ has the binary tree property iff there is a negation $\psi (x, y)$ of $\varphi (x, y)$ such that $R_{\varphi , \psi }(x=x) \geq \omega $ .

Proof By Lemma 3.9 and compactness.

Theorem 3.11. The following are equivalent for a formula $\varphi (x, y){:}$

1. (i) $\varphi $ is stable,

2. (ii) $|{\operatorname {S}}_\varphi (B)| \leq (|B| + |T|)^{|T|}$ for every B,

3. (iii) $\varphi $ does not have the order property,

4. (iv) $\varphi $ does not have the binary tree property,

5. (v) $R_{\varphi ,\psi }(x=x) < \omega $ for every negation $\psi (x, y)$ of $\varphi (x, y)$ ,

6. (vi) for any B every type over B is $\varphi $ -definable.

Proof The equivalence (iv) $\Leftrightarrow $ (v) is Lemma 3.10. The equivalence between (i), (ii), (v), and (vi) is exactly [3, 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., [21, 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.

Example 3.12. In full first-order logic, for a formula $\varphi (x, y)$ the following are equivalent (see, e.g., [21, Theorem 8.2.3]):

1. (i) $\varphi $ is stable,

2. (ii) there is no sequence $(a_i b_i)_{i < \omega }$ such that $\models \varphi (a_i, b_j)$ iff $i < j$ ,

3. (iii) $|{\operatorname {S}}_\varphi (B)| \leq |B|$ for any infinite B.

Of course, (ii) is the classical formulation of the order property. In a full first-order theory this is easily seen to be equivalent to Definition 3.5: just take $\psi (x, y)$ to be $\neg \varphi (x, y)$ . Point (iii) is a stronger version of Theorem 3.11(ii).

We will show that this equivalence generally fails in positive logic. That is, we will construct a theory together with a stable formula $\varphi (x, y)$ (in fact, the entire theory will be stable) such that (ii) and (iii) fail for $\varphi $ .

Write $\mathbb {Q}_{(0,1)} = \{q \in \mathbb {Q} : 0 < q < 1\}$ . Consider the language ${\mathcal {L}}$ with a constant for each element of $\mathbb {Q}_{(0,1)}$ , and an order symbol $\leq $ . Considering the obvious ${\mathcal {L}}$ -structure on $\mathbb {Q}_{(0,1)}$ , we let T be the set of all h-inductive sentences true in $\mathbb {Q}_{(0,1)}$ . One quickly verifies that the real unit interval $[0, 1]$ is a maximal e.c. model for this theory. So the number of $\varphi $ -types is bounded by $2^{\aleph _0}$ , for any $\varphi $ . Hence every formula is stable.

Consider the formula $\varphi (x, y)$ given by $x \leq y$ . For $n < \omega $ set $a_n = 1-\frac {1}{n+2}$ and $b_n = 1-\frac {1}{n+1}$ . Then clearly $\models \varphi (a_i, b_j)$ iff $i < j$ , so (ii) fails for $\varphi (x, y)$ . The important difference with Definition 3.5 is of course that for $i \geq j$ there is not just one uniform reason (in the form of a negation of $\varphi $ ) for $\not \models \varphi (a_i, b_j)$ .

Using the same formula $\varphi (x, y)$ , we let $B = \mathbb {Q}_{(0,1)}$ . The $\varphi $ -types over B then correspond exactly to real numbers in $[0,1]$ , via Dedekind cuts. So we have $|{\operatorname {S}}_\varphi (B)| = 2^{\aleph _0}> \aleph _0 = |B|$ , and hence (iii) fails. As B only contains constants we may even take $B = \emptyset $ , but then B is no longer infinite, which is technically required for (iii).

Generally, this example shows that in positive logic we may find some infinite linear order in a stable theory, but as long as they are bounded this should not cause instability. Intuitively this is because growth (e.g., of the type spaces) beyond that bound is then again well-behaved.

Note that in particular this sort of behaviour can also appear in unbounded theories, if they have bounded sorts or bounded positively definable sets. For example, we could add a separate sort with a symbol for inequality to the theory in this example, and have our theory state that the additional sort is an infinite set. The theory is now unbounded, but the example still goes through.

With the adjusted definitions for stability of a formula, we get the usual equivalent definitions of a stable theory. The arguments are standard, but we include them for completeness’ sake.

Definition 3.13. Let $\lambda $ be an infinite cardinal. A theory T is $\lambda $ -stable if $|B| \leq \lambda $ implies $|{\operatorname {S}}_n(B)| \leq \lambda $ for all $n < \omega $ , where ${\operatorname {S}}_n(B)$ is the set of n-types with parameters in B. We call T stable if it is $\lambda $ -stable for some $\lambda $ .

Example 3.14. Any bounded theory is stable: since every type must be realised in the monster, we have for all $n < \omega $ that $|S_n(\mathfrak {M})|=|\mathfrak {M}|$ . Considering $|\mathfrak {M}|$ is fine here, because in bounded theories the monster is small, see Remark 2.8.

Theorem 3.15. The following are equivalent for a theory $T{:}$

1. (i) T is stable,

2. (ii) all formulas in T are stable,

3. (iii) T is $\lambda $ -stable for all $\lambda $ such that $\lambda ^{|T|} = \lambda $ .

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.

In the remainder of this section we finish the proof of Theorem 3.11.

Definition 3.16. Let $\varphi (x, y)$ and $\psi (y, z)$ be formulas without parameters and let $A \subseteq B$ be sets of parameters. We say that a type $p(x) \in {\operatorname {S}}_\varphi (B)\ (\psi , \varphi )$ -splits over A if there are $b, b' \in B$ such that $\operatorname {\mathrm {tp}}_\psi (b/A) = \operatorname {\mathrm {tp}}_\psi (b'/A)$ while $\varphi (x, b) \in p(x)$ and $\varphi (x, b') \not \in p(x)$ .

Lemma 3.17. Let $\varphi (x, y)$ and $\psi (y, z)$ be formulas without parameters, and let $A \subseteq C$ be parameter sets.

1. (i) Suppose B is such that $A \subseteq B \subseteq C$ and it realises every $\psi $ -type over A that is realised in C. Then if $p_1, p_2 \in {\operatorname {S}}_\varphi (C)$ do not $(\psi , \varphi )$ -split over A we have that $p_1|_B = p_2|_B$ implies $p_1 = p_2$ .

2. (ii) There are at most $2^{|{\operatorname {S}}_\psi (A)| + |A| + |T|}$ many types in ${\operatorname {S}}_\varphi (C)$ that do not $(\psi , \varphi )$ -split over A.

3. (iii) If $\lambda \geq |A| + |T|$ then there are at most $2^{2^\lambda }$ many types in ${\operatorname {S}}_\varphi (C)$ that do not $(\psi , \varphi )$ -split over A.

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 $ .

We can now fill in the final missing piece of Theorem 3.11. The proof strategy used here is based on [9].

Lemma 3.18. If a formula $\varphi (x, y)$ does not have the order property then it is stable.

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$ .

Proof of claim

Suppose for a contradiction that the claim is false. Then there is some $\alpha < \mu ^+$ such that for all $\alpha < i < \mu ^+$ there is $j_i < \lambda _T$ and $B_i \subseteq A_{j_i}$ of cardinality at most $\lambda _T$ such that $\operatorname {\mathrm {tp}}_\varphi (a_i / A_{j_i})$ does not $(\chi , \varphi )$ -split over $B_i$ . As $\mu ^+> \lambda _T$ , by the pigeonhole principle, we can find some $I \subseteq \mu ^+$ with $|I| = \mu ^+$ such that $j_i = j_{i'}$ for all $i,i' \in I$ . Write j for $j_i$ , where $i \in I$ . As $\mu ^+> \mu = \mu ^{\lambda _T} \geq |A_j|^{\lambda _T}$ we can apply the pigeonhole principle again to find $I' \subseteq I$ with $|I'| = \mu ^+$ and $B_i = B_{i'}$ for all $i,i' \in I'$ . Write B for $B_i$ , where $i \in I'$ . We have that $A \subseteq A_j$ , so for any distinct $i, i' \in I'$ we have that $\operatorname {\mathrm {tp}}_\varphi (a_i / A_j) \neq \operatorname {\mathrm {tp}}_\varphi (a_{i'} / A_j)$ . We thus find $\mu ^+> 2^{2^{\lambda _T}}$ many types that do not $(\chi , \varphi )$ -split over a set of cardinality at most $\lambda _T$ . This contradicts Lemma 3.17(iii) and completes the proof of the claim.

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.

Remark 3.19. We compare the work in this section to [1, Chapter 4]. Their Definition 4.10 is a definition for the order property for formulas $\varphi (x, y)$ where x and y are tuples of variables of the same length (and sorts). One quickly verifies that their order property implies our Definition 3.5. Conversely, given $\varphi (x, y)$ satisfying our Definition 3.5, as witnessed by $(a_i)_{i < \omega }$ , $(b_i)_{i < \omega }$ and $\psi (x, y)$ , the formula $\theta (x_1 y_1, x_2 y_2) := \varphi (x_1, y_2)$ has the order property in the sense of [1] as witnessed by $(a_i b_i)_{i < \omega }$ and negation $\psi '(x_1 y_1, x_2 y_2) := \psi (x_1, y_2)$ . Another difference is that [1] treats bounded theories separately, proving in [1, Lemme 4.8] that they are stable. However, as we noted in Remark 2.8, there is no need for such special treatment: we have seen how stability of bounded theories fits in our approach in Example 3.14. Given the translation of the notion of stability for formulas, we get the same results as [1] on the level of theories. However, our version allows for local stability and comparison to further combinatorial properties on the level of formulas (e.g., Corollary 5.9).

4 Definitions of the combinatorial properties

In this section we gather the definitions of the combinatorial properties we will consider. The definitions are very similar to those we know from full first-order logic, and they do indeed coincide when considering a full first-order theory as a positive theory (Remark 2.2). The main ingredient, which we already used in Definition 3.5 for $\mathsf {OP}$ , is the idea of [10, Section 6] to introduce “inconsistency witnesses”. Whenever a traditional definition would say that a set of formulas is inconsistent, we now require the satisfaction of a positive formula that implies the inconsistency of that set of formulas. For example, if we would normally say that $\{\varphi (x, a_1), \varphi (x, a_2)\}$ is inconsistent, we now want $\models \psi (a_1, a_2)$ where $\psi (y_1, y_2)$ is a negation of $\exists x(\varphi (x, y_1) \wedge \varphi (x, y_2))$ . The importance of this is that we can then use compactness to change the size or shape of the set of parameters involved. For example, instead of only considering sequences of shape $\omega $ for $\mathsf {OP}$ we can consider any infinite sequence.

Definition 4.1. A formula $\varphi (x,y)$ has the independence property ( $\mathsf {IP}$ ) if there are $(a_i)_{i < \omega }$ , $(c_\sigma )_{\sigma \in 2^\omega }$ and a negation $\psi (x,y)$ of $\varphi (x,y)$ such that for all $i < \omega $ and $\sigma \in 2^\omega $ we have

$$ \begin{align*} &\models \varphi(a_i, c_\sigma) \quad\text{if} \ \sigma(i) = 1, \\ &\models \psi(a_i, c_\sigma) \quad\text{if} \ \sigma(i) = 0. \end{align*} $$

The study of $\mathsf {IP}$ in positive logic has been initiated in the recent preprint [8] by Dobrowolski and Mennuni.

Definition 4.2. Let $\kappa $ and $\lambda $ be (potentially finite) cardinals. As usual, we will consider the set $\kappa ^{<\lambda }$ of functions $\eta : \alpha \to \kappa $ where $\alpha < \lambda $ , as a tree. The partial order on the tree is given by $\eta \preceq \mu $ if $\mu $ extends $\eta $ as a function. We call $\eta $ and $\mu $ incomparable if $\eta \not \preceq \mu $ and $\mu \not \preceq \eta $ . For any $\eta , \mu \in \kappa ^{<\lambda }$ we write $\eta ^\frown \mu $ for their concatenation (viewing the functions as strings of ordinals $< \kappa $ ).

Definition 4.3. For a natural number $k \geq 2$ , a formula $\varphi (x,y)$ has the k-tree property (k- $\mathsf {TP}$ ) if there are $(a_\eta )_{\eta \in \omega ^{< \omega }}$ and a negation $\psi (y_1, \ldots , y_k)$ of the formula $\exists x (\varphi (x, y_1) \wedge \cdots \wedge \varphi (x, y_k))$ such that:

1. (1) for all $\sigma \in \omega ^\omega $ the set $\{ \varphi (x, a_{\sigma |_n}): n < \omega \}$ is consistent,

2. (2) for all $\eta \in \omega ^{< \omega }$ and $i_1 < \ldots < i_k < \omega $ we have $\models \psi (a_{\eta ^\frown i_1}, \ldots , a_{\eta ^\frown i_k})$ .

A formula $\varphi (x,y)$ has the tree property ( $\mathsf {TP}$ ) if there exists a natural number $k \geq 2$ such that $\varphi (x,y)$ has k- $\mathsf {TP}$ .

Definition 4.4. A formula $\varphi (x,y)$ has the tree property of the first kind ( $\mathsf {TP}_{1}$ ) if there are $(a_\eta )_{\eta \in \omega ^{< \omega }}$ and a negation $\psi (y_1,y_2)$ of $\exists x (\varphi (x,y_1) \wedge \varphi (x,y_2))$ such that:

1. (1) for all $\sigma \in \omega ^\omega $ the set $\{\varphi (x,a_{\sigma |_n}) : n < \omega \}$ is consistent,

2. (2) for all incomparable $\mu ,\eta \in \omega ^{<\omega }$ we have $\models \psi (a_\mu ,a_\eta )$ .

Definition 4.5. A formula $\varphi (x,y)$ has the k-tree property of the second kind (k- $\mathsf {TP}_{2}$ ) if there are $(a_{i,j})_{i,j < \omega }$ and a negation $\psi (y_1, \ldots , y_k)$ of the formula $\exists x (\varphi (x, y_1) \wedge \cdots \wedge \varphi (x, y_k))$ such that:

1. (1) for all $\sigma \in \omega ^\omega $ the set $\{ \varphi (x, a_{i, \sigma (i)}): i < \omega \}$ is consistent,

2. (2) for all $i < \omega $ and $j_1 < \cdots < j_k < \omega $ we have $\models \psi (a_{i,j_1}, \ldots , a_{i,j_k})$ .

A formula $\varphi (x,y)$ has the tree property of the second kind ( $\mathsf {TP}_{2}$ ) if there exists a natural number $k \geq 2$ such that $\varphi (x,y)$ has k- $\mathsf {TP}_{2}$ .

The definition of $\mathsf {TP}_{2}$ in positive logic first appeared in [10], as did the following definition of $\mathsf {SOP}_{1}$ .

Definition 4.6. A formula $\varphi (x,y)$ has the $1$ -strong order property ( $\mathsf {SOP}_{1}$ ) if there are $(a_\eta )_{\eta \in 2^{<\omega }}$ and a negation $\psi (y_1,y_2)$ of $\exists x (\varphi (x,y_1) \wedge \varphi (x,y_2))$ such that:

1. (1) for all $\sigma \in 2^\omega $ the set $\{\varphi (x,a_{\sigma |_n}) : n < \omega \}$ is consistent,

2. (2) for all $\mu , \eta \in 2^{<\omega }$ , if $\mu ^\frown 0 \preceq \eta $ then $\models \psi (a_{\mu ^\frown 1}, a_\eta )$ .

Definition 4.7. A formula $\varphi (x,y)$ has the $2$ -strong order property ( $\mathsf {SOP}_{2}$ ) if there are $(a_\eta )_{\eta \in 2^{< \omega }}$ and a negation $\psi (y_1,y_2)$ of $\exists x (\varphi (x,y_1) \wedge \varphi (x,y_2))$ such that:

1. (1) for all $\sigma \in 2^\omega $ the set $\{\varphi (x,a_{\sigma |_n}) : n < \omega \}$ is consistent,

2. (2) for all incomparable $\mu ,\eta \in 2^{<\omega }$ we have $\models \psi (a_\mu ,a_\eta )$ .

Definition 4.8. A theory T has one of the properties above ( $\mathsf {OP}$ , $\mathsf {IP}$ , k- $\mathsf {TP}$ , k- $\mathsf {TP}_{2}$ , $\mathsf {SOP}_{1}$ , $\mathsf {SOP}_{2}$ ) if there exists a formula witnessing it.

Definition 4.9. A theory T has the $3$ -strong order property ( $\mathsf {SOP}_{3}$ ) if there are formulas $\varphi _0(x,y)$ and $\varphi _1(x,y)$ , a sequence $(a_i)_{i < \omega }$ , and a negation $\psi (y_1,y_2)$ of $\exists x (\varphi _0(x,y_2) \wedge \varphi _1(x,y_1))$ such that:

1. (1) for all $k < \omega $ the $\{\varphi _0(x,a_i):i < k\} \cup \{\varphi _1(x,a_j):j \geq k\} $ is consistent,

2. (2) for all $i<j<\omega $ we have $\models \psi (a_i,a_j)$ .

In the full first-order setting, $\mathsf {SOP}_{3}$ is usually defined on the level of formulas with a definition which easily generalizes to any natural number larger than $3$ , giving rise to the notion of an $\mathsf {SOP}_{\mathrm {n}}$ formula (or theory). This definition heavily relies on the use of negation, which forms an obstruction to translating it to the positive setting, see Remark 7.4. The definition given here, on the level of theories, is based on [20, Claim 2.19].

Definition 4.10. If a theory T does not have one of the properties $\mathsf {OP}$ , $\mathsf {IP}$ , $\mathsf {TP}$ , $\mathsf {TP}_{1}$ , $\mathsf {TP}_{2}$ , $\mathsf {SOP}_{1}$ , $\mathsf {SOP}_{2}$ , $\mathsf {SOP}_{3}$ , we say that T is $\mathsf {NOP}$ , $\mathsf {NIP}$ , $\mathsf {NTP}$ , $\mathsf {NTP}_{1}$ , $\mathsf {NTP}_{2}$ , $\mathsf {NSOP}_{1}$ , $\mathsf {NSOP}_{2}$ , $\mathsf {NSOP}_{3}$ , respectively.

5 Implications between the combinatorial properties

In this section we prove Theorem 1.1 by proving the implications between the various properties of positive theories defined in Section 4. We break up the proof in its individual components, stating each arrow separately. We start from the left-most implication and make our way inside the diagram. Some of the implications will be proved on a formula level (e.g., Proposition 5.3) and for some implications this will only happen on a theory level (e.g., Corollary 5.7).

Remark 5.1. We make some remarks about the strictness of the implications in Theorem 1.1.

• • The strictness of the implication ${\mathsf {SOP}_{3}} \implies {\mathsf {SOP}_{2}}$ is also still open in full first-order logic. See also Question 7.2.

• • Mutchnik’s recent preprint [14] proves the implication ${\mathsf {SOP}_{1}} \implies {\mathsf {SOP}_{2}}$ in full first-order logic. As the machinery used there is considerably more involved than what we apply here, we do not deal with this problem and leave it to future work, see Question 7.1.

• • In full first-order logic we have $k\text{-}{\mathsf {TP}_{2}} \implies 2\text{-}{\mathsf {TP}_{2}}$ . A recent preprint by the third author proves this for thick theories [12, Theorem 1.4]. See also Remark 7.3.

• • The remaining implications are known to be strict, already in full first-order logic.

Proposition 5.2. If a theory T has $\mathsf {SOP}_{3}$ then it has $\mathsf {SOP}_{2}$ .

This proof is based on the similar argument in Proposition 1.8 of [6], adapted to the definition of $\mathsf {SOP}_{3}$ at the level of theories that we use here.

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.

Proposition 5.3. A formula $\varphi (x,y)$ has $\mathsf {SOP}_{2}$ if and only if it has $\mathsf {TP}_{1}$ .

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 $ .

Proposition 5.4. If a formula $\varphi (x,y)$ has $\mathsf {SOP}_{2}$ then it has $\mathsf {SOP}_{1}$ .

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)$ .

Proposition 5.5. If a formula $\varphi (x,y)$ has $\mathsf {SOP}_{1}$ then it has $2$ - $\mathsf {TP}$ .

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 $ .

The following argument is based on [19, Theorem III.7.7].

Theorem 5.6. If $\varphi (x, y)$ has $\mathsf {TP}$ then for some $k'$ the conjunction $\varphi (x, y_1) \wedge \cdots \wedge \varphi (x, y_{k'})$ has $2$ - $\mathsf {TP}$ .

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).

Corollary 5.7. A theory T has $\mathsf {TP}$ if and only if it has $2$ - $\mathsf {TP}$ .

Proposition 5.8. Suppose $\varphi (x,y)$ has $2$ - $\mathsf {TP}$ . Then there exists an infinite set B such that $|{\operatorname {S}}_\varphi (B)|> (|B| + |T|)^{|T|}$ .

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 $ .

Corollary 5.9. If a formula $\varphi (x,y)$ has $2$ - $\mathsf {TP}$ then it has $\mathsf {OP}$ .

Proof By Proposition 5.8 and Theorem 3.11.

Proposition 5.10. If a formula $\varphi (x,y)$ has k- $\mathsf {TP}_{2}$ then it has k- $\mathsf {TP}$ .

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}$ .

Proposition 5.11. If a theory T has $2$ - $\mathsf {TP}_{2}$ then it has $\mathsf {IP}$ .

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}$ .

Proposition 5.12. If a formula $\varphi (x,y)$ has $\mathsf {IP}$ then it has $\mathsf {OP}$ .

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)$ .

6 Interactions with independence relations

In this section we study the interaction between independence relations and some of the combinatorial properties studied above. We first recall the notion of dividing and the corresponding definition of simplicity, and the way different notions of independence interact with a theory being $\mathsf {NSOP}_{1}$ , simple or stable. We do not define Kim-dividing or use it directly; we rely on the axiomatic characterization of the notion of independence given in [7, Theorem 9.1].

Definition 6.1. Let $p(x, b) = \operatorname {\mathrm {tp}}(a/Cb)$ be a type. We say that $p(x, b)$ divides over C if there is a C-indiscernible sequence $(b_i)_{i < \omega }$ , with $b_0 \equiv _C b$ , such that $\bigcup _{i < \omega } p(x, b_i)$ is inconsistent. We write if $\operatorname {\mathrm {tp}}(a/Cb)$ does not divide over C.

Lemma 6.2. A type $p(x, b) = \operatorname {\mathrm {tp}}(a/Cb)$ divides over C if and only if it contains a formula $\varphi (x, b) \in p(x, b)$ and there are a negation $\psi (y_1, \ldots , y_k)$ of $\exists x(\varphi (x, y_1) \wedge \cdots \wedge \varphi (x, y_k))$ and some infinite sequence $(b_i)_{i < \omega }$ such that $b_i \equiv _C b$ for all $i < \omega $ and for all $i_1 < \cdots < i_k < \omega $ we have $\models \psi (b_{i_1}, \ldots , b_{i_k})$ .

The above lemma is the positive variant of k-dividing (see, e.g., [21, Definition 7.1.2]). The role of k is replaced by $\psi $ , and accordingly we say in the situation of Lemma 6.2 that $\varphi (x, b)\ \psi $ -divides over C. The proof is standard, but instructive on how $\psi $ is used.

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.

Definition 6.3. We say that a theory T is simple if dividing has local character. That is, there is some cardinal $\lambda $ such that for any finite a and any parameter set B there is $B_0 \subseteq B$ with $|B_0| \leq \lambda $ such that $\operatorname {\mathrm {tp}}(a/B)$ does not divide over $B_0$ .

To make independence work nicely in simple and $\mathsf {NSOP}_{1}$ positive theories we need the mild assumption of thickness from [4]. Note that in particular every theory in full first-order logic, viewed as a positive theory, is thick.

Definition 6.4. A theory T is called thick if being an indiscernible sequence is type-definable. So there is a partial type $\Theta ((x_i)_{i < \omega })$ such that $\models \Theta ((a_i)_{i < \omega })$ iff $(a_i)_{i < \omega }$ is an indiscernible sequence.

Definition 6.5. We write ${\operatorname {d}}_B(a, a') \leq n$ if there are $a = a_0, a_1, \ldots , a_n = a'$ such that $a_i$ and $a_{i+1}$ are on a B-indiscernible sequence for all $0 \leq i < n$ . We say that a and $a'$ have the same Lascar strong type  $(over B)$ , and write $a \equiv ^{\text {Ls}}_B a'$ , if ${\operatorname {d}}_B(a, a') \leq n$ for some $n < \omega $ .

Fact 6.6 [7, 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 [7, 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 [3, Theorem 1.51] and [4, 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 [3, 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'$ .

In Fact 6.9 we use $\lambda _T$ -saturated e.c. models, because we want types over these e.c. models to be Lascar strong types (see Fact 6.6). The proof of [3, Theorem 2.8] works with $|T|^+$ -saturated e.c. models, but goes through for $\lambda _T$ -saturated e.c. models as well (noting that $\lambda _T> |T|^+$ ).

Proposition 6.10. A thick $\mathsf {NSOP}_{1}$ theory T is stable iff Kim-independence satisfies Stationarity over $\lambda _T$ -saturated e.c. models.

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.

Definition 6.11. Let M be some e.c. model. An -Morley sequence is an M-indiscernible sequence $(a_i)_{i < \omega }$ such that for all $i < \omega $ .

Lemma 6.12. Let T be a thick $\mathsf {NSOP}_{1}$ theory, and let a be any tuple and M be any e.c. model. Then there is an -Morley sequence $(a_i)_{i < \omega }$ with $a_0 = a$ .

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}$ .

Theorem 1.4, repeated. A thick theory T has $\mathsf {OP}$ iff it has $\mathsf {IP}$ or $\mathsf {SOP}_{1}$ . Equivalently $: T$ is stable iff it is $\mathsf {NIP}$ and $\mathsf {NSOP}_{1}$ .

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}$ .

Theorem 1.5, repeated. A thick theory T has $\mathsf {TP}$ iff it has $\mathsf {SOP}_{1}$ or $\mathsf {TP}_{2}$ . Equivalently $: T$ is simple iff it is $\mathsf {NSOP}_{1}$ and $\mathsf {NTP}_{2}$ .

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, [7, 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}$ .

Remark 6.13. Compared to Theorem 1.2 we replaced $\mathsf {SOP}$ by $\mathsf {SOP}_{1}$ in Theorem 1.4, which gives a weaker result. However, it is not even clear how the $\mathsf {SOP}$ property should be formulated in positive logic, see also Remark 7.4. In the Theorem 1.5 we replaced $\mathsf {TP}_{1}$ by $\mathsf {SOP}_{1}$ , compared to Theorem 1.3, again giving an a priori slightly weaker result. However, for full first-order logic Mutchnik’s recent preprint [14] proves that $\mathsf {SOP}_{1}$ is equivalent to $\mathsf {TP}_{1}$ , and it is very reasonable to expect the same thing in positive logic, see also Question 7.1.

It is worth noting that the proofs of both theorems here are completely different from the classical proofs for Theorems 1.2 and 1.3. In particular, modulo Mutchnik’s result, Theorem 1.5 gives a completely new proof of Theorem 1.3.

For the remainder of this section we shift our focus to the equivalent definitions of a simple theory.

Theorem 6.14. A theory T is simple if and only if it does not have $\mathsf {TP}$ .

Proof $\mathsf {TP}$ $\implies $ failure of local character. Take any cardinal $\lambda $ and suppose that $\varphi (x, y)$ has $\mathsf {TP}$ . By compactness we can assume this is witnessed by $(c_\eta )_{\eta \in \kappa ^{< \lambda ^+}}$ for $\kappa = (2^{|T| + \lambda ^+})^+$ and $\psi (y_1, \ldots , y_k)$ .

We construct some $\sigma \in \kappa ^{\lambda ^+}$ by induction on its length (i.e., its domain). Suppose we have already defined $\sigma |_\gamma $ for some $\gamma < \lambda ^+$ . Write $C = \{c_{\sigma |_i} : i \leq \gamma \}$ and $\eta = \sigma |_{\gamma }$ . Consider the set of types $\{\operatorname {\mathrm {tp}}(c_{\eta ^\frown i} / C) : i < \kappa \}$ . There are at most $2^{|T| + \lambda ^+}$ different types over C, so by our choice of $\kappa $ and the pigeonhole principle there exists infinite $I_\gamma \subseteq \kappa $ such that for any $i, j \in I_\gamma $ we have $\operatorname {\mathrm {tp}}(c_{\eta ^\frown i} / C) = \operatorname {\mathrm {tp}}(c_{\eta ^\frown j} / C)$ . Let $i_0$ be the least element of $I_\gamma $ and define $\sigma (\gamma ) = i_0$ .

Now that the construction of $\sigma $ is finished we write $b_i = c_{\sigma |_i}$ for $i < \lambda ^+$ . With this notation, and using the fact that $(c_\eta )_{\eta \in \kappa ^{< \lambda ^+}}$ witnesses $\mathsf {TP}$ for $\varphi (x, y)$ , we find some a realising $\{\varphi (x, b_i) : i < \lambda ^+ \}$ . We claim that $\operatorname {\mathrm {tp}}(a / (b_i)_{i < \lambda ^+})$ divides over every subset $B_0 \subseteq (b_i)_{i<\lambda ^+}$ with $|B_0| \leq \lambda $ . Suppose for a contradiction that $\operatorname {\mathrm {tp}}(a / (b_i)_{i < \lambda ^+})$ does not divide over some $B_0 \subseteq (b_i)_{i<\lambda ^+}$ , where $|B_0| \leq \lambda $ . Let $\gamma < \lambda ^+$ such that $B_0 \subseteq (b_i)_{i<\gamma }$ . Then $\operatorname {\mathrm {tp}}(a / (b_i)_{i < \lambda ^+})$ does not divide over $(b_i)_{i<\gamma }$ by Base-Monotonicity (which holds for dividing in any theory, as already mentioned in the proof of Theorem 1.5). We have $\varphi (x, b_\gamma ) \in \operatorname {\mathrm {tp}}(a / (b_i)_{i<\lambda ^+})$ , hence by Lemma 6.2 it suffices to prove that $\varphi (x, b_\gamma )\ \psi $ -divides over $(b_i)_{i<\gamma }$ . Enumerate the set $I_\gamma $ from the construction of $\sigma $ as $i_0 < i_1 < \ldots $ and let $d_j = c_{{\sigma |_\gamma }^\frown i_j}$ for $j < \omega $ . Note that $d_0 = b_\gamma $ . Then by the construction of $I_\gamma $ , $(d_j)_{j < \omega }$ is a sequence of realizations of $\operatorname {\mathrm {tp}}(b_\gamma / (b_i)_{i<\gamma })$ . Moreover, by $\mathsf {TP}$ we also have $\models \psi (d_{j_1}, \ldots , d_{j_k})$ for all $j_1 < \cdots < j_k < \omega $ . Therefore, $\operatorname {\mathrm {tp}}(a/(b_i)_{i<\lambda ^+})$ divides over $B_0$ and T does not have local character.

Failure of local character $\implies $ $\mathsf {TP}$ . Let $\lambda = |T|^+$ . As local character for dividing fails there is some finite a and a parameter set B such that $\operatorname {\mathrm {tp}}(a/B)$ divides over $B_0$ for every $B_0 \subseteq B$ with $|B_0| \leq \lambda $ .

We construct a tree $(c_\eta )_{\eta \in \omega ^{< \lambda }}$ by induction on its height. Let $\zeta _\alpha \in \omega ^\alpha $ denote the constant zero function. As induction hypothesis for step $\delta $ we use three statements:

• • $c_{\zeta _\alpha }$ is a finite tuple of elements from B for all $\alpha \leq \delta $ ;

• • $(c_{\eta |_\alpha })_{\alpha \leq \delta } \equiv (c_{\zeta _\alpha })_{\alpha \leq \delta }$ for all $\eta \in \omega ^\delta $ ;

• • if $\delta = \gamma + 1$ is a successor then there are $\varphi _\delta (x, y)$ and a negation $\psi _\delta (y_1, \ldots , y_{k_\delta })$ of $\exists x (\varphi _\delta (x, y_1) \wedge \cdots \wedge \varphi _\delta (x, y_{k_\delta }))$ such that for any $\eta \in \omega ^\gamma $ and any $i_1 < \cdots < i_{k_\delta } < \omega $ we have $\models \psi _\delta (c_{\eta ^\frown i_1}, \ldots , c_{\eta ^\frown i_{k_\delta }})$ .

For $\delta < \lambda $ limit or zero we let all $c_\eta $ , where $\eta \in \omega ^\delta $ , be the empty tuple. Now suppose that we constructed $(c_\eta )_{\eta \in \omega ^{\leq \delta }}$ and we need to construct level $\delta +1$ . As $c_{\zeta _\alpha }$ is a finite tuple for all $\alpha \leq \delta $ and $\delta < \lambda $ , we have that $|\{c_{\zeta _\alpha } : \alpha \leq \delta \}| < \lambda $ and so $\operatorname {\mathrm {tp}}(a/B)$ divides over $\{c_{\zeta _\alpha } : \alpha \leq \delta \}$ . By Lemma 6.2 there exists formulas $\varphi _{\delta +1}(x, d) \in \operatorname {\mathrm {tp}}(a/B)$ and a negation $\psi _{\delta +1}(y_1, \ldots , y_{k_{\delta +1}})$ of $\exists x (\varphi _{\delta +1}(x, y_1) \wedge \cdots \wedge \varphi _{\delta +1}(x, y_{k_{\delta +1}}))$ together with a sequence $(d_i)_{i< \omega }$ such that $d_i \equiv _{(c_{\zeta _\alpha })_{\alpha \leq \delta }} d$ for all $i < \omega $ and for any $i_1 < \cdots < i_{k_{\delta +1}} < \omega $ we have $\models \psi _{\delta +1}(d_{i_1}, \ldots , d_{i_{k_{\delta +1}}})$ . By an automorphism we may assume $d_0 = d$ . Note that $d_0$ is a finite tuple of elements from B. We start by defining $c_{\zeta _\delta ^\frown i}$ to be $d_i$ for all $i < \omega $ . Since $d_i \equiv _{(c_{\zeta _\alpha })_{\alpha \leq \delta }} d_j$ for all $i, j < \omega $ , we have $(c_{{\zeta _\delta ^\frown i}|_\alpha })_{\alpha \leq \delta +1} \equiv (c_{\zeta _\alpha })_{\alpha \leq \delta +1}$ . Now take any $\eta \in \omega ^\delta $ . We know by induction hypothesis that $(c_{\eta |_\alpha })_{\alpha \leq \delta } \equiv (c_{\zeta _\alpha })_{\alpha \leq \delta }$ . Let $(c_{\eta ^\frown i})_{i < \omega }$ be such that $(c_{\eta ^\frown i})_{i < \omega } (c_{\eta |_\alpha })_{\alpha \leq \delta } \equiv (d_i)_{i < \omega } (c_{\zeta _\alpha })_{\alpha \leq \delta }$ . Then the induction hypothesis holds by construction. Moreover, since for any $i_1 < \cdots < i_{k_{\delta +1}} < \omega $ we have $\models \psi _{\delta +1}(d_{i_1}, \ldots , d_{i_{k_{\delta +1}}})$ , we now also get $\models \psi _{\delta +1}(c_{\eta ^\frown i_1}, \ldots , c_{\eta ^\frown i_{k_{\delta +1}}})$ . This completes the inductive construction of the tree $(c_\eta )_{\eta \in \omega ^{< \lambda }}$ .

There are $|T|$ possible pairs of formulas $\varphi (x,y)$ and $\psi (y_1, \ldots , y_k)$ but we have $\lambda = |T|^+$ successor levels, and each is assigned a pair $\varphi _\delta (x,y)$ and $\psi _\delta (y_1, \ldots , y_{k_\delta })$ . Hence, by pigeonhole principle we can choose an infinite set of successor levels $l_0 < l_1 < l_2 < \ldots $ having the same $\varphi _\delta $ and $\psi _\delta $ . We denote these just as $\varphi (x,y)$ and $\psi (y_1, \ldots , y_k)$ . We consider a subtree $(f_\mu )_{\mu \in \omega ^{< \omega }}$ that consists only of the chosen levels (with the root being the leftmost point on level $l_0$ ). That is, for $\mu \in \omega ^{< \omega }$ of length n we define $\eta _\mu \in \omega ^{l_n}$ of length $l_n$ as

$$\begin{align*}\eta_\mu(l) = \begin{cases} \mu(i), & \text{if } l = l_{i+1} - 1,\\ 0, & \text{otherwise.} \end{cases} \end{align*}$$

Note that $l_{i+1} - 1$ makes sense, because we only chose successor levels. Let $f_\mu = c_{\eta _\mu }$ .

We claim $(f_\mu )_{\mu \in \omega ^{< \omega }}$ and $\psi $ witness $\mathsf {TP}$ for $\varphi $ . Let $\sigma \in \omega ^\omega $ . By construction $\{\varphi (x, f_{\zeta _n}) : n < \omega \} \subseteq \operatorname {\mathrm {tp}}(a/B)$ , and so this set is consistent. Then since $(f_{\sigma |_n})_{n < \omega } \equiv (f_{\zeta _n})_{n < \omega }$ we get that $\{\varphi (x, f_{\sigma |_n}) : n < \omega \}$ is consistent. Finally take any $\mu \in \omega ^{< \omega }$ and $i_1 < \cdots < i_k < \omega $ . The elements $f_{\mu ^\frown i_1}, \ldots , f_{\mu ^\frown i_k}$ are equal to $c_{\eta ^\frown i_1}, \ldots , c_{\eta ^\frown i_k}$ for some $\eta \in \omega ^{< \lambda }$ . Hence, by construction of the subtree, we get $\models \psi (f_{\mu ^\frown i_1}, \ldots , f_{\mu ^\frown i_k})$ . We conclude that $\varphi $ , and thus T, has $\mathsf {TP}$ .

Remark 6.15. In [3] simplicity of a theory is defined as dividing having local character, as we did here. In [15] simplicity is defined as forking having local character. Note that trivially local character of forking implies local character of dividing. In thick theories the converse is true: by [4, Theorem 1.15] non-dividing satisfies Extension and so dividing coincides with forking.

Without the thickness assumption the converse can fail. By [3, Example 4.3] there is a stable positive theory T with a type over the empty set that forks over the empty set.

The above example motivates our choice of terminology for simplicity, because if we defined simplicity in terms of local character for forking then stability would not imply simplicity. Furthermore, the fact that local character of dividing is equivalent to $\mathsf {NTP}$ (Theorem 6.14) does not need thickness. So the T from above is an example of an $\mathsf {NTP}$ theory where local character for forking fails, further motivating our choice of terminology.

7 Further discussion and open questions

In light of the recent [14], where it is shown that $\mathsf {SOP}_{1}$ is equivalent to $\mathsf {SOP}_{2}$ for theories in full first-order logic, the following is a natural question.

Question 7.1. Is $\mathsf {SOP}_{1}$ equivalent to $\mathsf {SOP}_{2}$ in positive logic? As Mutchnik’s proof [14] makes heavy use of various notions of independence, and these tend to work better in thick theories [4, 7], it would be natural to assume thickness in order to answer this question.

Question 7.2. Is $\mathsf {SOP}_{3}$ equivalent to $\mathsf {SOP}_{2}$ , and so, if Question 7.1 has a positive answer, also equivalent to $\mathsf {SOP}_{1}$ ?

Remark 7.3. In full first-order logic we have that if $\varphi (x, y)$ has k- $\mathsf {TP}_{2}$ for some $k \geq 2$ then some conjunction $\bigwedge _{i = 1}^n \varphi (x, y_i)$ has $2$ - $\mathsf {TP}_{2}$ [13, Proposition 5.7]. The proof for this makes use of array-indiscernibles and array-modelling. The development of these tools is out of the scope of this paper, but it is done in a recent preprint [12] by the third author. In particular, [12, Theorem 1.4] proves the above statement for thick theories. This implies in particular that a thick theory has $2$ - $\mathsf {TP}_{2}$ iff it has k- $\mathsf {TP}_{2}$ for some $k \geq 2$ .

Remark 7.4. In this work we left out the $\mathsf {SOP}_{\mathrm {n}}$ hierarchy for $n \geq 4$ , as well as the strict order property $\mathsf {SOP}$ . It is not clear what would be the right definition of these properties in positive logic. The combinatorial properties we have considered all have a similar form: there is some combinatorial configuration of parameters and we require a formula to be consistent along certain parts of those parameters, while being inconsistent along other parts. The only change for positive logic is then that we require this inconsistency to be uniformly witnessed by some negation. However, $\mathsf {SOP}_{\geq 4}$ and $\mathsf {SOP}$ are defined in a different way and, unlike $\mathsf {SOP}_{3}$ , there is no known equivalent formulation of the above form.

Remark 7.5. The first work to consider the independence property $\mathsf {IP}$ in positive logic is [8]. There some basics for positive $\mathsf {NIP}$ theories are developed, such as closure of $\mathsf {NIP}$ formulas under conjunctions and disjunctions and the fact that one can swap the roles of the variables. On the level of theories they also prove that to verify that a theory is $\mathsf {NIP}$ one only needs to check the formulas $\varphi (x, y)$ where y is a single variable (as opposed to a tuple of variables).

Remark 7.6. In positive logic we can add hyperimaginaries (e.g., the $(-)^{\text {heq}}$ -construction) in the same way we can add imaginaries (e.g., the $(-)^{\text {eq}}$ -construction) in full first-order logic, see [7, Subsection 10C] for details. In [7, Theorem 10.18] it is proved that whether a theory is $\mathsf {SOP}_{1}$ or $\mathsf {NSOP}_{1}$ is preserved under such hyperimaginary extensions. As is remarked there as well, the proof strategy should go through for any of the combinatorial properties discussed in this paper. For $\mathsf {NIP}$ the details of this are verified in [8, Proposition 6.22].