thlabel [name=notes,title=Notes throughout the document (red text),columns=1]

###### Proof.

]https://markkamsma.nl

###### Positive indiscernibles

###### Abstract.

We generalise various theorems for finding indiscernible trees and arrays to
positive logic: based on an existing modelling theorem for s-trees, we prove
modelling theorems for str-trees, str0-trees (the reduct of str-trees that
forgets the length comparison relation) and arrays. In doing so we prove
stronger versions for basing—rather than locally basing or EM-basing—str-trees
on s-trees and str0-trees on str-trees. As an application we show that a thick
positive theory has $k$-$\mathsf{TP_{2}}$ iff it has $2$-$\mathsf{TP_{2}}$.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
  3. 3 Generalised indiscernibles
  4. 4 The tree modelling theorems
  5. 5 The array modelling theorem
  6. 6 An application: $\mathsf{TP_{2}}$

##  1\. Introduction

As model theory in positive logic is maturing (see e.g. [BY03a, BY03b, PY18,
HK21, DK22, DGK23]) the need for the development of tools available to us in
full first-order logic becomes more and more necessary. An important notion in
model-theoretic arguments is that of indiscernibles. The most popular
occurrence of this is an indiscernible sequence, a sequence where any two
finite subsequences have the same type. The notion of indiscernibility can be
generalised by replacing the linear order that indexes an indiscernible
sequence by another indexing structure. In this paper we consider various
kinds of trees and an array as indexing structure. The main results are
modelling theorems for positive logic, which allow us to find indiscernibles
indexed by trees or arrays based on an arbitrary set of parameters indexed by
the same structure, while inheriting certain local structure.

As any full first-order theory can be seen as a (thick) positive theory (see
morleyisation), our main results are a direct generalisation of existing
results for full first-order logic [KKS14, TT12, Sco15]. The main difficulty
in generalising the proofs is that arguments using Ramsey’s theorem break
down, usually because we have to choose from infinitely many things at once.
The solution is to replace any such uses by the Erdős-Rado theorem. This makes
arguments more complicated, but we also get stronger statements (see str-
basing,str0-basing).

Main results. Our main results are the following three modelling theorems. The
thickness assumption is the mild assumption that being an indiscernible
sequence is type-definable (thickness).

######  Theorem 1.1 (str-modelling).

str-modelling Let $T$ be a thick theory. Let
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ be a tree of tuples of the same length
and let $C$ be any set of parameters, then there is a tree
$(b_{\eta})_{\eta\in\omega^{<\omega}}$ that is str-indiscernible over $C$ and
$\operatorname{EM}_{\textup{str}}$-based on
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ over $C$.

In the process of proving the above theorem we prove str-basing, which states
that given a tall enough s-indiscernible tree we can base an str-indiscernible
tree on it. This statement is interesting on its own because more information
is carried over when basing one tree on another, instead of EM-basing trees on
each other. Similarly, in proving the following theorem we prove that
str0-trees can be based on str-trees, see str0-basing.

######  Theorem 1.2 (str0-modelling).

str0-modelling Let $T$ be a thick theory. Let
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ be a tree of tuples of the same length
and let $C$ be any set of parameters, then there is a tree
$(b_{\eta})_{\eta\in\omega^{<\omega}}$ that is str0-indiscernible over $C$ and
$\operatorname{EM}_{{\textup{str}}_{0}}$-based on
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ over $C$.

######  Theorem 1.3 (array modelling).

array-modelling Let $T$ be a thick theory. Let $(a_{i,j})_{i,j<\omega}$ be an
array of tuples of the same length and let $C$ be any set of parameters, then
there is an array $(b_{i,j})_{i,j<\omega}$ that is array-indiscernible over
$C$ and $\operatorname{EM}_{{\textup{ar}}}$-based on $(a_{i,j})_{i,j<\omega}$
over $C$.

As an application of the array modelling theorem we generalise the following
from full first-order logic, completing a task from [DGK23, Remark 7.3].

######  Theorem 1.4.

k-tp2-iff-2-tp2 Let $T$ be a thick theory. If $\varphi(x,y)$ has
$k$-$\mathsf{TP_{2}}$ for some $k\geq 2$ then some conjunction
$\bigwedge_{i=1}^{n}\varphi(x,y_{i})$ has $2$-$\mathsf{TP_{2}}$. Hence, $T$
has $k$-$\mathsf{TP_{2}}$ for some $k\geq 2$ iff $T$ has
$2$-$\mathsf{TP_{2}}$.

##  2\. Preliminaries

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

######  Definition 2.1.

positive-syntax A _positive formula_ in a fixed language is one that is
obtained from combining atomic formulas using $\wedge$, $\vee$, $\top$, $\bot$
and $\exists$. An _h-inductive sentence_ is a sentence of the form $\forall
x(\varphi(x)\to\psi(x))$, where $\varphi(x)$ and $\psi(x)$ are positive
existential formulas. A _positive theory_ is a set of h-inductive sentences.

######  Remark 2.2.

morleyisation Full first-order logic can be studied as a special case of
positive logic. This is done through _Morleyisation_. For this we add a
relation symbol $R_{\varphi}(x)$ to our language for every full first-order
formula $\varphi(x)$, and have our theory (inductively) express that
$R_{\varphi}(x)$ and $\varphi(x)$ are equivalent. This way every first-order
formula is (equivalent to) a relation symbol, and thus in particular to a
positive formula.

We are interested in _existentially closed_ models. There are various
characterisations (see e.g. [DK22, Definition 2.5]), but we only need one.

######  Definition 2.3.

existentially-closed We call a model $M$ of a positive theory $T$
_existentially closed_ or _e.c._ if for every positive formula $\varphi(x)$,
whenever $M\not\models\varphi(a)$ then there is a positive formula $\psi(x)$
that implies $\neg\varphi(x)$ modulo $T$, i.e.
$T\models\neg\exists(\varphi(x)\wedge\psi(x))$, with $M\models\psi(a)$

A _positive type_ will be a set of positive formulas, over some parameter set
$B$, satisfied by some tuple $a$ in some e.c. model $M$:

$\operatorname{tp}(a/B)=\\{\varphi(x,b):\varphi\text{ is a positive formula,
}M\models\varphi(a,b)\text{ and }b\in B\\}.$

Throughout we will work in a monster model $\mathfrak{M}$. These can be
constructed for positive theories using the usual techniques. We let the
reader fix their favourite notion of smallness (e.g., fix a big enough
cardinal $\kappa$, and let “small” mean $<\kappa$). We recall the properties
of a monster model $\mathfrak{M}$:

  * •

_existentially closed_ , $\mathfrak{M}$ is an e.c. model;

  * •

_very homogeneous_ , for any small $a,b,C$ we have
$\operatorname{tp}(a/C)=\operatorname{tp}(b/C)$ iff there is
$f\in\operatorname{Aut}(\mathfrak{M}/C)$ with $f(a)=b$ (we will also write
$a\equiv_{C}b$);

  * •

_very saturated_ , any finitely satisfiable small set of formulas $\Sigma$
over $\mathfrak{M}$ is satisfiable in $\mathfrak{M}$.

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

######  Definition 2.4.

indiscernible-sequences A sequence $(a_{i})_{i\in I}$ (for some linear order
$I$) is $C$-indiscernible if for any $i_{1}<\ldots<i_{n}$ and
$j_{1}<\ldots<j_{n}$ in $I$ we have $a_{i_{1}}\ldots
a_{i_{n}}\equiv_{C}a_{j_{1}}\ldots a_{j_{n}}$.

######  Definition 2.5.

lascar-distance We write $\operatorname{d}_{C}(a,a^{\prime})\leq n$ if there
are $a=a_{0},a_{1},\ldots,a_{n}=a^{\prime}$ such that $a_{i}$ and $a_{i+1}$
are on a $C$-indiscernible sequence for all $0\leq i<n$, and we say that $a$
and $a^{\prime}$ have _Lascar distance_ at most $n$.

######  Definition 2.6 ([BY03c, Proposition 1.5]).

thickness A positive theory $T$ is called _thick_ if the following equivalent
conditions hold:

  1. (i)

being an indiscernible sequence is type-definable, i.e. there is a partial
type $\Theta((x_{i})_{i<\omega})$ such that
$\models\Theta((a_{i})_{i<\omega})$ iff $(a_{i})_{i<\omega}$ is an
indiscernible sequence;

  2. (ii)

the property $\operatorname{d}_{z}(x,y)\leq n$ is type-definable for all
$n<\omega$, i.e. for all $n<\omega$ there is a partial type
$\Sigma_{n}(x,y,z)$ such that $\models\Sigma_{n}(a,a^{\prime},C)$ iff
$\operatorname{d}_{C}(a,a^{\prime})\leq n$.

Any full first-order theory, seen as a positive theory (morleyisation), is
thick.

Conventions.

  * •

Any formula in the language of the monster model, will be a positive formula.
Similarly, “theory” and “type” will mean “positive theory” and “positive type”
respectively. We will also consider parameters in the monster indexed by some
structure in a different language $\mathcal{L}$, and we will consider
quantifier-free $\mathcal{L}$-formulas. This convention is only about the
monster, so these quantifier-free $\mathcal{L}$-formulas should be understood
in the sense of full first-order logic, and hence the $\neg$ symbol is allowed
in them.

  * •

Let $I$ be some indexing set and suppose that we have an $I$-indexed set of
variables $(x_{i})_{i\in I}$ or parameters $(a_{i})_{i\in I}$. Then for any
tuple $\bar{\eta}=(\eta_{1},\ldots,\eta_{n})$ in $I$ we write $x_{\bar{\eta}}$
and $a_{\bar{\eta}}$ for the tuples $(x_{\eta_{1}},\ldots,x_{\eta_{n}})$ and
$(a_{\eta_{1}},\ldots,a_{\eta_{n}})$ respectively.

##  3\. Generalised indiscernibles

The following idea stems from [She90, Definition VII.2.4].

######  Definition 3.1.

generalised-indiscernibles Let $\mathcal{L}$ be a language (which we always
assume to include the equality symbol), $I$ an $\mathcal{L}$-structure, and
$(a_{i})_{i\in I}$ an $I$-indexed set of parameters. We will refer to $I$ as
the _indexing structure_. Let $C$ be any parameter set. We say that
$(a_{i})_{i\in I}$ is _$I$ -indiscernible over $C$_ if for any two tuples
$\bar{\eta}$ and $\bar{\nu}$ in $I$ we have that

$\operatorname{qftp}_{\mathcal{L}}(\bar{\eta})=\operatorname{qftp}_{\mathcal{L}}(\bar{\nu})\implies
a_{\bar{\eta}}\equiv_{C}a_{\bar{\nu}},$

where $\operatorname{qftp}_{\mathcal{L}}(\bar{\eta})$ is the quantifier-free
$\mathcal{L}$-type of $\bar{\eta}$.

We emphasise once more that for the language $\mathcal{L}$ of the indexing
structures that we consider, the quantifier-free formulas should be understood
in the sense of full first-order logic, so they allow for the $\neg$ symbol.

######  Example 3.2.

indiscernible-sequence-as-generalised-indiscernible We let
$\mathcal{L}_{<}=\\{<\\}$ be the language with a single ordering symbol and
consider $\omega$ as an $\mathcal{L}_{<}$-structure with the usual ordering.
Then $(a_{i})_{i<\omega}$ being $\omega$-indiscernible over $C$ means
precisely that $(a_{i})_{i<\omega}$ is a $C$-indiscernible sequence.

######  Definition 3.3.

based-on Let $\mathcal{L}$ be some language and let $(a_{i})_{i\in I}$ and
$(b_{i})_{i\in I^{\prime}}$ be two sets of parameters indexed by
$\mathcal{L}$-structures $I$ and $I^{\prime}$ respectively. Let furthermore
$C$ be any parameter set. We say that _$(b_{i})_{i\in I^{\prime}}$ is
$\mathcal{L}$-based on $(a_{i})_{i\in I}$ over $C$_ if for any finite tuple
$\bar{\eta}$ in $I^{\prime}$ there is a tuple $\bar{\nu}$ in $I$ such that
$\operatorname{qftp}_{\mathcal{L}}(\bar{\nu})=\operatorname{qftp}_{\mathcal{L}}(\bar{\eta})$
and $b_{\bar{\eta}}\equiv_{C}a_{\bar{\nu}}$.

We say that _$(b_{i})_{i\in I^{\prime}}$ is locally $\mathcal{L}$-based on
$(a_{i})_{i\in I}$ over $C$_ if for any finite tuple $\bar{\eta}$ in
$I^{\prime}$ and any formula $\varphi(x_{\bar{\eta}})$ over $C$ such that
$\models\varphi(b_{\bar{\eta}})$ there is a tuple $\bar{\nu}$ in $I$ such that
$\operatorname{qftp}_{\mathcal{L}}(\bar{\nu})=\operatorname{qftp}_{\mathcal{L}}(\bar{\eta})$
and $\models\varphi(a_{\bar{\nu}})$.

We note the difference in terminology from [KKS14, Definition 3.8], where
“based on” is used for what we call “locally based on”, a distinction that is
further promoted in [Sco15, Definition 2.5]. The difference is important, see
based-on-implications-non-reversible. Another difference is that we call it
“(locally) $\mathcal{L}$-based on” instead of “(locally) $I$-based on”, this
is because we wish to compare sets of parameters indexed by different
structures in the same language.

######  Remark 3.4.

