TRANSITIVITY, LOWNESS, AND RANKS IN NSOP$_{1}$ THEORIES

Abstract

We develop the theory of Kim-independence in the context of NSOP$_{1}$ theories satisfying the existence axiom. We show that, in such theories, Kim-independence is transitive and that -Morley sequences witness Kim-dividing. As applications, we show that, under the assumption of existence, in a low NSOP$_{1}$ theory, Shelah strong types and Lascar strong types coincide and, additionally, we introduce a notion of rank for NSOP$_{1}$ theories.

1 Introduction

This paper furthers the development of the theory of Kim-independence in the context of NSOP $_{1}$ theories satisfying the existence axiom. Building on earlier work in [4] and a suggestion of the second-named author [11], Kim-independence was introduced in [7], where it was shown to be a well-behaved notion of independence in NSOP $_{1}$ theories. This work established a strong analogy between the theory of non-forking independence in simple theories and Kim-independence in NSOP $_{1}$ theories, an analogy which subsequent works have only deepened [8, 9, 13]. Nonetheless, one major difference between the two notions of independence is that, unlike non-forking which makes sense over all sets, Kim-independence is only a sensible notion of independence over models: Kim-independence is defined in terms of formulas that divide with respect to a Morley sequence in a global invariant type, and such a sequence, in general, is only guaranteed to exist over a model. In [5], the second- and third-named author, together with Dobrowolski, focused on the context of NSOP $_{1}$ theories that satisfy the existence axiom. There, it was shown that Kim-independence may be defined over arbitrary sets and basic theorems of Kim-independence over models hold in this broader context.

The existence axiom states that every complete type has a global non-forking extension, i.e., every set is an extension base in the terminology of [3]. This is equivalent to the statement that, in every type, there is a (non-forking) Morley sequence and, hence, assuming existence, one may redefine Kim-independence in terms of the formulas that divide along Morley sequences of this kind. New technical challenges arise in this setting, but in [5] it was shown that Kim-independence satisfies Kim’s lemma, symmetry, and the independence theorem for Lascar strong types. Moreover, all simple theories and all known examples in the growing list of NSOP $_{1}$ theories satisfy existence, and it is expected to hold in all NSOP $_{1}$ theories (see, e.g., [5, Fact 2.14]).

Here we continue work on Kim-independence in NSOP $_{1}$ theories satisfying existence, in particular, exploring aspects of the theory that are too cumbersome or uninteresting over models. In Section 3, we show that Kim-independence is transitive in an NSOP $_{1}$ theory satisfying existence and that, moreover, Kim-dividing is witnessed by -Morley sequences. These results were first established over models for all NSOP $_{1}$ theories in [8] and our proofs largely follow the same strategy. Nonetheless, suitable replacements need to be found for notions that only make sense, in general, over models, like heirs and coheirs. We find that arguments involving these notions can often be replaced by an argument involving a tree-induction, as in the construction of tree Morley sequences in [8]. In Section 4, we apply these results to low NSOP $_{1}$ theories satisfying existence, showing that Shelah strong types and Lascar strong types coincide, generalizing a result of Buechler for simple theories [1] (see also [12, 17]). In Section 5, we introduce a notion of rank for NSOP $_{1}$ theories and establish some of its basic properties. Finally, in Section 6, we generalize the Kim–Pillay criterion for Kim-independence from [4, Theorem 6.1] and [8, Theorem 6.11] to give a criterion for NSOP $_{1}$ in theories satisfying existence, which, additionally, gives an abstract characterization of Kim-independence over arbitrary sets in this setting.

2 Preliminaries

In this paper, T will always be a complete theory with monster model $\mathbb {M}$ . We will implicitly assume all models and sets of parameters are small, that is, of cardinality less than the degree of saturation and homogeneity of $\mathbb {M}$ . If we discuss an I-indexed indiscernible sequence $(a_{i})_{i \in I}$ , we will implicitly assume I is linearly ordered by $<$ and, given $i \in I$ , we will write $a_{<i}$ and $a_{\leq i}$ for the subsequences $(a_{j})_{j < i}$ and $(a_{j})_{j \leq i}$ respectively.

Definition 2.1. Suppose A is a set of parameters.

1. (1) We say that a formula $\varphi (x;a)$ divides over a set A if there is an A-indiscernible sequence $\langle a_{i} : i < \omega \rangle $ with $a_{0} = a$ such that $\{\varphi (x;a_{i}) : i < \omega \}$ is inconsistent.

2. (2) A formula $\varphi (x;a)$ is said to fork over A if $\varphi (x;a) \vdash \bigvee _{i < k} \psi _{i}(x;c_{i})$ , for some $k < \omega $ , with $\psi _{i}(x;c_{i})$ dividing over A.

3. (3) We say a partial type divides (forks) over A if it implies a formula that divides (forks) over A.

4. (4) For tuples a and b, we write or to indicate that $\text {tp}(a/Ab)$ does not divide over A or does not fork over A, respectively.

5. (5) A Morley sequence $(a_{i})_{i \in I}$ over A is an infinite A-indiscernible sequence such that for all $i \in I$ . If $p \in S(A)$ , we say $(a_{i})_{i \in I}$ is a Morley sequence in p if, additionally, $a_{i} \models p$ for all $i \in I$ .

The following is one of the key definitions of this paper. It defines a context in which Kim-independence may be studied over arbitrary sets.

Definition 2.2. We define the existence axiom to be any one of the following equivalent conditions on T:

1. (1) For all parameter sets A, any type $p \in S(A)$ does not fork over A.

2. (2) For all parameter sets A, no consistent formula over A forks over A.

3. (3) For all parameter sets A, every type $p \in S(A)$ has a global extension that does not fork over A.

4. (4) For all parameter sets A and any $p\in S(A)$ , there is a Morley sequence in p.

If T satisfies the existence axiom, we will often abbreviate this by writing T is with existence. See, e.g., [5, Remark 2.6] for the equivalence of (1)–(4).

Under existence, we may define Kim-independence over arbitrary sets. The following definition was given in [5], but it was observed already in [7, Theorem 7.7] that this agrees with the original definition over models.

Definition 2.3. Suppose T satisfies the existence axiom.

1. (1) We say a formula $\varphi (x;a)$ Kim-divides over A if there is a sequence $\langle a_{i} : i < \omega \rangle $ which is a Morley sequence over A with $a_{0} = a$ and $\{\varphi (x;a_{i}) : i < \omega \}$ inconsistent.

2. (2) A formula $\varphi (x;a)$ is said to Kim-fork over A if $\varphi (x;a) \vdash \bigvee _{i < k} \psi _{i}(x;c_{i})$ , where each $\psi _{i}(x;c_{i})$ Kim-divides over A.

3. (3) We say a type Kim-divides (Kim-forks) over A if it implies a formula that Kim-divides (Kim-forks) over A.

4. (4) For tuples a and b, we write to indicate that $\text {tp}(a/Ab)$ does not Kim-divide over A.

5. (5) An -Morley sequence $(a_{i})_{i \in I}$ over A is an infinite A-indiscernible sequence such that for all $i \in I$ .

Remark 2.4. By Kim’s lemma [12, Proposition 2.2.6], if T is simple, a formula Kim-divides over a set A if and only if it divides over A.

Definition 2.5 [6, Definition 2.2].

The formula $\varphi (x;y)$ has SOP $_{1}$ if there is a collection of tuples $(a_{\eta })_{\eta \in 2^{<\omega }}$ so that:

• • For all $\eta \in 2^{\omega }$ , $\{\varphi (x;a_{\eta | \alpha }) : \alpha < \omega \}$ is consistent.

• • For all $\eta \in 2^{<\omega }$ , if $\nu $ extends $\eta \frown \langle 0 \rangle $ , then $\{\varphi (x;a_{\nu }), \varphi (x;a_{\eta \frown 1})\}$ is inconsistent,

where $\unlhd $ denotes the tree partial order on $2^{<\omega }$ . We say T is SOP $_{1}$ if some formula has SOP $_{1}$ modulo T. T is NSOP $_{1}$ otherwise.

Definition 2.6. Suppose A is a set of parameters.

1. (1) We say that tuples a and b have the same (Shelah) strong type over A, written $a \equiv ^{S}_{A} b$ , if $E(a,b)$ holds (i.e., $E(a',b')$ holds for all corresponding finite subtuples $a'$ and $b'$ of a and b, respectively) for every A-definable equivalence relation $E(x,y)$ with finitely many classes.

2. (2) The group $\mathrm {Autf}(\mathbb {M}/A)$ of Lascar strong automorphisms (of the monster) over A is the subgroup of $\mathrm {Aut}(\mathbb {M}/A)$ generated by $\bigcup \{\mathrm {Aut}(\mathbb {M}/M) : A \subseteq M \prec \mathbb {M} \}$ . We say a and b have the same Lascar strong type over A, written $a \equiv ^{L}_{A} b$ , if there is some $\sigma \in \mathrm {Autf}(\mathbb {M}/A)$ such that $\sigma (a) = b$ . By a Lascar strong type over A, we mean an equivalence class of the relation $\equiv ^{L}_{A}$ .

3. (3) A type-definable equivalence relation E on $\alpha $ -tuples, for an ordinal $\alpha $ , is called bounded if it has small number of classes. We say a and b have the same KP-strong type over A, written $a \equiv ^{\mathrm {KP}}_{A} b$ , if $E(a,b)$ holds for all bounded type-definable equivalence relations over A.

4. (4) We say that T is G-compact over A when $a \equiv ^{L}_{A} b$ if and only if $a \equiv ^{\mathrm {KP}}_{A} b$ for all (possibly infinite) tuples $a,b$ . We say T is G-compact if it is G-compact over all finite sets A.

In [5], several basic facts about Kim-independence in NSOP $_{1}$ theories with existence were established. As we will make extensive use of them throughout the paper, we record them below.

Fact 2.7. Assume T is NSOP $_{1}$ with existence and A is a set of parameters. Then the following properties hold.

1. (1) Extension: If $\pi (x)$ is a partial type over $B \supseteq A$ which does not Kim-divide over A, then there is a completion $p \in S(B)$ of $\pi $ that does not Kim-divide over A. In particular, if and c is arbitrary, there is some $a' \equiv _{Ab} a$ such that [5, Proposition 4.1].

2. (2) Symmetry: [5, Corollary 4.9].

3. (3) Kim’s lemma for Morley sequences: The formula $\varphi (x;a)$ Kim-divides over A if and only if $\{\varphi (x;a_{i}) : i < \omega \}$ is inconsistent for all Morley sequences $\langle a_{i} : i < \omega \rangle $ over A with $a_{0} = a$ [5, Theorem 3.5].

4. (4) Kim-forking = Kim-dividing: If a formula $\varphi (x;a)$ Kim-forks over A, then $\varphi (x;a)$ Kim-divides over A [5, Proposition 4.1].

5. (5) The chain condition: If and $I = \langle b_{i} : i < \omega \rangle $ is a Morley sequence over A with $b_{0} = b$ , then there is $a' \equiv _{Ab} a$ such that I is $Aa'$ -indiscernible and (this follows from (3), as in, e.g., [5, Corollary 5.15]).

6. (6) The independence theorem for Lascar strong types: If $a_{0} \equiv ^{L}_{A} a_{1}$ , , , and , then there is some $a_{*}$ with $a_{*} \equiv ^{L}_{Ab} a_{0}$ , $a_{*} \equiv ^{L}_{Ac} a_{1}$ , and [5, Theorem 5.8].

7. (7) $T_{A}$ is G-compact for any small set A, where $T_{A}$ is the theory of the monster model in the language with constants for the elements of A [5, Corollary 5.9].

As these facts make up part of the standard tool box for reasoning about Kim-independence, we will often make implicit use of these properties. For example, Kim’s lemma for Morley sequences, item (3) in the above list, is often used in this paper in the following way: if $I = \langle a_{i} : i < \omega \rangle $ is a Morley sequence over A with $a_{0} = a$ which is $Ab$ -indiscernible, then . To see this, by symmetry (Item (2)), it suffices to show that which, by item (4), means that we need to show that there is no formula $\varphi (x;a) \in \text {tp}(b/Aa)$ which Kim-divides over A. But if $\varphi (x;a)$ Kim-divides over A, then Kim’s lemma implies that $\{\varphi (x;a_{i}) : i < \omega \}$ is inconsistent. This set of formulas, however, is realized by b so there can be no such formula.

The following is local character of Kim-independence for NSOP $_{1}$ theories. The usual formulation of local character for non-forking independence in simple theories merely asserts that, for any type $p \in S(A)$ , the set of B with $|B| \leq |T|$ such that p does not fork over B is non-empty, but it follows by base monotonicity, then, that p does not fork over C for any $B \subseteq C \subseteq A$ . Because Kim-independence, in general, does not satisfy base monotonicity in NSOP $_{1}$ theories, the following is the appropriate analogue for this setting:

Fact 2.8 [9, Theorem 3.9].

Suppose T is NSOP $_{1}$ and $M \models T$ with $|M| \geq |T|$ . Given any $p \in S(M)$ (in finitely many variables), the set X defined by

$$ \begin{align*} X := \{N \prec M : |N| = |T| \text{ and } p \text{ does not Kim-divide over }N\} \end{align*} $$

satisfies the following:

1. (1) X is closed: if $\langle N_{i} : i < |T| \rangle $ is a sequence of models in X with $N_{i} \subseteq N_{j}$ for all $i < j$ , then $\bigcup _{i < |T|} N_{i} \in X$ .

2. (2) X is unbounded: if $Y \subset M$ has cardinality $\leq |T|$ , there is some $N \in X$ with $Y \subseteq N$ .

Remark 2.9. It is an easy consequence of Fact 2.8 that if $M \models T$ is equal to the union of $\langle N_{i} : i < |T|^{+}\rangle $ , an increasing and continuous (i.e., $N_{\delta } = \bigcup _{i < \delta } N_{i}$ for all limit $\delta $ ) elementary chain of models of T of size $|T|$ , then for any $p \in S(M)$ , there is some $i < |T|^{+}$ such that p does not Kim-divide over $N_{i}$ .

2.1 Trees

At several points in the paper, we will construct indiscernible sequences by an inductive construction of indiscernible trees. We recall the basic framework for these ‘tree-inductions’ from [7]. For an ordinal $\alpha $ , let the language $L_{s,\alpha }$ be $\langle \unlhd , \wedge , <_{lex}, (P_{\beta })_{\beta \leq \alpha } \rangle $ . For us, a tree will mean a partial order $\unlhd $ such that for all x, the elements $\{y : y \unlhd x\}$ below x are linearly ordered (and not necessarily well-ordered) by $\unlhd $ and such that for all $x,y$ , x and y have an infimum, i.e., there is a $\unlhd $ -greatest element $z \unlhd x,y$ , which is called the meet of x and y. We may view a tree with $\alpha $ levels as an $L_{s,\alpha }$ -structure by interpreting $\unlhd $ as the tree partial order, $\wedge $ as the binary meet function, $<_{lex}$ as the lexicographic order, and $P_{\beta }$ interpreted to define level $\beta $ . The specific trees, and the interpretations of these symbols that turn them into $L_{s,\alpha }$ -structures, that we will need in this paper are outlined precisely in Definition 2.12.

