to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}^{\eth^{k}}$.

This concludes the proof of Theorem 3.2, and our discussion of the free roots
of the complete graph.

######  Example 3.8.

(Model companion of directed graphs with no directed cycles of length $\leq
n$.) In Example 2.8.3 of [35], Shelah shows that the theory of directed graphs
with no directed cycles of length $\leq n$ has a strictly
$\mathrm{NSOP}_{n+1}$ model companion $T_{n}$. (Note that if there is a
directed cycle of length $\leq n$ that repeats vertices, there is one that
does not repeat any vertices.) We show again that if $2^{k}\geq n$, then
$\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}^{\eth^{k}}$
coincides with $\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}^{a}$. This will
be for somewhat different reasons than Example 3.1, with successive
approximations of forking-independence given by longer directed distances,
rather than distances tending away from the extremes. We will use the same
technique as in Theorem 3.2, but the proof will be more intuitive.

Shelah observes that $T_{n}$ has quantifier elimination in the language with
binary relation symbols $R_{n}(x,y)$ indicating a path of length $n$ from $x$
to $y$. We refine this quantifier elimination. Let
$n^{*}=\lceil\frac{n}{2}\rceil$. Then there must be a path of length $\leq
n^{*}$ between any two nodes by existential closedness: if there is not one,
one can be added on without creating any cycles of length $\leq n$. Moreover,
by the lack of cycles, if there is a path of $\leq\frac{n}{2}$ there must be
such a path in only one direction, by the absence of directed cycles of length
$\leq n$. So if $n$ is even any pair of distinct nodes $a,b$ has one of
$2n^{*}=n$ types, depending on the length of a minimal path, which will be at
most $n^{*}$, and the direction of that path; call this the “directed
distance” between $a$ and $b$. If $n$ is odd, any pair of distinct nodes has
one of $2n^{*}+1=n$ types, depending on the length of a minimal path, which
will be at most $n^{*}$, and the direction of that path if its length is
$<n^{*}$; if the length of a minimal path is $n^{*}$, $a$ and $b$ will have an
bi-directed distance of $n^{*}$, and $a$ and $b$ will otherwise have a
directed distance of $<n^{*}$.

The type of a set $S$ of distinct nodes will be determined by the distances
between any two elements of $S$. We give necessary and sufficient criteria for
an assignment of distances to pairs of nodes in $S$ to be consistent:

(1) If a directed path of length $k\leq\frac{n}{2}$ is indicated by a chain of
directed distances from $a$ and $b$ with total length $d$ (i.e. there are
$a=a_{0},a_{1},\ldots,a_{m-1},a_{m}=b$, with a directed distance of $d_{i}$
from $a_{i-1}$ to $a_{i}$ and $d=\sum_{i=1}^{n}d_{i}\leq\frac{n}{2}$), then
the directed distance from $a$ to $b$ is at most $d$.

(2) Chains of distances distances cannot indicate a directed cycle of length
$\leq n$ (i.e. $a=a_{0},a_{1},\ldots,a_{m-1},a_{m}=a$, with a directed (or bi-
directed) distance of $a_{i}$ from $a_{i-1}$ to $a_{i}$ and
$d=\sum_{i=1}^{n}d_{i}\leq n$).

Clearly (1) and (2) are necessary. To show they are sufficient, assume
distances are assigned to pairs in a set $S$; we will find a model $M$
containing $S$ realizing those assignments. For each pair $a,b\in S$, if a
directed distance of $d$ (or an bi-directed distance of $d=n^{*}$) is assigned
from $a$ to $b$, draw a path from $a$ to $b$ of length $d$ as well as a path
in the opposite direction of length $n+1-d$. We show that $S$ together with
these new vertices has no directed cycles of length $\leq n$. Suppose it
contained such a cycle. That cycle can be partitioned into the paths added
between elements of $S$. Suppose it contained the longer of the two paths, of
length $n-d+1$, added from, say, $b$ to $a$. It cannot contain the shorter
path, of length $d$, between $a$ and $b$, as then this cycle would be too
long. But perhaps there another path that is even shorter than the directed
distance $d$ from $a$ to $b$, formed out of paths of length less than $d\leq
n^{*}$ between other vertices in $S$. This cannot happen, by (1). (This also
handles the case where $a$ and $b$ have an bi-directed distance of $n^{*}$
when $n$ is odd.) Otherwise, all of the added paths between elements of $S$
that make up the cycle of length $\leq n$, are the paths of length $<n^{*}$
going in the direction of the directed distances. But this cannot happen, by
(2). Call the union of $S$ with the additional paths $T$, which we have shown
has no cycles of length $\leq n$, and find a model $M$ containing $T$. Then
any two nodes in $S$ will have directed distance in $M$ at most the assigned
distance $d$, as we added the shorter path going in that direction, but no
less than the assigned distance, as we added the longer paths of length $n-d$
in the other direction, so a new path of length $<d$ in the direction of the
directed distance would create a cycle of length $\leq n$.

We next show, as an analogue of Lemma 3.3, that sets can be “freely
amalgamated:” if $A\cap B=C$ with $A$ and $B$ given consistent assignments of
distances agreeing on $C$, then there is an assignment of distances on $C$
agreeing with that on $A$ and $B$ and so that for $a\in A\backslash C$, $b\in
B\backslash C$, the distance between $a$ and $b$ is the least total length of
a chain of directed distances of total length $\leq n^{*}$ between $A$ and $B$
going through $C$ (i.e., without requiring a directed distance between a point
of $A\backslash C$ and a point of $B\backslash C$ as one of the steps in the
chain), going in the direction of that chain, and is otherwise of length
$n^{*}$. We first show that the directed distances already within $A\cup B$
(i.e. not between a point of $A\backslash C$ and a point of $B\backslash C$)
satisfy (1) and (2) (i.e., if $a\in A$ then $b\in A$, and if $a_{i}\in A$ then
$a_{i+1}\in A$, and similarly for $B$.) For (1), we can assume without loss of
generality that $a$ and $b$ are in $A$, and then the chain can be broken up
into parts in $A$ and parts in $B$ each going between two nodes of $C$, but
all of the parts in $B$ can be presumed to be in $C\subseteq A$, by (1) on
$B$; having assumed this, we can then apply $1$ on $A$. For (2), a directed
cycle of length $\leq n$ formed by chains of directed distances can similarly
be broken up into parts in $A$ and parts in $B$, but only one of the parts,
say in $A$ can have length $\geq n^{*}$, and all of the other parts, by (1) in
$A$ and $B$, can be presumed in $C\subseteq A$, contradicting (2) in $A$. So
the direction of the chain of shortest total length $\leq n^{*}$ between a
point of $A\backslash C$ and a point of $B\backslash C$ going through $C$ is
well-defined, by (2) for chains in $A\cup B$ going through $C$, so if such a
chain exists we use it as the definition for the directed distance, and
otherwise we choose a distance in an arbitrary direction of size $n^{*}$.