locally-based-on-alternative-formulation An alternative formulation to
$(b_{i})_{i\in I^{\prime}}$ being locally $\mathcal{L}$-based on
$(a_{i})_{i\in I}$ over $C$ is the following (see e.g. [Sco15, Definition
2.5]). For any finite set of formulas $\Phi$ with parameters in $C$ denote by
$\operatorname{tp}_{\Phi}(a/C)$ the restriction of $\operatorname{tp}(a/C)$ to
the formulas in $\Phi$. Then $(b_{i})_{i\in I^{\prime}}$ is locally
$\mathcal{L}$-based on $(a_{i})_{i\in I}$ over $C$ if for every finite set
$\Phi$ of formulas over $C$ and any finite tuple $\bar{\eta}$ in $I^{\prime}$
there is a finite tuple $\bar{\nu}$ in $I$ such that
$\operatorname{tp}_{\Phi}(b_{\bar{\eta}}/C)=\operatorname{tp}_{\Phi}(a_{\bar{\nu}}/C)$.
This is indeed an equivalent formulation, even in positive logic. It clearly
implies the formulation in based-on, so we prove the converse.

Let $\varphi\in\Phi$ be some formula and let
$\bar{\eta}^{\prime}\subseteq\bar{\eta}$ be a tuple whose length matches the
number of free variables in $\varphi$. Define
$\psi_{\varphi,\bar{\eta}^{\prime}}(x_{\bar{\eta}^{\prime}})$ as follows: if
$\models\varphi(b_{\bar{\eta}^{\prime}})$ then take
$\psi_{\varphi,\bar{\eta}^{\prime}}(x_{\bar{\eta}^{\prime}})$ to be
$\varphi(x_{\bar{\eta}^{\prime}})$, otherwise there is
$\chi((x_{i})_{i\in\bar{\eta}^{\prime}})$ that implies
$\neg\varphi(x_{\bar{\eta}^{\prime}})$ modulo $T$ such that
$\models\chi(b_{\bar{\eta}^{\prime}})$ and we take
$\psi_{\varphi,\bar{\eta}^{\prime}}(x_{\bar{\eta}^{\prime}})$ to be
$\chi(x_{\bar{\eta}^{\prime}})$. Now let

$\psi(x_{\bar{\eta}})=\bigwedge\\{\psi_{\varphi,\bar{\eta}^{\prime}}(x_{\bar{\eta}^{\prime}}):\varphi\in\Phi\text{
and }\bar{\eta}^{\prime}\subseteq\bar{\eta}\text{ matching the free variables
in }\varphi\\}.$

By construction $\models\psi(b_{\bar{\eta}})$ and so there is $\bar{\nu}$ in
$I$ such that $\models\psi(a_{\bar{\nu}})$, from which it follows that
$\operatorname{tp}_{\Phi}(b_{\bar{\eta}}/C)=\operatorname{tp}_{\Phi}(a_{\bar{\nu}}/C)$.

######  Example 3.5.

indiscernible-sequence-basing-on We recall the following fact for finding
indiscernible sequences [BY03b, Lemma 1.2]. Let $C$ be any parameter set and
let $\kappa$ be any cardinal, and set
$\lambda=\beth_{(2^{|T|+|C|+\kappa})^{+}}$. Then for any sequence
$(a_{i})_{i<\lambda}$ of $\kappa$-tuples there is a $C$-indiscernible sequence
$(b_{i})_{i<\omega}$ such that for all $n<\omega$ there are
$i_{1}<\ldots<i_{n}<\lambda$ with $b_{1}\ldots b_{n}\equiv_{C}a_{i_{1}}\ldots
a_{i_{n}}$.

With $C$, $\kappa$ and $\lambda$ as above, this is exactly saying that for any
sequence $(a_{i})_{i<\lambda}$ there is $C$-indiscernible $(b_{i})_{i<\omega}$
that is $\mathcal{L}_{<}$-based on $(a_{i})_{i<\lambda}$ over $C$.

######  Definition 3.6.

em-type Let $I$ be a structure in some language $\mathcal{L}$, let
$(a_{i})_{i\in I}$ be an $I$-indexed set of parameters and let $C$ be some set
of parameters. We write

$\displaystyle\operatorname{EM}_{\mathcal{L}}((a_{i})_{i\in
I}/C)=\\{\varphi(x_{\bar{\eta}})\ :\ $
$\displaystyle\varphi(x_{\bar{\eta}})\text{ is a formula with parameters in
}C\text{ and }$ $\displaystyle\models\varphi(a_{\bar{\nu}})\text{ for all
}\bar{\nu}\text{ with
}\operatorname{qftp}_{\mathcal{L}}(\bar{\nu})=\operatorname{qftp}_{\mathcal{L}}(\bar{\eta})\\}.$

for the _$\operatorname{EM}_{\mathcal{L}}$ -type of $(a_{i})_{i\in I}$ over
$C$_, which is a partial type in variables $(x_{i})_{i\in I}$. For
$\varphi(x_{\bar{\eta}})\in\operatorname{EM}_{\mathcal{L}}((a_{i})_{i\in
I}/C)$ we call $\operatorname{qftp}_{\mathcal{L}}(\bar{\eta})$ the _associated
quantifier-free $\mathcal{L}$-type_.

Let $I^{\prime}$ be a second $\mathcal{L}$-structure. We say that
_$(b_{i})_{i\in I^{\prime}}$ is $\operatorname{EM}_{\mathcal{L}}$-based on
$(a_{i})_{i\in I}$ over $C$_ if the following holds: for any
$\varphi\in\operatorname{EM}_{\mathcal{L}}((a_{i})_{i\in I}/C)$ with
associated quantifier-free $\mathcal{L}$-type $\Delta$, and any tuple
$\bar{\eta}$ in $I^{\prime}$ realising $\Delta$ we have
$\models\varphi(b_{\bar{\eta}})$.

It could be the case that $(b_{i})_{i\in I^{\prime}}$ is (locally)
$\mathcal{L}$-based or $\operatorname{EM}_{\mathcal{L}}$-based on
$(a_{i})_{i\in I}$ because $I$ does not realise a quantifier-free
$\mathcal{L}$-type that is realised in $I^{\prime}$, or vice versa. For
example, for any sequence $(a_{i})_{i<\omega}$ we have that $a_{0}$ (as a
singleton indexed set) is $\mathcal{L}_{<}$-based on $(a_{i})_{i<\omega}$. To
circumvent this issue we introduce the following definition, which will be
satisfied by all our indexing structures of interest.

######  Definition 3.7.

qftp-comparable Two $\mathcal{L}$-structures $I$ and $I^{\prime}$ are _qftp-
comparable_ if $I^{\prime}$ realises every quantifier-free $\mathcal{L}$-type
in finitely many variables that is realised in $I$, and vice versa.

######  Remark 3.8.

basing-transitive Let $I$, $I^{\prime}$ and $I^{\prime\prime}$ be pairwise
qftp-comparable $\mathcal{L}$-structures. Suppose that $(d_{i})_{i\in
I^{\prime\prime}}$ is $\mathcal{L}$-based on $(b_{i})_{i\in I^{\prime}}$ over
some parameter set $C$ and $(b_{i})_{i\in I^{\prime}}$ is $\mathcal{L}$-based
on $(a_{i})_{i\in I}$ over $C$. Then $(d_{i})_{i\in I^{\prime\prime}}$ is
$\mathcal{L}$-based on $(a_{i})_{i\in I}$ over $C$. We call this “transitivity
of $\mathcal{L}$-basing”, and similarly for locally $\mathcal{L}$-basing and
$\operatorname{EM}_{\mathcal{L}}$-basing.

######  Remark 3.9.

em-basing-alternative Let $I$ and $I^{\prime}$ be two qftp-comparable
$\mathcal{L}$-structures. Then we can equivalently be phrase the definition of
being $\operatorname{EM}_{\mathcal{L}}$-based as follows. Define

$\displaystyle\Sigma((x_{i})_{i\in I^{\prime}})=\\{\varphi(x_{\bar{\eta}})\ :\
$ $\displaystyle\bar{\eta}\text{ is a finite tuple in }I^{\prime}\text{ and}$
$\displaystyle\text{for some tuple }\bar{\nu}\text{ in }I\text{ with
}\operatorname{qftp}_{\mathcal{L}}(\bar{\nu})=\operatorname{qftp}_{\mathcal{L}}(\bar{\eta})$
$\displaystyle\text{we have
}\varphi(x_{\bar{\nu}})\in\operatorname{EM}_{\mathcal{L}}((a_{i})_{i\in
I}/C)\\}.$

Then $(b_{i})_{i\in I^{\prime}}$ is $\operatorname{EM}_{\mathcal{L}}$-based on
$(a_{i})_{i\in I}$ over $C$ iff $\Sigma((x_{i})_{i\in
I^{\prime}})\subseteq\operatorname{EM}_{\mathcal{L}}((b_{i})_{i\in
I^{\prime}}/C)$ iff $\models\Sigma((b_{i})_{i\in I^{\prime}})$. Note that when
$I=I^{\prime}$ then $\Sigma((x_{i})_{i\in
I})=\operatorname{EM}_{\mathcal{L}}((a_{i})_{i\in I}/C)$, so in that case we
get that $(b_{i})_{i\in I}$ is $\operatorname{EM}_{\mathcal{L}}$-based on
$(a_{i})_{i\in I}$ over $C$ iff $\operatorname{EM}_{\mathcal{L}}((a_{i})_{i\in
I}/C)\subseteq\operatorname{EM}_{\mathcal{L}}((b_{i})_{i\in I}/C)$ iff
$(b_{i})_{i\in I}\models\operatorname{EM}_{\mathcal{L}}((a_{i})_{i\in I}/C)$.

######  Proposition 3.10.

based-on-implies-locally-based-on-implies-em-based-on Let $(a_{i})_{i\in I}$
and $(b_{i})_{i\in I^{\prime}}$ be sets of parameters indexed by qftp-
comparable $\mathcal{L}$-structures $I$ and $I^{\prime}$ respectively. For any
parameter set $C$ we have that (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii) as
below:

  1. (i)

$(b_{i})_{i\in I^{\prime}}$ is $\mathcal{L}$-based on $(a_{i})_{i\in I}$ over
$C$,

  2. (ii)

$(b_{i})_{i\in I^{\prime}}$ is locally $\mathcal{L}$-based on $(a_{i})_{i\in
I}$ over $C$,

  3. (iii)

$(b_{i})_{i\in I^{\prime}}$ is $\operatorname{EM}_{\mathcal{L}}$-based on
$(a_{i})_{i\in I}$ over $C$.

###### Proof.

The implication (i) $\implies$ (ii) is clear (even without the assumption of
being qftp-comparable), we prove (ii) $\implies$ (iii). So let
$\varphi\in\operatorname{EM}_{\mathcal{L}}((a_{i})_{i\in I}/C)$ and let
$\Delta$ be the associated quantifier-free $\mathcal{L}$-type. Let
$\bar{\eta}$ be a tuple in $I^{\prime}$ satisfying $\Delta$, which exists by
qftp-comparability. Suppose for a contradiction that
$\not\models\varphi(b_{\bar{\eta}})$. Then there is $\psi(\bar{x})$ that
implies $\neg\varphi(\bar{x})$ modulo $T$ such that
$\models\psi(b_{\bar{\eta}})$. As $(b_{i})_{i\in I^{\prime}}$ is locally
$\mathcal{L}$-based on $(a_{i})_{i\in I}$ over $C$ there must then be
$\bar{\nu}$ with
$\operatorname{qftp}_{\mathcal{L}}(\bar{\nu})=\operatorname{qftp}_{\mathcal{L}}(\bar{\eta})$
such that $\models\psi(a_{\bar{\nu}})$. However, that means that
$\not\models\varphi(a_{\bar{\nu}})$, contradicting
$\varphi\in\operatorname{EM}_{\mathcal{L}}((a_{i})_{i\in I}/C)$. ∎

######  Example 3.11.

based-on-implications-non-reversible None of the implications in based-on-
implies-locally-based-on-implies-em-based-on are reversible. As an example we
will consider a language with countably many unary predicates
$(P_{n})_{n<\omega}$ and the structure $M=\omega\times\omega$ where $P_{n}$ is
interpreted as $\\{n\\}\times\omega$. Let $T$ be the positive theory of $M$
(i.e. all h-inductive sentences true in $M$) and let $T^{\prime}$ be the full
first-order theory of $M$. One straightforwardly verifies that $T^{\prime}$
has quantifier elimination and $T$ has positive quantifier elimination (i.e.
every positive formula is equivalent, modulo $T$, to a positive quantifier-
free formula).

Working in a (full first-order) monster model of $T^{\prime}$, we let
$(a_{i})_{i<\omega}$ be a sequence such that $\models P_{i}(a_{i})$ for all
$i<\omega$, and thus $\models\neg P_{j}(a_{i})$ for all $i\neq j$. We also let
$(b_{i})_{i<\omega}$ be a sequence such that $\models\neg P_{j}(b_{i})$ for
all $i,j<\omega$. Then $(b_{i})_{i<\omega}$ is locally $\mathcal{L}_{<}$-based
on $(a_{i})_{i<\omega}$ but it is not $\mathcal{L}_{<}$-based on
$(a_{i})_{i<\omega}$ (in both cases over $\emptyset$).