We now recall the modeling property. In what follows, we will write $\mathrm {qftp}_{L'}(a)$ to denote the quantifier-free type of a in the language $L'$ and write $\text {tp}_{\Delta }(b/A)$ to denote the $\Delta $ -type of b over A (i.e., the set of positive and negative instances of formulas in $\Delta $ with parameters from A satisfied by b). Although the subscript is used in two conflicting ways, it will be clear from context which is intended.

Definition 2.10. Suppose I is an $L'$ -structure, where $L'$ is some language.

1. (1) We say $(a_{i} : i \in I)$ is a set of I-indexed indiscernibles over A if whenever

   $(s_{0}, \ldots , s_{n-1})$ , $(t_{0}, \ldots , t_{n-1})$ are tuples from I with

   $$ \begin{align*} \text{qftp}_{L'}(s_{0}, \ldots, s_{n-1}) = \text{qftp}_{L'}(t_{0}, \ldots, t_{n-1}), \end{align*} $$
   then we have
   $$ \begin{align*} \text{tp}(a_{s_{0}},\ldots, a_{s_{n-1}}/A) = \text{tp}(a_{t_{0}},\ldots, a_{t_{n-1}}/A). \end{align*} $$

2. (2) In the case that $L' = L_{s,\alpha }$ for some $\alpha $ , we say that an I-indexed indiscernible is s-indiscernible. As the only $L_{s,\alpha }$ -structures we will consider will be trees, we will often refer to I-indexed indiscernibles in this case as s-indiscernible trees.

3. (3) We say that I-indexed indiscernibles have the modeling property if, given any $(a_{i} : i \in I)$ from $\mathbb {M}$ and any A, there is an I-indexed indiscernible $(b_{i} : i \in I)$ over A in $\mathbb {M}$ locally based on $(a_{i} : i \in I)$ over A. That is, given any finite set of formulas $\Delta $ from $L(A)$ and a finite tuple $(t_{0}, \ldots , t_{n-1})$ from I, there is a tuple $(s_{0}, \ldots , s_{n-1})$ from I so that

   $$\begin{align*}\text{qftp}_{L'} (t_{0}, \ldots, t_{n-1}) =\text{qftp}_{L'}(s_{0}, \ldots , s_{n-1}) \end{align*}$$
   and also
   $$\begin{align*}\text{tp}_{\Delta}(b_{t_{0}}, \ldots, b_{t_{n-1}}) = \text{tp}_{\Delta}(a_{s_{0}}, \ldots, a_{s_{n-1}}). \end{align*}$$

Fact 2.11 [14, Theorem 4.3].

Let $I_{s}$ denote the $L_{s,\omega }$ -structure

$$ \begin{align*} I_{s} = (\omega^{<\omega}, \unlhd, <_{lex}, \wedge, (P_{\alpha})_{\alpha < \omega}) \end{align*} $$

with all symbols being given their intended interpretations and each $P_{\alpha }$ naming the elements of the tree at level $\alpha $ . Then $I_{s}$ -indexed indiscernibles have the modeling property.

Our trees will be understood to be an $L_{s,\alpha }$ -structure for some appropriate $\alpha $ . As in [7], we introduce a distinguished class of trees $\mathcal {T}_{\alpha }$ .

Definition 2.12. Suppose $\alpha $ is an ordinal. We define $\mathcal {T}_{\alpha }$ to be the set of functions f such that:

• • $\text {dom}(f)$ is an end-segment of $\alpha $ of the form $[\beta ,\alpha )$ for $\beta $ equal to $0$ or a successor ordinal. If $\alpha $ is a successor, we allow $\beta = \alpha $ , i.e., $\text {dom}(f) = \emptyset $ .

• • $\text {ran}(f) \subseteq \omega $ .

• • Finite support: The set $\{\gamma \in \text {dom}(f) : f(\gamma ) \neq 0\}$ is finite.

We interpret $\mathcal {T}_{\alpha }$ as an $L_{s,\alpha }$ -structure by defining:

• • $f \unlhd g$ if and only if $f \subseteq g$ . Write $f \perp g$ if $\neg (f \unlhd g)$ and $\neg (g \unlhd f)$ .

• • $f \wedge g = f|_{[\beta , \alpha )} = g|_{[\beta , \alpha )}$ where $\beta = \text {min}\{ \gamma : f|_{[\gamma , \alpha )} =g|_{[\gamma , \alpha )}\}$ , if non-empty (note that $\beta $ will not be a limit, by finite support). Define $f \wedge g$ to be the empty function if this set is empty (note that this cannot occur if $\alpha $ is a limit).

• • $f <_{lex} g$ if and only if $f \vartriangleleft g$ or, $f \perp g$ with $\text {dom}(f \wedge g) = [\gamma +1,\alpha )$ and $f(\gamma ) < g(\gamma ).$

• • For all $\beta \leq \alpha $ , $P_{\beta } = \{ f \in \mathcal {T}_{\alpha } : \text {dom}(f) = [\beta , \alpha )\}$ . Note that $P_{0}$ are the leaves of the tree (i.e., the top level) and $P_{\alpha }$ is empty for $\alpha $ limit.

Fact 2.11 and compactness can be used to show that $\mathcal {T}_{\alpha }$ -indexed indiscernibles have the modeling property as well [7, Corollary 5.6].

Definition 2.13. Suppose $\alpha $ is an ordinal.

1. (1) (Restriction) If $v \subseteq \alpha $ , the restriction of $\mathcal {T}_{\alpha }$ to the set of levels v is the $L_{s,\alpha }$ -substructure of $\mathcal {T}_{\alpha }$ with the following underlying set:

   $$ \begin{align*} \mathcal{T}_{\alpha} \upharpoonright v = \{\eta \in \mathcal{T}_{\alpha} : \min (\text{dom}(\eta)) \in v \text{ and }\beta \in \text{dom}(\eta) \setminus v \implies \eta(\beta) = 0\}. \end{align*} $$

2. (2) (Concatenation) If $\eta \in \mathcal {T}_{\alpha }$ , $\text {dom}(\eta ) = [\beta +1,\alpha )$ for $\beta $ non-limit, and $i < \omega $ , let $\eta \frown \langle i \rangle $ denote the function $\eta \cup \{(\beta ,i)\}$ . We define $\langle i \rangle \frown \eta \in \mathcal {T}_{\alpha +1}$ to be $\eta \cup \{(\alpha ,i)\}$ . We write $\langle i \rangle $ for $\emptyset \frown \langle i \rangle $ .

3. (3) (Canonical inclusions) If $\alpha < \beta $ , we define the map $\iota _{\alpha \beta } : \mathcal {T}_{\alpha } \to \mathcal {T}_{\beta }$ by $\iota _{\alpha \beta }(f) := f \cup \{(\gamma , 0) : \gamma \in \beta \setminus \alpha \}$ .

4. (4) (The all $0$ ’s path) If $\beta < \alpha $ , then $\zeta _{\beta }$ denotes the function with $\text {dom}(\zeta _{\beta }) = [\beta , \alpha )$ and $\zeta _{\beta }(\gamma ) = 0$ for all $\gamma \in [\beta ,\alpha )$ . This defines an element of $\mathcal {T}_{\alpha }$ if and only if $\beta \in \{\gamma \in \alpha \mid \gamma \mbox { is not limit}\}=:[\alpha ]$ .

5. (5) (Tuple notation) Given $\nu \in \mathcal {T}_{\alpha }$ , we write $a_{\unrhd \nu }$ for the tuple enumerating $\{a_{\xi } : \nu \unlhd \xi \in \mathcal {T}_{\alpha }\}$ .

In previous works on Kim-independence over arbitrary sets, there was a gap concerning the construction of Morley trees (and a parallel gap in the theory over models), first discovered by Jan Dobrowolski and Mark Kamsma. Namely, there is no reason a priori for an s-indiscernible tree locally based on a weakly spread out tree (see Definition 2.17) to be weakly spread out, which is needed to continue the induction. Over models this has a very easy fix: one can check that it is possible to choose a global M-invariant type $q \supseteq \text {tp}((a_{\eta })_{\eta \in \mathcal {T}_{\alpha }}/M)$ such that, if $(a^{\prime }_{\eta })_{\eta \in \mathcal {T}_{\alpha }} \models q$ then $(a^{\prime }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ is $\mathbb {M}$ -indiscernible. Morley sequences in such types allow the argument to work without change (the details for this case will appear elsewhere). But over sets, a lengthier argument is required to patch the proofs. The relevant notion for the modification is that of a mutually s-indiscernible sequence. We prove in Lemma 2.15 that, given an s-indiscernible tree, there is a Morley sequence starting with this tree which is mutually s-indiscernible, and then we show in Lemma 2.16 that this notion is preserved upon passage to an s-indiscernible tree.

Definition 2.14. We say a sequence $\langle (a_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }} : i < \kappa \rangle $ is mutually s-indiscernible over A if, for all $i < \kappa $ , $(a_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }}$ is s-indiscernible over $A\{a_{\eta ,j} : \eta \in \mathcal {T}_{\alpha }, j \neq i \}$ .

Lemma 2.15. Assume A is an extension base. Given a tree $(a_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ that is s-indiscernible over A, there is a sequence $I = \langle (a_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }} : i < \omega \rangle $ such that $(a_{\eta ,0})_{\eta \in \mathcal {T}_{\alpha }} = (a_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ , I is a Morley sequence over A, and I is mutually s-indiscernible over A.

Proof Let $\kappa $ be sufficiently large with respect to $|A|$ . By induction on $\gamma < \kappa $ , we will choose $(a_{\eta ,\gamma })_{\eta \in \mathcal {T}_{\alpha }}$ such that, taking $I_{\gamma }$ to be the sequence $\langle (a_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }} : i < \gamma \rangle $ , we have that $I_{\gamma }$ starts with $(a_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ , is mutually s-indiscernible over A, and satisfies

for all $i < \gamma $ . The sequence $I_{1}$ is already specified and trivially satisfies the requirements.

Assume we are given $(a_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }}$ for all $i < \gamma $ and set $I_{\gamma } = \langle (a_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }} : i < \gamma \rangle $ . Apply extension to get some $(b_{\eta })_{\eta \in \mathcal {T}_{\alpha }} \equiv _{A} (a_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ such that

By the modeling property, we can take $(b^{\prime }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ to be locally based on $(b_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ and s-indiscernible over $AI_{\gamma }$ , then we we still have $(b^{\prime }_{\eta })_{\eta \in \mathcal {T}_{\alpha }} \equiv _{A} (a_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ , as $(a_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ was assumed to be s-indiscernible over A, and local basedness and strong finite character of non-forking imply

Now by induction on $i < \gamma $ , we will choose $(a^{\prime }_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }}$ satisfying the following conditions:

1. (1) $(a^{\prime }_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }}$ is s-indiscernible over

   $$ \begin{align*}A \cup \{a^{\prime}_{\eta,j} : \eta \in \mathcal{T}_{\alpha}, j < i\} \cup \{a_{\eta,k} : \eta \in \mathcal{T}_{\alpha}, k> i\} \cup \{b^{\prime}_{\eta} : \eta \in \mathcal{T}_{\alpha}\}. \end{align*} $$

2. (2) $(b^{\prime }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ is s-indiscernible over

   $$ \begin{align*}A \cup \{a^{\prime}_{\eta,j} : \eta \in \mathcal{T}_{\alpha}, j \leq i\} \cup \{a_{\eta,k} : \eta \in \mathcal{T}_{\alpha}, k> i\}. \end{align*} $$

3. (3) $(a^{\prime }_{\eta ,j})_{\eta \in \mathcal {T}_{\alpha }, j \leq i} (a_{\eta ,k})_{\eta \in \mathcal {T}_{\alpha }, k> i} \equiv _{A} (a_{\eta ,j})_{\eta \in \mathcal {T}_{\alpha }, j \leq i} (a_{\eta ,k})_{\eta \in \mathcal {T}_{\alpha }, k > i}$ .

4. (4) The following independence holds:

   

Fix $i < \gamma $ and suppose we have chosen $(a^{\prime }_{\eta ,j})_{\eta \in \mathcal {T}_{\alpha }}$ for all $j < i$ . Pick $(a^{\prime }_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }}$ s-indiscernible over $A \cup \{a^{\prime }_{\eta ,j} : \eta \in \mathcal {T}_{\alpha }, j < i\} \cup \{a_{\eta ,k} : \eta \in \mathcal {T}_{\alpha }, k> i\} \cup \{b^{\prime }_{\eta } : \eta \in \mathcal {T}_{\alpha }\}$ and locally based on $(a_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }}$ . Then (1) is satisfied and (2) is easy to check using local basedness and the inductive assumption. We assumed $I_{\gamma }$ was mutually s-indiscernible over A and hence by (3) of the inductive hypothesis, we know that $(a_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }}$ is s-indiscernible over

$$ \begin{align*}A \cup \{a^{\prime}_{\eta,j} : \eta \in \mathcal{T}_{\alpha}, j < i\} \cup \{a_{\eta,k} : \eta \in \mathcal{T}_{\alpha}, k> i\}, \end{align*} $$

and therefore $(a^{\prime }_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }}$ has the same type over this set, which establishes (3). Finally, (4) follows by local basedness, (3), and the invariance of non-forking independence. More explicitly, suppose there is a finite tuple b from $(b^{\prime }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ , a finite tuple a from $\{a^{\prime }_{\eta ,j} : j < i\} \cup \{a_{\eta ,k} : k> i\}$ , and a finite tuple $\overline {\eta }$ from $\mathcal {T}_{\alpha }$ such that

$$ \begin{align*}\models \varphi(b;a^{\prime}_{\overline{\eta},i},a), \end{align*} $$

where $\varphi (x;y,z) \in L(A)$ is a formula such that $\varphi (x;a^{\prime }_{\overline {\eta },i},a)$ forks over A. Local basedness entails that there is $\overline {\nu }$ with $\mathrm {qftp}_{L_{s,\alpha }}(\overline {\nu }) = \mathrm {qftp}_{L_{s,\alpha }}(\overline {\eta })$ such that

$$ \begin{align*}\models \varphi(b;a_{\overline{\nu},i},a). \end{align*} $$

But by mutual s-indiscernibility, $a_{\overline {\nu },i} \equiv _{Aa} a_{\overline {\eta },i}$ and, by (3), $a_{\overline {\eta },i} \equiv _{Aa} a^{\prime }_{\overline {\eta },i}$ and hence $\varphi (x;a_{\overline {\nu },i},a)$ forks over A as well. This contradicts the inductive hypothesis that

This shows that our choice of $(a^{\prime }_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }}$ satisfies the requirements.