It remains to show (1) and (2) on the whole of $A\cup B$. For (1), if $a,b$
are not both in $A$ or both in $B$, then any directed distance of length $\leq
n^{*}$ on a chain from $a$ to $b$ between a point of $A\backslash C$ and a
point of $B\backslash C$ can be replaced with a chain going through $C$ of the
same total length in the same direction, by construction. So any chain of
directed distances between $a$ and $b$ can be replaced by a chain of directed
distances of the same total length between $a$ and $b$ and in the same
direction, going through $C$, so the directed distance between $a$ and $b$
will be as short or shorter in that direction, by definition. To complete (1)
on the whole of $A\cup B$, if $a,b$ both belong to, say, $A$, then again by
construction we can assume a chain of directed distances to be a chain going
through $C$, and then use (1) for chains going through $C$. Finally, for (2),
suppose first that the distances indicating a $\leq n$ cycle are either
between two points of $A$ or $B$ or added between a point of $A\backslash C$
and a point of $B\backslash C$ because of a chain of the same length and the
same direction going through $C$. Then those distances can be replaced with
those chains, reducing (2) to the case of chains going through $C$, see above.
Otherwise, one of the distances must be $n^{*}$ between a point $a\in
A\backslash C$ and a point $b\in B\backslash C$, added because there is no
chain going through $C$ of length $\leq n^{*}$. But the rest of the cycle must
be a chain of distances of total length $\leq n^{*}$, each of which, being of
length $<n^{*}$ can be replaced with chains going through $C$, and can thus be
assumed a chain of length $<n^{*}$ going through $C$ from $a$ to $b$, a
contradiction to the assumption on $a$ and $b$ that caused their distance to
have length $n^{*}$.

Say that $C\subset A,B$, sitting in a fixed model, have distance $\geq k$ over
$C$ for $k\leq n^{*}$ if $A\cap B=C$ and any $a\in A\backslash C$ and $b\in
B\backslash C$ have distance in the same length and direction as the directed
chain of distances of minimal total length through $C$ in $A\cup B$ if that
length is $<k$, and otherwise have distance of length $\geq k$. We show an
analogue of Lemma 3.5: if $C\subseteq A,B,D$ with $A\cup D$ and $B\cup D$
freely amalgamated over $D$ as in the above discussion, and $A$ and $B$ both
of distance $\geq k$ from $D$ over $C$, then (a) $A$ has distance
$\geq\mathrm{min}(2k,n^{*})$ from $B$ over $C$ and (b) $A\cup B$ has distance
$\geq k$ from $D$ over $C$. To show $A$, if a point $a\in A\backslash C$ and
$b\in B\backslash C$ have distance of length $<\mathrm{min}(2k,n^{*})$ (say,
going from $a$ to $b$), then there must be a chain of length
$<\mathrm{min}(2k,n^{*})$ going through $D$. This chain can be broken
alternately into parts entirely in $A$ and entirely in $B$. Using the fact
that the chain has length $\leq n^{*}$, all of the parts except for the first
and the last can be assumed entirely in $D$, and then replaced by (1) with a
single distance between two points in $D$; that distance and the distance from
the second point in $D$ to $B$ can then be replaced by a single distance,
giving a chain of length $2$, going from $a$ to $d\in D$ and then to $B$. One
of the two distances, say from $a$ to $d$, must have length $<k$, so there
must be a chain of distances with the same total length and direction from $A$
to $D$, going through $C$ in $A\cup D$. So we can replace the distance from
$a$ to $d$ with a distance from $a$ to $c$ followed by from $c$ to $d$, and
can then replace the distance from $c$ to $d$ and from $d$ to $b$ with a
single distance from $c$ to $b$, yielding a chain of equal or shorter length
from $a$ to $b$ going through $C$, as desired. Meanwhile, (b) is obvious.

Next, we show, if $A\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}_{C}B$ denotes a
distance of $\geq n^{*}$ (so, $A$ and $B$ are freely amalgamated over $C$;
note that this amalgamation is not unique), it implies forking-independence.
We first show it implies dividing-independence: let $I=\\{B_{i}\\}_{i<\omega}$
with $B_{0}=B$ be a $C$-indiscernible sequence. Assign distances on $A\cup I$
to give $AB_{i}$ the same quantifier-free type as $AB$, and so the assignment
agrees with the actual one on $I$. It suffices to show this satisfies (1) and
(2). If $b\in B_{i}\backslash C$ and $a\in A\backslash C$, then if there is a
chain of distances of length $\leq n^{*}$ in $A\cup I$ going through $C$
between $a$ and $b$, then by breaking this chain up into parts in $A$ and
parts in $I$, and replacing the parts in $I$ with parts in $B_{i}$, there is a
chain of distances of total length at least as short going in the same
direction in $A\cup B_{i}$ through $C$. So the distance between $a$ and $b$ in
our chosen assignment is the length and direction of the chain of least total
length between $a$ and $b$ in $A\cup I$ going through $C$, using the actual
assignments on $A$ and $I$. For the other pairs $a\in A\backslash C$ and $b\in
I\backslash C$, a distance of length $n^{*}$ is chosen. But in constructing
the free amalgam, we showed that an arbitrary choice of direction for
distances of length $n^{*}$ (though there will only be a choice when $n$ is
even) is allowed for pairs with no path of length $\leq n^{*}$ going through
the base. So our chosen assignment is one instance of the construction of the
free amalgam of $A$ and $I$ over $C$, so in fact satisfies (1) and (2).