Next we work in a monster model (now in the positive sense) of $T$. We let
$(a_{i})_{i<\omega}$ be such that $\models P_{i+1}(a_{i})$ for all $i<\omega$,
so in particular $\not\models P_{0}(a_{i})$ for all $i<\omega$. We also let
$(b_{i})_{i<\omega}$ be such that $\models P_{0}(b_{i})$ for all $i<\omega$,
and so $\not\models P_{j}(b_{i})$ for all $i<\omega$ and $1\leq j<\omega$.
Then $(b_{i})_{i<\omega}$ is $\operatorname{EM}_{\mathcal{L}_{<}}$-based on
$(a_{i})_{i<\omega}$ but it is not locally $\mathcal{L}_{<}$-based on
$(a_{i})_{i<\omega}$ (in both cases over $\emptyset$).

Note that in the last case we really needed to consider an example in positive
logic. The key is that $\neg P_{0}(x)$ is not a positive formula and is thus
not in the $\operatorname{EM}_{\mathcal{L}_{<}}$-type. In fact, as is well
known, in full first-order logic we do have that (ii) and (iii) from based-on-
implies-locally-based-on-implies-em-based-on are equivalent (for qftp-
comparable structures). We include a proof for completeness’ sake, and to
point out the usage of negation.

Let $\bar{\eta}$ be any finite tuple in $I^{\prime}$ and let
$\varphi(x_{\bar{\eta}})$ be any formula over $C$ such that
$\models\varphi(b_{\bar{\eta}})$. Suppose for a contradiction that there is no
tuple $\bar{\nu}$ in $I$ with
$\operatorname{qftp}_{\mathcal{L}}(\bar{\nu})=\operatorname{qftp}_{\mathcal{L}}(\bar{\eta})$
such that $\models\varphi(a_{\bar{\nu}})$. Then we have that
$\models\neg\varphi(a_{\bar{\nu}})$ for all such $\bar{\nu}$. Now picking one
such $\bar{\nu}$, which exists by qftp-comparability, we get
$\neg\varphi(x_{\bar{\nu}})\in\operatorname{EM}_{\mathcal{L}}((a_{i})_{i\in
I}/C)$. This is a contradiction, because then we have
$\models\neg\varphi(b_{\bar{\eta}})$ as $(b_{i})_{i\in I^{\prime}}$ is
$\operatorname{EM}_{\mathcal{L}}$-based on $(a_{i})_{i\in I}$ over $C$.

######  Remark 3.12.

sequence-em-modelling In indiscernible-sequence-basing-on we saw that we can
base an indiscernible sequence on a sufficiently long sequence. In based-on-
implications-non-reversible we saw examples of indiscernible sequences that
are $\operatorname{EM}_{\mathcal{L}_{<}}$-based on sequences of length
$\omega$ (in both examples $(b_{i})_{i<\omega}$ is indiscernible). This can
always be done and illustrates the use of $\operatorname{EM}$-types.

That is, for any sequence $(a_{i})_{i<\omega}$ of tuples of the same length
and any parameter set $C$ there is a $C$-indiscernible sequence
$(b_{i})_{i<\omega}$ that is $\operatorname{EM}_{\mathcal{L}_{<}}$-based on
$(a_{i})_{i<\omega}$ over $C$. To see this we let $\lambda$ be the cardinal
from indiscernible-sequence-basing-on. Then we define

$\displaystyle\Sigma((x_{i})_{i<\lambda})=\\{\varphi(x_{i_{1}},\ldots,x_{i_{n}})\
:\ $
$\displaystyle\varphi(x_{1},\ldots,x_{n})\in\operatorname{EM}_{\mathcal{L}_{<}}((a_{i})_{i<\omega}/C)$
$\displaystyle\text{and }i_{1}<\ldots<i_{n}<\lambda\\},$

note that this is the same construction of $\Sigma$ as in em-basing-
alternative, just specialised to $\mathcal{L}_{<}$. Let
$(a^{\prime}_{i})_{i<\lambda}$ be any realisation of $\Sigma$, which exists by
compactness because every finite part of $\Sigma$ is realised by
$(a_{i})_{i<\omega}$. Then use indiscernible-sequence-basing-on to
$\mathcal{L}_{<}$-base a $C$-indiscernible sequence $(b_{i})_{i<\omega}$ on
$(a^{\prime}_{i})_{i<\omega}$. By based-on-implies-locally-based-on-implies-
em-based-on this means that $(b_{i})_{i<\omega}$ is in particular
$\operatorname{EM}_{\mathcal{L}_{<}}$-based on $(a^{\prime}_{i})_{i<\lambda}$
over $C$, which is in turn $\operatorname{EM}_{\mathcal{L}_{<}}$-based on
$(a_{i})_{i<\omega}$ over $C$ by construction. Since
$\operatorname{EM}$-basing is transitive, we conclude that
$(b_{i})_{i<\omega}$ is as required.

In the remainder of this section we provide tools to deal with carrying over
indiscernibility and $\operatorname{EM}$-types between indexing structures in
different languages. We refer to trees-examples for examples.

######  Definition 3.13 ([Sco21, Definitions 3.2 and 3.3]).

qftp-respecting Let $\mathcal{L}$ and $\mathcal{L}^{\prime}$ be languages and
$I$ and $I^{\prime}$ be structures in those respective languages. We call a
function $f:I\to I^{\prime}$ _qftp-respecting_ if for any two finite tuples
$\bar{\eta}$ and $\bar{\nu}$ in $I$ we have that
$\operatorname{qftp}_{\mathcal{L}}(\bar{\eta})=\operatorname{qftp}_{\mathcal{L}}(\bar{\nu})$
implies
$\operatorname{qftp}_{\mathcal{L}^{\prime}}(f(\bar{\eta}))=\operatorname{qftp}_{\mathcal{L}^{\prime}}(f(\bar{\nu}))$.

######  Lemma 3.14 (Re-indexing lemma).

reindexing-lemma Let $f:I\to I^{\prime}$ be a qftp-respecting function between
structures $I$ and $I^{\prime}$ in languages $\mathcal{L}$ and
$\mathcal{L}^{\prime}$ respectively. Let $C$ be any parameter set.

  1. (i)

Let $(a^{\prime}_{i})_{i\in I^{\prime}}$ and $(a_{i})_{i\in I}$ be such that
$a_{i}=a^{\prime}_{f(i)}$ for all $i\in I$. If $(a^{\prime}_{i})_{i\in
I^{\prime}}$ is $I^{\prime}$-indiscernible over $C$ then $(a_{i})_{i\in I}$ is
$I$-indiscernible over $C$.

  2. (ii)

Let $(a^{\prime}_{i})_{i\in I^{\prime}}$, $(b^{\prime}_{i})_{i\in
I^{\prime}}$, $(a_{i})_{i\in I}$ and $(b_{i})_{i\in I}$ be such that
$a_{i}=a^{\prime}_{f(i)}$ and $b_{i}=b^{\prime}_{f(i)}$ for all $i\in I$. If
$f$ is surjective and $(b_{i})_{i\in I}$ is
$\operatorname{EM}_{\mathcal{L}}$-based on $(a_{i})_{i\in I}$ over $C$ then
$(b^{\prime}_{i})_{i\in I^{\prime}}$ is
$\operatorname{EM}_{\mathcal{L}^{\prime}}$-based on $(a^{\prime}_{i})_{i\in
I^{\prime}}$ over $C$.

  3. (iii)

Suppose that there is $g:J\to I$, where $J$ is an
$\mathcal{L}^{\prime}$-structure, such that $fg$ is an
$\mathcal{L}^{\prime}$-embedding. Let $(a^{\prime}_{i})_{i\in I^{\prime}}$,
$(b_{i})_{i\in I}$, $(a_{i})_{i\in I}$ and $(b^{\prime}_{j})_{j\in J}$ be such
that $a_{i}=a^{\prime}_{f(i)}$ and $b^{\prime}_{j}=b_{g(j)}$ for all $i\in I$
and $j\in J$. If $(b_{i})_{i\in I}$ is $\operatorname{EM}_{\mathcal{L}}$-based
on $(a_{i})_{i\in I}$ over $C$ then $(b^{\prime}_{j})_{j\in J}$ is
$\operatorname{EM}_{\mathcal{L}^{\prime}}$-based on $(a^{\prime}_{i})_{i\in
I^{\prime}}$ over $C$.

###### Proof.

  1. (i)

Let $\bar{\eta}$ and $\bar{\nu}$ be tuples in $I$ such that
$\operatorname{qftp}_{\mathcal{L}}(\bar{\eta})=\operatorname{qftp}_{\mathcal{L}}(\bar{\nu})$
then
$\operatorname{qftp}_{\mathcal{L}^{\prime}}(f(\bar{\eta}))=\operatorname{qftp}_{\mathcal{L}^{\prime}}(f(\bar{\nu}))$
because $f$ is qftp-respecting. Hence, by $I^{\prime}$-indiscernibility of
$(a^{\prime}_{i})_{i\in I^{\prime}}$ we have that
$a_{\bar{\eta}}=a^{\prime}_{f(\bar{\eta})}\equiv_{C}a^{\prime}_{f(\bar{\nu})}=a_{\bar{\nu}}$.

  2. (ii)

Let $\varphi\in\operatorname{EM}_{\mathcal{L}^{\prime}}((a^{\prime}_{i})_{i\in
I^{\prime}}/C)$ and let $\Delta^{\prime}$ be the associated quantifier-free
$\mathcal{L}^{\prime}$-type. Let $\bar{\eta}^{\prime}$ be any tuple in
$I^{\prime}$ satisfying $\Delta^{\prime}$. By surjectivity there is a tuple
$\bar{\eta}$ in $I$ such that $f(\bar{\eta})=\bar{\eta}^{\prime}$. For any
tuple $\bar{\nu}$ in $I$ such that
$\operatorname{qftp}_{\mathcal{L}}(\bar{\nu})=\operatorname{qftp}_{\mathcal{L}}(\bar{\eta})$
we have that
$\operatorname{qftp}_{\mathcal{L}^{\prime}}(f(\bar{\nu}))=\operatorname{qftp}_{\mathcal{L}^{\prime}}(f(\bar{\eta}))=\Delta^{\prime}$
because $f$ is qftp-respecting. So we have
$\models\varphi(a^{\prime}_{f(\bar{\nu})})$, and hence
$\models\varphi(a_{\bar{\nu}})$. As $\bar{\nu}$ as arbitrary satisfying
$\operatorname{qftp}_{\mathcal{L}}(\bar{\eta})$, we see that
$\varphi\in\operatorname{EM}_{\mathcal{L}}((a_{i})_{i\in I}/C)$ with
$\operatorname{qftp}_{\mathcal{L}}(\bar{\eta})$ as the associated quantifier-
free $\mathcal{L}$-type. Since $(b_{i})_{i\in I}$ is
$\operatorname{EM}_{\mathcal{L}}$-based (over $C$) on $(a_{i})_{i\in I}$, we
get that $\models\varphi(b_{\bar{\eta}})$ and hence
$\models\varphi(b^{\prime}_{\bar{\eta}^{\prime}})$. As $\bar{\eta}^{\prime}$
was arbitrary satisfying $\Delta^{\prime}$ we conclude that
$\varphi\in\operatorname{EM}_{\mathcal{L}^{\prime}}((b^{\prime}_{i})_{i\in
I^{\prime}}/C)$, as required.

  3. (iii)

Let $\varphi\in\operatorname{EM}_{\mathcal{L}^{\prime}}((a^{\prime}_{i})_{i\in
I^{\prime}}/C)$ and let $\Delta^{\prime}$ be the associated quantifier-free
$\mathcal{L}^{\prime}$-type. Let $\bar{\eta}^{\prime}$ be any tuple in $J$
satisfying $\Delta^{\prime}$. Let $\bar{\nu}$ be any tuple in $I$ satisfying
$\operatorname{qftp}_{\mathcal{L}}(g(\bar{\eta}^{\prime}))$. Then
$\operatorname{qftp}_{\mathcal{L}^{\prime}}(f(\bar{\nu}))=\operatorname{qftp}_{\mathcal{L}^{\prime}}(fg(\bar{\eta}^{\prime}))=\Delta^{\prime}$
because $f$ is qftp-respecting and because of our assumption on $fg$. We thus
have that $\models\varphi(a^{\prime}_{f(\bar{\nu})})$ and so
$\models\varphi(a_{\bar{\nu}})$. As $\bar{\nu}$ was arbitrary satisfying
$\operatorname{qftp}_{\mathcal{L}}(g(\bar{\eta}^{\prime}))$ and such
$\bar{\nu}$ exists (take $\bar{\nu}=g(\bar{\eta}^{\prime})$) we get that
$\varphi\in\operatorname{EM}_{\mathcal{L}}((a_{i})_{i\in I}/C)$ with
$\operatorname{qftp}_{\mathcal{L}}(g(\bar{\eta}^{\prime}))$ as the associated
quantifier-free $\mathcal{L}$-type. Since $(b_{i})_{i\in I}$ is
$\operatorname{EM}_{\mathcal{L}}$-based on $(a_{i})_{i\in I}$ over $C$, we get
that $\models\varphi(b_{g(\bar{\eta}^{\prime})})$ and hence
$\models\varphi(b^{\prime}_{\bar{\eta}^{\prime}})$. As $\bar{\eta}^{\prime}$
was arbitrary satisfying $\Delta^{\prime}$ we conclude that
$\varphi\in\operatorname{EM}_{\mathcal{L}^{\prime}}((b^{\prime}_{j})_{j\in
J}/C)$, as required.

∎

##  4\. The tree modelling theorems

######  Definition 4.1 ([KKS14, Definition 2.1]).