Having constructed our sequence $I^{\prime }_{\gamma } = \langle (a^{\prime }_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }} : i < \gamma \rangle $ , we have $I^{\prime }_{\gamma } \equiv _{A} I_{\gamma }$ by (3) and $(b^{\prime }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ is s-indiscernible over $I^{\prime }_{\gamma }$ by (2). Moreover, each $(a_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }}$ is indiscernible over $A(b^{\prime }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}(a_{\eta ,j})_{\eta \in \mathcal {T}_{\alpha },j \neq i}$ by (1). Finally, by (4), we have . Choosing $(a_{\eta ,\gamma })$ such that

$$ \begin{align*} I_{\gamma} (a_{\eta,\gamma})_{\eta \in \mathcal{T}_{\alpha}} \equiv_{A} I^{\prime}_{\gamma} (b^{\prime}_{\eta})_{\eta \in \mathcal{T}_{\alpha}} \end{align*} $$

we arrive at $I_{\gamma +1}$ . There is nothing to do at limits, so we have succeeded in constructing our sequence $I_{\kappa }$ . Applying Erdős–Rado to $I_{\kappa }$ , then, we obtain the desired sequence I.

Lemma 2.16. Suppose $(a_{\eta })_{\eta \in \mathcal {T}_{\alpha +1}}$ is a tree of tuples such that $I = \langle a_{\unrhd \langle i \rangle } : i < \omega \rangle $ is mutually s-indiscernible and Morley over A. Then if $(a^{\prime }_{\eta })_{\eta \in \mathcal {T}_{\alpha +1}}$ is s-indiscernible and locally based on $(a_{\eta })_{\eta \in \mathcal {T}_{\alpha +1}}$ over A and $I' = \langle a^{\prime }_{\unrhd \langle i \rangle }: i < \omega \rangle $ , then $I' \equiv _{A} I$ and thus $I'$ is also mutually s-indiscernible and Morley over A.

Proof Suppose $\overline {\eta }$ and $\overline {\nu }$ are tuples from $\mathcal {T}_{\alpha +1} \setminus \{\emptyset \}$ with $\mathrm {qftp}_{L_{s,\alpha +1}}(\overline {\eta }) = \mathrm {qftp}_{L_{s,\alpha +1}}(\overline {\nu })$ . After possibly reordering the tuples, there are $i_{0} < \cdots < i_{k-1}$ and $j_{0} < \cdots < j_{k-1}$ such that $\overline {\eta } = (\overline {\eta }_{0}, \ldots , \overline {\eta }_{k-1})$ and $\overline {\nu } = (\overline {\nu }_{0}, \ldots , \overline {\nu }_{k-1})$ where each $\overline {\eta }_{l}$ comes from the tree $\unrhd \langle i_{l} \rangle $ and $\overline {\nu }_{l}$ comes from the tree $\unrhd \langle j_{l} \rangle $ for $l < k$ . Then, in particular, $\mathrm {qftp}_{L_{s,\alpha +1}}(\overline {\eta }_{l}) = \mathrm {qftp}_{L_{s,\alpha +1}}(\overline {\nu }_{l})$ for all $l < k$ . Additionally, for all $l < k$ , let $\overline {\eta }^{\prime }_{l}$ be the element of the tree $\unrhd \langle j_{l} \rangle $ corresponding to $\overline {\eta }_{l}$ (i.e., replace each node $\langle i_{l}\rangle ^{\frown } \xi $ enumerated in $\overline {\eta }_{l}$ with $\langle j_{l} \rangle ^{\frown } \xi $ ). Because I is an A-indiscernible sequence, we have