It remains to show right-extension for $\mathop{\mathchoice{\displaystyle\kern
5.71527pt\hbox to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}$, which will hold
if it is transitive, that is for $C\subseteq A$ and $C\subseteq B\subseteq D$,
$A\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}_{C}B$ and
$A\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}_{B}D$ implies
$A\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}_{C}D$. Suppose
that $a\in A\backslash C$, $d\in D\backslash C$ and $a$ and $d$ have a
distance $<n^{*}$, say, going from $a$ to $d$. Then there is, as above, a
chain of distances going from, say $a$ to $b\in B$ to $d$, of the same total
length. There is also a chain going from $a$ to $c\in C$ to $d$ of the same
total length as the distance between $a$ and $d$, because that distance is
also $<n^{*}$, so following that with the distance from $d\in D\subseteq B$ to
$b\in B$, we get a chain going through $C$ of the same total length as the
distance from $a$ to $b$, as desired.

Now let $\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}^{0}=\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}^{a}$,
$\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}^{i}$ denote a
distance of $\mathrm{min}(2^{i},n^{*})$ over the base. Exactly as in Example
3.1, we can then show that $\mathop{\mathchoice{\displaystyle\kern
5.71527pt\hbox to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}^{\eth^{k}}=\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}^{a}$ when
$2^{k+1}\geq n$.

######  Example 3.9.

(Model companion of undirected graphs without odd cycles of length $\leq n$,
for $n$ odd).

In [35], Shelah shows that the theory $T_{n}$ of undirected graphs without odd
cycles of length $\leq n$, for $n$ odd, has a model companion and is strictly
$\mathrm{NSOP}_{n+1}$. (This theory is further developed in [8].) Again, this
theory has quantifier elimination in the language with binary relations for
paths of length $k$ ([35]). Instead of directed distances in the previous
example, we now have the minimal length of a path between two vertices, an
undirected distance which will be $\leq n^{*}=\lceil\frac{n}{2}\rceil$. A
similar analysis to example 3.8 will hold in this theory. Note, however, that
because it is never true that $n=2^{k}$, $T_{n}$ in this case cannot be used
to witness that there are $\mathrm{SOP}_{2^{k}}$ theories where
$\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}^{\eth^{k}}$ is
symmetric.

##  4\. Bounds for symmetry and transitivity

We now show that $\mathrm{SOP}_{2^{k+1}+1}$ is required for
$\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}^{\eth^{k}}$ to be
symmetric. (See Theorem 6.2 of [30] for a related result on
$\mathrm{NSOP}_{4}$.) From this and the previous section will follow the
second clause of this theorem:

######  Theorem 4.1.

Assume $\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}^{\eth^{n}}$ is
symmetric for $n\geq 1$. Then $T$ is $\mathrm{NSOP}_{2^{n+1}+1}$. Thus
$2^{n+1}+1$ is the least $k$ so that every theory where
$\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}^{\eth^{n}}$ is
symmetric is $\mathrm{NSOP}_{k}$.