tree-language For any ordinals $\alpha$ and $\beta$ we consider the set
$\alpha^{<\beta}$ of functions $\eta:\gamma\to\alpha$ with $\gamma<\beta$ as a
tree with the usual partial ordering: $\eta\unlhd\nu$ iff $\nu$ is an
extension of $\eta$. We will simultaneously view a function
$\eta:\gamma\to\alpha$ as a sequence of elements in $\alpha$ of length
$\gamma$. We put further structure on $\alpha^{<\beta}$ as follows, where
$\eta,\nu\in\alpha^{<\beta}$:

  * •

we write $\eta\wedge\nu$ for the _meet_ of $\eta$ and $\nu$ with respect to
$\unlhd$, i.e. the largest initial segment shared by $\eta$ and $\nu$;

  * •

we write $\eta<_{\textup{lex}}\nu$ for the _lexicographical ordering_ , i.e.
either $\eta\lhd\nu$ or $\eta$ and $\nu$ are incomparable with respect to
$\unlhd$ and for the least ordinal $\gamma$ such that
$\eta(\gamma)\neq\nu(\gamma)$ we have $\eta(\gamma)<\nu(\gamma)$;

  * •

we write $\ell(\eta)$ for the _length_ or _level_ of $\eta$, i.e. $\ell(\eta)$
is the domain of $\eta$;

  * •

we write $\eta<_{\textup{len}}\nu$ iff $\ell(\eta)<\ell(\nu)$;

  * •

for $\gamma<\beta$ we let
$P_{\gamma}=\\{\eta\in\alpha^{<\beta}:\ell(\eta)=\gamma\\}$.

Based on the above we put different structures on $\alpha^{<\beta}$ using the
following languages.

  * •

the _Shelah language_
$\mathcal{L}_{\textup{s}}=\\{\unlhd,\wedge,<_{\textup{lex}},(P_{\gamma})_{\gamma<\beta}\\}$,

  * •

the _strong Shelah language_
$\mathcal{L}_{\textup{str}}=\\{\unlhd,\wedge,<_{\textup{lex}},<_{\textup{len}}\\}$,

  * •

the _$0$ -strong Shelah language_
$\mathcal{L}_{{\textup{str}}_{0}}=\\{\unlhd,\wedge,<_{\textup{lex}}\\}$.

To abbreviate notation we will write “$\operatorname{EM}_{\textup{s}}$” and
“s-based” for “$\operatorname{EM}_{\mathcal{L}_{\textup{s}}}$” and
“$\mathcal{L}_{\textup{s}}$-based”. Whenever we consider a tree
$\alpha^{<\beta}$ as an $\mathcal{L}_{\textup{s}}$-structure we will call it
an _s-tree_ and write “s-indiscernible” instead of
“$\alpha^{<\beta}$-indiscernible”. For any two tuples $\bar{\eta}$ and
$\bar{\nu}$ in $\alpha^{<\beta}$ we will write
$\bar{\eta}\equiv^{\textup{s-qf}}\bar{\nu}$ for
$\operatorname{qftp}_{\mathcal{L}_{\textup{s}}}(\bar{\eta})=\operatorname{qftp}_{\mathcal{L}_{\textup{s}}}(\bar{\nu})$.

We abbreviate notation involving $\mathcal{L}_{\textup{str}}$ and
$\mathcal{L}_{{\textup{str}}_{0}}$ in a similar way, replacing the “s” in the
above by “str” or “str0” respectively.

######  Definition 4.2.

notation-for-tree-nodes For $\gamma_{0},\ldots,\gamma_{n-1}\in\alpha$ we write
$\langle\gamma_{0},\ldots,\gamma_{n-1}\rangle$ for the function
$i\mapsto\gamma_{i}$, which is an element of $\alpha^{<\beta}$. For
$\eta,\nu\in\alpha^{<\beta}$ we write $\eta^{\frown}\nu$ for the concatenation
of $\eta$ and $\nu$. Formally:

$(\eta^{\frown}\nu)(i)=\begin{cases}\eta(i)&\text{if }i<\ell(\eta)\\\
\nu(j)&\text{if }i=\ell(\eta)+j\end{cases}$

For $n<\omega$ we will write $\eta^{n}$ for the concatenation of $\eta$ with
itself $n$ times:

$\eta^{n}=\underbrace{\eta^{\frown}\eta^{\frown}\ldots{}^{\frown}\eta}_{n\text{
times}}$

So $\langle 0\rangle^{n}$ is the sequence of $n$ zeroes, or formally: the
constant function $n\to\\{0\\}$.

######  Example 4.3.

trees-examples We apply the re-indexing lemma (reindexing-lemma) to the
different tree structures.

  1. (i)

We consider the identity function $f:\omega^{<\omega}\to\omega^{<\omega}$,
where the domain and codomain will carry different structures. If a tree
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ is str0-indiscernible over $C$ then it
is also str-indiscernible over $C$. This is due to reindexing-lemma(i): $f$ is
just a reduct of structures, and hence qftp-respecting. Similarly, if
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ is str-indiscernible over $C$ then it
is s-indiscernible over $C$. However, now $f$ is not simply a reduct of
languages, but it is still a qftp-respecting as the predicates
$(P_{n})_{n<\omega}$ determine the relation $<_{\textup{len}}$.

  2. (ii)

Like in the previous point, we consider the identity function
$f:\omega^{<\omega}\to\omega^{<\omega}$ as a qftp-respecting function between
an str-structure and str0-structure, or between an s-structure and an str-
structure. We get the following from reindexing-lemma(ii): if
$(b_{\eta})_{\eta\in\omega^{<\omega}}$ is
$\operatorname{EM}_{\textup{s}}$-based on
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ over $C$ then it is also
$\operatorname{EM}_{\textup{str}}$-based on
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ over $C$, and if
$(b_{\eta})_{\eta\in\omega^{<\omega}}$ is
$\operatorname{EM}_{\textup{str}}$-based on
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ over $C$ then it is also
$\operatorname{EM}_{{\textup{str}}_{0}}$-based on
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ over $C$.

  3. (iii)

Let $L\subseteq\omega$ be an infinite set, and enumerate $L$ in order as
$\ell_{0}<\ell_{1}<\ldots$. For $\eta\in\omega^{<\omega}$ of length $n$ we
define $\nu_{\eta}\in\omega^{<\omega}$ of length $\ell_{n}$ as:

$\nu_{\eta}(k)=\begin{cases}\eta(i)&\text{if }k=\ell_{i+1}-1\\\
0&\text{otherwise}\end{cases}$

Define $f_{L}:\omega^{<\omega}\to\omega^{<\omega}$ as
$f_{L}(\eta)=\nu_{\eta}$. If we consider the domain and codomain of $f_{L}$ as
s-trees then $f_{L}$ is qftp-respecting. We write
$\omega^{<\omega}{\upharpoonright_{L}}$ for the image of $f_{L}$ with the
induced s-structure, and call this _the restriction of $\omega^{<\omega}$ to
levels $L$_. If $(a_{\eta})_{\eta\in\omega^{<\omega}}$ is s-indiscernible over
$C$ then so is $(a_{\eta})_{\eta\in\omega^{<\omega}{\upharpoonright_{L}}}$.
This construction works in the exact same way for str-trees and str0-trees.

  4. (iv)

Fix some $\eta\in\omega^{<\omega}$ and consider
$f_{\eta}:\omega\to\omega^{<\omega},i\mapsto\eta^{\frown}\langle i\rangle$. We
consider $\omega$ as the usual $\mathcal{L}_{<}$-structure and
$\omega^{<\omega}$ as an s-structure. Then $f_{\eta}$ is qftp-respecting. So
if $(a_{\eta})_{\eta\in\omega^{<\omega}}$ is s-indiscernible over $C$ then
$(a^{\prime}_{i})_{i<\omega}$ defined by $a^{\prime}_{i}=a_{f_{\eta}(i)}$ is a
$C$-indiscernible sequence, by reindexing-lemma(i).

The following notation will be useful in proofs. We define it for finite
tuples, but it would make sense for infinite tuples.

######  Definition 4.4.

tree-tuple-extra-notation Let $\bar{\eta}=(\eta_{1},\ldots,\eta_{n})$ be a
tuple in a tree $\alpha^{<\beta}$. We define:

  * •

$\ell(\bar{\eta})=\\{\ell(\eta_{i}):1\leq i\leq n\\}$ to be the set of levels
of the elements in $\bar{\eta}$,

  * •

$\operatorname{cl}_{\wedge}(\bar{\eta})$ to be the closure of $\bar{\eta}$
under meets.

The thickness assumption in the main theorems is needed to make the various
forms of indiscernibility type-definable.

######  Proposition 4.5.

s-str-str0-indiscernible-type-definable Let $T$ be a thick theory. The
properties of being s-indiscernible, being str-indiscernible and being
str0-indiscernible are type-definable. More precisely, define the partial type
$\pi_{\textup{s}}((x_{\eta})_{\eta\in\omega^{<\omega}},y)$ to be

$\bigcup\\{\operatorname{d}_{y}(x_{\bar{\eta}},x_{\bar{\nu}})\leq
2:\bar{\eta},\bar{\nu}\text{ are finite tuples in }\omega^{<\omega}\text{ with
}\bar{\eta}\equiv^{\textup{s-qf}}\bar{\nu}\\},$

define $\pi_{\textup{str}}((x_{\eta})_{\eta\in\omega^{<\omega}},y)$ to be

$\bigcup\\{\operatorname{d}_{y}(x_{\bar{\eta}},x_{\bar{\nu}})\leq
2:\bar{\eta},\bar{\nu}\text{ are finite tuples in }\omega^{<\omega}\text{ with
}\bar{\eta}\equiv^{\textup{str-qf}}\bar{\nu}\\},$

and define $\pi_{{\textup{str}}_{0}}((x_{\eta})_{\eta\in\omega^{<\omega}},y)$
to be

$\bigcup\\{\operatorname{d}_{y}(x_{\bar{\eta}},x_{\bar{\nu}})\leq
2:\bar{\eta},\bar{\nu}\text{ are finite tuples in }\omega^{<\omega}\text{ with
}\bar{\eta}\equiv^{\textup{str${}_{0}$-qf}}\bar{\nu}\\}.$

Then for any parameter set $C$ we have
$\models\pi_{\textup{s}}((a_{\eta})_{\eta\in\omega^{<\omega}},C)$ iff
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ is s-indiscernible over $C$, and
similarly for $\pi_{\textup{str}}$ and $\pi_{{\textup{str}}_{0}}$ and being
str-indiscernible and being str0-indiscernible over $C$.

###### Proof.

For $\pi_{\textup{s}}$ this is [DK22, Corollary 5.7]. We prove the case for
$\pi_{\textup{str}}$ using a similar argument, and the case for
$\pi_{{\textup{str}}_{0}}$ uses the exact same argument as for
$\pi_{\textup{str}}$.

If $\models\pi_{\textup{str}}((a_{\eta})_{\eta\in\omega^{<\omega}},C)$ holds
then for any finite tuples $\bar{\eta}$, $\bar{\nu}$ in $\omega^{<\omega}$
with $\bar{\eta}\equiv^{\textup{str-qf}}\bar{\nu}$ we have
$\operatorname{d}_{C}(a_{\bar{\eta}},a_{\bar{\nu}})\leq 2$, and so in
particular $a_{\bar{\eta}}\equiv_{C}a_{\bar{\nu}}$.

Conversely, suppose that $(a_{\eta})_{\eta\in\omega^{<\omega}}$ is str-
indiscernible over $C$. Let $\bar{\eta}$, $\bar{\nu}$ be finite tuples in
$\omega^{<\omega}$ such that $\bar{\eta}\equiv^{\textup{str-qf}}\bar{\nu}$. We
may assume that both $\bar{\eta}$ and $\bar{\nu}$ are closed under meets. As
$\bar{\eta}$ and $\bar{\nu}$ are both finite, there is some $k<\omega$ such
that they are both contained in $k^{<k}$. Write
$\bar{\eta}=(\eta_{1},\ldots,\eta_{n})$. For $i<\omega$ and $1\leq j\leq n$ we
define $\chi^{j}_{i}=\langle k\rangle^{(i+1)k}{}^{\frown}\eta_{j}$, and write
$\bar{\chi}_{i}=(\chi^{1}_{i},\ldots,\chi^{n}_{i})$. One straightforwardly
verifies that $\bar{\eta},\bar{\chi}_{0},\bar{\chi}_{1},\ldots$ and
$\bar{\nu},\bar{\chi}_{0},\bar{\chi}_{1},\ldots$ are indiscernible sequences
with respect to quantifier-free $\mathcal{L}_{\textup{str}}$-formulas. Then
$\operatorname{d}_{C}(a_{\bar{\eta}},a_{\bar{\nu}})\leq 2$ follows from str-
indiscernibility of $(a_{\eta})_{\eta\in\omega^{<\omega}}$. ∎

######  Theorem 4.6 (s-modelling, [DK22, Proposition 5.8]).

s-modelling Let $T$ be a thick theory. Let
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ be a tree of tuples and let $C$ be any
set of parameters, then there is a tree $(b_{\eta})_{\eta\in\omega^{<\omega}}$
that is s-indiscernible over $C$ and $\operatorname{EM}_{\textup{s}}$-based on
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ over $C$.

###### Proof.

The cited result [DK22, Proposition 5.8] only states the above theorem for
trees of finite height (i.e., trees indexed by $\omega^{\leq k}$ for some
$k<\omega$). However, type-definability of s-indiscernibility in thick
theories is also established there [DK22, Corollary 5.7]. So the statement
here is really just an easy application of compactness, and so we still
attribute it to [DK22]. ∎