$$ \begin{align*} (a_{\overline{\eta}_{0}}, \ldots, a_{\overline{\eta}_{k-1}}) \equiv_{A} (a_{\overline{\eta}^{\prime}_{0}}, \ldots, a_{\overline{\eta}_{k-1}'}). \end{align*} $$

Additionally, in the tree $\unrhd \langle j_{l} \rangle $ (naturally viewed as an $L_{s,\alpha }$ -structure), we have $\mathrm {qftp}_{L_{s,\alpha }}(\overline {\eta }_{l}') = \mathrm {qftp}_{L_{s,\alpha }}(\overline {\eta }_{l})$ for all $l < k$ . Thus, mutual s-indiscernibility entails

$$ \begin{align*} (a_{\overline{\eta}^{\prime}_{0}}, \ldots, a_{\overline{\eta}_{k-1}'}) \equiv_{A} (a_{\overline{\nu}_{0}}, \ldots, a_{\overline{\nu}_{k-1}}). \end{align*} $$

Thus we have shown that $a_{\overline {\eta }} \equiv _{A} a_{\overline {\nu }}$ . Therefore, it follows, by local basedness, that $I \equiv _{A} I'$ and the result follows.

Definition 2.17. Suppose $(a_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ is a tree of tuples in $\mathbb {M}$ , and A is a set of parameters.

1. (1) We say $(a_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ is weakly spread out over A if for all $\eta \in \mathcal {T}_{\alpha }$ with $\text {dom}(\eta ) =[\beta +1,\alpha )$ for some $\beta \in [\alpha ]$ , the sequence of cones $(a_{\unrhd \eta \frown \langle i \rangle })_{i < \omega }$ is a Morley sequence in $\mathrm {tp}(a_{\unrhd \eta \frown \langle 0 \rangle }/A)$ .

2. (2) Suppose $(a_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ is a tree which is weakly spread out and s-indiscernible over A and for all pairs of finite subsets $w,v$ of $\alpha $ with $|w| = |v|$ ,

   $$ \begin{align*}(a_{\eta})_{\eta \in \mathcal{T}_{\alpha} \upharpoonright w} \equiv_{A} (a_{\eta})_{\eta \in \mathcal{T}_{\alpha} \upharpoonright v} \end{align*} $$
   then we say $(a_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ is a weakly Morley tree over A.

3. (3) A weak tree Morley sequence over A is a A-indiscernible sequence of the form $(a_{\zeta _\beta })_{\beta \in [\alpha ]}$ for some weakly Morley tree $(a_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ over A. More generally, we will say an A-indiscernible sequence I is a weak tree Morley sequence over A if it is EM-equivalent to a sequence of this form.

Remark 2.18. If $I = \langle b_{i} : i < \omega \rangle $ is an A-indiscernible sequence and $I \equiv _{A} J$ for some weak tree Morley sequence J over A, then I is a weak tree Morley sequence over A. In particular, if I is a subsequence of J, by the A-indiscernibility of J, the sequence I is also weak tree Morley over A.

Fact 2.19. Suppose T is NSOP $_{1}$ with existence and A is a set of parameters.

1. (1) If , there is an $Ab$ -indiscernible sequence $I = \langle a_{i} : i < \omega \rangle $ over A with $a_{0} = a$ such that I is weak tree Morley over A [5, Lemma 4.7].

2. (2) Kim’s lemma for weak tree Morley sequences: the formula $\varphi (x;a_{0})$ Kim-divides over A if and only if $\{\varphi (x;a_{i}) : i < \omega \}$ is inconsistent for some weak tree Morley sequence $\langle a_{i} : i < \omega \rangle $ over A if and only if $\{\varphi (x;a_{i}) : i < \omega \}$ is inconsistent for all weak tree Morley sequences $\langle a_{i} : i < \omega \rangle $ over A [5, Corollary 4.8].

3. (3) If $a \equiv ^{L}_{A} b$ and , there is an -Morley sequence over A starting with $(a,b)$ as its first two elements (follows from Fact 2.7 as in [7, Corollary 6.6]).

2.2 Further properties of Kim-independence

Fact 2.20 [5, Lemma 5.7].

Suppose T is NSOP $_{1}$ with existence. If A is a set of parameters, c is an arbitrary tuple, and , then there is $a' \equiv ^{L}_{Ab} a$ such that .

The following lemma is easy and well-known, but, in the absence of a clear reference, we provide a proof:

Lemma 2.21. Suppose T is NSOP $_{1}$ with existence, A is a set of parameters, and $p(x) \in S(A)$ .

1. (1) Given any tuple of variables y, there is a partial type $\Gamma (x,y)$ over A such that $(a,b) \models \Gamma (x,y)$ if and only if $a \models p$ and .

2. (2) There is a partial type $\Delta (x_{i} : i < \omega )$ over A such that $I = \langle a_{i} : i < \omega \rangle \models \Delta $ if and only if I is an -Morley sequence over A in p.

Proof (1) By compactness, we may assume y is finite. Fix $c \models p$ and define $\Gamma (x,y)$ by

$$ \begin{align*} \Gamma(x,y) = p(x) \cup \{\neg \varphi(y;x) : \varphi(y;c) \text{ Kim-divides over } A\}. \end{align*} $$

By symmetry, invariance, and Kim-forking = Kim-dividing, this partial type is as desired.

(2) One can take $\Delta $ to be the partial type that asserts $\langle x_{i} : i < \omega \rangle $ is A-indiscernible, every $x_{i} \models p$ , and (which is type-definable over A by (1)).

The following lemma is the analogue of the ‘strong independence theorem’ of [16, Theorem 2.3] for Lascar strong types.

Lemma 2.22. Suppose T is NSOP $_{1}$ with existence. If A is a set of parameters, , , , and $a_{0} \equiv ^{L}_{A} a_{1}$ , then there is a such that $a \equiv ^{L}_{Ab} a_{0}$ , $a \equiv ^{L}_{Ac} a_{1}$ and, additionally, we have , , and .

Proof By Fact 2.20, there is $c' \equiv ^{L}_{Ab} c$ such that . Let $\sigma \in \mathrm {Autf}(\mathbb {M}/Ab)$ be an automorphism such that $\sigma (c') = c$ and let $c_{0} = \sigma (c)$ . Then we have and $c_{0} \equiv _{Ab}^{L} c$ and hence, in particular, $c_{0}b \equiv _{A}^{L} cb$ . By symmetry and a second application of Fact 2.20 once again, we find $b"c" \equiv ^{L}_{Ac} bc_{0}$ with . Let $\tau \in \mathrm {Autf}(\mathbb {M}/Ac)$ be a strong automorphism with $\tau (b"c") = bc_{0}$ and define $b_{1} = \tau (b)$ . Then by construction, we have $b"c" \equiv _{A} bc_{0}$ and $bc_{0} \equiv ^{L}_{A} bc$ , it follows that $b"c" \equiv ^{L}_{A} bc$ , and hence $\tau (b"c") \equiv ^{L}_{A} \tau (bc)$ , which, after unraveling definitions, gives $bc_{0} \equiv ^{L}_{A} b_{1}c$ . Moreover, since , we obtain by invariance. Let $b_{0} = b$ and $c_{1} = c$ . By Fact 2.19(3), we can extend the sequence $\langle (b_{i},c_{i}) : i < 2 \rangle $ to a weak tree Morley sequence $I = \langle (b_{i},c_{i}) : i \in \mathbb {Z} \rangle $ over A.

Choose $a'$ such that $a_{1}c_{1} \equiv ^{L}_{A} a'c_{0}$ . Then we have $a_{0} \equiv ^{L}_{A} a'$ , as well as , by our assumptions. Additionally, since , $b_{0} = b$ and $c \equiv _{Ab} c_{0}$ , we have . Therefore, by Fact 2.7(6), there is $a_{*}$ with $a_{*} \equiv ^{L}_{Ab_{0}} a_{0}$ , $a_{*} \equiv ^{L}_{Ac_{0}} a'$ , with .

Because I is a weak tree Morley sequence and , by Kim’s lemma, compactness, and an automorphism, there is such that $a_{**}b_{0}c_{0} \equiv ^{L}_{A} a_{*}b_{0}c_{0}$ and such that I is $Aa_{**}$ -indiscernible. Note that, by construction, $a_{**} \equiv ^{L}_{Ab} a_{0}$ , $a_{**} \equiv ^{L}_{Ac} a_{1}$ , and .

Additionally, the sequence $\langle b_{i} : i \in \mathbb {Z}^{\leq 0} \rangle $ is a weak tree Morley sequence over A which is $Aa_{**}c$ -indiscernible and containing $b_{0} = b$ , hence , by Kim’s lemma for weak tree Morley sequences. Similarly, the sequence $\langle c_{i} : i \in \mathbb {Z}^{\geq 1} \rangle $ is a weak tree Morley sequence over A containing $c = c_{1}$ which is $Aa_{**}b$ -indiscernible, yielding . By symmetry, we conclude.

3 Transitivity and witnessing

3.1 Preliminary lemmas

We begin by establishing some lemmas, allowing us to construct sequences that are -Morley over more than one base simultaneously. The broad structure of the argument will follow that of [8], which established transitivity over models for Kim-independence in NSOP $_{1}$ theories, however, all uses of coheirs and heirs will need to be replaced.

In particular, the following lemma does not follow the corresponding [8, Lemma 3.1], instead producing the desired sequence by a tree-induction.

Lemma 3.1. Suppose T is NSOP $_{1}$ and satisfies the existence axiom. If $A \subseteq B$ and , then there is a weak tree Morley sequence $\langle a_{i} : i < \omega \rangle $ over B with $a_{0} = a$ such that for all $i < \omega $ .

Proof By induction on $\alpha $ , we will construct trees $(a^{\alpha }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ so that:

1. (1) $(a^{\alpha }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ is s-indiscernible and weakly spread out over B.

2. (2) $a^{\alpha }_{\eta } \models \text {tp}(a/B)$ for all $\eta \in \mathcal {T}_{\alpha }$ .

3. (3) If $\alpha $ is a successor, .

4. (4) If $\alpha < \beta $ , then $a^{\beta }_{\iota _{\alpha \beta }(\eta )} = a^{\alpha }_{\eta }$ for all $\eta \in \mathcal {T}_{\alpha }$ .

For $\alpha = 0$ , we put $a^{0}_{\emptyset } = a$ , and for $\delta $ limit, we will define $(a^{\delta }_{\eta })_{\eta \in \mathcal {T}_{\delta }}$ by setting $a^{\delta }_{\iota _{\alpha \delta }(\eta )} = a^{\alpha }_{\eta }$ for all $\alpha < \delta $ and $\eta \in \mathcal {T}_{\alpha }$ which, by (4) and induction, is well-defined and satisfies the requirements.

Now suppose we are given $(a^{\beta }_{\eta })_{\eta \in \mathcal {T}_{\beta }}$ satisfying the requirements for all $\beta \leq \alpha $ . Let $\langle (a^{\alpha }_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }} : i < \omega \rangle $ be a mutually s-indiscernible Morley sequence over B with $a^{\alpha }_{\eta ,0} = a^{\alpha }_{\eta }$ for all $\eta \in \mathcal {T}_{\alpha }$ , which exists by Lemma 2.15. Apply extension to find $a_{*} \equiv _{B} a$ so that . Define a tree $(b_{\eta })_{\eta \in \mathcal {T}_{\alpha +1}}$ by setting $b_{\emptyset }= a_{*}$ and $b_{\langle i \rangle \frown \eta } = a^{\alpha }_{\eta ,i}$ for all $i < \omega $ and $\eta \in \mathcal {T}_{\alpha }$ . We may define $(a^{\alpha +1}_{\eta })_{\eta \in \mathcal {T}_{\alpha +1}}$ to be a tree which is s-indiscernible over B and locally based on $(b_{\eta })_{\eta \in \mathcal {T}_{\alpha +1}}$ over B. By an automorphism, we may assume $a^{\alpha +1}_{\iota _{\alpha \alpha +1}(\eta )} = a^{\alpha }_{\eta }$ for all $\eta \in \mathcal {T}_{\alpha }$ , hence conditions (2), and (4) are clearly satisfied. Moreover, by Lemma 2.16, we have $\langle (a_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }} : i < \omega \rangle \equiv _{B} \langle a^{\alpha +1}_{\unrhd \langle i \rangle } : i < \omega \rangle $ so $\langle a^{\alpha +1}_{\unrhd \langle i \rangle } : i < \omega \rangle $ is a Morley sequence over B. Then by (4) and induction, it follows that $(a^{\alpha +1}_{\eta })_{\eta \in \mathcal {T}_{\alpha +1}}$ is s-indiscernible and spread out over B, which shows (1).

For (3), we just note that, by symmetry, if , there is some formula $\varphi (x;a_{\emptyset }^{\alpha +1}) \in \text {tp}(Ba^{\alpha +1}_{\vartriangleright \emptyset }/Aa^{\alpha +1}_{\emptyset })$ that Kim-divides over A. As the tree $(a^{\alpha +1}_{\eta })_{\eta \in \mathcal {T}_{\alpha +1}}$ is locally based on $(b_{\eta })_{\eta \in \mathcal {T}_{\alpha +1}}$ , it follows that some tuple from $Bb_{\vartriangleright \emptyset }$ also realizes $\varphi (x;a_{*})$ and $a_{*} \equiv _{B} a^{\alpha +1}_{\emptyset }$ , so $\varphi (x;a_{*})$ Kim-divides over A as well, contradicting the choice of $a_{*}$ . This contradiction establishes (3), completing the induction.

By considering $(a^{\kappa }_{\eta })_{\eta \in \mathcal {T}_{\kappa }}$ for $\kappa $ sufficiently large, we may apply Erdős–Rado, as in [7, Lemma 5.10], to find the desired sequence.

The proof of the next lemma follows [8, Lemma 3.2].

Lemma 3.2. Suppose T is an NSOP $_{1}$ theory satisfying the existence axiom. If and , then there is $c'$ so that $c' \equiv _{Ab} c$ , , and .

Proof Define a partial type $\Gamma (x;b,a)$ over $Aab$ as follows:

$$ \begin{align*} \Gamma(x;b,a) = \text{tp}(c/Ab) \cup \{\neg \varphi(x,a;b) : \varphi(x,y;b) \in L(Ab) \text{ Kim-divides over }A\}. \end{align*} $$

Claim 1. If $\langle a_{i} : i < \omega \rangle $ is an $Ab$ -indiscernible sequence satisfying $a_{0} = a$ and for all $i < \omega $ , then $\bigcup _{i < \omega } \Gamma (x;b,a_{i})$ is consistent.

Proof of claim

By induction on $n < \omega $ , we will find $c_{n} \equiv ^{L}_{A} c$ such that and $c_{n} \models \bigcup _{i < n} \Gamma (x;b,a_{i})$ . For $n = 0$ , we can put $c_{0} = c$ , since by assumption. Assume we have found $c_{n}$ , and, by Fact 2.20, choose $c'$ such that $c' \equiv ^{L}_{A} c$ and . Then $c' \equiv ^{L}_{A} c \equiv ^{L}_{A} c_{n}$ and, since , we may apply Lemma 2.22 to find $c_{n+1} \equiv ^{L}_{A} c$ such that $c_{n+1} \models \text {tp}(c_{n}/Aba_{<n}) \cup \text {tp}(c'/Aa_{n})$ and such that and , hence, in particular, $c_{n+1} \models \bigcup _{i < n+1} \Gamma (x;b,a_{i})$ . The claim follows by compactness.

Next we define a partial type $\Delta (x;b,a)$ as follows:

$$ \begin{align*} \Delta(x;b,a) = \Gamma(x;b,a) \cup \{\neg\psi(x;b,a) : \psi(x;b,a) \in L(Aab) \text{ Kim-divides over }Ab\}. \end{align*} $$

Claim 2. The set of formulas $\Delta (x;b,a)$ is consistent.

Proof of claim

Suppose not. Then because Kim-forking and Kim-dividing are the same in NSOP $_{1}$ with existence, there is some formula $\psi (x;b,a) \in L(Aab)$ such that

$$ \begin{align*} \Gamma(x;b,a) \vdash \psi(x;b,a) \end{align*} $$

and $\psi (x;b,a)$ Kim-divides over $Ab$ . As , we know by Lemma 3.1 that there is a sequence $\langle a_{i} : i < \omega \rangle $ with $a_{0} = a$ which is a weak tree Morley sequence over $Ab$ and satisfies for all $i < \omega $ . Then by Claim 1, $\bigcup _{i < \omega } \Gamma (x;b,a_{i})$ is consistent. However, we have

$$ \begin{align*} \bigcup_{i < \omega} \Gamma(x;b,a_{i}) \vdash \{\psi(x;b,a_{i}) : i < \omega\} \end{align*} $$

and $\{\psi (x;b,a_{i}) : i < \omega \}$ is inconsistent, because weak tree Morley sequences witness Kim-dividing. This contradiction proves the claim.

To conclude, we may take $c'$ to be any realization of $\Delta (x;b,a)$ .

The next proposition is a strengthening of Fact 2.19(1).

Proposition 3.3. Suppose T is an NSOP $_{1}$ theory satisfying the existence axiom. If , then there is a sequence $I = \langle a_{i} : i < \omega \rangle $ with $a_{0} = a$ such that I is a weak tree Morley sequence over A and an -Morley sequence over $Ab$ .

Proof By induction on $\alpha $ , we will construct trees $(a^{\alpha }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ satisfying the following:

1. (1) For all $\eta \in \mathcal {T}_{\alpha }$ , $a^{\alpha }_{\eta } \models \text {tp}(a/Ab)$ .

2. (2) The tree $(a^{\alpha }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ is s-indiscernible over $Ab$ and weakly spread out over A.

3. (3) If $\alpha $ is a successor, then .

4. (4) .

5. (5) If $\alpha < \beta $ , then $a^{\beta }_{\iota _{\alpha \beta }(\eta )} = a^{\alpha }_{\eta }$ for all $\eta \in \mathcal {T}_{\alpha }$ .

Put $a^{0}_{\emptyset } = a$ and for $\delta $ limit, if we are given $(a^{\alpha }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ for every $\alpha < \delta $ , we can define $(a^{\delta }_{\eta })_{\eta \in \mathcal {T}_{\delta }}$ by setting $a^{\delta }_{\iota _{\alpha \delta }(\eta )} = a^{\alpha }_{\eta }$ for all $\alpha < \delta $ and $\eta \in \mathcal {T}_{\alpha }$ , which is well-defined by (5) and is easily seen to satisfy the requirements.

Suppose now we are given $(a^{\alpha }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ . Let $J = \langle (a^{\alpha }_{\eta ,i})_{\eta \in \mathcal {T}_{\alpha }} : i < \omega \rangle $ be a mutually s-indiscernible Morley sequence over A with $(a^{\alpha }_{\eta ,0})_{\eta \in \mathcal {T}_{\alpha }} = (a^{\alpha }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ , which exists by Lemma 2.15. By (4), symmetry, and the chain condition, Fact 2.7(5) we may assume J is $Ab$ -indiscernible and . By Lemma 3.2, there is $a_{*} \equiv _{Ab} a$ such that and . After defining a tree $(c_{\eta })_{\eta \in \mathcal {T}_{\alpha +1}}$ by $c_{\emptyset } = a_{*}$ and $c_{\langle i \rangle \frown \eta } = a^{\alpha }_{\eta ,i}$ for all $\eta \in \mathcal {T}_{\alpha }$ , these conditions on $a_{*}$ imply that $(c_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ satisfy (3) and (4), respectively. Let $(a^{\alpha +1}_{\eta })_{\eta \in \mathcal {T}_{\alpha +1}}$ be any tree s-indiscernible over $Ab$ locally based on $(c_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ over $Ab$ . This still satisfies (2) by Lemma 2.16. Moreover, as $c_{\unrhd \langle i \rangle } \models \mathrm {tp}((a^{\alpha }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}/Ab)$ for all $i < \omega $ , it follows from local basedness that $a^{\alpha +1}_{\unrhd \langle i \rangle } \models \mathrm {tp}((a^{\alpha }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}/Ab)$ for all $i < \omega $ as well. Hence, by an automorphism over $Ab$ , we may assume $a^{\alpha +1}_{0 \frown \eta } = a^{\alpha }_{\eta }$ for all $\eta \in \mathcal {T}_{\alpha }$ , which ensures the constructed tree satisfies (5), and (1)–(4) are easy to verify.

Given $(a^{\kappa }_{\eta })_{\eta \in \mathcal {T}_{\kappa }}$ for $\kappa $ sufficiently large, we may, by Erdős–Rado (see, e.g., [7, Lemma 5.10]), obtain a weak Morley tree $(b_{\eta })_{\eta \in \mathcal {T}_{\omega }}$ over A satisfying (1)–(4). Then the sequence $I = \langle a_{i} : i < \omega \rangle $ defined by $a_{i} = b_{\zeta _{i}}$ for all $i < \omega $ is a weak tree Morley sequence over A, as it is a path in a weak Morley tree over A, but by (3), we have for all i, so I is -Morley over $Ab$ as well.

3.2 Transitivity and witnessing

The following theorem establishes the transitivity of Kim-independence in NSOP $_{1}$ theories with existence.

Theorem 3.4. Suppose T is NSOP $_{1}$ with existence. Then if $A \subseteq B$ , and , then .

Proof By Proposition 3.3 and the assumption that , there is a sequence $I = \langle a_{i} : i < \omega \rangle $ with $a_{0} = a$ such that I is an -Morley sequence over B and a weak tree Morley sequence over A. As , by symmetry, and I is -Morley over B, there is $I' \equiv _{Ba}I$ such that $I'$ is $Bc$ -indiscernible. Because $I'$ is also a weak tree Morley sequence over A, it follows by Kim’s lemma that . By symmetry, we conclude.

Proposition 3.5. Assume T is NSOP $_1$ with existence. The following are equivalent.

1. (1) .

2. (2) There is a model $M\supseteq A$ such that (or ) and .

3. (3) There is a model $M\supseteq A$ such that (or ) and .

Proof (1) $\Rightarrow $ (2) Since , there is a Morley sequence $I=\langle a_i : i<\omega \rangle $ over A with $a_0=a$ such that I is $Ab$ -indiscernible. By [5, Lemma 2.17], there is a model N containing A such that and I is a coheir sequence over N. By compactness and extension we can clearly assume the length of I is arbitrarily large, and . Hence by the pigeonhole principle, there is an infinite subsequence J of I such that all the tuples in J have the same type over $Nb$ . Thus, for $a'\in J$ , we have and . Hence $M=f(N)$ is a desired model, where f is an $Ab$ -automorphism sending $a'$ to a.

(2) $\Rightarrow $ (3) Clear.

(3) $\Rightarrow $ (1) follows from transitivity and symmetry of .

Proposition 3.6. Suppose T satisfies the existence axiom. The following are equivalent for a cardinal $\kappa \geq |T|$ :

1. (1) T is NSOP $_{1}$ .

2. (2) There is no increasing continuous sequence $\langle A_{i} : i < \kappa ^{+} \rangle $ of parameter sets and finite tuple d such that $|A_{i}| \leq \kappa $ and for all $i < \kappa ^{+}$ .

3. (3) There is no set A of parameters of size $\kappa ^{+}$ and $p(x) \in S(A)$ with x a finite tuple of variables such that for some increasing and continuous sequence of sets $\langle A_{i} : i < \kappa ^{+} \rangle $ with union A, we have $|A_{i}| \leq \kappa $ and p Kim-divides over $A_{i}$ for all $i < \kappa ^{+}$ .

Proof (1) $\implies $ (2) It suffices to show that, given any increasing continuous sequence $\langle A_{i} : i < \kappa ^{+} \rangle $ of parameter sets and tuple d such that $|A_{i}| \leq \kappa $ and for all $i < \kappa ^{+}$ , there is a continuous increasing sequence of models $\langle M_{i} : i < \kappa ^{+} \rangle $ and a finite tuple $d'$ such that $|M_{i}| \leq \kappa $ and for all $i < \kappa ^{+}$ . This follows from Fact 2.8, since the existence of such a sequence of models implies T has SOP $_{1}$ . Moreover, after naming constants, we may assume $\kappa = |T|$ .

So suppose we are given $\langle A_{i} : i < |T|^{+} \rangle $ , an increasing continuous sequence of sets of parameters with $|A_{i}| \leq |T|$ for all $i < |T|^{+}$ . Let $A = \bigcup _{i < |T|^{+}} A_{i}$ , and suppose further that we are given some tuple d such that for all $i < |T|^{+}$ . By induction on $i < |T|^{+}$ we will build increasing and continuous sequences $\langle A^{\prime }_{i} : i < |T|^{+} \rangle $ and $\langle M_{i} : i < |T|^{+} \rangle $ satisfying the following for all $i < |T|^{+}$ :

1. (1) $A^{\prime }_{0} = A_{0}$ and $A^{\prime }_{\leq i} \equiv A_{\leq i}$ .

2. (2) $M_{i}\models T$ with $|M_{i}| = |T|$ and $A^{\prime }_{i} \subseteq M_{i}$ .

3. (3) .

To begin, we define $A^{\prime }_{0} = A_{0}$ and take $M_{0}$ be any model containing $A^{\prime }_{0}$ of size $|T|$ . Given $A^{\prime }_{\leq i}$ and $M_{\leq i}$ satisfying the requirements, we pick $A^{\prime \prime }_{i+1}$ such that $A^{\prime }_{\leq i} A^{\prime \prime }_{i+1} \equiv A_{\leq i+1}$ . Then we apply extension, to obtain $A^{\prime }_{i+1} \equiv _{A^{\prime }_{\leq i}} A^{\prime \prime }_{i+1}$ such that . Note that $A^{\prime }_{\leq i+1} \equiv A_{\leq i+1}$ . We define $M_{i+1}$ to be any model containing $A^{\prime }_{i+1}M_{i}$ of size $|T|$ . This satisfies the requirements.

At limit $\delta $ , we define $A^{\prime }_{\delta } = \bigcup _{i < \delta } A^{\prime }_{i}$ and $M_{\delta } = \bigcup _{i < \delta } M_{i}$ . This clearly satisfies (1) and (2) and (3) is trivial. Therefore this completes the construction.

Let $M = \bigcup _{i < |T|^{+}} M_{i}$ . Choose $d'$ such that $d\langle A_{i} : i < |T|^{+} \rangle \equiv d' \langle A^{\prime }_{i} : i < |T|^{+} \rangle $ , which is possible by (1). Then we have for all $i < |T|^{+}$ .

Towards contradiction, suppose that there is some $i < |T|^{+}$ with the property that . Then, in particular, we have . Additionally, because , we know, by symmetry and transitivity, that . By symmetry once more, we get , a contradiction. This shows that for all $i < |T|^{+}$ , completing the proof of this direction.

(2) $\implies $ (3) Suppose (3) fails, i.e., we are given A of size $\kappa ^{+}$ , $p \in S(A)$ , and an increasing continuous sequence of sets $\langle A_{i} : i < \omega \rangle $ such that $|A_{i}| \leq \kappa $ and p Kim-divides over $A_{i}$ for all $i < \kappa ^{+}$ . We will define an increasing continuous sequence of ordinals $\langle \alpha _{i} : i < \kappa ^{+} \rangle $ such that $\alpha _{i} \in \kappa ^{+}$ and $p \upharpoonright A_{\alpha _{i+1}}$ Kim-divides over $A_{\alpha _{i}}$ for all $i < \kappa ^{+}$ . We set $\alpha _{0} = 0$ and given $\langle \alpha _{j} : j \leq i \rangle $ , we know that there is some formula $\varphi (x;a_{i+1}) \in p$ that Kim-divides over $A_{\alpha _{i}}$ , by our assumption on p. Let $\alpha _{i+1}$ be the least ordinal $< \kappa ^{+}$ such that $a_{i+1}$ is contained in $A_{\alpha _{i+1}}$ . For limit i, if we are given $\langle \alpha _{j} : j < i \rangle $ , we put $\alpha _{i} = \sup _{j < i} \alpha _{j}$ . Then we define $\langle A_{i} : i < \kappa ^{+} \rangle $ by $A^{\prime }_{i} = A_{\alpha _{i}}$ for all $i < \kappa $ , and let $d \models p$ be any realization. By construction, we have for all $i < \kappa ^{+}$ , which witnesses the failure of (2).

(3) $\implies $ (1) This was established in [9, Theorem 3.9].

Remark 3.7. In [2, Proposition 4.6] it is shown that in every theory with TP $_{2}$ , there is an increasing chain of sets $\langle D_{i} : i < |T|^{+} \rangle $ and tuple d such that $|D_{i}| \leq |T|$ and for all $i < |T|^{+}$ . Hence, for non-simple NSOP $_{1}$ theories, the condition of continuity in the statement of Proposition 3.6 is essential.

The following theorem will be referred to as ‘witnessing.’ It shows that -Morley sequences are witnesses to Kim-dividing. Over models this was established in [8, Theorem 5.1], however for us it will be deduced as a corollary of Proposition 3.6.

Theorem 3.8. Suppose T is NSOP $_{1}$ with existence and $I = \langle a_{i} : i < \omega \rangle $ is an -Morley sequence over A. If $\varphi (x;a_{0})$ Kim-divides over A, then $\{\varphi (x;a_{i}) : i < \omega \}$ is inconsistent.

Proof Suppose towards contradiction that $\varphi (x;a_{0})$ Kim-divides over A and $I = \langle a_{i} : i < \omega \rangle $ is an -Morley sequence over A such that $\{\varphi (x;a_{i}) : i < \omega \}$ is consistent. By naming A as constants, we may assume $|A| \leq |T|$ . We may stretch I such that $I = \langle a_{i} : i < |T|^{+} \rangle $ . Define $A_{i} = Aa_{<i}$ . Then $\langle A_{i} : i < |T|^{+} \rangle $ is increasing and continuous and $|A_{i}| \leq |T|$ . Let $d \models \{\varphi (x;a_{i}) : i < |T|^{+} \}$ . We claim for all $i < |T|^{+}$ . If not, then for some $i < |T|^{+}$ , we have , or, in other words . Since I is an -Morley sequence, we also have , hence , by transitivity (Theorem 3.4). This entails, in particular, that , which is a contradiction, since $\varphi (x;a_{i})$ Kim-divides over A. This completes the proof.

4 Low NSOP $_{1}$ theories

This section is dedicated to proving that Lascar and Shelah strong types coincide in any low NSOP $_{1}$ theory with existence. This generalizes the corresponding result of Buechler for low simple theories [1] (also independently discovered by Shami [17]).

Definition 4.1. We say that the theory T is low if, for every formula $\varphi (x;y)$ , there is some $k < \omega $ , such that if $I = \langle a_{i} : i < \omega \rangle $ is an indiscernible sequence and $\{\varphi (x;a_{i}) : i < \omega \}$ is inconsistent, then it is k-inconsistent.

In [1], the definition of lowness is given in terms of the finiteness of certain $D(p,\varphi )$ ranks, which we will not need here. However, as observed in [1], the above definition coincides with this definition in the case that T is simple.

Lemma 4.2. Suppose T is NSOP $_{1}$ with existence. Assume we are given tuples $(a_{i})_{i \leq n}$ and $L(A)$ -formulas $(\varphi _{i}(x;y_{i}))_{i \leq n}$ such that for all $i \leq n$ . Then the following are equivalent:

1. (1) The formula $\bigwedge _{i \leq n} \varphi _{i}(x;a_{i})$ does not Kim-divide over A.

2. (2) For all A-indiscernible sequences $\langle \overline {a}_{j} : j < \omega \rangle = \langle (a_{j,0},\ldots , a_{j,n}) : j < \omega \rangle $ with $(a_{0,0},\ldots , a_{0,n}) = (a_{0},\ldots , a_{n})$ and for all $j < \omega $ and $i \leq n$ , the following set of formulas does not Kim-divide over A:

   $$ \begin{align*} \left\{ \bigwedge_{i \leq n} \varphi_{i}(x;a_{j,i}) : j < \omega \right\}. \end{align*} $$

3. (3) There is an A-indiscernible sequence $\langle \overline {a}_{j} : j < \omega \rangle = \langle (a_{j,0},\ldots , a_{j,n}) : j < \omega \rangle $ with $(a_{0,0},\ldots , a_{0,n}) = (a_{0},\ldots , a_{n})$ and for all $j < \omega $ , $i \leq n$ such that

   $$ \begin{align*} \left\{ \bigwedge_{i \leq n} \varphi_{i}(x;a_{j,i}) : j < \omega \right\} \end{align*} $$
   is consistent.

Proof (1) $\implies $ (2) Suppose we are given $\langle \overline {a}_{j} : j < \omega \rangle $ as in (2) and let $c \models \bigwedge _{i \leq n} \varphi _{i}(x;a_{i})$ with . As $\langle \overline {a}_{j} : j < \omega \rangle $ is A-indiscernible, for each $j> 0$ , there is some $\sigma _{j} \in \mathrm {Autf}(\mathbb {M}/A)$ with $\sigma _{j}(\overline {a}_{0}) = \overline {a}_{j}$ . Define $c_{0} = c$ and $c_{j} = \sigma _{j}(c)$ for all $j> 0$ . Then we have $c_{j} \equiv ^{L}_{A} c_{0}$ and $c_{j} \models \bigwedge _{i \leq n} \varphi _{i}(x;a_{j,i})$ for all $j < \omega $ . By inductively applying the independence theorem (with respect to the lexicographic order on $\omega \times n$ ), we obtain $c_{*} \models \{\varphi _{i}(x;a_{j,i}) : i \leq n, j < \omega \}$ with , which establishes (2).

(2) $\implies $ (3) It suffices to show that there is an A-indiscernible sequence $\langle \overline {a}_{j} : j < \omega \rangle = \langle (a_{j,0},\ldots , a_{j,n}) : j < \omega \rangle $ with $(a_{0,0},\ldots , a_{0,n}) = (a_{0},\ldots , a_{n})$ and such that for all $j < \omega $ , $i \leq n$ .

First, we construct by induction a sequence $\langle (a^{\prime }_{j,0},\ldots , a^{\prime }_{j,n} : j < \omega \rangle = \langle \overline {a}^{\prime }_{j} : j < \omega \rangle $ with $\overline {a}^{\prime }_{j} \equiv _{A} (a_{0},\ldots , a_{n})$ and for all $j < \omega $ , $i \leq n$ . Given $\overline {a}^{\prime }_{\leq k}$ , we apply extension to find $a^{\prime }_{k+1,0} \equiv _{A} a_{0}$ with . Given $\overline {a}^{\prime }_{k+1,\leq i}$ for $i < n$ , we find $b_{k+1,i+1}$ such that $a^{\prime }_{k+1,\leq i}b_{k+1,i+1} \equiv _{A} a_{\leq i}a_{i+1}$ . By invariance, this implies . Applying extension once more, we can find $a^{\prime }_{k+1,i+1} \equiv _{Aa^{\prime }_{k+1,\leq i}} b_{k+1,i+1}$ such that . This completes the construction of $\langle \overline {a}^{\prime }_{j} : j < \omega \rangle $ . By Ramsey, compactness, and an automorphism, we can extract an A-indiscernible sequence $\langle \overline {a}_{j} : j < \omega \rangle $ with $\overline {a}_{0} = (a_{0},\ldots , a_{n})$ as desired.

(3) $\implies $ (1) Let $c \models \left \{ \bigwedge _{i \leq n} \varphi _{i}(x;a_{j,i}) : j < \omega \right \}$ . Note that, for each $i \leq n$ , the sequence $\langle a_{j,i} : j < \omega \rangle $ is an -Morley sequence over A. Hence, by witnessing, Theorem 3.8, and the fact that $c \models \{\varphi _{i}(x;a_{j,i}) : j < \omega \}$ , we see that for each $i \leq n$ .

By induction on $k \leq n$ , we will choose $c_{k} \equiv ^{L}_{A} c$ such that $c_{k} \models \{\varphi _{i}(x;a_{i}) : i \leq k\}$ and . To begin we set $c_{0} = c$ . Given $c_{k}$ for some $k < n$ , we apply the independence theorem to find $c_{k+1}$ with $c_{k+1} \equiv _{Aa_{\leq k}}^{L} c_{k}$ , $c_{k+1} \equiv ^{L}_{Aa_{k+1}} c$ , and . After n steps, we obtain $c_{n} \models \bigwedge _{i \leq n} \varphi _{i}(x;a_{i})$ with , which shows (1).

Remark 4.3. The independence conditions of (2) and (3) do not imply that the sequence $\langle (a_{i,0},\ldots , a_{i,n}) : i < \omega \rangle $ is -Morley, due to the lack of base monotonicity. Consequently, this lemma strengthens witnessing, Theorem 3.8, for formulas of a certain form, showing that they Kim-divide along sequences that are themselves not necessarily -Morley sequences.

Corollary 4.4. Suppose T is NSOP $_{1}$ with existence. Assume that for each $i \leq n$ , we are given a complete type $p(y_{i}) \in S(A)$ and an $L(A)$ -formula $\varphi _{i}(x;y_{i})$ .

1. (1) There is a partial type $R(y_{0},\ldots , y_{n})$ over A containing $\bigcup _{i \leq n} p_{i}(y_{i})$ such that $a^{\prime }_{0},\ldots , a^{\prime }_{n} \models R(y_{0},\ldots , y_{n})$ if and only if for all $i \leq n$ and $\bigwedge _{i \leq n} \varphi _{i}(x;a^{\prime }_{i})$ does not Kim-divide over A.

2. (2) If, additionally, T is low, then there is a formula $\gamma (y_{0},\ldots , y_{n})$ over A such that, if $(a^{\prime }_{0},\ldots , a^{\prime }_{n}) \models p(y_{0}) \cup \ldots \cup p(y_{n})$ and for all $i\leq n$ , then $\mathbb {M} \models \gamma (a^{\prime }_{0},\ldots , a^{\prime }_{n})$ if and only if $\bigwedge _{i \leq n} \varphi _{i}(x;a^{\prime }_{i})$ does not Kim-divide over A.

Proof By Lemma 2.21(1), there is a partial type $\Lambda (z_{i,j} : i < \omega , j \leq n)$ over A which expresses the following:

1. (a) $z_{i,j} \models p_{j}$ for all $i < \omega $ and $j \leq n$ .

2. (b) for all $i < \omega $ and $j \leq n$ , where $\overline {z}_{i} = (z_{i,0},\ldots , z_{i,n})$ .

3. (c) The sequence $\langle \overline {z}_{i} : i < \omega \rangle $ is A-indiscernible.

Let $\lambda '(y_{0},\ldots , y_{n},\overline {z}_{i} : i < \omega )$ be the partial type given by $\{y_{j} = z_{0,j} : j \leq n\} \cup \Lambda (\overline {z}_{i} : i < \omega )$ .

To show (1), consider the partial type $R_{0}(y_{0},\ldots , y_{n},\overline {z}_{i} : i < \omega )$ which extends $\lambda '$ and expresses additionally that $\{\bigwedge _{i \leq n} \varphi _{i}(x;z_{i,j}) : i < \omega \}$ is consistent. Then R may be defined by

$$ \begin{align*}R(y_{0},\ldots, y_{n}) \equiv (\exists \overline{z}_{i} : i < \omega) \bigwedge R_{0}(y_{0},\ldots, y_{n},\overline{z}_{i}; i < \omega). \end{align*} $$

This R is clearly type definable and, by Lemma 4.2(3), R has the desired properties.

For (2), we know, by the lowness of T, that there is some $k < \omega $ such that, if, given any $\langle (a^{\prime }_{i,j})_{j \leq n} : i < \omega \rangle $ is an A-indiscernible sequence and

$$ \begin{align*} \left\{ \bigwedge_{j \leq n} \varphi_{i}(x;a_{i,j}) : i < \omega\right\} \end{align*} $$

is inconsistent, then this set of formulas is k-inconsistent. Consider the partial type $R_{1}(y_{0},\ldots , y_{n},\overline {z}_{i} : i < \omega )$ which extends $\lambda '$ and expresses additionally that $\{\bigwedge _{j \leq n} \varphi _{i}(x;z_{i,j}) : i < \omega \}$ is k-inconsistent. Then we will define $R'$ by

$$ \begin{align*} R'(y_{0},\ldots, y_{n}) \equiv (\exists \overline{z}_{i} : i < \omega) \bigwedge R_{1}(y_{0},\ldots, y_{n},\overline{z}_{i}; i < \omega). \end{align*} $$

It follows that if $(a^{\prime }_{j})_{j \leq n} \models \bigcup _{j \leq n} p_{j}(y_{j})$ and , then $(a^{\prime }_{j})_{j \leq n} \models R'$ if and only if $\bigwedge _{j \leq n} \varphi _{j}(x;a^{\prime }_{j})$ Kim-divides over A, by Lemma 4.2(2). We showed in (1) that the complement of $R'$ is type-definable (by R), and therefore, by compactness, we obtain the desired $\gamma $ .

Theorem 4.5. If T is a low NSOP $_{1}$ theory with existence, then Lascar strong types are strong types. That is, for any (possibly infinite) tuples $a,b$ and small set of parameters A, if $a \equiv ^{S}_{A} b$ then $a \equiv ^{L}_{A} b$ .

Proof Let A be any small set of parameters. As $T_{A}$ is G-compact by Fact 2.7(7) and, trivially, $T_{A}$ is low, it suffices to prove the theorem when a and b realize a type $p(x)$ over $\emptyset $ , where x is a finite tuple of variables. Let $r(x,y)$ be a partial type, closed under conjunctions, expressing that $x \equiv ^{L} y$ , i.e., $r(x,y)$ defines the finest type-definable equivalence relation over $\emptyset $ with boundedly many classes. Fix $\varphi (x;y) \in r(x,y)$ . Note that, for any $a \models p$ , $\varphi (x;a)$ does not divide over $\emptyset $ , because if $\langle a_{i} : i < \omega \rangle $ is an indiscernible sequence with $a_{0} = a$ , then $a_{0} \equiv ^{L} a_{i}$ for all $i< \omega $ , hence $a_{0} \models \bigcup _{i < \omega } r(x;a_{i})$ . In particular, $\varphi (x;a)$ does not Kim-divide over $\emptyset $ .

Define a relation $R_{\varphi }(u,v)$ expressing the following:

1. (1) $u,v \models p$ .

2. (2) There exists $v'$ satisfying:

   1. (a) $v' \equiv ^{L} v$ .

   2. (b) .

   3. (c) $\varphi (x;u) \wedge \varphi (x;v')$ does not Kim-divide over $\emptyset $ .

Clearly if $v \models p$ and $v \equiv ^{L}v'$ , then $v' \models p$ . By Lemma 2.21 and Corollary 4.4(1), there is a partial type $\Gamma (z,w)$ over $\emptyset $ such that $(v',u) \models \Gamma (z,w)$ if and only if $v',u \models p$ , , and $\varphi (x;v') \wedge \varphi (x;u)$ does not Kim-divide over $\emptyset $ . It follows that $R_{\varphi }(u,v)$ if and only if $(\exists v')\left [\bigwedge r(v,v') \wedge \Gamma (v',u)\right ]$ , which shows $R_{\varphi }(u,v)$ is type-definable.

In a similar fashion, we define a relation $S_{\varphi }(u,v)$ to hold when the following conditions are satisfied:

1. (1) $u,v \models p$ .

2. (2) There is $v'$ satisfying the following:

   1. (a) $v' \equiv ^{L} v$ .

   2. (b) .

   3. (c) $\varphi (x;u) \wedge \varphi (x;v)$ Kim-divides over $\emptyset $ .

The type-definability of $S_{\varphi }$ follows from an identical argument, using Corollary 4.4(2) in the place of Corollary 4.4(1) (this is where we make use of our hypothesis that T is low).

From here, our proof follows the argument of [1], as presented in [12, Section 5.2]. First, we show the following:

Claim 1. If $u,v \models p$ , then $R_{\varphi }(u,v)$ if and only if $\neg S_{\varphi }(u,v)$ .

Proof of Claim 1

First, it is clear that it is impossible for both $\neg R_{\varphi }(u,v)$ and $\neg S_{\varphi }(u,v)$ to hold since, by extension for Lascar strong types (Fact 2.20) there is $v' \equiv ^{L} v$ with and it must be the case that either $\varphi (x,u) \wedge \varphi (x;v')$ Kim-divides or $\varphi (x;u) \wedge \varphi (x;v')$ does not Kim-divide over $\emptyset $ .

Secondly, suppose $R_{\varphi }(u,v)$ holds witnessed by $v'$ and $S_{\varphi }(u,v)$ holds witnessed by $v"$ . Then we have $v \equiv ^{L} v' \equiv ^{L} v"$ , , , $\varphi (x;u) \wedge \varphi (x;v')$ does not Kim-divide over $\emptyset $ , and $\varphi (x;u) \wedge \varphi (x;v")$ Kim-divides over $\emptyset $ . Choose $c'$ realizing $\varphi (x;u) \wedge \varphi (x;v')$ with , and pick $c"$ so that $c'v' \equiv ^{L} c"v"$ . Then, in particular, we have $c' \equiv ^{L} c"$ , , , and so, by the independence theorem, there is c with $c \models \mathrm {Lstp}(c'/u) \cup \mathrm {Lstp}(c/v")$ and . Since c realizes $\varphi (x;u) \wedge \varphi (x;v")$ , we obtain a contradiction. Together with the first part, this establishes the claim.

By the claim and compactness, there is a formula $\sigma (x,y) = \sigma _{\varphi }(x,y)$ such that $p(x) \cup p(y) \vdash R_{\varphi }(x,y)$ if and only if $\sigma (x,y)$ . Moreover, it is clear from the definitions that $R_{\varphi }(x,y) \wedge r(y,y')$ implies $R_{\varphi }(x,y')$ . Again by compactness, there is a formula $\delta (x) \in p(x)$ such that

1. (*) $\delta (x) \wedge \delta (y) \wedge \sigma (x,y) \wedge \bigwedge r(x,z) \models \sigma (x,z).$

It follows from $(*)$ and the symmetry of r that, for any $z \models \delta $ , we have $\models \sigma (z,x) \leftrightarrow \sigma (z,y)$ , for all $x,y \models \delta $ . Therefore, we obtain a definable equivalence relation $E_{\varphi }(x,y)$ as follows:

$$ \begin{align*} E_{\varphi}(x,y) \equiv \left[ \neg \delta(x) \wedge \neg \delta(y) \right] \vee \left[ \delta(x) \wedge \delta(y) \wedge (\forall z) \left(\delta(z) \to (\sigma(z,x) \leftrightarrow \sigma(z,y) \right)\right]. \end{align*} $$

To conclude, we establish the following:

Claim 2. The partial type $p(x) \cup p(y)$ implies $r(x,y)$ holds if and only if $\bigwedge _{\varphi \in r} E_{\varphi }(x,y)$ holds.

Proof of claim

First, we will show $r(x,y)$ entails $E_{\varphi }(x,y)$ for all $\varphi \in r$ . Clearly $r(x,y)$ implies $\delta (x) \leftrightarrow \delta (y)$ . Moreover, as noted above, if $r(x,y)$ and $\delta (x) \wedge \delta (y)$ both hold, then for any $z \models \delta $ we have $\sigma (z,x) \leftrightarrow \sigma (z,y)$ by (*) above and the symmetry of $r(x,y)$ . Hence $E_{\varphi }(x,y)$ holds.

Second, we will show that if $(a,b)\models p(x) \cup p(y)$ does not realize $r(x,y)$ , then $\neg \bigwedge _{\varphi \in r} E_{\varphi }(a,b)$ . Choose $\psi (x,y) \in r(x,y)$ such that $\neg \psi (a,b)$ . Because r is an equivalence relation, there is some $\varphi (x,y) \in r(x,y)$ such that

$$ \begin{align*} (\exists x,x') \left( \varphi(x,y) \wedge \varphi(x,x') \wedge \varphi(x',z) \right) \vdash \psi(y,z). \end{align*} $$

Then if $E_{\varphi }(a,b)$ holds, then, because $R_{\varphi }(a,a)$ holds, we have $\sigma _{\varphi }(a,a)$ and $\sigma _{\varphi }(a,b)$ and therefore $R_{\varphi }(a,b)$ . By the definition of $R_{\varphi }(a,b)$ , this implies there is some $c \equiv ^{L} b$ such that $\varphi (x,a) \wedge \varphi (x,c)$ is consistent, and therefore $\models \psi (a,b)$ , a contradiction. This concludes the proof of the claim, and hence the theorem.

5 Rank

In this section, we introduce a family of ranks, suitable for the study of NSOP $_{1}$ theories. This makes critical use of witnessing over arbitrary sets and provides a clear context in which working over arbitrary sets greatly simplifies the situation. Our definition is close to the definition of D-rank familiar from simple theories, but we are required to add a new parameter in the rank, which keeps track of the type of the parameters that appear in instances of Kim-dividing.

Definition 5.1. Suppose $q(y) \in S(B)$ , $\Delta (x;y)$ is a finite set of $L(B)$ -formulas, and $k < \omega $ . Then for any set of formulas $\pi (x)$ over $\mathbb {M}$ , we define $D_{1}(\pi ,\Delta ,k,q) \geq 0$ if $\pi $ is consistent, and $D_{1}(\pi ,\Delta ,k,q) \geq n+1$ if there is a sequence $I = \langle c_{i} : i < \omega \rangle $ such that the following conditions hold:

1. (1) The sequence I is an -Morley sequence over B with $c_{i} \models q$ .

2. (2) The sequence I is indiscernible over $\mathrm {dom}(\pi )B$ (and hence for all i).

3. (3) We have $\{\varphi (x;c_{i}) : i < \omega \}$ is k-inconsistent for some formula $\varphi (x;y) \in \Delta $ .

4. (4) We have $D_{1}(\pi \cup \{\varphi (x;c_{i})\},\Delta ,k,q) \geq n$ for all $i < \omega $ .

We define $D_{1}(\pi ,\Delta ,k,q) = n$ if n is least such that $D_{1}(\pi ,\Delta ,k,q) \geq n$ and also $D_{1}(\pi ,\Delta ,k,q) \not \geq n+1$ . We say $D_{1}(\pi ,\Delta , k,q) = \infty $ if $D_{1}(\pi ,\Delta ,k,q) \geq n$ for all $n < \omega $ .

Lemma 5.2. Suppose $q(y) \in S(B)$ , $\Delta (x;y)$ is a finite set of $L(B)$ -formulas, and $k <\omega $ . Then we have the following:

1. (1) For all $\sigma \in \mathrm {Aut}(\mathbb {M}/B)$ ,

   $$ \begin{align*}D_{1}(\sigma(\pi),\Delta, k, q) = D_{1}(\pi,\Delta,k,q). \end{align*} $$

2. (2) If $\pi $ and $\pi '$ are partial types over $\mathbb {M}$ such that $\pi (x) \vdash \pi '(x)$ , then

   $$ \begin{align*}D_{1}(\pi,\Delta,k,q) \leq D_{1}(\pi',\Delta,k,q). \end{align*} $$

3. (3) If $n \geq m$ , then $D_{1}(\pi , \Delta ,k,q) \geq n$ implies $D_{1}(\pi ,\Delta ,k,q) \geq m$ .

4. (4) If $\psi _{0}(x),\ldots , \psi _{m-1}(x)$ are formulas over $\mathbb {M}$ , then

   $$ \begin{align*}D_{1}\left(\pi \cup \left\{ \bigvee_{j < m} \psi_{i}(x)\right\},\Delta,k,q\right) = \max_{j < m} D_{1}(\pi \cup \{\psi_{j}(x)\},\Delta,k,q). \end{align*} $$

Proof (1) is clear.

(2) By induction on n, we will show

$$ \begin{align*}D_{1}(\pi,\Delta,k,q) \geq n \implies D_{1}(\pi',\Delta,k,q) \geq n. \end{align*} $$

For $n = 0$ there is nothing to show. Suppose the statement holds for n, and assume $D_{1}(\pi ,\Delta ,k,q) \geq n+1$ . Then there is a $\mathrm {dom}(\pi )B$ -indiscernible sequence $I = \langle c_{i} : i < \omega \rangle $ which is additionally an -Morley sequence over B in q and $\varphi (x;y) \in \Delta $ such that $\{\varphi (x;c_{i}) : i < \omega \}$ is k-inconsistent and $D_{1}(\pi \cup \{\varphi (x;c_{i})\},\Delta ,k,q) \geq n$ . Let $I' = \langle c^{\prime }_{i} : i < \omega \rangle $ be a $B\mathrm {dom}(\pi )\mathrm {dom}(\pi ')$ -indiscernible sequence locally based on I. Clearly we have that $I'$ is an -Morley sequence in q over B and $D_{1}(\pi \cup \{\varphi (x;c^{\prime }_{i})\},\Delta ,k,q) \geq n$ for all $i < \omega $ , by (1). As $\pi \cup \{\varphi (x;c^{\prime }_{i})\} \vdash \pi ' \cup \{\varphi (x;c^{\prime }_{i})\}$ , we have $D_{1}(\pi ' \cup \{\varphi (x;c^{\prime }_{i})\},\Delta ,k,q) \geq n$ by induction, which implies $D_{1}(\pi ',\Delta ,k,q) \geq n+1$ .

(3) We will prove by induction on $l < \omega $ that $D_{1}(\pi ,\delta ,k,q) \geq n+l$ implies $D_{1}(\pi ,\delta ,k,q) \geq n$ . For $l = 0$ , this is trivial. Assume it has been shown for l and that $D_{1}(\pi ,\Delta ,k,q) \geq n + l+1$ . Then there is a sequence $I = \langle c_{i} : i < \omega \rangle $ satisfying the conditions of Definition 5.1 such that $D_{1}(\pi \cup \{\varphi (x;c_{i})\}, \Delta , k,q) \geq n + l$ for all i. By (2), this entails, in particular, that $D_{1}(\pi ,\Delta , k,q) \geq n+l$ and hence $D_{1}(\pi ,\Delta ,k,q) \geq n$ by induction.

(4) By (2), we have

$$ \begin{align*}\max_{j < m} D_{1}(\pi \cup \{\psi_{j}(x)\},\Delta,k,q) \leq D_{1}\left(\pi \cup \left\{ \bigvee_{j < m} \psi_{j}(x)\right\},\Delta,k,q\right). \end{align*} $$

Hence, it suffices to show, for $n < \omega $ , that

$$ \begin{align*}D_{1}\left(\pi \cup \left\{ \bigvee_{j < m} \psi_{j}(x)\right\},\Delta,k,q\right) \geq n \implies \max_{j < m} D_{1}(\pi \cup \{\psi_{j}(x)\},\Delta,k,q) \geq n. \end{align*} $$

Let C be the (finite) set of parameters appearing in the formulas $\psi _{0},\ldots , \psi _{n-1}$ . For $n = 0$ , this is clear. If $D_{1}\left (\pi \cup \left \{ \bigvee _{j < m} \psi _{j}(x)\right \},\Delta ,k,q\right ) \geq n+1$ , then, as in (2), there is an -Morley sequence $I = \langle c_{i} : i < \omega \rangle $ over B in q which is $\mathrm {dom}(\pi )BC$ -indiscernible and $\varphi (x;y) \in \Delta $ such that $\{\varphi (x;c_{i}) : i < \omega \}$ is k-inconsistent with

$$ \begin{align*} D_{1}\left( \pi \cup \left\{ \bigvee_{j < m} \psi_{j}(x) \right\} \cup \{\varphi(x;c_{i})\},\Delta,k,q\right) \geq n, \end{align*} $$

which implies $\max _{j<m} D_{1}(\pi \cup \{\psi _{j}(x), \varphi (x;c_{i})\},\Delta ,k,q) \geq n$ , by the induction hypothesis for n, for each i. By the pigeonhole principle, we may assume this maximum witnessed by the same j for all $i < \omega $ . This shows $\max _{j<m} D_{1}(\pi \cup \{\psi _{j}(x)\},\Delta ,k,q) \geq n+1$ .

Remark 5.3. Lemma 5.2(2) implies, in particular, that if $\pi (x)$ and $\pi '(x)$ are equivalent then the ranks (with respect to a choice of $\Delta $ , k, and q) will be the same, even if they have different domains.

Lemma 5.4. Suppose T is NSOP $_{1}$ with existence. Suppose $q \in S(B)$ , $\Delta (x;y)$ is a finite set of $L(B)$ -formulas, and $k < \omega $ . Then for all $n < \omega $ , we have $D_{1}(\pi ,\Delta ,k,q) \geq n$ if and only if there are $(c_{\eta })_{\eta \in \omega ^{\leq n} \setminus \{\emptyset \}}$ and $\varphi _{i}(x;y) \in \Delta $ for $i < n$ satisfying the following:

1. (a) For all $\eta \in \omega ^{n}$ ,

   $$ \begin{align*}\pi(x) \cup \{\varphi_{i}(x;c_{\eta |(i+1)}) : i < n\} \end{align*} $$

   is consistent.

2. (b) For all $\eta \in \omega ^{< n}$ , $\{\varphi _{l(\eta )}(x;c_{\eta \frown \langle i \rangle }) : i < \omega \}$ is k-inconsistent.

3. (c) For all $\eta \in \omega ^{< n}$ , $\langle c_{\eta \frown \langle i \rangle } : i < \omega \rangle $ is an -Morley sequence over B in q.

4. (d) The tree $(c_{\eta })_{\eta \in \omega ^{\leq n} \setminus \{\emptyset \}}$ is s-indiscernible over $B\mathrm {dom}(\pi )$ .

Proof For the case of $n = 0$ , (a) is satisfied if and only if $\pi $ is consistent and (b)–(d) hold trivially, which gives the desired equivalence.

Now assume, for a given n, that $D_{1}(\pi ,\Delta ,k,q) \geq n$ if and only if there are $(c_{\eta })_{\eta \in \omega ^{\leq n} \setminus \{\emptyset \}}$ and $\varphi _{i}(x;y) \in \Delta $ for $i < n$ such that (a)–(d) hold. First, suppose $D_{1}(\pi ,\Delta ,k,q) \geq n+1$ . Then we can find a $\mathrm {dom}(\pi )B$ -indiscernible sequence $I = \langle c_{i} : i < \omega \rangle $ which is also -Morley over B in q and $\varphi (x;y) \in \Delta $ such that $\{\varphi (x;c_{i}) : i < \omega \}$ is k-inconsistent and $D_{1}(\pi \cup \{\varphi (x;c_{i})\},\Delta ,k,q) \geq n$ for all $i < \omega $ . By induction, for each $i < \omega $ , there is a tree $(c_{i,\eta })_{\eta \in \omega ^{\leq n} \setminus \{\emptyset \}}$ and sequence of formulas $(\varphi _{i,j}(x;y))_{1 \leq j \leq n}$ from $\Delta $ satisfying (a)–(d), with $\pi $ replaced by $\pi \cup \{\varphi (x;c_{i})\}$ . As $\Delta $ is a finite set of formulas, we may, by the pigeonhole principle, assume that there are $\varphi _{j} \in \Delta $ such that $\varphi _{i,j}(x;y) = \varphi _{j}(x;y)$ for all $i < \omega $ and $1 \leq j \leq n$ . Now define a tree $(c^{\prime }_{\eta })_{\eta \in \omega ^{\leq n+1} \setminus \{\emptyset \}}$ such that $c^{\prime }_{\langle i \rangle } = c_{i}$ and $c^{\prime }_{\langle i \rangle \frown \eta } = c_{i,\eta }$ for all $i < \omega $ and $\eta \in \omega ^{\leq n} \setminus \{\emptyset \}$ . Define $\varphi _{0}(x;y) = \varphi (x;y)$ . Let $(c_{\eta })_{\eta \in \omega ^{\leq n+1} \setminus \{\emptyset \}}$ be a tree that is s-indiscernible tree over $\mathrm {dom}(\pi )B$ and locally based on $(c^{\prime }_{\eta })_{\eta \in \omega ^{\leq n+1} \setminus \{\emptyset \}}$ over B. Note that for all $\eta \in \omega ^{<n+1}$ , the sequence $\langle c_{\eta \frown \langle i \rangle } : i < \omega \rangle $ has the same type over B as a Morley sequence in q and hence is a Morley sequence in q. It is clear that $(c_{\eta })_{\eta \in \omega ^{\leq n+1} \setminus \{\emptyset \}}$ and $(\varphi _{j}(x;y))_{j < n+1}$ satisfy the requirements.

Conversely, given $(c_{\eta })_{\eta \in \omega ^{\leq n+1} \setminus \{\emptyset \}}$ and $(\varphi _{j}(x;y))_{j < n+1}$ satisfying (a)–(d), we observe by induction that the tree $(c_{\langle i \rangle \frown \eta })_{\eta \in \omega ^{\leq n} \setminus \{\emptyset \}}$ witnesses

$$ \begin{align*}D_{1}(\pi \cup \{\varphi_{0}(x;c_{\langle i \rangle})\},\Delta,k,q) \geq n, \end{align*} $$

for all $i < \omega $ . As the sequence $\langle c_{\langle i \rangle } : i < \omega \rangle $ is -Morley over B and $\mathrm {dom}(\pi )B$ -indiscernible, and $\{\varphi _{0}(x;c_{\langle i \rangle }) : i < \omega \}$ is k-inconsistent, it follows that

$$ \begin{align*}D_{1}(\pi,\Delta,k,q) \geq n+1, \end{align*} $$

completing the proof.

Corollary 5.5. If T is NSOP $_{1}$ with existence, then given $q(y) \in S(B)$ , a finite set of $L(B)$ -formulas $\Delta (x;y)$ , and $k < \omega $ , there is some $n < \omega $ such that $D_{1}(x = x, \Delta ,k,q) = n$ .

Proof Suppose towards contradiction that there are q, $\Delta $ , and $k < \omega $ such that $D(x=x,\Delta , k,q)> n$ for all $n < \omega $ . By Lemma 5.4, Lemma 2.21, compactness, and the pigeonhole principle (by the finiteness of $\Delta $ ), we can find a tree $(c_{\eta })_{\eta \in \omega ^{<\omega } \setminus \{\emptyset \}}$ and $\varphi (x;y) \in \Delta $ satisfying the following:

1. (a) For all $\eta \in \omega ^{\omega }$ ,

   $$ \begin{align*}\{\varphi(x;c_{\eta | (i+1)}) : i < \omega\} \end{align*} $$

   is consistent.

2. (b) For all $\eta \in \omega ^{< \omega }$ , $\{\varphi (x;c_{\eta \frown \langle i \rangle }) : i < \omega \}$ is k-inconsistent.

3. (c) For all $\eta \in \omega ^{< \omega }$ , $\langle c_{\eta \frown \langle i \rangle } : i < \omega \rangle $ is an -Morley sequence over B in q.

4. (d) The tree $(c_{\eta })_{\eta \in \omega ^{<\omega } \setminus \{\emptyset \}}$ is s-indiscernible over B.

Note that, by s-indiscernibility, we have $\langle c_{0^{n} \frown \langle i \rangle } : i < \omega \rangle $ is an -Morley sequence over B which is $Bc_{0\frown 0^{< n}}$ -indiscernible, for all $n < \omega $ . By witnessing, it follows that for all n. Let $\langle d_{i} : i < \omega \rangle $ be a B-indiscernible sequence locally based on $\langle c_{0^{n}} : 1 \leq n < \omega \rangle $ over B. As each $c_{0^{n}} \models q$ , for $1 \leq n < \omega $ , we have that for all n as well, and therefore $\langle d_{i} : i < \omega \rangle $ is an -Morley sequence over B in $q'$ . Moreover, since $\{\varphi (x;c_{0^{n}}) : 1 \leq n < \omega \}$ is consistent, we know $\{\varphi (x;d_{n}) : n < \omega \}$ is consistent. However, we know $\varphi (x;c_{0^{n}})$ Kim-divides over B and hence $\varphi (x;d_{n})$ Kim-divides over B. This contradicts witnessing (Theorem 2.5).

Remark 5.6. Corollary 5.5 has a converse: if T has SOP $_{1}$ , then for some B, there is a $q(y) \in S(B)$ , a finite set of $L(B)$ -formulas $\Delta (x;y)$ , and $k < \omega $ such that $D_{1}(x = x, \Delta ,k,q) = \infty $ . One way to see this is to note that by [5, Corollary 3.7] Kim’s lemma for non-forking Morley sequences fails over some set B in any theory with SOP $_{1}$ (this doesn’t use existence). Concretely, this means there are Morley sequences $I = \langle a_{i} : i < \omega \rangle $ and $J = \langle b_{i} : i < \omega \rangle $ over B with $a_{0} = b_{0}$ and a formula $\varphi (x;y)$ such that $\{\varphi (x;a_{i}) : i < \omega \}$ is k-inconsistent and $\{\varphi (x;b_{i}) : i < \omega \}$ is consistent. Then, by [5, Lemma 3.4], this implies there is a tree $(c_{\eta })_{\eta \in \omega ^{<\omega }}$ satisfying the following properties:

1. (1) For all $\eta \in \omega ^{<\omega }$ , $(c_{\eta \frown \langle i \rangle })_{i < \omega } \equiv _{B} I$ .

2. (2) For all $\eta \in \omega ^{<\omega }$ , $(c_{\eta },c_{\eta | l(\eta ) - 1}, \ldots , c_{\emptyset }) \equiv _{B} (b_{0},b_{1},\ldots , b_{l(\eta )})$ .

3. (3) $(c_{\eta })_{\eta \in \omega ^{<\omega }}$ is s-indiscernible over B.

Then, by Lemma 5.4, for $q = \text {tp}(a_{0}/B)$ , we have $D_{1}(x = x, \Delta , k,q) \geq n$ for all n.

Lemma 5.7. Suppose T is NSOP $_{1}$ with existence. Suppose $q(y) \in S(B)$ , $\Delta (x,y)$ is a finite set of $L(B)$ -formulas, and $k < \omega $ .

1. (1) For any partial type p, there is a finite $r \subseteq p$ such that

   $$ \begin{align*}D_{1}(p,\Delta,k,q) = D_{1}(r,\Delta,k,q). \end{align*} $$

2. (2) For any small set $A \subseteq \mathbb {M}$ and any partial type p over A, there is $p' \in S(A)$ extending p such that

   $$ \begin{align*}D_{1}(p,\Delta,k,q) = D_{1}(p,\Delta,k,q). \end{align*} $$

Proof (1) By Lemma 5.2(1), if r is a subtype of p then $D_{1}(r,\Delta ,k,q) \geq D_{1}(p,\Delta ,k,q)$ so it suffices to find a finite $r \subseteq p$ with $D_{1}(r,\Delta ,k,q) \leq D_{1}(p,\Delta ,k,q)$ . Suppose $D_{1}(p,\Delta ,k,q) = n$ . Consider, for each sequence $\overline {s} = (\varphi _{i}(x;y))_{i < n+1}$ of formulas from $\Delta $ , the set of formulas $\Gamma _{\overline {s}}(x,(z_{\eta })_{\eta \in \omega ^{\leq n+1} \setminus \{\emptyset \}})$ over $\mathrm {dom}(p)B$ expressing the following:

1. (1) For all $\eta \in \omega ^{n+1}$ ,

   $$ \begin{align*}p(x) \cup \{\varphi_{i}(x;z_{\eta |(i+1)}) : i < n+1\} \end{align*} $$

   is consistent.

2. (2) For all $\eta \in \omega ^{< n+1}$ , $\{\varphi _{l(\eta )}(x;z_{\eta \frown \langle i \rangle }) : i < \omega \}$ is k-inconsistent.

3. (3) For all $\eta \in \omega ^{< n+1}$ , $\langle z_{\eta \frown \langle i \rangle } : i < \omega \rangle $ is an -Morley sequence over B in q (possible by Lemma 2.21(2)).

4. (4) The tree $(z_{\eta })_{\eta \in \omega ^{\leq n+1} \setminus \{\emptyset \}}$ is s-indiscernible over $B\mathrm {dom}(p)$ .

By Lemma 5.4 and the fact that $D_{1}(p,\Delta ,k,q) = n < n+1$ , we know that $\Gamma _{\overline {s}}$ is inconsistent. By compactness, there is some finite $r_{\overline {s}}(x) \subseteq p(x)$ such that, replacing $p(x)$ with $r_{\overline {s}}(x)$ in (1), the formulas remain inconsistent. Let r be the union of $r_{\overline {s}}$ as $\overline {s}$ ranges over all length $n+1$ sequences of formulas of $\Delta $ . As $\Delta $ is finite, this is a finite set, so r is a finite extension of each $r_{\overline {s}}$ and a subtype of p. Then by Lemma 5.4 again, $D_{1}(r,\Delta ,k,q) \leq n = D_{1}(p,\Delta ,k,q)$ .

(2) Let $\Gamma (x)$ be defined as follows:

$$ \begin{align*}\Gamma(x) = \{ \neg \psi(x) \in L(A) : D_{1}(p(x) \cup \{\psi(x)\}, \Delta,k,q) < D_{1}(p,\Delta,k,q)\}. \end{align*} $$

If $p(x) \cup \Gamma (x)$ is inconsistent, then by compactness, there are $\psi _{0},\ldots , \psi _{n-1} \in \Gamma $ such that $p(x) \vdash \bigvee _{j < n} \psi _{j}$ . By Lemma 5.2(1) and (2), this gives

$$ \begin{align*} D_{1}(p,\Delta,k,q) &= D_{1} \left(p \cup \left\{\bigvee_{j < n} \psi_{j}(x)\right\},\Delta,k,q\right) \\ &= \max_{j} D_{1}(p \cup \{\psi_{j}(x)\},\Delta,k,q) \\ &< D_{1}(p,\Delta,k,q), \end{align*} $$

a contradiction. Therefore, we can choose a complete type $p' \in S(A)$ extending $p(x) \cup \Gamma (x)$ . By (1), if $D_{1}(p',\Delta ,k,q) < D_{1}(p,\varphi ,k,q)$ , then there is a formula $\psi (x) \in p'$ such that $D_{1}(p \cup \{\psi (x)\}, \Delta ,k,q) < D_{1}(p,\Delta ,k,q)$ but this is impossible by the definition of $\Gamma $ . Therefore $p'$ is as desired.

Theorem 5.8. Assume T is NSOP $_{1}$ with existence.

1. (1) Suppose $\pi $ is a partial type over B and $\pi \subseteq \pi '$ . If $\pi '$ Kim-divides over B, witnessed by the formula $\varphi (x;c_{0})$ , and $I = \langle c_{i} : i < \omega \rangle $ is an -Morley sequence over B in q such that $\{\varphi (x;c_{i}) : i < \omega \}$ is k-inconsistent, then we have

   $$ \begin{align*}D_{1}(\pi',\varphi,k,q) < D_{1}(\pi,\varphi,k,q). \end{align*} $$

2. (2) If T is simple, , then for any $q(y) \in S(B)$ , any finite set of $L(B)$ -formulas $\Delta (x,y)$ , and any $k < \omega $ , we have

   $$ \begin{align*}D_{1}(p', \Delta,k,q) = D_{1}(p,\Delta,k,q), \end{align*} $$

   where $p' = \mathrm {tp}(a/BDC)$ and $p = \mathrm {tp}(a/BD)$ .

Proof Suppose we are given $\pi \subseteq \pi '$ , $\varphi $ , k, I, and q as in the statement. We claim that $D_{1}(\pi \cup \{\varphi (x;c_{0})\},\varphi ,k,q) < D_{1}(\pi ,\varphi ,k,q)$ . If not, then, again by Lemma 5.2(1), we have

$$ \begin{align*}n := D_{1}(\pi \cup \{\varphi(x;c_{0})\},\varphi,k,q) = D_{1}(\pi,\varphi,k,q), \end{align*} $$

and therefore, by B-indiscernibility, $D_{1}(\pi \cup \{\varphi (x;c_{i})\},\varphi ,k,q) = n$ for all i. This implies, by definition of the rank, that $D_{1}(\pi ,\varphi ,k,q) \geq n+1$ , a contradiction. Therefore, since $\varphi (x;c_{0}) \in \pi '$ , we have

$$ \begin{align*}D_{1}(\pi',\varphi,k,q) \leq D_{1}(\pi \cup \{\varphi(x;c_{0})\},\varphi,k,q) < D_{1}(\pi,\varphi,k,q), \end{align*} $$

which proves (1).

Now we prove (2). As we are working in a simple theory, Kim-dividing and forking coincide by Kim’s lemma [10]. Fix an arbitrary $q \in S(B)$ , finite set of $L(B)$ -formulas $\Delta (x,y)$ and $k < \omega $ . By Lemma 5.2(2), we have

$$ \begin{align*}D_{1}(p', \Delta,k,q) \leq D_{1}(p,\Delta,k,q). \end{align*} $$

Hence, it suffices to show, by induction on $n < \omega $ ,

$$ \begin{align*}D_{1}(p,\Delta,k,q) \geq n \implies D_{1}(p', \Delta,k,q) \geq n. \end{align*} $$

For $n = 0$ , this is clear, so assume it holds for n and suppose $D_{1}(p,\Delta ,k,q) \geq n+1$ . Then there is a Morley sequence $I = \langle c_{i} : i < \omega \rangle $ over B in q which is $BD$ -indiscernible such that, for some $\varphi (x,y) \in \Delta $ , $\{\varphi (x;c_{i}) : i < \omega \}$ is k-inconsistent and $D_{1}(p \cup \{\varphi (x;c_{i}) \}, \Delta , k, q) \geq n$ for all $i < \omega $ . Let $p_{*} = p_{*}(x;c_{0})$ be a completion of $p \cup \{\varphi (x;c_{0})\}$ over $BDc_{0}$ with

$$ \begin{align*}D_{1}(p_{*},\Delta,k,q) = D_{1}(p \cup \{\varphi(x;c_{0})\},\Delta,k,q) \geq n, \end{align*} $$

which is possible by Lemma 5.7(2). Without loss of generality, $a \models p_{*}$ .

By extension and an automorphism over $aBD$ , we may assume , and hence there is $I' = \langle c^{\prime }_{i} : i < \omega \rangle \equiv _{BDc_{0}} I$ such that $I'$ is $BCD$ -indiscernible. Note that $I'$ is still Morley in q. Moreover, by base monotonicity and symmetry, this gives . Let $p_{*}' = \text {tp}(a/BCDc^{\prime }_{0}) \supseteq p'$ . By the inductive hypothesis, the fact that $D_{1}(p_{*},\Delta ,k,q) \geq n$ gives

$$ \begin{align*}D_{1}(p_{*}',\Delta,k,q) \geq n. \end{align*} $$

By Lemma 5.2(1) and (2), we obtain

$$ \begin{align*}D_{1}(p' \cup \{\varphi(x;c^{\prime}_{i})\}, \Delta,k,q) \geq n \end{align*} $$

for all $i < \omega $ , which allows us to conclude $D_{1}(p',\Delta ,k,q) \geq n+1$ , completing the proof.

Remark 5.9. By witnessing (Theorem 3.8), we know that if $\pi $ is a partial type over B and $\pi '$ Kim-divides over B, then this will be witnessed by some formula $\varphi (x;c_{0})$ implied by $\pi '$ and an -Morley sequence over B. Therefore, Theorem 5.8(1) implies that, if for all $\varphi (x;y) \in L(B)$ , $q(y) \in S(B)$ , and $k < \omega $ ,

$$ \begin{align*} D_{1}(\pi',\varphi,k,q) = D_{1}(\pi,\varphi,k,q), \end{align*} $$

then $\pi '$ does not Kim-divide over B.

Question 5.10. Does Theorem 5.8(2) hold for in all NSOP $_{1}$ theories satisfying existence? Evidently, the proof above makes use of base monotonicity, which is known to fail in all non-simple NSOP $_{1}$ theories.

6 The Kim–Pillay theorem over arbitrary sets

The Kim–Pillay-style criterion for NSOP $_{1}$ of [4] proceeds, essentially, by first showing that any relation that satisfies axioms (1)–(5) over models in the axioms below must be weaker than coheir independence, in the sense that if $M \models T$ and $\text {tp}(a/Mb)$ is finitely satisfiable in M then . Consequently, this proof does not adapt to arbitrary sets. Instead, we relate any relation satisfying the axioms to Kim-independence directly, using a tree-induction, to prove the following theorem.

Theorem 6.1. Assume T satisfies existence. The theory T is NSOP $_{1}$ if and only if there is an $\text {Aut}(\mathbb {M})$ -invariant ternary relation on small subsets of the monster $\mathbb {M} \models T$ which satisfies the following properties, for an arbitrary set of parameters A and arbitrary tuples from $\mathbb {M}$ .

1. (1) Strong finite character: if , then there is a formula $\varphi (x,b,m) \in \text {tp}(a/bA)$ such that for any $a' \models \varphi (x,b,m)$ , .

2. (2) Existence and Extension: always holds and, if , then, for any c, there is $a' \equiv _{Ab} a$ such that .

3. (3) Monotonicity: .

4. (4) Symmetry: .

5. (5) The independence theorem: , , and $a \equiv ^{L}_{A} a'$ implies there is $a"$ with $a" \equiv _{Ab} a$ , $a" \equiv _{Ac} a'$ and .

Moreover, any such relation satisfying (1)–(5) strengthens , i.e., implies . If, additionally, satisfies the following:

1. (6) Transitivity: if and then .

2. (7) Local character: if $\kappa \geq |T|^{+}$ is a regular cardinal, $\langle A_{i} : i < \kappa \rangle $ is an increasing continuous sequence of sets of size $ <\kappa $ , $A_{\kappa } = \bigcup _{i < \kappa } A_{i}$ and $|A_{\kappa }| = \kappa $ , then for any finite d, there is some $\alpha < \kappa $ such that ,

then .

Proof We know that if T is NSOP $_{1}$ with existence then satisfies (1)–(5) by Fact 2.7, so we will show the other direction.

First, assume satisfies axioms (1)–(5), and we will show that strengthens . By [4, Theorem 6.1], the existence of such a relation over models entails that the theory is NSOP $_{1}$ . Towards contradiction, suppose there is some set of parameters A and tuples $a,b$ such that but , witnessed by the formula $\varphi (x;b) \in \text {tp}(a/Ab)$ . By induction on the ordinals $\alpha $ , we will construct trees $(b^{\alpha }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ satisfying the following conditions for all $\alpha $ :

1. (a) For all $\eta \in \mathcal {T}_{\alpha }$ , $b^{\alpha }_{\eta } \models \text {tp}(b/A)$ .

2. (b) $(b^{\alpha }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ is s-indiscernible and weakly spread out over A.

3. (c) For $\alpha $ successor, .

4. (d) If $\beta < \alpha $ , then $b^{\alpha }_{\iota _{\beta \alpha }(\eta )} = b^{\beta }_{\eta }$ for all $\eta \in \mathcal {T}_{\beta }$ .

To begin, we may take $b^{0}_{\emptyset } = b$ and at limits we take unions. Given $(b^{\alpha }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ , let $I = \langle (b^{\alpha }_{i,\eta })_{\eta \in \mathcal {T}_{\alpha }} : i < \omega \rangle $ be a mutually s-indiscernible Morley sequence over A with $(b^{\alpha }_{0,\eta })_{\eta \in \mathcal {T}_{\alpha }} = (b^{\alpha }_{\eta })_{\eta \in \mathcal {T}_{\alpha }}$ , which exists by Lemma 2.15. We may apply extension to find $b_{*} \equiv _{A} b$ such that . Define a tree $(c_{\eta })_{\eta \in \mathcal {T}_{\alpha +1}}$ by setting $c_{\emptyset } = b_{*}$ and $c_{\langle i \rangle \frown \eta } = b_{i,\eta }^{\alpha }$ for all $i < \omega $ and $\eta \in \mathcal {T}_{\alpha }$ . Finally, we may define $(b^{\alpha +1}_{\eta })_{\eta \in \mathcal {T}_{\alpha +1}}$ to be an s-indiscernible tree over A locally based on $(c_{\eta })_{\eta \in \mathcal {T}_{\alpha +1}}$ . After moving by an automorphism, we can assume $b^{\alpha +1}_{\iota _{\alpha \alpha +1}(\eta )} = b^{\alpha }_{\eta }$ for all $\eta \in \mathcal {T}_{\alpha }$ . This completes the construction. By strong finite character and invariance, our construction ensures (b) and (c) will be satisfied for $(b^{\alpha +1}_{\eta })_{\eta \in \mathcal {T}_{\alpha +1}}$ .

Applying Erdős–Rado, we obtain a weak Morley tree $(b_{\eta })_{\eta \in \mathcal {T}_{\omega }}$ over A such that for all $\alpha < \omega $ . In particular, $(b_{\zeta _{\alpha }})_{\alpha < \omega }$ is an -Morley sequence over A. Define $\nu _{\alpha } = \zeta _{\alpha +1} \frown \langle 1 \rangle $ for all $\alpha < \omega $ . Because the tree is weakly spread out over A, we have for all $\alpha < \omega $ , and hence since $(b_{\nu _{\beta }})_{\beta < \alpha }$ was enumerated in $b_{\unrhd \zeta _{\alpha +1} \frown 0}$ . Since the tree is a weak Morley tree, we have that both $(b_{\zeta _{\alpha }})_{\alpha < \omega }$ and $(b_{\nu _{\alpha }})_{\alpha < \omega }$ are A-indiscernible.

As $b \equiv _{A} b_{\zeta _{0}}$ , there is $a_{0}$ such that $a_{0}b_{\zeta _{0}} \equiv _{A} ab$ . As $(b_{\zeta _{\alpha }})_{\alpha < \omega }$ is A-indiscernible, for each $\alpha> 0$ , there is $\sigma _{\alpha } \in \mathrm {Autf}(\mathbb {M}/A)$ such that $\sigma _{\alpha }(b_{\zeta _{0}}) = b_{\zeta _{\alpha }}$ . Setting $a_{\alpha } = \sigma _{\alpha }(a_{0})$ , we have $a_{\alpha }b_{\zeta _{\alpha }} \equiv ^{L}_{A} a_{0}b_{\zeta _{0}}$ . By the independence theorem for , we may find some $a_{*}$ such that $a_{*} b_{\zeta _{\alpha }} \equiv _{A} ab$ for all $\alpha < \omega $ . In particular, this implies $\{\varphi (x;b_{\zeta _{\alpha }}) : \alpha < \omega \}$ is consistent. However, since $\varphi (x;b)$ Kim-divides over A, $\{\varphi (x;b_{\nu _{\alpha }}) : \alpha < \omega \}$ is k-inconsistent for some k. The s-indiscernibility of the tree implies that $b_{\zeta _{\alpha }} \equiv _{A b_{\zeta _{>\alpha }}b_{\nu _{>\alpha }}} b_{\nu _{\alpha }}$ for all $\alpha $ , so by compactness, we have shown $\varphi $ has SOP $_{1}$ . This contradiction shows that strengthens .

Second, assume additionally that satisfies (6) and (7). The proof of Theorem 3.8 shows that (6) and (7) imply witnessing: if $I = (b_{i})_{i < \omega }$ is an A-indiscernible sequence with $b_{0} = b$ satisfying , then whenever , there is $\varphi (x;c,b) \in \text {tp}(a/Ab)$ such that $\{\varphi (x;c,b_{i}) : i < \omega \}$ is inconsistent.

Suppose that and, by extension and Erdős–Rado, find an -Morley sequence $I = \langle b_{i} : i < \omega \rangle $ over A with $b_{0} =b$ . By the remarks above, we know that I is, in particular, an -Morley sequence over A, so there is $a' \equiv _{Ab} a$ such that I is $Aa$ -indiscernible (using . By witnessing, this entails . In other words, and coincide.

Remark 6.2. It is clear from the proof of Theorem 6.1 that, in order to get the same conclusion, we can replace (6) and (7) with witnessing: if $I = (b_{i})_{i < \omega }$ is an A-indiscernible sequence with $b_{0} = b$ satisfying , then whenever , there is $\varphi (x;c,b) \in \text {tp}(a/Ab)$ such that $\{\varphi (x;c,b_{i}) : i < \omega \}$ is inconsistent.

To do so gives a result that more closely resembles [8, Theorem 6.11], while the formulation of Theorem 6.1 is closer to the original Kim–Pillay theorem for simple theories [15, Theorem 4.2] (see also [12, Theorem 3.3.1]).