We state the construction; fix a Skolemization of $T$. Suppose $T$ is
$\mathrm{SOP}_{2^{n+1}+1}$; we show $\mathop{\mathchoice{\displaystyle\kern
5.71527pt\hbox to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}^{\eth^{n}}$ is
asymmetric. Let $R(x,y)$ witness this; then there is an indiscernible sequence
$\\{c^{*}_{i}\\}_{i\in 3\mathbb{Z}}$ so that $\models R(c_{i},c_{j})$ for
$i<j$, but there are no $(2^{n+1}+1)$-cycles. Let
$M=\mathrm{dcl}_{\mathrm{Sk}}(\\{c^{*}_{i}\\}_{i\in\mathbb{Z}}\cup\\{c^{*}_{2\mathbb{Z}+i}\\}_{i\in\mathbb{Z}})$,
and let $c_{i}=c^{*}_{\mathbb{Z}+i}$ for $i\in\mathbb{Z}$. For $k\geq 1$, let
$R_{k}(x,y)=:\exists x_{0}\ldots
x_{n-2}R(x,x_{0})\wedge\bigwedge^{n-3}_{i=0}R(x_{i},x_{i+1})\wedge
R(x_{n-2},y)$ (so $R_{1}(x,y)=:R(x,y)$ and $R_{2}(x,y)=:\exists
x_{0}R(x,x_{0})\wedge R(x_{0},y)$. We find instances of $k$-$\eth$-dividing:

######  Lemma 4.2.

Let $0\leq k\leq n$. Then

$R^{k}(y_{0},\ldots,y_{2^{k}-1},c_{0},\ldots,c_{2^{k}})=:\bigwedge^{2^{k}-1}_{i=0}R_{2^{n-k}}(c_{i},y_{i})\wedge
R_{2^{n-k}}(y_{i},c_{i+1})$

$k$-$\eth$-divides (and therefore $k$-$\eth$-forks) over $M$.

###### Proof.

By induction on $k$. For $k=0$, we show that $R_{2^{n}}(c_{0},y)\wedge
R_{2^{n}}(y,c_{1})$ divides over $M$, specifically by
$\\{c_{2i}c_{2i+1}\\}_{i<\omega}$. That is, $\\{R_{2^{n}}(c_{2i},y)\wedge
R_{2^{n}}(y,c_{2i+1})\\}_{i<\omega}$ is inconsistent; suppose it is
consistent, realized by $c$. Then $\models R_{2^{n}}(c,c_{1})\wedge
R(c_{1},c_{2})\wedge R_{2^{n}}(c_{2},c)$. So there is a $(2^{n+1}+1)$-cycle, a
contradiction.

Now suppose the statement holds for $0\leq k\leq n-1$; we prove it is true for
$k+1$. Let $\\{c^{i}_{j}\\}^{i<\omega}_{0\leq j\leq 2^{k+1}}$ be a sequence
with $c^{0}_{j}=c_{j}$ so that
$\\{R^{k+1}(y_{0},\ldots,y_{2^{k+1}-1},c^{i}_{0},\ldots,c^{i}_{2^{k+1}})\\}_{i<\omega}$
is realized by $c^{\prime}_{0},\ldots,c^{\prime}_{2^{k+1}-1}$; by the
definition of $(k+1)$-$\eth$-dividing, it suffices to show that
$\\{c^{i}_{j}\\}^{i<\omega}_{0\leq j\leq 2^{k+1}}$ is not an
$\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}^{\eth^{k}}$-Morley sequence over $M$. For $0\leq i\leq 2^{k}-1$,
in particular

$\models R_{2^{n-(k+1)}}(c_{2i}^{1},c^{\prime}_{2i})\wedge
R_{2^{n-(k+1)}}(c^{\prime}_{2i},c^{0}_{2i+1})\wedge
R_{2^{n-(k+1)}}(c^{0}_{2i+1},c^{\prime}_{2i+1})\wedge
R_{2^{n-(k+1)}}(c^{\prime}_{2i+1},c^{1}_{2(i+1)})$

It follows that $\models R_{2^{n-k}}(c^{1}_{2i},c^{0}_{2i+1})\wedge
R_{2^{n-k}}(c^{0}_{2i+1},c^{1}_{2(i+1)})$ for $0\leq i\leq 2^{k}-1$.
Therefore,

$R^{k}(y_{0},\ldots,y_{2^{k}-1},c_{0}^{1},\ldots,c^{1}_{2i},\ldots,c^{1}_{2^{k+1}})\in\mathrm{tp}(c^{0}_{1}\ldots
c^{0}_{2i+1}\ldots c^{0}_{2^{k+1}-1}/Mc_{0}^{1}\ldots c^{1}_{2i}\ldots
c^{1}_{2^{k+1}})$

Because $c^{1}_{0}\ldots c^{1}_{2i}\ldots
c^{1}_{2^{k+1}}\equiv_{M}c^{0}_{0}\ldots c^{0}_{2i}\ldots
c^{0}_{2^{k+1}}=c_{0}\ldots c_{2i}\ldots c_{2^{k+1}}\equiv_{M}c_{0}\ldots
c_{2^{k}}$, and $R^{k}(y_{0},\ldots,y_{2^{k}-1},c_{0},\ldots,c_{2^{k}})$
$k$-$\eth$-divides over $M$ by the induction hypothesis,
$R^{k}(y_{0},\ldots,y_{2^{k}-1},c_{0}^{1},\ldots,c^{1}_{2i},\ldots,c^{1}_{2^{k+1}})$
$k$-$\eth$-divides over $M$, so

$c^{0}_{1}\ldots c^{0}_{2i+1}\ldots
c^{0}_{2^{k+1}-1}\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mathchar 12854\relax$\kern 8.00134pt\hss}\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mathchar 12854\relax$\kern
8.00134pt\hss}\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mathchar 12854\relax$\kern
3.92064pt\hss}\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mathchar 12854\relax$\kern
2.00034pt\hss}\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower
0.96873pt\hbox to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M}^{\eth^{k}}c_{0}^{1},\ldots c^{1}_{2i}\ldots c^{1}_{2^{k+1}}$

and therefore,

$c^{0}_{0}\ldots c^{0}_{2^{k+1}}\mathop{\mathchoice{\displaystyle\kern
5.71527pt\hbox to0.0pt{\hss$\displaystyle\mathchar 12854\relax$\kern
8.00134pt\hss}\hbox to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mathchar 12854\relax$\kern
8.00134pt\hss}\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mathchar 12854\relax$\kern
3.92064pt\hss}\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mathchar 12854\relax$\kern
2.00034pt\hss}\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower
0.96873pt\hbox to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M}^{\eth^{k}}c_{0}^{1}\ldots c^{1}_{2^{k+1}}$

So $\\{c^{i}_{j}\\}^{i<\omega}_{0\leq j\leq 2^{k+1}}$ is not an
$\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}^{\eth^{k}}$-Morley sequence over $M$.

∎

It follows from the case $k=n$ of Lemma 4.2 and an automorphism that

$\\{c_{2i-1}\\}_{-2^{n-1}<i\leq 2^{n-1}}\mathop{\mathchoice{\displaystyle\kern
5.71527pt\hbox to0.0pt{\hss$\displaystyle\mathchar 12854\relax$\kern
8.00134pt\hss}\hbox to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mathchar 12854\relax$\kern
8.00134pt\hss}\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mathchar 12854\relax$\kern
3.92064pt\hss}\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mathchar 12854\relax$\kern
2.00034pt\hss}\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower
0.96873pt\hbox to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}^{\eth^{n}}_{M}\\{c_{2i}\\}_{-2^{n-1}\leq i\leq 2^{n-1}}$

So we have obtained an instance of $n$-$\eth$ independence. When $n=1$, so
$c_{-1}c_{1}\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mathchar 12854\relax$\kern 8.00134pt\hss}\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mathchar 12854\relax$\kern
8.00134pt\hss}\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mathchar 12854\relax$\kern
3.92064pt\hss}\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mathchar 12854\relax$\kern
2.00034pt\hss}\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower
0.96873pt\hbox to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}^{\eth^{1}}_{M}c_{-2}c_{0}c_{2}$, this is one direction of the
asymmetry: $c_{-2}c_{0}c_{2}\mathop{\mathchoice{\displaystyle\kern
5.71527pt\hbox to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}^{\eth^{1}}_{M}c_{-1}c_{1}$. To show this, we extend
$\\{c_{i}\\}_{i\in\mathbb{Z}}$ to an $M$-indiscernible sequence
$\\{c_{i}\\}_{i\in\mathbb{Q}}$. Then by construction,
$\\{c_{-(1+i)}c_{1+i}\\}_{i\in[0,1)}$ (note $c_{-(1+0)}c_{1+0}=c_{-1}c_{1}$)
is a finitely satisfiable Morley sequence over $M$, indiscernible over
$Mc_{-2}c_{0}c_{2}$. So
$c_{-2}c_{0}c_{2}\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}^{\eth^{1}}_{M}c_{-1}c_{1}$ follows from the following fact, which
is immediate from Fact 6.1 of [30] (this is just a standard application of
left extension for finite satisfiability, as in the proof of Proposition 2.2):