Using the $<_{\textup{len}}$ relation in $\mathcal{L}_{\textup{str}}$ we get
the following fact.

######  Fact 4.7.

s-qf-type-is-str-qf-type-plus-levels Let $\bar{\eta}$ and $\bar{\nu}$ be
finite meet-closed tuples in $\alpha^{<\beta}$, then
$\bar{\eta}\equiv^{\textup{s-qf}}\bar{\nu}$ iff
$\bar{\eta}\equiv^{\textup{str-qf}}\bar{\nu}$ and
$\ell(\bar{\eta})=\ell(\bar{\nu})$.

######  Theorem 4.8.

str-basing Let $C$ be any parameter set, $\kappa$ be any cardinal, and let
$\lambda=\beth_{(2^{|T|+|C|+\kappa})^{+}}$. Given any tree
$(a_{\eta})_{\eta\in\omega^{<\lambda}}$ of $\kappa$-tuples that is
s-indiscernible over $C$, there is a tree
$(b_{\eta})_{\eta\in\omega^{<\omega}}$ that is str-indiscernible over $C$ str-
based on $(a_{\eta})_{\eta\in\omega^{<\lambda}}$ over $C$.

The proof of this theorem relies on the Erdős-Rado theorem, which we will
recall for the reader’s convenience. For $n<\omega$ and cardinals
$\kappa,\lambda,\mu$ the notation $\kappa\to(\lambda)^{n}_{\mu}$ means that
for any function $f:[\kappa]^{n}\to\mu$ we can find $X\subseteq\kappa$ with
$|X|=\lambda$ such that $f$ is constant on $[X]^{n}$, where $[\kappa]^{n}$ and
$[X]^{n}$ are the sets of subsets of size $n$ of $\kappa$ and $X$
respectively.

######  Fact 4.9 (Erdős-Rado).

erdos-rado For any $n<\omega$ and any infinite cardinal $\mu$ we have

$\beth^{+}_{n}(\mu)\to(\mu^{+})^{n+1}_{\mu}.$

###### Proof.

Let $S$ be the set of types over $C$ in $\max(\kappa,\omega)$ many variables.
Then $\lambda$ has the following properties:

  1. (i)

$\lambda$ is a limit cardinal with $\operatorname{cf}(\lambda)>|S|$,

  2. (ii)

for all $\mu<\lambda$ and $n<\omega$ there is $\mu^{\prime}<\lambda$ such that
$\mu^{\prime}\to(\mu)^{n}_{|S|}$.

Property (i) is immediate, and (ii) follows from Erdős-Rado (erdos-rado).

For any tuple $\bar{\eta}$ in $\omega^{<\omega}$ and any type
$p(x_{\bar{\eta}})$, we write

$\Sigma_{p,\bar{\eta}}((x_{\nu})_{\nu\in\omega^{<\omega}})=\bigcup\\{p(x_{\bar{\nu}}):\bar{\nu}\equiv^{\textup{str-
qf}}\bar{\eta}\\}$

for the partial type expressing that in the tree
$(x_{\nu})_{\nu\in\omega^{<\omega}}$ any tuple indexed by something with the
same str-quantifier-free type as $\bar{\eta}$ has type $p$.

There are countably many quantifier-free $\mathcal{L}_{\textup{str}}$-types in
finitely many variables. Enumerate the ones that are the type of a meet-closed
tuple in $\omega^{<\omega}$ as $(\Delta_{i})_{i<\omega}$. For $i<\omega$ we
let $\bar{\eta}_{i}$ be a tuple in $\omega^{<\omega}$ satisfying $\Delta_{i}$.
By induction we will construct types $(p_{i}(x_{\bar{\eta}_{i}}))_{i<\omega}$
over $C$ such that:

  1. (1)

$\bigcup_{j\leq i}\Sigma_{p_{j},\bar{\eta}_{j}}$ is consistent,

  2. (2)

for every $\mu<\lambda$ there is $I\subseteq\lambda$ with $|I|=\mu$ such that
for all $j\leq i$ we have that whenever $\bar{\nu}\equiv^{\textup{str-
qf}}\bar{\eta}_{j}$ with $\ell(\bar{\nu})\subseteq I$ then $\models
p_{j}(a_{\bar{\nu}})$.

Suppose that $(p_{j})_{j<i}$ has been constructed, we construct $p_{i}$. Set
$n=|\ell(\bar{\eta}_{i})|$. We define $f:[\lambda]^{n}\to S$ as follows. For
$E\in[\lambda]^{n}$ we let $\bar{\eta}_{E}$ be some tuple in
$\omega^{<\lambda}$ such that $\bar{\eta}_{E}\equiv^{\textup{str-
qf}}\bar{\eta}_{i}$ and $\ell(\bar{\eta}_{E})=E$. Then we set

$f(E)=\operatorname{tp}(a_{\bar{\eta}_{E}}/C).$

Let now $\mu<\lambda$ be arbitrary. By (ii) there is $\mu^{\prime}<\lambda$
such that $\mu^{\prime}\to(\mu)^{n}_{|S|}$. By (2) there is
$I\subseteq\lambda$ with $|I|=\mu^{\prime}$ such that for all $j<i$ we have
that whenever $\bar{\nu}\equiv^{\textup{str-qf}}\bar{\eta}_{j}$ with
$\ell(\bar{\nu})\subseteq I$ then $\models p_{j}(a_{\bar{\nu}})$ (in case
$i=0$ we just take $I=\mu^{\prime}$). We apply the fact that
$\mu^{\prime}\to(\mu)^{n}_{|S|}$ to the restriction of $f$ to $I$ to find
$I_{\mu}\subseteq I$ with $|I_{\mu}|=\mu$ such that $f$ is constant on
$[I_{\mu}]^{n}$. We write $q_{\mu}$ for the constant value of $f$ on
$[I_{\mu}]^{n}$, that is $q_{\mu}=f(E)$, where $E\in[I_{\mu}]^{n}$.

As $\mu<\lambda$ was arbitrary, we have such an $I_{\mu}$ and $q_{\mu}$ for
every $\mu<\lambda$. By (i) we then find a cofinal subset $J\subseteq\lambda$
of cardinals such that for any $\mu,\mu^{\prime}\in J$ we have that
$q_{\mu}=q_{\mu^{\prime}}$. Set $p_{i}=q_{\mu}$, where $\mu\in J$. For part
(2) of the induction hypothesis we note that for every $\mu<\lambda$ there is
$\mu^{\prime}\in J$ with $\mu<\mu^{\prime}$. We verify (2) for
$I_{\mu^{\prime}}$ (technically we would need to take a $\mu$-sized subset,
but that we can clearly do). For $j<i$ the required property follows by
construction of $I_{\mu^{\prime}}$, in particular because it is a subset of
what we called $I$ in its construction. For $j=i$ the required property
follows because $f$ is constant on $[I_{\mu^{\prime}}]^{n}$, together with
s-indiscernibility of $(a_{\eta})_{\eta\in\omega^{<\lambda}}$ and s-qf-type-
is-str-qf-type-plus-levels. Then part (1) follows from part (2) as follows:
let $\mu\in J$ be any infinite cardinal and let $L$ be the first $\omega$
elements of $I_{\mu}$. Then $\bigcup_{j\leq i}\Sigma_{p_{j},\bar{\eta}_{j}}$
is realised by the restriction
$(a_{\eta})_{\eta\in\omega^{<\lambda}{\upharpoonright_{L}}}$ to levels $L$
(see trees-examples(iii)).

This finishes the inductive construction of
$(p_{i}(x_{\bar{\eta}_{i}}))_{i<\omega}$. Set

$\Sigma((x_{\eta})_{\eta\in\omega^{<\omega}})=\bigcup_{i<\omega}\Sigma_{p_{i},\bar{\eta}_{i}}.$

Then by (1) this is consistent, so we let
$(b_{\eta})_{\eta\in\omega^{<\omega}}$ be a realisation. Then we have the
following properties:

  1. (a)

for any finite tuple $\bar{\eta}$ in $\omega^{<\omega}$ there is some $i$ such
that $\operatorname{cl}_{\wedge}(\bar{\eta})\equiv^{\textup{str-
qf}}\bar{\eta}_{i}$,

  2. (b)

if $\operatorname{cl}_{\wedge}(\bar{\eta})\equiv^{\textup{str-
qf}}\bar{\eta}_{i}$ then $b_{\operatorname{cl}_{\wedge}(\bar{\eta})}\models
p_{i}$.

It follows that $(b_{\eta})_{\eta\in\omega^{<\omega}}$ is str-indiscernible
over $C$. Let $\bar{\eta}\equiv^{\textup{str-qf}}\bar{\nu}$ be finite tuples
in $\omega^{<\omega}$. Then
$\operatorname{cl}_{\wedge}(\bar{\eta})\equiv^{\textup{str-
qf}}\operatorname{cl}_{\wedge}(\bar{\nu})$. By (a) there is $i<\omega$ such
that $\operatorname{cl}_{\wedge}(\bar{\eta})\equiv^{\textup{str-
qf}}\bar{\eta}_{i}$. Then by (b) we get that
$b_{\operatorname{cl}_{\wedge}(\bar{\eta})}\models p_{i}$ and
$b_{\operatorname{cl}_{\wedge}(\bar{\nu})}\models p_{i}$, so since $p_{i}$ is
a type over $C$ we get $b_{\bar{\eta}}\equiv_{C}b_{\bar{\nu}}$ after
restricting the types. Finally, $(b_{\eta})_{\eta\in\omega^{<\omega}}$ is str-
based on $(a_{\eta})_{\eta\in\omega^{<\lambda}}$: for any finite tuple
$\bar{\eta}$ in $\omega^{<\omega}$ we have by (a) that there is $i<\omega$
with $\operatorname{cl}_{\wedge}(\bar{\eta})=\bar{\eta}_{i}$. By construction
$p_{i}$ is realised by $a_{\bar{\nu}^{\prime}}$ for some $\bar{\nu}^{\prime}$
in $\omega^{<\lambda}$ with $\bar{\nu}^{\prime}\equiv^{\textup{str-
qf}}\bar{\eta}_{i}$. Using the fact that
$\bar{\nu}^{\prime}\equiv^{\textup{str-
qf}}\operatorname{cl}_{\wedge}(\bar{\eta})$ we find
$\bar{\nu}\subseteq\bar{\nu}^{\prime}$ such that
$\bar{\nu}\equiv^{\textup{str-qf}}\bar{\eta}$. By (b) we have
$\operatorname{tp}(b_{\operatorname{cl}_{\wedge}(\bar{\eta})}/C)=p_{i}$, so
restricting types yields $b_{\bar{\eta}}\equiv_{C}a_{\bar{\nu}}$, as required.
∎

######  str-modelling, repeated.

Let $T$ be a thick theory. Let $(a_{\eta})_{\eta\in\omega^{<\omega}}$ be a
tree of tuples of the same length and let $C$ be any set of parameters, then
there is a tree $(b_{\eta})_{\eta\in\omega^{<\omega}}$ that is str-
indiscernible over $C$ and $\operatorname{EM}_{\textup{str}}$-based on
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ over $C$.

###### Proof.

By s-modelling we find $(a^{\prime}_{\eta})_{\eta\in\omega^{<\omega}}$ that is
s-indiscernible over $C$ and is $\operatorname{EM}_{\textup{s}}$-based on
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ over $C$. Let $\lambda$ be the cardinal
in str-basing. Using s-str-str0-indiscernible-type-definable we can write down
a partial type $\Sigma$ for a tree
$(a^{\prime\prime}_{\eta})_{\eta\in\omega^{<\lambda}}$ that is s-indiscernible
over $C$ and $\operatorname{EM}_{\textup{str}}$-based on
$(a^{\prime}_{\eta})_{\eta\in\omega^{<\omega}}$ over $C$. Using
$(a^{\prime}_{\eta})_{\eta\in\omega^{<\omega}}$, and renaming levels whenever
needed, we see that $\Sigma$ is finitely satisfiable. So we find our tree
$(a^{\prime\prime}_{\eta})_{\eta\in\omega^{<\lambda}}$ that is s-indiscernible
over $C$ and $\operatorname{EM}_{\textup{str}}$-based on
$(a^{\prime}_{\eta})_{\eta\in\omega^{<\omega}}$ over $C$. We apply str-basing
to $(a^{\prime\prime}_{\eta})_{\eta\in\omega^{<\lambda}}$ to find
$(b_{\eta})_{\eta\in\omega^{<\omega}}$ that is str-indiscernible over $C$ and
str-based on $(a^{\prime\prime}_{\eta})_{\eta\in\omega^{<\lambda}}$ over $C$.
Being str-based and $\operatorname{EM}_{\textup{s}}$-based both imply being
$\operatorname{EM}_{\textup{str}}$-based, and being
$\operatorname{EM}_{\textup{str}}$-based is transitive, so
$(b_{\eta})_{\eta\in\omega^{<\omega}}$ is
$\operatorname{EM}_{\textup{str}}$-based on
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ over $C$. ∎

######  Theorem 4.10.

str0-basing Let $C$ be any parameter set. Given any tree
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ that is str-indiscernible over $C$,
there is a tree $(b_{\eta})_{\eta\in\omega^{<\omega}}$ that is
str0-indiscernible over $C$ and str0-based on
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ over $C$.

###### Proof.

Fix $1\leq k<\omega$. By induction on $m<\omega$ we define $f_{k}^{m}:k^{\leq
m}\to\omega^{<\omega}$ and $l_{k}^{m}<\omega$ as in [Sco15, Claim A.7] (which
in turn is based on [DS04, page 142]):

$\displaystyle f_{k}^{m}(\emptyset)$ $\displaystyle=\emptyset$
$\displaystyle\text{for all }m<\omega,$ $\displaystyle l_{k}^{m}$
$\displaystyle=\max\\{\ell(f_{k}^{m}(\eta))+1:\eta\in k^{\leq m}\\},$
$\displaystyle f_{k}^{m+1}(\langle i\rangle^{\frown}\eta)$
$\displaystyle=\langle i\rangle^{\frown}\langle
0\rangle^{(i+1)l_{k}^{m}}{}^{\frown}f_{k}^{m}(\eta).$

Then for all $k,m<\omega$:

(*) $f_{k}^{m}$ is an $\mathcal{L}_{{\textup{str}}_{0}}$-embedding such that
$\eta<_{\textup{lex}}\nu$ implies
$f_{k}^{m}(\eta)<_{\textup{len}}f_{k}^{m}(\nu)$.

Let $\bar{\eta}$ be a finite tuple in $\omega^{<\omega}$ and let $k,m<\omega$
be such that $\bar{\eta}$ is contained in $k^{\leq m}$. Then we assign the
type
$p_{\bar{\eta}}(x_{\bar{\eta}})=\operatorname{tp}(a_{f_{m}^{k}(\bar{\eta})}/C)$
to $\bar{\eta}$. By (*) and str-indiscernibility, the type $p_{\bar{\eta}}$
does not depend on $k$ or $m$ and whenever
$\bar{\eta}\equiv^{\textup{str${}_{0}$-qf}}\bar{\nu}$ then
$p_{\bar{\eta}}=p_{\bar{\nu}}$ (after renaming variables). Define

$\Sigma((x_{\eta})_{\eta\in\omega^{<\omega}})=\bigcup\\{p_{\bar{\eta}}:\bar{\eta}\text{
is a finite tuple in }\omega^{<\omega}\\}.$

Let $\Sigma_{0}$ be any finite part of $\Sigma$, and let $k,m<\omega$ be such
that the variables appearing in $\Sigma_{0}$ are contained in
$(x_{\eta})_{\eta\in k^{\leq m}}$. Then $\Sigma_{0}$ is realised by
$(a^{\prime}_{\eta})_{\eta\in k^{\leq m}}$ where
$a^{\prime}_{\eta}=a_{f_{k}^{m}(\eta)}$ for all $\eta\in k^{\leq m}$. So by
compactness we find a realisation $(b_{\eta})_{\eta\in\omega^{<\omega}}$ of
$\Sigma$, which is the tree we needed to construct. Indeed, let $\bar{\eta}$
be any finite tuple in $\omega^{<\omega}$ and let $k,m<\omega$ be such that
$\bar{\eta}$ is contained in $k^{\leq m}$. Then
$\operatorname{tp}(b_{\bar{\eta}}/C)=p_{\bar{\eta}}=\operatorname{tp}(a_{f_{k}^{m}(\bar{\eta})}/C)$,
and so because
$f_{k}^{m}(\bar{\eta})\equiv^{\textup{str${}_{0}$-qf}}\bar{\eta}$ this shows
that $(b_{\eta})_{\eta\in\omega^{<\omega}}$ is based on
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ over $C$. Let now $\bar{\nu}$ be such
that $\bar{\nu}\equiv^{\textup{str${}_{0}$-qf}}\bar{\eta}$, then
$\operatorname{tp}(b_{\bar{\eta}}/C)=p_{\bar{\eta}}=p_{\bar{\nu}}=\operatorname{tp}(b_{\bar{\nu}}/C)$
and we have established str0-indiscernibility over $C$. ∎

######  str0-modelling, repeated.

Let $T$ be a thick theory. Let $(a_{\eta})_{\eta\in\omega^{<\omega}}$ be a
tree of tuples of the same length and let $C$ be any set of parameters, then
there is a tree $(b_{\eta})_{\eta\in\omega^{<\omega}}$ that is
str0-indiscernible over $C$ and $\operatorname{EM}_{{\textup{str}}_{0}}$-based
on $(a_{\eta})_{\eta\in\omega^{<\omega}}$ over $C$.

###### Proof.

By str-modelling there is a tree
$(a^{\prime}_{\eta})_{\eta\in\omega^{<\omega}}$ that is str-indiscernible over
$C$ and $\operatorname{EM}_{\textup{str}}$-based on
$(a_{\eta})_{\eta\in\omega^{<\omega}}$ over $C$. By str0-basing there is then
a tree $(b_{\eta})_{\eta\in\omega^{<\omega}}$ that is str0-indiscernible over
$C$ and str0-based on $(a^{\prime}_{\eta})_{\eta\in\omega^{<\omega}}$ over
$C$. Being $\operatorname{EM}_{\textup{str}}$-based and being str0-based both
imply being $\operatorname{EM}_{{\textup{str}}_{0}}$-based, and being
$\operatorname{EM}_{{\textup{str}}_{0}}$-based is transitive, so we conclude
that $(b_{\eta})_{\eta\in\omega^{<\omega}}$ is the required tree. ∎

##  5\. The array modelling theorem

######  Definition 5.1 ([KKS14, Definition 5.4]).

array-language We define the following structure on $\omega\times\omega$,
where $(i,j),(s,t)\in\omega\times\omega$:

  * •

$(i,j)<_{1}(s,t)$ iff $i<s$,

  * •

$(i,j)<_{2}(s,t)$ iff $i=s$ and $j<t$.

We define the _array language_ to be
$\mathcal{L}_{\textup{ar}}=\\{<_{1},<_{2}\\}$ and we call the structure
$\omega\times\omega$ an _array_. We abbreviate notation involving
$\mathcal{L}_{\textup{ar}}$ in a similar way as described at the end of tree-
language, replacing the “s” there by “ar” or “array”.

######  array-modelling, repeated.

Let $T$ be a thick theory. Let $(a_{i,j})_{i,j<\omega}$ be an array of tuples
of the same length and let $C$ be any set of parameters, then there is an
array $(b_{i,j})_{i,j<\omega}$ that is array-indiscernible over $C$ and
$\operatorname{EM}_{{\textup{ar}}}$-based on $(a_{i,j})_{i,j<\omega}$ over
$C$.

###### Proof.

Let $J$ be the $<_{\textup{lex}}$-order type of $\omega^{<\omega}$ and, using
compactness, let $(a^{\prime}_{i,j})_{i<\omega,j\in J}$ be an array that is
$\operatorname{EM}_{\textup{ar}}$-based on $(a_{i,j})_{i,j<\omega}$ over $C$.
Here $\omega\times J$ carries the expected
$\mathcal{L}_{\textup{ar}}$-structure: $(i,j)<_{1}(s,t)$ iff $i<s$, and
$(i,j)<_{2}(s,t)$ iff $i=s$ and $j<t$ in the order on $J$. Let
$f^{\prime}:\omega^{<\omega}\to J$ be the $<_{\textup{lex}}$-order isomorphism
and define $f:\omega^{<\omega}\to\omega\times J$ as
$f(\eta)=(\ell(\eta),f^{\prime}(\eta))$. Then $f$ is an injection such that
for any $\eta,\nu\in\omega^{<\omega}$:

  1. (i)

$\eta<_{\textup{len}}\nu$ implies $f(\eta)<_{1}f(\nu)$,

  2. (ii)

$\ell(\eta)=\ell(\nu)$ and $\eta<_{\textup{lex}}\nu$ implies
$f(\eta)<_{2}f(\nu)$.

So in particular, $f$ is qftp-respecting, where $\omega^{<\omega}$ is
considered as an str-tree. Define a tree
$(a^{*}_{\eta})_{\eta\in\omega^{<\omega}}$ by
$a^{*}_{\eta}=a^{\prime}_{f(\eta)}$. By str-modelling we find a tree
$(b^{*}_{\eta})_{\eta\in\omega^{<\omega}}$ that is str-indiscernible over $C$
and $\operatorname{EM}_{\textup{str}}$-based on
$(a^{*}_{\eta})_{\eta\in\omega^{<\omega}}$. Define
$g:\omega\times\omega\to\omega^{<\omega}$ by $g(i,j)={\langle
0\rangle^{2i}}^{\frown}\langle j+1\rangle$ and define an array
$(b_{i,j})_{i,j<\omega}$ by $b_{i,j}=b^{*}_{g(i,j)}$. We claim that
$(b_{i,j})_{i,j<\omega}$ is the required array.

First, we note that $g$ is qftp-respecting. Indeed, for any
$(i,j),(s,t)\in\omega\times\omega$ we have that:

  * •

$(i,j)<_{1}(s,t)$ implies $g((i,j))<_{\textup{len}}g((s,t))$ and
$g((s,t))<_{\textup{lex}}g((i,j))$,

  * •

$(i,j)<_{2}(s,t)$ implies $g((i,j))<_{\textup{lex}}g((s,t))$,

  * •

$g((i,j))\unlhd g((s,t))$ iff $(i,j)=(s,t)$.

That leaves the relations between any meets in the image of $g$ to be checked,
but this is also straightforward using the fact that the meet of a finite
number of nodes in $\omega^{<\omega}$ can be written as the meet of two of
those nodes, together with the fact that $g((i,j))\wedge g((s,t))=\langle
0\rangle^{2\min(i,s)}$ (unless $(i,j)=(s,t)$, of course). We can thus apply
the re-indexing lemma, reindexing-lemma(i), and get that
$(b_{i,j})_{i,j<\omega}$ is array-indiscernible over $C$ because
$(b^{*}_{\eta})_{\eta\in\omega^{<\omega}}$ is str-indiscernible over $C$.

We will again use the re-indexing lemma, reindexing-lemma(iii), to conclude
that $(b_{i,j})_{i,j<\omega}$ is $\operatorname{EM}_{\textup{ar}}$-based on
$(a^{\prime}_{i,j})_{i<\omega,j\in J}$ over $C$. From this the result then
follows because $(a^{\prime}_{i,j})_{i<\omega,j\in J}$ is
$\operatorname{EM}_{\textup{ar}}$-based on $(a_{i,j})_{i,j<\omega}$ over $C$.
So we only need to verify that for any finite tuple $\bar{\eta}$ in
$\omega\times\omega$ we have that $\bar{\eta}\equiv^{\textup{ar-
qf}}fg(\bar{\eta})$. Indeed, let $(i,j),(s,t)\in\omega\times\omega$, then

  * •

$f$ and $g$ are both injective functions, so equality is preserved and
reflected;

  * •

if $(i,j)<_{1}(s,t)$ then $g((i,j))<_{\textup{len}}g((s,t))$, and so
$fg((i,j))<_{1}fg((s,t))$;

  * •

if $fg((i,j))<_{1}fg((s,t))$ then $2i+1=\ell(g((i,j)))<\ell(g((s,t)))=2s+1$
and so $(i,j)<_{1}(s,t)$;

  * •

if $(i,j)<_{2}(s,t)$ then $\ell(g((i,j)))=\ell(g((s,t)))$ and
$g((i,j))<_{\textup{lex}}g((s,t))$, so $fg((i,j))<_{2}fg((s,t))$;

  * •

if $fg((i,j))<_{2}fg((s,t))$ then $\ell(g((i,j)))=\ell(g((s,t)))$ and
$f^{\prime}(g((i,j)))<f^{\prime}(g((s,t)))$, the latter means that
$g((i,j)))<_{\textup{lex}}g((s,t))$ and since their lengths are the same, and
so $i=s$, we must have $j+1<t+1$ and thus $(i,j)<_{2}(s,t)$.

∎

######  Remark 5.2.

kim-kim-scow-embedding The proof of array-modelling is based on that of
[KKS14, Theorem 5.5]. However, there the existence of a non-existing embedding
is claimed. In more detail, we view $\omega^{<\omega}$ as an
$\mathcal{L}_{\textup{ar}}$-structure by interpreting $<_{1}$ as
$<_{\textup{len}}$ and setting $\eta<_{2}\nu$ iff $\ell(\eta)=\ell(\nu)$ and
$\eta<_{\textup{lex}}\nu$. The claim is then that there is an
$\mathcal{L}_{\textup{ar}}$-embedding
$f:\omega^{<\omega}\to\omega\times\omega$. Such an $f$ cannot exist. Our proof
fixes this by stretching the original array, so that our $f$ can play the role
of this embedding, and the third author of [KKS14] has a similar fix in
[Sco21, Corollary 3.8].

Suppose that an $f$ as above exists. Let $\eta,\nu\in\omega^{<\omega}$ be such
that $\ell(\eta)=\ell(\nu)$, and let $(i,j)=f(\eta)$ and $(s,t)=f(\nu)$. Then
we must have $i=s$, because $<_{1}$ is interpreted as $<_{\textup{len}}$ in
the tree and $<_{1}$ is preserved and reflected by $f$. Let $g$ be the
restriction of $f$ to the nodes of length two. Then the image of $g$ is
contained in $\\{n\\}\times\omega$ for some $n<\omega$. So $g(\langle
1,0\rangle)=(n,k)$ for some $k<\omega$. However, $\langle
0,i\rangle<_{\textup{lex}}\langle 1,0\rangle$ for all $i<\omega$. We thus get
that the second coordinate of $g(\langle 0,i\rangle)$ is strictly less than
$k$ for all $i<\omega$, contradicting injectivity of $g$. So $f$ cannot exist.