######  Fact 4.3.

Let $\\{b_{i}\\}_{i<\omega}$ be a finitely satisfiable Morley sequence over
$M$ with $b_{0}=b$ so that $\\{\varphi(x,b_{i})\\}_{i<\omega}$ is consistent.
Then $\varphi(x,b)$ does not $1$-$\eth$-fork over $M$.

This concludes the $\mathrm{NSOP}_{5}$ case. When $n\geq 2$, we may not be
able to obtain the desired finitely satisfiable Morley sequence. However,
unlike the case where $n=1$, we would not need anything stronger than an
$\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}^{\eth^{n-1}}$-Morley sequence to show that a formula does not
$n$-$\eth$-fork over $M$, as opposed to just $n$-$\eth$-dividing over $M$,
because $n$-$\eth$-forking already coincides with $n$-$\eth$-dividing
(Proposition 2.2). Still, we do not show that $\\{c_{2i}\\}_{-2^{n}\leq i\leq
2^{n}}\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}^{\eth^{n}}_{M}\\{c_{2i-1}\\}_{-2^{n}<i\leq 2^{n}}$ using an
explicit $\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}^{\eth^{n-1}}$-Morley sequence. Rather, let $m\leq 2^{n-1}$ be
least such that

$\\{c_{2i-1}\\}_{-m<i\leq m}\mathop{\mathchoice{\displaystyle\kern
5.71527pt\hbox to0.0pt{\hss$\displaystyle\mathchar 12854\relax$\kern
8.00134pt\hss}\hbox to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mathchar 12854\relax$\kern
8.00134pt\hss}\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mathchar 12854\relax$\kern
3.92064pt\hss}\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mathchar 12854\relax$\kern
2.00034pt\hss}\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower
0.96873pt\hbox to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}^{\eth^{n}}_{M}\\{c_{2i}\\}_{-m\leq i\leq m}$

Then $m>0$. Let $\bar{a}=\\{c_{2i}\\}_{-m<i<m}$,
$\bar{b}=\\{c_{2i-1}\\}_{-m<i\leq m}$, and $\bar{c}=c_{-2m}c_{2m}$. Then
$\bar{b}\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mathchar 12854\relax$\kern 8.00134pt\hss}\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mathchar 12854\relax$\kern
8.00134pt\hss}\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mathchar 12854\relax$\kern
3.92064pt\hss}\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mathchar 12854\relax$\kern
2.00034pt\hss}\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower
0.96873pt\hbox to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M}^{\eth^{n}}\bar{a}\bar{c}$,
$\bar{a}\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M}^{\eth^{n}}\bar{b}$ by minimality of $m$ and the fact that
$\overline{a}\overline{b}\equiv_{M}\\{c_{2i-1}\\}_{-(m-1)<i\leq
m-1}\\{c_{2i}\\}_{-(m-1)\leq i\leq m-1}$, and $\mathrm{tp}(ab/cM)$ is finitely
satisfiable over $M$ by construction. To show asymmetry of
$\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}_{M}^{\eth^{n}}$,
it remains to show that $\bar{a}\bar{c}\mathop{\mathchoice{\displaystyle\kern
5.71527pt\hbox to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M}^{\eth^{n}}\bar{b}$. We use the proof technique from Claim 6.2
of [29]. Let
$\varphi(\bar{x},\bar{z},\bar{b})\in\mathrm{tp}(\bar{a}\bar{c}/M\bar{b})$; we
show it does not $n$-$\eth$-fork over $M$, for which it suffices that it not
$n$-$\eth$-divide over $M$. More explicitly,
$\models\varphi(\bar{a},\bar{c},\bar{b})$, so
$\models\varphi(\bar{a},\bar{y},\bar{b})\in\mathrm{tp}(\bar{c}/M\bar{a}\bar{b})$.
By finite satisfiability, there is some $\bar{m}\in M$ so that
$\models\varphi(\bar{a},\bar{m},\bar{b})$. So
$\varphi(\bar{x},\bar{m},\bar{b})\in\mathrm{tp}(\bar{a}/M\bar{b})$. Because
$\bar{a}\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M}^{\eth^{n}}\bar{b}$, there is then some
$\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}^{\eth^{n-1}}$-Morley sequence $\\{\bar{b}_{i}\\}_{i<\omega}$ over
$M$ with $\bar{b}_{0}=\bar{b}$ so that
$\\{\varphi(\bar{x},m,\bar{b}_{i})\\}_{i<\omega}$ is consistent. A fortiori,
$\\{\varphi(\bar{x},\bar{z},\bar{b}_{i})\\}_{i<\omega}$ is consistent. So
$\varphi(\bar{x},\bar{z},\bar{b})$ does not $n$-$\eth$-divide over $M$, and as
$\varphi(\bar{x},\bar{z},\bar{b})\in\mathrm{tp}(\bar{a}\bar{c}/M\bar{b})$ was
arbitrary, $\bar{a}\bar{c}\mathop{\mathchoice{\displaystyle\kern
5.71527pt\hbox to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M}^{\eth^{n}}\bar{b}$. This concludes the proof of Theorem 4.1.

In all of the examples of the previous section,
$\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}^{\eth^{n}}=\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}^{a}$ has the
following properties:

Right transitivity: $a\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M}^{\eth^{n}}M^{\prime}$ and
$a\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M^{\prime}}^{\eth^{n}}b$ implies
$a\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}_{M}^{\eth^{n}}b$

Left transitivity:

$M^{\prime}\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}_{M}^{\eth^{n}}b$
and $a\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M^{\prime}}^{\eth^{n}}b$ implies
$a\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}_{M}^{\eth^{n}}b$