Though we have no use for it, the following may be useful in future
applications.

######  Proposition 5.3.

array-indiscernibility-type-definable Let $T$ be a thick theory. The property
of being array-indiscernible is type-definable. That is, let
$\pi_{\textup{ar}}((x_{i,j})_{i,j<\omega},y)$ be the union of the following
partial types:

  * •

$\Sigma_{1}$, which expresses that $((x_{i,j})_{j<\omega})_{i<\omega}$ is
$y$-indiscernible;

  * •

for each $i<\omega$, $\Sigma_{2,i}$, which expresses that
$(x_{i,j})_{j<\omega}$ is indiscernible over $(y,(x_{k,j})_{k,j<\omega,k\neq
i})$.

Then for any parameter set $C$ we have
$\models\pi_{\textup{ar}}((a_{i,j})_{i,j<\omega},C)$ iff
$(a_{i,j})_{i,j<\omega}$ is array-indiscernible over $C$.

###### Proof.

If $(a_{i,j})_{i,j<\omega}$ is array-indiscernible over $C$ then we clearly
have that:

  * •

$((a_{i,j})_{j<\omega})_{i<\omega}$ is $C$-indiscernible;

  * •

for each $i<\omega$, $(a_{i,j})_{j<\omega}$ is indiscernible over
$(C,(a_{k,j})_{k,j<\omega,k\neq i})$.

So $\models\pi_{\textup{ar}}((a_{i,j})_{i,j<\omega},C)$.

For the converse, we assume
$\models\pi_{\textup{ar}}((a_{i,j})_{i,j<\omega},C)$ and let
$(q_{1},r_{1}),\ldots,(q_{n},r_{n})\in\omega\times\omega$ and
$(s_{1},t_{1}),\ldots,(s_{n},t_{n})\in\omega\times\omega$ be such that
$(q_{1},r_{1})\ldots(q_{n},r_{n})\equiv^{\textup{ar-
qf}}(s_{1},t_{1})\ldots(s_{n},t_{n})$. For notational convenience we may
assume that
$(q_{1},r_{1})\leq_{1}(q_{2},r_{2})\leq_{1}\ldots\leq_{1}(q_{n},r_{n})$ and
(necessarily) the same for the $(s_{i},t_{i})$. Then because
$((a_{i,j})_{j<\omega})_{i<\omega}$ is $C$-indiscernible we have that

$a_{q_{1},r_{1}}\ldots a_{q_{n},r_{n}}\equiv_{C}a_{s_{1},r_{1}}\ldots
a_{s_{n},r_{n}}.$

Now let $1\leq m\leq n$ be maximal such that $s_{1}=s_{m}$ (so for all $1\leq
m^{\prime}\leq m$ we have $s_{1}=s_{m^{\prime}}$). Then because
$(a_{s_{1},j})_{j<\omega}$ is indiscernible over
$(C,(a_{k,j})_{k,j<\omega,k\neq s_{1}})$, we have that

$a_{s_{1},r_{1}}\ldots a_{s_{n},r_{n}}\equiv_{C}a_{s_{1},t_{1}}\ldots
a_{s_{m},t_{m}}a_{s_{m+1},r_{m+1}}\ldots a_{s_{n},r_{n}}.$

Repeating this process we find

$a_{s_{1},r_{1}}\ldots a_{s_{n},r_{n}}\equiv_{C}a_{s_{1},t_{1}}\ldots
a_{s_{n},t_{n}},$

and thus $a_{q_{1},r_{1}}\ldots a_{q_{n},r_{n}}\equiv_{C}a_{s_{1},t_{1}}\ldots
a_{s_{n},t_{n}}$, as required. ∎

##  6\. An application: $\mathsf{TP_{2}}$

The definition of $2$-$\mathsf{TP_{2}}$ in positive logic first appeared in
[HK21, Definition 6.1]. We take the version from [DGK23], which defines
$k$-$\mathsf{TP_{2}}$ for $k\geq 2$.

######  Definition 6.1 ([DGK23, Definition 4.5]).

def-tp2 A formula $\varphi(x,y)$ has the _$k$ -tree property of the second
kind_ ($k$-$\mathsf{TP_{2}}$) for $k\geq 2$ if there are
$(a_{i,j})_{i,j<\omega}$ and $\psi(y_{1},\ldots,y_{k})$ that implies
$\neg\exists x(\varphi(x,y_{1})\wedge\ldots\wedge\varphi(x,y_{k}))$ modulo $T$
such that:

  1. (i)

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

  2. (ii)

for all $i<\omega$ and $j_{1}<\ldots<j_{k}<\omega$ we have
$\models\psi(a_{i,j_{1}},\ldots,a_{i,j_{k}})$.

We say that a theory $T$ has $k$-$\mathsf{TP_{2}}$ if some formula has
$k$-$\mathsf{TP_{2}}$.

######  Lemma 6.2.

indiscernible-tp2 Let $T$ be a thick theory. A formula $\varphi(x,y)$ has
$k$-$\mathsf{TP_{2}}$ for $k\geq 2$ if and only if there is an array-
indiscernible array $(a_{i,j})_{i,j<\omega}$ such that

  1. (i)

$\\{\varphi(x,a_{i,0}):i<\omega\\}$ is consistent,

  2. (ii)

$\\{\varphi(x,a_{0,i}):i<\omega\\}$ is $k$-inconsistent.

###### Proof.

If $\varphi(x,y)$ has $k$-$\mathsf{TP_{2}}$ as witnessed by
$(a^{\prime}_{i,j})_{i,j<\omega}$ and $\psi(y_{1},\ldots,y_{k})$ then we can
use array-modelling to $\operatorname{EM}_{\textup{ar}}$-base an array-
indiscernible array $(a_{i,j})_{i,j<\omega}$ on
$(a^{\prime}_{i,j})_{i,j<\omega}$. Then points (i) and (ii) in def-tp2 are
captured by the $\operatorname{EM}_{\textup{ar}}$-type of
$(a^{\prime}_{i,j})_{i,j<\omega}$ and respectively yield points (i) and (ii)
for $(a_{i,j})_{i,j<\omega}$ as above.

Conversely, let $(a_{i,j})_{i,j<\omega}$ be as above. Then
$((i,\sigma(i)))_{i<\omega}\equiv^{\textup{ar-qf}}((i,0))_{i<\omega}$ for any
$\sigma\in\omega^{\omega}$, so by (i) and array-indiscernibility
$\\{\varphi(x,a_{i,\sigma(i)}):i<\omega\\}$ is consistent. By (ii) we have
$\not\models\exists
x(\varphi(x,a_{0,0})\wedge\ldots\wedge\varphi(x,a_{0,k-1}))$. Let
$\psi(y_{1},\ldots,y_{k})$ be such that it implies $\neg\exists
x(\varphi(x,y_{1})\wedge\ldots\wedge\varphi(x,y_{k}))$ modulo $T$ and
$\models\psi(a_{0,0},\ldots,a_{0,k-1})$. Then by array-indiscernibility
$\models\psi(a_{i,j_{1}},\ldots,a_{i,j_{k}})$ for all $i<\omega$ and
$j_{1}<\ldots<j_{k}<\omega$. We conclude that $(a_{i,j})_{i,j<\omega}$ and
$\psi$ witness $k$-$\mathsf{TP_{2}}$ for $\varphi(x,y)$. ∎

######  k-tp2-iff-2-tp2, repeated.

Let $T$ be a thick theory. If $\varphi(x,y)$ has $k$-$\mathsf{TP_{2}}$ for
some $k\geq 2$ then some conjunction $\bigwedge_{i=1}^{n}\varphi(x,y_{i})$ has
$2$-$\mathsf{TP_{2}}$. Hence, $T$ has $k$-$\mathsf{TP_{2}}$ for some $k\geq 2$
iff $T$ has $2$-$\mathsf{TP_{2}}$.

###### Proof.

Based on [KKS14, Proposition 5.7]. We prove this by induction on $k\geq 2$.
The base case, $k=2$, is trivial. So assume that the theorem holds for
$2,\ldots,k-1$ and suppose that $\varphi(x,y)$ has $k$-$\mathsf{TP_{2}}$. By
indiscernible-tp2 there is an array-indiscernible array
$(a_{i,j})_{i,j<\omega}$ such that

  1. (i)

$\\{\varphi(x,a_{i,0}):i<\omega\\}$ is consistent,

  2. (ii)

$\\{\varphi(x,a_{0,i}):i<\omega\\}$ is $k$-inconsistent.

We finish the induction step, and thus the proof, by considering two cases.

  * •

The case where $\\{\varphi(x,a_{i,0}),\varphi(x,a_{i,1}):i<\omega\\}$ is
consistent. Define an array $(b_{i,j})_{i,j<\omega}$ by
$b_{i,j}=(a_{i,2j},a_{i,2j+1})$ for all $i,j<\omega$, then
$(b_{i,j})_{i,j<\omega}$ is array-indiscernible. Let
$\varphi^{\prime}(x,y_{0},y_{1})$ be $\varphi(x,y_{0})\wedge\varphi(x,y_{1})$.
Then by assumption $\\{\varphi^{\prime}(x,b_{i,0}):i<\omega\\}$ is consistent,
while $\\{\varphi^{\prime}(x,b_{0,i}):i<\omega\\}$ is $\lceil
k/2\rceil$-inconsistent. So by indiscernible-tp2 we have that
$\varphi^{\prime}(x;y_{0},y_{1})$ has $\lceil k/2\rceil$-$\mathsf{TP_{2}}$,
and we conclude this case by using the induction hypothesis.

  * •

The case where $\\{\varphi(x,a_{i,0}),\varphi(x,a_{i,1}):i<\omega\\}$ is
inconsistent. By compactness there is then $n<\omega$ such that
$\\{\varphi(x,a_{i,0}),\varphi(x,a_{i,1}):i<n\\}$ is inconsistent. Define an
array $(b_{i,j})_{i,j<\omega}$ by $b_{i,j}=(a_{ni,j},\ldots,a_{ni+n-1,j})$,
then $(b_{i,j})_{i,j<\omega}$ is array-indiscernible. Let
$\varphi^{\prime}(x,y_{0},\ldots,y_{n-1})$ be
$\varphi(x,y_{0})\wedge\ldots\wedge\varphi(x,y_{n-1})$. Then
$\\{\varphi^{\prime}(x,b_{i,0}):i<\omega\\}$ is consistent, while by
assumption $\\{\varphi^{\prime}(x,b_{0,i}):i<\omega\\}$ is $2$-inconsistent.
So by indiscernible-tp2 we have that
$\varphi^{\prime}(x;y_{0},\ldots,y_{n-1})$ has $2$-$\mathsf{TP_{2}}$,
completing the induction step for this case.

∎

## References

  * [BY03a] Itay Ben-Yaacov.  Positive model theory and compact abstract theories.  Journal of Mathematical Logic, 03(01):85–118, May 2003.
  * [BY03b] Itay Ben-Yaacov.  Simplicity in compact abstract theories.  Journal of Mathematical Logic, 03(02):163–191, November 2003.
  * [BY03c] Itay Ben-Yaacov.  Thickness, and a categoric view of type-space functors.  Fundamenta Mathematicae, 179:199–224, 2003.
  * [DGK23] Anna Dmitrieva, Francesco Gallinaro, and Mark Kamsma.  Dividing Lines between Positive Theories, April 2023.  arXiv:2304.07557.
  * [DK22] Jan Dobrowolski and Mark Kamsma.  Kim-independence in positive logic.  Model Theory, 1(1):55–113, June 2022.
  * [DS04] Mirna Džamonja and Saharon Shelah.  On $\lhd^{*}$-maximality.  Annals of Pure and Applied Logic, 125(1):119–158, February 2004\.
  * [HK21] Levon Haykazyan and Jonathan Kirby.  Existentially closed exponential fields.  Israel Journal of Mathematics, 241(1):89–117, March 2021.
  * [KKS14] Byunghan Kim, Hyeung-Joon Kim, and Lynn Scow.  Tree indiscernibilities, revisited.  Archive for Mathematical Logic, 53(1):211–232, February 2014.
  * [PY18] Bruno Poizat and Aibat Yeshkeyev.  Positive Jonsson Theories.  Logica Universalis, 12(1):101–127, May 2018.
  * [Sco15] Lynn Scow.  Indiscernibles, EM-Types, and Ramsey Classes of Trees.  Notre Dame Journal of Formal Logic, 56(3):429–447, January 2015\.
  * [Sco21] Lynn Scow.  Ramsey transfer to semi-retractions.  Annals of Pure and Applied Logic, 172(3), March 2021.
  * [She90] Saharon Shelah.  Classification theory and the number of nonisomorphic models.  North-Holland Publishing, Amsterdam, 2nd edition, 1990.
  * [TT12] Kota Takeuchi and Akito Tsuboi.  On the existence of indiscernible trees.  Annals of Pure and Applied Logic, 163(12):1891–1902, December 2012\.


# The Width of a Ball in a Hypercube

Kada K Williams

(March 15, 2024)

##  1 Introduction

In [1], Sperner asked how many subsets of $[n]$, the set $\\{1,2,\dots,n\\}$,
can be selected without having one that is a proper subset of another. Since
then, this question has been extended to finite partially ordered sets –
posets for short – asking how many pairwise incomparable elements can be
picked. The answer to this question is referred to as the width of a poset.

Certainly, in a chain, a poset whose order is total, at most one element can
be chosen. Therefore, the number of pairwise incomparable elements is limited
by the number of chains required to cover the poset. Dilworth [2] proved that
conversely, denoting by $w$ the width of a poset $P$, one can partition $P$
into $w$ many chains. The subset of a poset formed by pairwise incomparable
elements is called an antichain.

Expanding on Dilworth’s ideas, if $(P,<)$ is a poset and $x\in P$, then we
consider the height of $x$, the largest non-negative value $h$ such that one
can find elements $x_{0},x_{1},\dots,x_{h}\in P$ such that
$x_{0}<x_{1}<\dots<x_{h}$ and $x=x_{h}$. For example, regarding subsets of
$[n]$, any $k$-element subset has height $k$, because descending to a proper
subset means removing at least one element. Let $P_{h}$, the layer $h$, denote
the set of $x\in P$ with height $h$. Then for $P=\mathcal{P}([n])$, the family
of subsets of $[n]$, we observe that $P_{h}$ is the family of $h$-element
subsets.

A modern approach to Sperner’s theorem [3] exploits the symmetry of
$\mathcal{P}([n])$. First, one sees that
$\emptyset\subset[1]\subset[2]\subset\dots\subset[n]$ is a maximal chain that
contains an element in each layer. However, upon permuting
$\\{1,2,\dots,n\\}$, the set $[k]$ maps to every point in layer $k$ equally.
Now if $A$ is an antichain, then at most one $x\in A$ can appear in a chain.
In particular, if $x$ is in layer $k$, then its chance of occurring is
${n\choose k}^{-1}$. The sum of these chances over all $x\in A$ cannot exceed
$1$:

$\sum_{x\in A}{n\choose h(x)}^{-1}\leq 1.$

More generally, let $P$ be a poset where any antichain $A$ satisfies

$\sum_{x\in A}\Big{|}P_{h(x)}\Big{|}^{-1}\leq 1.$

Such a poset is described as a KLYM poset [4] and has the simple property that
its width equals the size of its largest layer. In this vein, the width of
$\mathcal{P}([n])$ is clearly ${n\choose\lfloor n/2\rfloor}$.

Nevertheless, Greene and Kleitman [5] obtained an explicit construction that
partitions $P=\mathcal{P}([n])$ into $w(P)$ many chains. Actually, their
bracketing strategy extends to the case of a multiset power set $P$, where
$i\in[n]$ can be contained not only $0$ or $1$ times, but up to $\mu_{i}$
times. The poset in question is then isomorphic to the set of positive
divisors of $N=\prod_{i=1}^{n}p_{i}^{\mu_{i}}$ under the relation of proper
divisors. Wang and Yeh [6] provide a novel proof that $P$ has the KLYM
property, whilst $\frac{|P_{h}|}{|P_{h-1}|}$ is decreasing in $h$, via product
argument.

The problem of calculating or bounding $w(P)$ for an arbitrary subposet $P$ of
$\mathcal{P}([n])$, such as a downset [7], or the intersection of a downset
and an upset, continues to be wide open. In the spirit of Richard Hamming’s
recurring question of which problem in this field is most important, we
restrict our focus to the subposet obtained from a $p$-element set by removing
or adding at most $r$ elements.

##  2 Sublayers

Write $[n]=\\{1,\dots,p\\}\cup\\{p+1,\dots,p+q\\}$, where $q=n-p$. For the
family of sets obtained by subtracting $i$ elements of $\\{1,\dots,p\\}$ and
adding $j$ elements from $\\{p+1,\dots,p+q\\}$, write $X_{i,j}$. Here, the
subtraction and addition are independent, in the sense that
$|X_{i,j}|={p\choose i}\cdot{q\choose j}$. Since the sets in $X_{i,j}$ have
$p-i+j$ elements, their height shall depend on the value $i-j$.

15810402810801405658028028070 Figure 1: The sublayers of $B_{4}[5,8]$ and its
largest layer

######  Definition 1.

The ball of radius $r$ centered at $[p]$ in $\mathcal{P}([p+q])$ is given by

$B_{r}[p,q]=\bigcup_{i+j\leq r}X_{i,j}.$

######  Conjecture 2.

The largest layer of $B_{r}[p,q]$ is its unique largest antichain.

We can prove this conjecture in most cases, because $B_{r}[p,q]$ has the
symmetries of relabelling $\\{1,\dots,p\\}$ and $\\{p+1,\dots,p+q\\}$, and the
$|X_{i,j}|$ are well-behaved.

######  Lemma 3.

In the poset $B_{r}[p,q]$, let $\mathcal{C}$ be a weighted collection of
chains that contains a set in every layer. Of those, let $\mathcal{C}_{i,j}$
contain the chains that pass through $X_{i,j}$. In view of the proportions
$\frac{|\mathcal{C}_{i,j}|}{|X_{i,j}|}$, if there is a layer such that these
proportions are no larger outside than within, that layer is a maximal
antichain.

###### Proof.

Without loss of generality, $\mathcal{C}$ passes through all the sets in
$X_{i,j}$ an equal number of times. Indeed, $X_{i,j}$ is an orbit of the
action that relabels $\\{1,\dots,p\\}$ and $\\{p+1,\dots,p+q\\}$. Furthermore,
if $\mathcal{C}^{\prime}$ includes all $p!\cdot q!$ many images of each
$C\in\mathcal{C}$, then the proportions are scaled as
$\frac{|\mathcal{C}^{\prime}_{i,j}|}{|X_{i,j}|}=p!\cdot
q!\cdot\frac{|\mathcal{C}_{i,j}|}{|X_{i,j}|}$, thus yielding the number of
$C\in\mathcal{C}^{\prime}$ containing any given $x\in X_{i,j}$. Therefore, we
may assume that $\mathcal{C}(x)=\\{C\in\mathcal{C}|x\in C\\}$ has no larger
size outside layer $L$ than within.

Now for any antichain $A$, a chain from $\mathcal{C}$ can contain at most one
$x\in A$. Hence, the $\mathcal{C}(x)$ are disjoint, implying

$\sum_{x\in A}|\mathcal{C}(x)|\leq|\mathcal{C}|.$

Since each $C\in\mathcal{C}$ visits every layer, $A=L$ is a case of equality.
Given that $|A|=w=w(P)\geq|L|$, the left-hand sum is minimal when it contains
the smallest possible values. If $w>|L|$, then these values are given by the
values across $x\in L$, and more, in contradiction with how the sum over $x\in
L$ equals $1$. It follows that $L$ is a maximal antichain. Moreover, if
$w=|L|$, and values outside $L$ are strictly larger than values within, then
only $A=L$ is maximal. ∎

Our proof strategy, then, involves finding the largest layer and selecting a
collection of chains that passes through every point of this layer once, but
includes a point in $X_{i,j}$ no less than $|X_{i,j}|$ times for all $i,j$.

######  Observation 4.

For fixed radius $i+j-1$, the ratios $\frac{|X_{i-1,j}|}{|X_{i,j-1}|}$ are
decreasing in $j$.

###### Proof.

Since ${p\choose i}{p\choose{i-1}}^{-1}=\frac{p-i+1}{i}$, it is clear that

$\frac{|X_{i-1,j}|}{|X_{i,j-1}|}=\frac{(q-j+1)i}{(p-i+1)j}$

If $j\nearrow$, then $i\searrow$, $(q-j+1)i\searrow$, $(p-i+1)j\nearrow$, so
the fraction decreases. ∎

######  Corollary 5.

The spheres $S_{r}[p,q]=\bigcup_{i+j=r}X_{i,j}$ have the KLYM property.

###### Proof.

Let $\mathcal{C}$ contain any chain that proceeds from a minimal point by
successively adding an element of $\\{p+1,\dots,p+q\\}$ and removing an
element of $\\{1,\dots,p\\}$. Upon relabelling those elements, we obtain a
list of chains that passes through every point in a layer equally. We readily
deduce the KLYM inequality. ∎

Analytically, $\frac{|X_{i-1,j}|}{|X_{i,j-1}|}=1$ holds exactly when
$\frac{(q-j+1)i}{(p-i+1)j}=1$, which rearranges to a linear condition
$\frac{i}{j}=\frac{p+1}{q+1}$. This determines the largest layer of
$S_{r}[p,q]$.

Polynomially, $|X_{i,j}|$ has degree $i+j$ in $(p,q)$, indicating that
$B_{r}[p,q]$ resembles $S_{r}[p,q]$ in general. On the other hand, there exist
$r,p,q$ for which the largest layer of $B_{r}[p,q]$ is different from the
largest layer of $S_{r}[p,q]$.

19173615313615593761633632519792445536 Figure 2: In $B_{10}[9,17]$, sphere
layers decrease downwards from below the divide

Notice that ${p\choose i}$ increases while $i\leq\frac{1}{2}p$, and the same
is true of ${q\choose j}$, showing that provided $i+j<\frac{1}{2}(p+q)$,
incrementing $i$ or $j$ yields an $X_{i,j}$ at least as large. Hence, if
$r\leq\frac{1}{2}(p+q)$, then the largest sublayer of $B_{r}[p,q]$ is on
$S_{r}[p,q]$. For this $X_{i,j}$, let us take one chain through each $x\in
X_{i,j}$ and anticipate where it continues.

##  3 Conclusion

######  Theorem 6.

Let $r\leq\frac{1}{2}(p+q)$. Then abbreviating $B_{r}=B_{r}[p,q]$ and
$S_{r}=S_{r}[p,q]$,

$w(B_{r})\leq w(S_{2r})+w(S_{2r-2})+w(S_{2r-4})+\dots$

In fact, if $\max(p,q)=\Omega(r^{3})$, then Conjecture 2 holds.

###### Proof.

As we have seen, $\frac{i+1}{j}>\frac{p+1}{q+1}$ if and only if
$|X_{i,j}|>|X_{i+1,j-1}|$. The solution of $\frac{i+1}{j}=\frac{p+1}{q+1}$,
given $i+j=r$, satisfies $i+1+j\leq\frac{1}{2}(p+1+q+1)$, whence
$i+1\leq\frac{1}{2}(p+1)$ and $j\leq\frac{1}{2}(q+1)$. Rounding $j$ down and
$i$ up, we obtain the indices of a largest layer $X_{i,j}\subset S_{r}$. It
follows that $S_{r-1}$ has largest layer either $X_{i-1,j}$ or $X_{i,j-1}$,
both of which have size not exceeding that of $X_{i,j}$.

If $\mathcal{C}$ contains one chain that passes through every layer of
$S_{r}\cup S_{r-1}$, we are able to deduce that its width is at most
$|X_{i,j}|$. The inequality follows by induction.

Interchanging $p$ and $q$, let $q=\max(p,q)$. Further, consider that

$|X_{i,j}|-|X_{i+1,j-1}|\geq|X_{i,j-2}|$

or equivalently, $\frac{q-j+1}{j}-\frac{p-i}{i+1}\geq\frac{j-1}{q-j+2}$. For
the values of $i,j$ as before, the left-hand fraction is at least
$\frac{1}{j(i+1)}$, from least common denominators. As $q-j+2\geq q-r+3$, we
now have $q-r+3\geq j(j-1)(i+1)$, implied by
$q\geq\left(\frac{r+\frac{1}{2}}{3}\right)^{3}+r-3=\Omega(r^{3})$.

Wishing for a list $\mathcal{C}$ of chains in $B_{r}$ that strike every
$X_{i,j}$ at least once per point, let us begin with striking the largest
$X_{i,j}\subset S_{r}$ as above. Directing all chains through $X_{i,j-1}$, it
has been struck, and then we can strike $X_{i,j-2}$ as well as $X_{i+1,j-1}$,
according to the bound. This can be iterated all the way down, as the bound
stays in range. Going upward from $X_{i,j}$, it suffices to zigzag in
$S_{r-1}\cup S_{r}$. Since chains through that $X_{i,j}$ can fulfill all
sublayers it covers, we are free to keep $x\cap[p]$ fixed for chains
descending from $x\in X_{i-l,j-l}$, $l=1,2,\dots$, zigzagging upwards. This
completes the proof, according to the Lemma. ∎

Although our Conjecture can be verified case by case with ideas presented
here, a comprehensive proof is unknown as of yet.

## References

  * [1] Sperner, E. Ein Satz über Untermengen einer endlichen Menge. Mathematische Zeitschrift 27, 544-548, 1928.
  * [2] Dilworth, R. P. A Decomposition Theorem for Partially Ordered Sets. Annals of Mathematics 51, 161-165, 1950.
  * [3] Yamamoto, K. Logarithmic Order of Free Distributive Lattice. Journal of the Mathematical Society of Japan 6 (3-4), 343–353, 1954.
  * [4] Daykin, D. E. and Frankl, P. Inequalities for Subsets of a Set and KLYM Posets. SIAM Journal on Algebraic and Discrete Methods 4 (1), 67-69, 1983.
  * [5] Greene, C., Kleitman, D. Strong Versions of Sperner’s Theorem. Journal of Combinatorial Theory 20, 80-88, 1976.
  * [6] Wang, Y. and Yeh, Y.-N. A Class of LYM Orders in Divisor Lattices. Taiwanese Journal of Mathematics 12 (4), 991-996, 2008.
  * [7] Duffus, D., Howard, D., Leader, I. B. The Width of Downsets. European Journal of Combinatorics 79, 46-59, 2019.

Department of Pure Mathematics and Mathematical Statistics, University of
Cambridge, Wilberforce Road, Cambridge CB3 0WB.

E-mail address<EMAIL_ADDRESS>