when $M\prec M^{\prime}$ are models. We show:

######  Theorem 4.4.

Assume $\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}^{\eth^{n}}$ is
left or right transitive for $n\geq 1$. Then $T$ is
$\mathrm{NSOP}_{2^{n+1}+1}$. Thus $2^{n+1}+1$ is the least $k$ so that every
theory where $\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}^{\eth^{n}}$ is
right transitive is $\mathrm{NSOP}_{k}$, and similarly for left transitivity.

The proof is easier, as to show, say, right transitivity fails, we produce
$a,b,M_{0}\prec M_{1}\prec\ldots\prec M_{k}$ so that
$a\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M_{i}}^{\eth^{n}}M_{i+1}$ for $0\leq i\leq k$,
$a\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M_{k}}^{\eth^{n}}b$, but $a\mathop{\mathchoice{\displaystyle\kern
5.71527pt\hbox to0.0pt{\hss$\displaystyle\mathchar 12854\relax$\kern
8.00134pt\hss}\hbox to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mathchar 12854\relax$\kern
8.00134pt\hss}\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mathchar 12854\relax$\kern
3.92064pt\hss}\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mathchar 12854\relax$\kern
2.00034pt\hss}\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower
0.96873pt\hbox to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M_{0}}^{\eth^{n}}b$; the dependency
$a\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mathchar 12854\relax$\kern 8.00134pt\hss}\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mathchar 12854\relax$\kern
8.00134pt\hss}\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mathchar 12854\relax$\kern
3.92064pt\hss}\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mathchar 12854\relax$\kern
2.00034pt\hss}\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower
0.96873pt\hbox to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M_{0}}^{\eth^{n}}b$ will be a slight modification of the above to
produce models, but the instances of independence,
$a\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M_{i}}^{\eth^{n}}M_{i+1}$, will arise directly from the
construction, unlike in the proof for symmetry. Again, assume $R(x,y)$ gives
an instance of $\mathrm{SOP}_{2^{n+1}+1}$. Choose a Skolemization of $T$ and a
$T^{\mathrm{Sk}}$-indiscernible sequence
$\\{c^{*}_{i}\\}_{\mathbb{Z}+\mathbb{Z}\times\mathbb{Z}+\mathbb{Z}}$ so that
$\models R(c_{i}^{*},c_{j}^{*})$ for
$i<j<\mathbb{Z}+\mathbb{Z}\times\mathbb{Z}+\mathbb{Z}$. Let
$M_{0}=\mathrm{dcl}_{\mathrm{Sk}}(\\{c^{*}_{i}\\}_{i\in\mathbb{Z}}\cup\\{c^{*}_{\mathbb{Z}+\mathbb{Z}\times\mathbb{Z}+i}\\}_{i\in\mathbb{Z}})$.
For $i\in\mathbb{Z}\times\mathbb{Z}$, let
$c^{\prime}_{i}=c^{\prime}_{\mathbb{Z}+i}$. Now $\mathbb{Z}\times\mathbb{Z}$
as a set of ordered pairs, ordered lexicographically, and define
$c_{i}=\\{c_{(i,j)}\\}_{j\in\mathbb{Z}}$. Again, it follows from Lemma 4.2
that

$\\{c_{2i-1}\\}_{-2^{n-1}<i\leq 2^{n-1}}\mathop{\mathchoice{\displaystyle\kern
5.71527pt\hbox to0.0pt{\hss$\displaystyle\mathchar 12854\relax$\kern
8.00134pt\hss}\hbox to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mathchar 12854\relax$\kern
8.00134pt\hss}\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mathchar 12854\relax$\kern
3.92064pt\hss}\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mathchar 12854\relax$\kern
2.00034pt\hss}\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower
0.96873pt\hbox to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}^{\eth^{n}}_{M_{0}}\\{c_{2i}\\}_{-2^{n-1}\leq i\leq 2^{n-1}}$

To make the notation easier, let $a_{i}=c_{2(-2^{n-1}+1+i)-1}$ for $0\leq
i<2^{n}$; in other words, $a_{i}$ is the $i$th term of
$\\{c_{2i-1}\\}_{-2^{n-1}<i\leq 2^{n-1}}$. Let $b_{i}=c_{2(-2^{n-1}+i)}$ for
$0\leq i\leq 2^{n}$. Let $a=\\{a_{i}\\}_{0\leq i<2^{n}}$ and
$b=\\{b_{i}\\}_{0\leq i\leq 2^{n}}$. Then
$a\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mathchar 12854\relax$\kern 8.00134pt\hss}\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mathchar 12854\relax$\kern
8.00134pt\hss}\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mathchar 12854\relax$\kern
3.92064pt\hss}\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mathchar 12854\relax$\kern
2.00034pt\hss}\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower
0.96873pt\hbox to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M_{0}}^{\eth^{n}}b$. For the right transitivity case, it suffices
to find $M_{0}\prec M_{1}\prec\ldots\prec M_{k}$ so that
$a\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M_{i}}^{\eth^{n}}M_{i+1}$ for $0\leq i\leq k=2^{n}+1$,
$a\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M_{k}}^{\eth^{n}}b$, despite having shown
$a\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mathchar 12854\relax$\kern 8.00134pt\hss}\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mathchar 12854\relax$\kern
8.00134pt\hss}\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mathchar 12854\relax$\kern
3.92064pt\hss}\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mathchar 12854\relax$\kern
2.00034pt\hss}\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower
0.96873pt\hbox to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M_{0}}^{\eth^{n}}b$. For $0<i\leq 2^{n}+1$, let
$M_{i}=\mathrm{dcl}_{\mathrm{Sk}}(\\{b_{0}\ldots b_{i-1}\\})$. We show that
for $0<i<2^{n}+1$, $a\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M_{i}}^{\eth^{n}}M_{i+1}$, and
$a\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M_{k}}^{\eth^{n}}b$. This follows directly from unwinding
definitions and applying to
$\\{c_{i}^{*}\\}_{i\in\mathbb{Z}+\mathbb{Z}\times\mathbb{Z}+\mathbb{Z}}$ the
following claim:

######  Claim 4.5.

Let $\\{e_{i}\\}_{i\in I}$ be an indiscernible sequence in $T^{\mathrm{Sk}}$,
where $I$ is a linear order. Let $J\subset I$ be a set with no greatest
element. Let $I_{1},I_{2}\subseteq I$ be such that every element of $I_{2}$ is
above every element of $J$, and no element of $I_{1}$ is between any two
elements of $I_{2}$. Let
$e_{I_{2}}=\mathrm{dcl}_{\mathrm{Sk}}(\\{e_{s}\\}_{s\in J\cup I_{2}})$,
$e_{J}=\mathrm{dcl}_{\mathrm{Sk}}(\\{e_{s}\\}_{s\in J})$, and let
$e_{I_{1}}=\\{e_{s}\\}_{s\in I}$. Then
$e_{I_{1}}\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{e_{J}}^{\eth^{n}}e_{I_{2}}$ (in $T$).

###### Proof.

We may assume that any element of $I_{2}$ between two elements of $I_{2}$ is
itself in $I_{2}$. Let $I_{-}$ be the set of elements of $I$ below all of the
elements of $I_{2}$, and $I_{+}$ the set of elements of $I$ above all of the
elements of $I_{2}$. Extend $\\{e_{i}\\}_{i\in I}$ to $\\{e_{i}\\}_{i\in
I_{-}+\omega\times I_{2}+I_{+}}$ (so that $e_{I_{2}}=\\{e_{s}\\}_{s\in
J\cup\\{0\\}\times I_{2}}$) so that it is still indiscernible in
$T^{\mathrm{Sk}}$. For $i<\omega$, let
$e_{I_{2}}^{i}=\mathrm{dcl}_{\mathrm{Sk}}(\\{e_{s}\\}_{s\in J\cup\\{i\\}\times
I_{2}})$. Then $\\{e^{i}_{I_{2}}\\}_{i<\omega}$ is a finitely satisfiable
Morley sequence over $e_{J}$ with $e_{I_{2}}^{0}=e_{I_{2}}$, because every
element of $I_{2}$ is above every element of $J$ and $J$ has no greatest
element. Moreover, because no element of $I_{1}$ is in between any two
elements of $I_{2}$, $\\{e^{i}_{I_{2}}\\}_{i<\omega}$ is indiscernible over
$e_{J}e_{I_{1}}$. So $e_{I_{1}}\mathop{\mathchoice{\displaystyle\kern
5.71527pt\hbox to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{e_{J}}^{\eth^{n}}e_{I_{2}}$ by Fact 4.3. ∎

This completes the case of right transitivity. For left transitivity, we must
find $M_{0}=M^{0}\prec M^{1}\prec\ldots\prec M^{k}$ so that for $0\leq i\leq
2^{n}$, $M^{i+1}\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M^{i}}^{n^{\eth}}b$, and $a\mathop{\mathchoice{\displaystyle\kern
5.71527pt\hbox to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M^{k}}^{\eth^{n}}b$, despite having shown
$a\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mathchar 12854\relax$\kern 8.00134pt\hss}\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mathchar 12854\relax$\kern
8.00134pt\hss}\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mathchar 12854\relax$\kern
3.92064pt\hss}\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mathchar 12854\relax$\kern
2.00034pt\hss}\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower
0.96873pt\hbox to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern
1.42882pt}}_{M_{0}}^{\eth^{n}}b$. For $0<i\leq 2^{n}$, let
$M_{i}=\mathrm{dcl}_{\mathrm{Sk}}(\\{a_{0}\ldots a_{i-1}\\})$. Then for $0\leq
i\leq 2^{n}$, $M^{i+1}\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}_{M^{i}}^{u}b$,
and $a\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}_{M^{k}}^{u}b$.
This completes the case of left transitivity and thus the proof of Theorem
4.4.

We conclude by asking whether the converse holds, giving us a theory of
independence for $\mathrm{NSOP}_{2^{n+1}+1}$ theories:

######  Question 4.6.

Does $\mathrm{NSOP}_{2^{n+1}+1}$ imply symmetry of
$\mathop{\mathchoice{\displaystyle\kern 5.71527pt\hbox
to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}^{\eth^{n}}$? Does
it imply transitivity of $\mathop{\mathchoice{\displaystyle\kern
5.71527pt\hbox to0.0pt{\hss$\displaystyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\displaystyle\smile$\hss}\kern 5.71527pt}{\textstyle\kern
5.71527pt\hbox to0.0pt{\hss$\textstyle\mid$\hss}\lower 3.87495pt\hbox
to0.0pt{\hss$\textstyle\smile$\hss}\kern 5.71527pt}{\scriptstyle\kern
2.80048pt\hbox to0.0pt{\hss$\scriptstyle\mid$\hss}\lower 1.89871pt\hbox
to0.0pt{\hss$\scriptstyle\smile$\hss}\kern 2.80048pt}{\scriptscriptstyle\kern
1.42882pt\hbox to0.0pt{\hss$\scriptscriptstyle\mid$\hss}\lower 0.96873pt\hbox
to0.0pt{\hss$\scriptscriptstyle\smile$\hss}\kern 1.42882pt}}^{\eth^{n}}$?

## References

  * [1] JinHoo Ahn and Joonhee Kim.  $\mathrm{SOP}_{1}$, $\mathrm{SOP}_{2}$, and antichain tree property, preprint. Available at https://arxiv.org/abs/2003.10030. 2020.
  * [2] JinHoo Ahn, Joonhee Kim, and Junguk Lee.  On the antichain tree property, preprint. Available at https://arxiv.org/abs/2106.03779. 2021.
  * [3] Franceso Gallinaro Anna Dimitrieva and Mark Kamsma.  Dividing lines between positive theories, , preprint. Available at https://arxiv.org/pdf/2304.07557.pdf. 2023.
  * [4] Byunghan Kim Artem Chernikov and Nicholas Ramsey.  Transitivity, lowness and ranks in $\mathrm{NSOP}_{1}$ theories, , preprint. Available at https://arxiv.org/pdf/2006.10486.pdf. 2020,.
  * [5] Steven Buechler.  Pseudoprojective strongly minimal sets are locally projective.  The Journal of Symbolic Logic, 56(4):1184–1194, 1991.
  * [6] Enrique Casanovas and Byunghan Kim.  More on tree properties.  Fundamenta Mathematicae, 2019.
  * [7] Enrique Casanovas and Frank O. Wagner.  The free roots of the complete graph.  Proceedings of the American Mathematical Society, 132(5):1543–1548, 2004.
  * [8] Gregory Cherlin, Saharon Shelah, and Niandong Shi.  Universal graphs with forbidden subgraphs and algebraic closure.  Advances in Applied Mathematics, 22(4):454–491, 1999.
  * [9] Artem Chernikov and Nicholas Ramsey.  On model-theoretic tree properties.  Journal of Mathematical Logic, 16(2):1650009, 2016.
  * [10] Gabriel Conant.  An axiomatic approach to free amalgamation.  The Journal of Symbolic Logic, 82(2):648–671, 2017.
  * [11] Gabriel Conant and Caroline Terry.  Model theoretic properties of the urysohn sphere.  Annals of Pure and Applied Logic, 167(1):49–72, 2016.
  * [12] Jan Dobrowolski, Byunghan Kim, and Nicholas Ramsey.  Independence over arbitrary sets in nsop1 theories.  Annals of Pure and Applied Logic, 173(2):103058, 2022.
  * [13] Mirna Džamonja and Saharon Shelah.  On $\lhd^{*}$-maximality.  Annals of Pure and Applied Logic, 125(1-3):119–158, 2004.
  * [14] David Evans.  $\aleph_{0}$ -categorical structures with a predimension.  Annals of Pure and Applied Logic - APAL, 116:157–186, 08 2002.
  * [15] David E. Evans and Mark Wing Ho Wong.  Some remarks on generic structures.  Journal of Symbolic Logic, 74(4):1143 – 1154, 2009.
  * [16] Mark Kamsma.  Independence relations in abstract elementary categories.  Bulletin of Symbolic Logic, 28(4):531–531, 2022.
  * [17] Itay Kaplan and Nicholas Ramsey.  On kim-independence.  Journal of the European Mathematical Society, 22, 02 2017.
  * [18] Itay Kaplan and Nicholas Ramsey.  Transitivity of kim-independence.  Advances in Mathematics, 379:107573, 2021.
  * [19] Itay Kaplan, Nicholas Ramsey, and Saharon Shelah.  Local character of kim-independence.  Proceedings of the American Mathematical Society, 147, 07 2017.
  * [20] Itay Kaplan, Nicholas Ramsey, and Pierre Simon.  Generic stability independence and treeless theories, , preprint. Available at https://arxiv.org/pdf/2305.01296.pdf. 2023,.
  * [21] BYUNGHAN KIM.  Weak canonical bases in nsop 1 theories.  The Journal of Symbolic Logic, 86(3):1259–1281, 2021.
  * [22] Byunghan Kim and Hyeung-Joon Kim.  Notions around tree property 1.  Annals of Pure and Applied Logic, 162(9):698–709, 2011.
  * [23] Alex Kruckman and Nicholas Ramsey.  Generic expansion and Skolemization in $\mathrm{NSOP}_{1}$ theories.  Annals of Pure and Applied Logic, 169(8):755–774, aug 2018.
  * [24] Alex Kruckman, Minh Chieu Tran, and Erik Walsberg.  Interpolative fusions ii: Preservation results, preprint. Available at https://arxiv.org/abs/2206.08512. 2022.
  * [25] Maryanthe Malliaris and Saharon Shelah.  Cofinality spectrum problems in model theory, set theory and general topology.  Journal of the American Mathematical Society, 2016.
  * [26] Maryanthe Malliaris and Saharon Shelah.  Model-theoretic applications of cofinality spectrum problems.  Israel Journal of Mathematics, 220(2):947–1014, 2017.
  * [27] M.E. Malliaris.  Edge distribution and density in the characteristic sequence.  Annals of Pure and Applied Logic, 162(1):1–19, 2010.
  * [28] Scott Mutchnik.  Properties of independence in $\mathrm{NSOP}_{3}$ theories, manuscript. 2023.
  * [29] Scott Mutchnik.  On $\mathrm{NSOP}_{2}$ theories, preprint. Available at https://arxiv.org/abs/2206.08512. 2022.
  * [30] Scott Mutchnik.  Conant-independence in generalized free amalgamation theories, preprint. Available at https://arxiv.org/abs/2210.07527. 2022.
  * [31] Rehana Patel.  A family of countably universal graphs without $\mathrm{NSOP}_{4}$, preprint. 2006.
  * [32] Massoud Pourmahdian.  The stable forking conjecture and generic structures.  Archive for Mathematical Logic, 42(5):415–421, 2003.
  * [33] Nicholas Ramsey.  A note on nsop1 in one variable.  Journal of Symbolic Logic, 84(1):388–392, 2019.
  * [34] Saharon Shelah.  The universality spectrum: Consistency for more classes.  arXiv Mathematics e-prints, page math/9412229, December 1994.
  * [35] Saharon Shelah.  Toward classifying unstable theories.  Annals of Pure and Applied Logic, 80(3):229–255, 1996.
  * [36] Saharon Shelah.  On what I do not understand (and have something to say), model theory, preprint. Available at https://arxiv.org/abs/math/9910158. 1999.
  * [37] Saharon Shelah and Alexander Usvyatsov.  More on $\mathrm{SOP}_{1}$ and $\mathrm{SOP}_{2}$.  Annals of Pure and Applied Logic, 155(1):16–31, 2008.
  * [38] Pierre Simon.  On Amalgamation in NTP2 Theories and Generically Simple Generics.  Notre Dame Journal of Formal Logic, 61(2):233 – 243, 2020.