2 Generalized indiscernibility

In model theory, it is often useful to study collections of elements (or tuples) from a structure which are particularly uniform—which “look similar” from the perspective of that structure. One notion of uniformity is that of an indiscernible sequence. Indiscernible sequences are central for the definition of many model-theoretic terms—in particular, dividing, forking, and the entire study of independence notions. This naturally suggests that other forms of indiscernibility may be a rich ground for research. Generalized indiscernibles are found in some form in [Reference Shelah20], and have been employed in numerous contexts since then. I primarily follow the presentation and treatment from [Reference Scow16].

Definition 2.1. Suppose $\mathcal {I}$ is an $L'$ -structure and M is an L-structure. Let ${A=(a_i)_{i\in \mathcal {I}}}$ be a collection of tuples from M. Then we say that A is a generalized indiscernible (set), and in particular, an $\mathcal {I}$ -indexed indiscernible (set) if, for all $n\geq 1$ and $i_0,i_1,\dots , i_{n-1},j_0,j_1,\dots , j_{n-1}\in \mathcal {I}$ , if $\text {qftp}_{\mathcal {I}}(i_0,\dots , i_{n-1})=\text {qftp}_{\mathcal {I}}(j_0,\dots , j_{n-1})$ , then

$$ \begin{align*}\text{tp}_M(a_{i_0},\dots a_{i_{n-1}})=\text{tp}_M(a_{j_0},\dots, a_{j_{n-1}}).\end{align*} $$

Whenever indiscernibility is discussed in this article, one could add “over a set of parameters C,” as usual. Unless otherwise stated (e.g., in the definition of dividing) we work over the empty set of parameters, for convenience.

Indiscernible sequences found so much utility in part because they are so plentiful. Applications of Ramsey’s theorem and compactness allow one to find indiscernible sequences that “look like” any arbitrary sequence of tuples in the monster model of any theory. This property, the modeling property, carries over to all other notable kinds of indiscernibles. What it means for a collection of tuples indexed by some structure to “look like” another is the following.

Definition 2.2. Suppose $\mathcal {I}, \mathcal {J}$ are two $L^*$ -structures expanding a linear order, $M,N$ are models of an L-theory, and $A=\{a_i\colon i\in \mathcal {I}\}$ is a set of parameters in M. Then we say that a set of parameters $B=\{b_i\colon i\in \mathcal {J}\}$ from N is locally based on A, (or that the $b_i$ are locally based on the $a_i$ ), if for any finite set $\Delta $ of L-formulas, and any finite tuple $\bar {t}=t_1\dots t_n$ from $\mathcal {J}$ , there exists a tuple $\bar {s}=s_1\dots s_n$ in $\mathcal {I}$ such that

$$\begin{align*}\text{qftp}_{\mathcal{J}}(\bar{t})=\text{qftp}_{\mathcal{I}}(\bar{s})\enspace \text{and}\enspace \text{tp}_N^\Delta(\bar{b}_{\bar{t}})=\text{tp}_M^\Delta(\bar{a}_{\bar{s}}).\end{align*}$$

Thus we may define the modeling property.

In [Reference Scow16], Scow proved that, under some natural assumptions, a structure $\mathcal {I}$ has the modeling property precisely when its age is a Ramsey class, that is, when a structural version of Ramsey’s theorem holds. The modeling property is what concerns us in this article, so we avoid deeper discussion of the Ramsey property, but are happy to borrow this name for “good” index structures, in keeping with convention. See, for instance, [Reference Scow18] for details on the Ramsey property. Scow’s result extends the classical proof, using Ramsey’s theorem, that infinite linear orders have the modeling property to the generalized indiscernible setting. We state the theorem in a form with the technical assumptions dropped, as was proved possible in [Reference Scow19], as well as in [Reference Meir and Papadopoulos14].

Henceforth, index structures with Ramsey ages, or equivalently, those with the modeling property, will be called Ramsey index structures. Many natural examples of Ramsey index structures have been discovered, and their correspondent types of indiscernibles have found deep and widespread use. The ordered random graph in the language $\{<, R\}$ is Ramsey, and it was employed in [Reference Scow17] to prove a collapse of indiscernibles result for the IP. Tree structures in various languages have been among the earliest and most fruitful Ramsey structures, appearing first in [Reference Shelah20], receiving treatment in [Reference Kim, Kim and Scow10, Reference Takeuchi and Tsuboi23], and finding numerous applications in the study of model-theoretic TPs (such as $\text {TP}_1$ and $\text {TP}_2$ ) in [Reference Chernikov and Ramsey5, Reference Kaplan and Ramsey8], for example. We will return to tree indiscernibles in Section 3.

As Ramsey theory is a subject of mathematical interest independent of model theory, there are many classes of structures known to be Ramsey, and techniques for producing more. With these in hand, Scow’s Theorem 2.4 provides a dictionary which furnishes model theorists with numerous ready-made Ramsey index structures. A particularly useful result from Ramsey theory, which will give us our main index structure for this article, is due to Nešetřil and Rödl [Reference Nešetřil and Rödl15]. It states that if $\tau $ is a relational language and $<$ a binary relation, then the class of all $\tau \cup \{<\}$ -structures in which $<$ is interpreted as a linear order and which forbid a collection of finite irreducible substructures is a Ramsey class.

This brings us to the colored linear order, a central index structure for the results which follow.

Each structure c is Ramsey, by the result of Nešetřil and Rödl above: $<$ is a linear order, while a family of 1-element (hence irreducible) structures is omitted, namely the structures consisting of an element which falls into 0 or $\geq 2$ distinct color predicates. The reduct of c to $<$ is a dense linear order. All of the colors are dense in this structure. This article’s interest in colored linear orders where the colors are dense is notably different from Malliaris and Shelah’s use of colored linear orders index structures elsewhere in the model-theoretic literature. In [Reference Malliaris and Shelah12], in particular the proof that the theory of the random graph is not maximal in the $\trianglelefteq ^*_1$ order (Theorem 5.5), Malliaris and Shelah utilize colored linear orders which are “separated,” that is, where every element of the linear order has a unique color. We are interested in the Frïassé limit, in which each color is dense.

However, even though c, properly speaking, has the order type of a dense linear order without endpoints, compactness allows us to be flexible with what colored order we consider, as long as we maintain the correct age.

This follows by an elementary application of the compactness theorem. As we will see, this fact affords us flexibility to take c to be of a convenient order type, when we wish. With that in mind, we introduce the following notation.

Notation 2.7. For finite k, let $\omega -\textbf {c}_k$ denote the k-colored linear order with order type $\omega $ which cycles through the colors sequentially. More carefully, in the language with $<$ and k-many color predicates $c_0,\dots , c_{k-1}$ , we take $\omega -\textbf {c}_k$ to be the structure $(\omega ;<, c_0, c_1,\dots , c_{k-1})$ in which, for $j\in \omega $ and $i<k$ ,

$$ \begin{align*}\omega-\textbf{c}_k\models c_i(j)\iff i=j\mod k.\end{align*} $$

In particular, $\omega -\textbf {c}_2$ has even elements of one color (call it “red”) and odd elements of another (call it “green”); this is the example which will be used most in this article. When the number of colors k is fixed and clear from context, we may refer to $\omega -\textbf {c}$ . We may add parentheses around $\omega -\textbf {c}_k$ when it makes notation clearer.

Observe that, for each $k<\omega $ , $\omega -\textbf {c}_k$ has the same age as $\textbf {c}_k$ , so they may be used interchangeably by Remark 2.6.

Additionally, the following notation will be helpful for succinctly describing quantifier-free types in the language of colored linear orders.

3 New tree indiscernibilities

While c is, in a sense, the only particular Ramsey index structure we are concerned with in this article, there is another class of index models which are essential. These are natural generalizations of the tree index structures, and give generalizations of the tree indiscernibilities, which have received considerable prior attention. I follow the terminology for these structures established in [Reference Kim, Kim and Scow10]. Three main languages for trees have been used to treat them as index structures. All of them contain the tree partial order $\trianglelefteq $ , as well as the lexicographic order $<_{lex}$ and the meet function $\land $ .

In this article, we shall only be concerned with $L_0$ and $L_{s}$ . When regarded as $L_0$ - and $L_{s}$ -structures, the trees $\lambda ^{<\kappa }$ , where $\lambda $ and $\kappa $ are infinite cardinals, are all Ramsey index structures. They are thus well-suited to serve as index structures for indiscernibles. The interest in tree indiscernibles lies centrally in the fact that TPs, like TP and $\text {TP}_1$ , require that there be a tree-indexed collection of parameters $(a_\eta )_{\eta \in \omega ^{<\omega }}$ satisfying various properties (see Definitions 5.1 and 6.1), and it is often helpful, when manipulating such a tree of parameters, that it have the uniformity guaranteed by indiscernibility. However, witnesses to TP and $\text {TP}_1$ cannot be taken to have the same “degree” of indiscernibility, since they demand different things of the tree of parameters: TP can, in general, only have the weaker $L_s$ -indiscernibility, while a witness to $\text {TP}_1$ can be taken as $L_0$ -indiscernible. This is an instance of the broader phenomenon with generalized indiscernibles: If $\mathcal {J}$ is a reduct of $\mathcal {I}$ , we have that $\mathcal {J}$ indiscernibility implies $\mathcal {I}$ indiscernibility. This is immediate from Definition 2.1, since the reduct language has fewer quantifier-free types, and so more tuples are required to have the same types in order to attain indiscernibility.

Some of the central results of this article concern generalizations of TP and $\text {TP}_1$ which demand the existence of a collection of parameters indexed by $\mathcal {I}^{<\kappa }$ , where $\mathcal {I}$ is a Ramsey index structure. As in the classical context, indiscernible witnesses to these properties are often useful. But $\mathcal {I}^{<\kappa }$ calls for a richer language than the tree languages above, and thus of new indiscernibility results. Fortunately, both are easily adapted.

On the set $\mathcal {I}^{<\kappa }$ , these languages are interpreted as follows: The tree partial order $\trianglelefteq $ is interpreted as usual, as is the lexicographic order, which respects the total ordering of $\mathcal {I}$ . The predicate $P_{\alpha }$ is taken to hold of all $\nu \in \mathcal {I}^{\alpha }$ , that is, the $\alpha $ th level of the tree. $L_{\mathcal {I}}$ is interpreted such that given any $\eta \in \mathcal {I}^{<\kappa }$ , the set of nodes immediately following $\eta $ is isomorphic to $\mathcal {I}$ . No relations are taken to hold between different copies of $\mathcal {I}$ .

The traditional notions of tree indiscernibility may be seen as special cases of this definition. This may be done by regarding $\omega $ as $(\omega ,<)$ , an infinite linear order and Ramsey index structure. The linear order introduced is redundant with the lexicographic order restricted to each copy of $\omega $ in the tree.

The fact that $(\omega , <)$ is Ramsey (i.e., that Ramsey’s theorem holds) figures into the proof that $L_{s,\kappa }$ -trees have the modeling property, in particular in Claim 4.9 of [Reference Kim, Kim and Scow10]. That proof goes through identically to show that $L_{s,\kappa ,\mathcal {I}}$ -trees have the modeling property for $\mathcal {I}$ Ramsey, simply using the fact that $\mathcal {I}$ has the modeling property when one comes to Claim 4.9. Though the proof in [Reference Kim, Kim and Scow10] only addresses trees of height $\omega $ , it may be adapted to height $\kappa $ trees by compactness. Showing Ramseyness via the modeling property requires demonstrating the consistency of a partial type (the union of the generalized Ehrenfeucht–Mostowski type of the original tree-indexed structure and the partial type asserting tree indiscernibility), and by compactness, it suffices to show the consistency of a finite subset of this partial type. This can only mention finitely many levels of the tree, so the arguments for an $\omega $ -high tree go through for a $\kappa $ -high one. See, for instance, [Reference Chernikov and Ramsey5, Lemma 3.6] for a similar argument about arbitrary-height trees. Thus we have the following.

Extending to the stronger notion of indiscernibility, that which uses $L_{0,\mathcal {I}}$ , likewise only makes use of the fact that $(\omega ,<)$ is Ramsey. This may be seen in [Reference Takeuchi and Tsuboi23], where the authors bootstrap the fact that $L_{s}$ trees have the modeling property to find that $L_{str}$ - and finally $L_0$ -trees likewise have it (Theorems 15 and 16, respectively).Footnote ² Thus, the correspondent generalized tree indiscernibilities also go through. While that paper also only addresses height $\omega $ trees, we may again use compactness to extend to trees of arbitrary height.

The final notion of indiscernibility needed in this article is a correspondent of strong array indiscernibility, which will be useful in discussion of generalized $\text {TP}_2$ below. While $\text {TP}_2$ is defined in terms of arrays $(a_{i,j})_{i<\kappa ,j<\lambda }$ (see Definition 6.4), we will use as index structure arrays in which the rows are copies of some Ramsey index structure $\mathcal {I}$ , namely $(a_{i,j})_{i<\kappa ,j\in \mathcal {I}}$ .

By Lemmas 1.2 and 1.3 of [Reference Chernikov4], given any array indexed by $\kappa \times \lambda $ with the structure of a convexly ordered equivalence relation (where the rows are equivalent), one may find a strongly indiscernible array locally based on it. As with the tree results, only the fact that rows have Ramsey index structures is needed for the proof. Thus we may generalize.

We likewise give $\kappa \times \mathcal {I}$ the structure of a convexly ordered equivalence relation, where the copies of $\mathcal {I}$ are equivalence classes. As in Definition 3.2, we assume that $L_{\mathcal {I}}$ is relational, and give each row $\{\alpha \}\times \mathcal {I}$ an interpretation of $L_{\mathcal {I}}$ so that it is isomorphic to $\mathcal {I}$ .Footnote ³

4 Generalized dividing and q-inconsistency

Generalized dividing is, naturally, a generalization of the classical notion of dividing, replacing the linear order with different kinds of Ramsey index structures.

Generalized dividing is defined in the most straightforward way possible: simply replace the indiscernible sequence in the definition of dividing with a generalized indiscernible.

Generalized dividing can be seen as a simplified version of the notion of shearing, defined in [Reference Malliaris and Shelah13]. Shearing likewise generalizes dividing to address indiscernibles with richer index structures. However, a number of differences exist between the notions. Most importantly for the contents of this article, generalized dividing allows for inconsistency to be given by indices with different quantifier-free types, such as the different colors of c. Shearing, by contrast, requires that inconsistency occur among elements indexed by tuples with the same quantifier-free type.

When a formula divides, the set of formulas $\{\varphi (x,a_i)\colon i\in \omega \}$ is said to be k-inconsistent, for a natural number k. The notion of k-inconsistency falls out of the assumption of inconsistency. By compactness, some finitely many (say k-many) formulas $\{\varphi (x, a_{i_0}),\dots , \varphi (x,a_{i_{k-1}})\}$ are inconsistent, where $i_0<\dots <i_{k-1}$ . Since sequences witnessing dividing are indiscernible, it follows that for any $j_0<\dots <j_{k-1}$ , $\{\varphi (x, a_{j_0}),\dots , \varphi (x,a_{j_{k-1}})\}$ is also inconsistent—hence we get that any k formulas from the sequence are inconsistent, that is, k-inconsistency.

To address index structures where not all k-tuples have the same quantifier-free type, k-inconsistency must be generalized. To see how, consider an index structure $\mathcal {I}$ which expands a linear order. If the set of formulas $\{\varphi (x,a_i)\colon i\in \mathcal {I}\}$ is inconsistent, a finite piece of it, $\{\varphi (x, a_{i_0}),\dots , \varphi (x,a_{i_{k-1}})\}$ , must be inconsistent, by compactness. The indexing sequence may, by the modeling property, be taken to be (generalized) indiscernible, in which case any tuple $(j_0,\dots , j_{k-1})$ with the same quantifier-free type as $(i_0,\dots , i_{k-1})$ must be such that $\{\varphi (x, a_{j_0}),\dots , \varphi (x,a_{j_{k-1}})\}$ is inconsistent. Thus, there must be some complete quantifier-free type q such that any tuples satisfying it give inconsistent formulas. This motivates the following definition.

Definition 4.3. (q-inconsistent) Given a formula $\varphi (x,y)$ and a set of tuples $(a_i)_{i\in \mathcal {I}}$ , where each $a_i$ is the appropriate length for the y variable, and a complete quantifier-free k-type q in the language of $\mathcal {I}$ , we say that the set of formulas $\{\varphi (x,a_i)\colon i\in \mathcal {I}\}$ is q-inconsistent if, whenever $i_0,\dots , i_{k-1}\in \mathcal {I}$ are such that $(i_0,\dots , i_{k-1})\models q$ , then the set of formulas

$$ \begin{align*}\{\varphi(x, a_{i_0}),\dots, \varphi(x,a_{i_{k-1}})\}\end{align*} $$

is inconsistent.

It is crucial to remember that, for some index structures $\mathcal {I}$ , when there is q-inconsistency, there may be an infinite subsequence of $\mathcal {I}$ indexing a set of parameters which give consistent $\varphi $ -formulas. This will often be the case when considering colored linear orders, where q is the type of a red index less than a green index, say, and all of the red-indexed elements, taken together, are consistent, yet any red and any green are inconsistent. This occurs, for instance, in the proof that the random graph has the colored TP, Proposition 5.3 below.

Many potential avenues of research spring from the notion of generalized dividing, most of which involve replacing the classical notion with specific generalized index structures. In this vein, we first define a generalization of local character, which in the classical context, is one way of defining simple theories. It is not, as it turns out, a good generalization of that notion to index structures such as c, as we will see below. However, it can be characterized, as usual, with a generalization of dividing chains.

We will sometimes notate the set $\{a_j\colon j<i\}$ by $a_{<i}$ .

As a seemingly minor alteration to the classical linear order index model, c was the first generalized index structure with which we investigated generalized local character. However, this notion turns out to be trivially strong for c, and thus fails to carve out any interesting classificatory property of theories. Its triviality may be seen by the following fact.

The failure of c-local character to define an interesting analog of simplicity led naturally to the investigation of analogs of the TP. Classically, having local character is equivalent to omitting the TP. That would suggest that the colored analog of the TP would also be trivial. But as we shall see, that is not the case.Footnote ⁵

5 The colored tree property

The original version of the TP is defined as follows.

At first glance, there are (at least) two natural ways to generalize this to trees involving a richer index structure $\mathcal {I}$ , and in particular, to c. Certainly, k-inconsistency of siblings must be replaced by q-inconsistency. Consequently, the successors of any node in the indexing tree must form a copy of $\mathcal {I}$ . For the consistency condition, one might either ask that all paths are consistent, or just the parts of paths indexed by things with the same quantifier-free types (e.g., same color). It turns out that the latter option is equivalent to the trivial notion of c-local character, so the former is more promising. We arrive at the following definition.

By Proposition 3.3, given a tree of parameters indexed by $\mathcal {I}^{<\omega }$ , we can find an $L_{s,\omega ,\mathcal {I}}$ -insiscernible tree locally based on it. Local basedness in this language preserves witnessing $\mathcal {I}$ -TP, so we may always take $\mathcal {I}$ -TP to be witnessed by an $L_{s,\omega ,\mathcal {I}}$ -indiscernible tree of parameters.

We will see below in Theorem 5.11 that c-TP is not trivially strong, as c-local character is. At the same time, it is genuinely different from TP. This difference is demonstrated by the fact that the Rado random graph has c-TP. The random graph is a structure of interest for many reasons, but one of them is that it is an unstable theory which is simple, that is, it omits TP.

That the random graph has $\textbf {c}_2$ -TP actually implies that it has every $\textbf {c}_k$ -TP. We will observe below (Corollary 5.13) that all of the $\textbf {c}_k$ TPs collapse into one property, at the level of theories.

The random graph is not just a simple unstable theory, but the prototypical structure with the IP but not TP. Thus, it follows that all structures with IP have c-TP. The following definition of IP in terms of the alternating number is not the most traditional, but will be useful in the proof of Theorem 6.9 below. See Lemma 2.7 of [Reference Simon22] for a proof that it is equivalent to a more standard definition.

Definition 5.5. A formula $\varphi (x,y)$ is said to have the IP if there is an indiscernible sequence $(a_i)_{i<\omega }$ such that the following set of formulas is consistent:

$$ \begin{align*}\{\varphi(x,a_i)\colon i\enspace\text{is even}\}\cup\{\neg\varphi(x,a_i)\colon i\enspace\text{is odd}\}.\end{align*} $$

We have now seen that both IP and TP theories have c-TP. In proving that all unstable theories have c-TP, we make use of Shelah’s Theorem II.4.7 from [Reference Shelah20], which implies that all unstable theories take one of these two forms.

In fact, c-TP also implies instability, completing a characterization of this classical notion using the generalized TP. Just as TP can be taken to be witnessed by an $L_s$ -indiscernible tree, one can likewise take an instance of $\mathcal {I}$ -TP to be $L_{s,\kappa ,\textbf {c}}$ -indiscernible, a fact we will make ready use of in the following proof.

Proof. Suppose $\varphi (x,y)$ is a c-TP formula. Towards a contradiction, suppose $\varphi $ is stable.

Let $\mathbb {M}^{Sk}\models T^{Sk}$ be a Skolemization of the monster model in language $L^{Sk}$ . The original witness to c-TP is still a witness after Skolemizing. By compactness, we can take the tree witnessing c-TP to be of height $\kappa>2^{|L^{Sk}|+\aleph _0}$ . Since $L_{s,\kappa , \textbf {c}}$ -trees have the modeling property, we may take c-TP to be witnessed by an $L_{s,\kappa , \textbf {c}}$ -indiscernible tree in $\mathbb {M}^{Sk}$ . Say that $A=(a_{\eta })_{\eta \in \textbf {c}^{<\kappa }}$ is such an indiscernible witness.

Suppose the quantifier-free type q for which siblings are q-inconsistent mentions precisely the distinct colors $c_0, c_1,\dots , c_{m-1}$ , where $m> 1$ (otherwise we have one-color c-TP, which is just ordinary TP, hence $\varphi $ is unstable.) Suppose that $q=c_{i_0}<c_{i_1}<\dots <c_{{i_{j-1}}}$ , where the $i_0,\dots , i_{j-1}$ may or may not be distinct.

We inductively define a sequence of trees $(\textbf {T}_n)_{n<\omega }$ , along with a sequence of tree elements $(\xi _n)_{n<\omega }$ , which satisfy the following:

1. (a) $\textbf {T}_{n+1}\subseteq \textbf {T}_{n}\subseteq \textbf {c}^{<\kappa }$ .

2. (b) For $\eta ,\nu \in \textbf {T}_n$ , $\eta \land ^{\textbf {T}_n}\nu =\eta \land ^{\textbf {c}^{<\kappa }}\nu $ .Footnote ⁶

3. (c) $\xi _n\in \textbf {T}_n$ .

4. (d) $\textbf {T}_n$ has $\kappa $ -many levels.

5. (e) $\xi _n\trianglelefteq \xi _{n+1}$ and $\xi _n\neq \xi _{n+1}$ .

6. (f) The $\xi _n$ rotate through the colors $c_{i_0},\dots , c_{i_{j-1}}$ , that is, $\xi _n$ has color $c_{i_\ell }$ if, and only if,

   $$ \begin{align*}n\mod j=\ell.\end{align*} $$

7. (g) If $\xi _{n}\trianglelefteq \eta ,\nu \in \textbf {T}_{n+1}$ and $\eta ,\nu $ have the same color, then

   $$ \begin{align*}\text{tp}_{L^{Sk}}(a_\eta/\{a_{\xi_i}\colon i\leq n\})=\text{tp}_{L^{Sk}}(a_\nu/\{a_{\xi_i}\colon i\leq n\}).\end{align*} $$

Take $\xi _0$ to be an arbitrary element of $\textbf {c}^{<\kappa }$ of color $c_{i_0}$ , and let $\textbf {T}_0=\{\eta \in \textbf {c}^{<\kappa }\colon \xi _0\trianglelefteq \eta \}$ .

Now, suppose we have chosen $\xi _0,\dots , \xi _{n-1}$ and $\textbf {T}_0,\dots , \textbf {T}_{n-1}$ satisfying (a-g).

Suppose $\xi _{n-1}\triangleleft \eta ,\nu \in \textbf {T}_{n-1}$ are two indices of the same color, say $c_t$ , at the same level of $\textbf {c}^{<\kappa }$ tree, say level $\alpha $ . Then observe that

$$ \begin{align*}\text{qftp}_{L_{s,\kappa,\textbf{c}}}(\eta,\xi_0,\dots, \xi_{n-1})=\text{qftp}_{L_{s,\kappa,\textbf{c}}}(\nu,\xi_0,\dots, \xi_{n-1}).\end{align*} $$

Thus by the $L_{s,\kappa ,\textbf {c}}$ -indiscernibility of A, we have that

$$ \begin{align*}\text{tp}_{L^{Sk}}(a_\eta/\{a_{\xi_i}\colon i<n\})=\text{tp}_{L^{Sk}}(a_\nu/\{a_{\xi_i}\colon i<n\}).\end{align*} $$

So there is a single ${L^{Sk}}$ -type over $\{a_{\xi _i}\colon i<n\}$ associated with the color $c_t$ and the level $\alpha $ , call it $r_{t,\alpha }$ . Moreover, there is an m-tuple of types associated with the colors $c_0,\dots , c_{m-1}$ at level $\alpha $ ,

$$ \begin{align*}(r_{0,\alpha},r_{1,\alpha},\dots, r_{m-1,\alpha}).\end{align*} $$

By counting, observe that there are at most $2^{|L^{Sk}|+\aleph _0}$ -many such m-tuples over $\{a_{\xi _i}\colon i<n\}$ . Since, by (d), $\textbf {T}_{n-1}$ has height $\kappa $ , we may apply the Pigeonhole Principle to find a single m-tuple of color types, $(R_{0,n},R_{1,n},\dots , R_{m-1,n})$ and $X_n\subseteq \kappa $ with $|X_n|=\kappa $ such that if $\alpha \in X_n$ , then

$$ \begin{align*}(r_{0,\alpha},r_{1,\alpha},\dots, r_{m-1,\alpha})=(R_{0,n},R_{1,n},\dots, R_{m-1,n}).\end{align*} $$

Then, let $\textbf {T}_n$ be the following “restriction” of $\textbf {T}_{n-1}$ to extensions of $\xi _{n-1}$ in the levels in $X_n$ :

$$ \begin{align*}\textbf{T}_n&=\{\eta\in \textbf{T}_{n-1}\colon \xi_{n-1}\trianglelefteq\eta,\enspace\text{and}\enspace length(\eta)\in X_n,\enspace\text{and if}\enspace\\ &\qquad length(\xi_{n-1})<\beta \in\text{dom }(\eta)\setminus X_n,\enspace\text{then}\enspace \eta(\beta)=0\}.\end{align*} $$

Choose $\xi _n\in \textbf {T}_n$ of color $c_{i_\ell }$ , where $n\mod j=\ell $ .

It is immediate that $\textbf {T}_n$ and $\xi _n$ satisfy (a) and (c), and (f). (d) holds because $\textbf {T}_n$ is the restriction of a height $\kappa $ tree, $\textbf {T}_{n-1}$ , to the levels in $X_n$ , a set of size $\kappa $ . (b) holds because of the way that the restriction is defined: the meets remain constant. The inequality condition of (e) holds because $\xi _{n-1}$ and $\xi _n$ have different colors. Finally, (g) holds by the construction of $\textbf {T}_n$ : two elements of $\textbf {T}_n$ of the same color $c_\ell $ share the type $R_{\ell ,n}$ over $\{a_{\xi _i}\colon i<n\}$ . So the induction continues.

Now, consider the partial type $\{\varphi (x, a_{\xi _n})\colon n< \omega \}$ . Since (e) implies that it is a subset of the partial type determined by a particular path through A, which witnesses c-TP for $\varphi $ , we must have that this partial type is consistent. Let $p(x)$ be a complete $\varphi $ -type over $M=Sk(\{a_{\xi _n}\colon n<\omega \})$ extending this partial type. Since we assumed that $\varphi $ was stable, we must have an M formula $d_\varphi (y)$ such that $\varphi (x,c)\in p(x)$ if and only if $\mathbb {M}\models d_\varphi (c)$ .

Since $d_\varphi $ is a formula over $M=Sk(\{a_{\xi _i}\colon i<\omega \})$ , there must be some $N<\omega $ such that all of the parameters appearing in $d_\varphi $ come from $Sk(\{a_{\xi _i}\colon i<N\})$ . So there is some $L^{Sk}$ -formula $d^{\prime }_\varphi (y,z_0,\dots , z_{N-1})$ over $\emptyset $ such that, for any $c\in |\mathbb {M}|$ , we have $\mathbb {M}\models d_\varphi (c)$ if, and only if, $\mathbb {M}^{Sk}\models d^{\prime }_\varphi (c,a_{\xi _0},\dots , a_{\xi _{N-1}})$ .

Consider an arbitrary immediate successor $\eta $ of $\xi _{N-1}$ in $\textbf {T}_N$ of one of the colors $c_0,\dots , c_{m-1}$ ; I will argue that we have $\mathbb {M}\models d_\varphi (a_\eta )$ . Suppose $\eta $ has color $c_\ell $ . Consider $\xi _{N'}$ for $N'\geq N$ , with $\ell =N'\mod j$ , so $\xi _{N'}$ has color $c_\ell $ . Since $p(x)$ extends $\{\varphi (x, a_{\xi _n})\colon n<\omega \}$ , which contains $\varphi (x, a_{\xi _{N'}})$ , we have $\mathbb {M}^{Sk}\models d^{\prime }_\varphi (a_{\xi _{N'}},a_{\xi _0},\dots , a_{i_{N-1}})$ . Since $\xi _{N-1}\trianglelefteq \eta , \xi _{N'}\in \textbf {T}_N$ , and $\eta $ and $\xi _{N'}$ share color $c_\ell $ , (g) implies that

$$ \begin{align*}\text{tp}_{L^{Sk}}(a_{\xi_{N'}}/\{a_{\xi_i}\colon i<N\})=\text{tp}_{L^{Sk}}(a_{\eta}/\{a_{\xi_i}\colon i<N\}).\end{align*} $$

Hence we may conclude that $\mathbb {M}^{Sk}\models d^{\prime }_\varphi (a_\eta ,a_{\xi _0},\dots , a_{i_{N-1}})$ , and thus $\mathbb {M}\models d_\varphi (a_\eta )$ .

We have seen that $\mathbb {M}\models d_\varphi (a_\eta )$ for all children in $\textbf {T}_N$ of $\xi _{N-1}$ which are of the colors $c_0,\dots , c_{m-1}$ . Hence for all such children $\eta $ , $\varphi (x,a_\eta )$ must be in the unique nonforking extension of $p(x)$ to a type over $\mathbb {M}$ . Thus

$$ \begin{align*}\{\varphi(x, a_\eta)\colon \eta\enspace\text{is a child in }\textbf{T}_N\text{ of}\enspace \xi_{N-1} \enspace\text{of color}\enspace c_\ell\in\{c_0,\dots, c_{m-1}\}\}\end{align*} $$

is consistent. But these are the children of a common node in A of all the colors appearing in q, and hence must be inconsistent by the definition of c-TP. This is a contradiction.

As an immediate corollary of the above facts, we get the following characterization.

It follows from this fact that all of the properties $\textbf {c}_k$ -TP collapse into one property at the level of theories.

Ultimately, the fact about c used in this section is that it is Ramsey index structure which has more than one quantifier-free one type, each of which has infinitely many instances which alternate with respect to the linear order. It is therefore possible to extend this result to arbitrary index structures which meet those criteria.

Using the notion of interleavedness, it is possible to extend Theorem 5.11 to a broader collection of TPs. This corollary is likely not optimal, and it may be an interesting problem to characterize the index structures which produce a TP equivalent to instability.

As noted in Section 1, this characterization of the stability property is positive, in the sense that the definition of $\mathcal {I}$ -TP uses only $\varphi $ -formulas, never $\neg \varphi $ .

6 Colored tree properties of the first and second kinds

TP is not the only tree property of interest. Thus, knowing that c-TP characterizes stability, a subsequent research question was to understand the colored generalizations of other TPs. First among these is the TP of the First Kind ( $ \text {TP}_1$ ).

In [Reference Kim and Kim9], Kim and Kim proved that we may always take k to be equal to 2 in the definition of $\text {TP}_1$ , and the definition is often presented that way. However, the generalization to c- $ \text {TP}_1$ is more obvious when stated in the original way, with k arbitrary.

While $\mathcal {I}$ -TP could straightforwardly be defined for any Ramsey index structure $\mathcal {I}$ , the same is not true $\text {TP}_1$ . The problem is that, in order to make sense of the inconsistency of incomparables together with q-inconsistency, relations and functions must be defined between arbitrary incomparable elements of $\mathcal {I}^{<\omega }$ . The conception of $\mathcal {I}^{<\omega }$ as consisting of “copies of” $\mathcal {I}$ , each of which has as its domain the set of immediate successors of a particular node, allows us to make sense of relations and functions defined on immediate successors. Yet it is less clear how to proceed with incomparables which are not siblings. One option, which we hope to explore in future work, involves taking the index structure to be the free superposition of the tree structure with a Ramsey index structure $\mathcal {I}$ . As per a result of Bodirsky in [Reference Bodirsky2], this way of amalgamating two Ramsey structures gives a new one. However, it also introduces a new, unwanted ordering, orthogonal to the tree’s lexicographic order. For now, we stick to the simple case of colored linear orders, where it is clear how to define the correct $\text {TP}_1$ analogue. Since the expansion of the linear order in c is only unary, there is no question of how to define higher arity relation or function symbols “between” different copies of c in the tree. Hence, we solely define c- $ \text {TP}_1$ , reserving study of a more general form for future work.

We may assume that trees witnessing c- $ \text {TP}_1$ are $L_{0,\textbf {c}}$ -indiscernible: By Proposition 3.4, such trees have the modeling property, and examining the definition of c- $ \text {TP}_1$ , it is clear that a tree locally based on a witness is still a witness.

The case of TP and c-TP above might suggest that c- $ \text {TP}_1$ is a strictly weaker notion than $\text {TP}_1$ , and perhaps carves out a distinct classificatory property of theories. In fact, it recaptures precisely the same notion, even locally (up to a conjunction of the original formula). This shows that the requirement that incomparables give inconsistent formulas is a particularly strong one, leading to a “collapse” to 2- $\text {TP}_1$ , both from k- $\text {TP}_1$ and from c- $ \text {TP}_1$ .

Theorem 6.3. If $\varphi (x,y)$ has c- $ \text {TP}_1$ , then a conjunction of instances of $\varphi (x,y)$ has $\text {TP}_1$ , while if $\varphi (x,y)$ has $\text {TP}_1$ , then $\varphi (x,y)$ has c- $ \text {TP}_1$ . Therefore, a theory T has c- $ \text {TP}_1$ if, and only if, it has $\text {TP}_1$ .

Proof. If $\varphi (x,y)$ has $\text {TP}_1$ , then coloring the tree witnessing it however you like will give a witness to c- $ \text {TP}_1$ .

Suppose $\varphi (x,y)$ has $(\omega -\textbf {c})$ - $\text {TP}_1$ , witnessed by the tree of parameters $A=(a_\eta )_{\eta \in (\omega -\textbf {c})^{<\omega }}$ . Assume that q is the type $c_0<c_1<\dots <c_{k-1}$ , where $c_0,\dots , c_{k-1}$ are color predicates that may or may not be distinct from each other.

We produce a new tree, indexed by $\omega ^{<\omega }$ , which will witness $\text {TP}_1$ for the formula $\psi (x,\bar {y})=\bigwedge _{0\leq i<k}\varphi (x,y_i)$ . This tree will consist of k-tuples of successive elements from A, cycling through the colors appearing in q. The diagram below depicts the tree constructed for $k=2$ .

Define a tree of parameters $B=(b_\eta )_{\eta \in \omega ^{<\omega }}$ as follows. Let $b_\emptyset =(a_\emptyset ,\dots , a_\emptyset )$ be a k-tuple. We proceed to choose the elements of the tree, making sure that the following are all satisfied for each $\eta \in \omega ^{<\omega }$ :

1. (a) $b_\eta $ is a k-tuple $(a_{\eta _0},\dots , a_{\eta _{k-1}})$ of (possibly distinct) elements from A.

2. (b) The elements of A appearing in $b_\eta $ and its predecessors lie on some path $\nu $ from A. More carefully, let $A_{b_\eta }$ be the set $\bigcup _{\gamma \trianglelefteq \eta }\{a_\xi \colon a_\xi \text { appears in the tuple } b_{\gamma }\}$ . Then there exists a path $\nu \in \textbf {c}^\omega $ such that

   $$ \begin{align*}A_{b_\eta}\subseteq \{a_{\nu(i)}\colon i<\omega\}.\end{align*} $$

3. (c) If $\eta \neq \emptyset $ , then for each $i<k$ , $b_\eta $ contains an element of A indexed by a node colored $c_i$ .

4. (d) If $\eta \bot \nu \in \omega ^{<\omega }$ , then $\eta _i\bot \nu _j$ , for $i,j\in \{0,\dots , k-1\}$ .

Suppose we have defined $b_\eta $ satisfying these conditions, for $\eta \in \omega ^{n}$ . Since, by (a) and (b), $b_\eta $ consists of tuples from A lying on a path, $A_{b_\eta }$ contains some element with $\trianglelefteq $ -maximal index, say $\eta ^*\in (\omega -\textbf {c})^{<\omega }$ . Let $(i_\ell )_{\ell <\omega }$ be a sequence of distinct elements from $\omega -\textbf {c}$ with color $c_0$ ; take these to be the even nodes, as depicted in the diagram. Let $d_1,d_2,\dots , d_{k-1}\in \omega -\textbf {c}$ be elements of colors $c_1,c_2,\dots , c_{k-1}$ , respectively. Define

$$ \begin{align*}b_{\eta^\smallfrown\ell}=(a_{\eta^{*\smallfrown}i_\ell},a_{\eta^{*\smallfrown}i_\ell^\smallfrown d_1},\dots, a_{\eta^{*\smallfrown}i_\ell^\smallfrown d_1^\smallfrown\dots^\smallfrown d_{k-1}}).\end{align*} $$

For this new element of the tree, (a) is satisfied because it is a k-tuple, (b) is satisfied because the elements appearing in $b_{\eta ^\smallfrown \ell }$ lie on a path, (c) is satisfied, since the $i_\ell $ accounts for color $c_0$ and the $d_i$ were chosen to include all the other colors, and (d) is satisfied because the $i_\ell $ s were chosen to be distinct.

The tree B witnesses k- $\text {TP}_1$ for $\psi (x,\bar {y})$ . By condition (b), the collection of tuples indexed by paths through B consist of elements appearing on paths through the original tree A. Since instances of $\varphi $ along those paths are consistent, as a witness to $(\omega -\textbf {c})$ - $\text {TP}_1$ , the paths in the new tree will likewise be consistent for $\psi $ , as it is a conjunction of instances of $\varphi $ . Now, by (c) and (d), each k-tuple of incomparable $\eta _0,\dots , \eta _{k-1}\in \omega ^{<\omega }$ index elements containing incomparables $a_{\nu _0}, a_{\nu _1},\dots ,a_{\nu _{k-1}}$ such that $(\nu _0,\dots , \nu _{k-1})\models q$ . Hence the formulas $\{\varphi (x, a_{\nu _0}),\varphi (x, a_{\nu _1}),\dots , \varphi (x,a_{\nu _{k-1}})\}$ must be inconsistent, by the q-inconsistency of A. Hence the formulas $\{\psi (x,b_{\eta _0}),\dots , \psi (x,b_{\eta _{k-1}})\}$ must be inconsistent, so we have k- $\text {TP}_1$ . Note that $\psi (x,\bar {y})$ is a conjunction of instances of $\varphi (x,y)$ .

We may also define a modified version of the TP of the Second Kind ( $\text {TP}_2$ ). Here is the original definition.

Unlike with $\text {TP}_1$ , $\text {TP}_2$ introduces no issues for offering a generalized definition.

With this definition, it may immediately be observed that the random graph again provides a distinction between c- $ \text {TP}_2$ and $\text {TP}_2$ .

With this fact in hand, we may observe through soft methods that a dichotomy theorem, analogous to Shelah’s result that T has TP if, and only if, T has $\text {TP}_1$ or $\text {TP}_2$ , holds in the colored context.

We noted that the random graph has IP. It is no coincidence that this structure, typical for simple theories with IP, has c- $ \text {TP}_2$ . For it turns out that c- $ \text {TP}_2$ is equivalent to IP for theories.

In the next proof, the following notation for the partial type determined by a path through an array will be helpful.

Notation 6.8. Suppose that $f\colon \omega \to \mathcal {I}$ is a path through an array of tuples $(a_{i,j})_{i\in \omega , j\in \mathcal {I}}$ . Then let

$$ \begin{align*}p_f(x)=\{\varphi(x,a_{i, f(i)})\colon i\in\omega\}.\end{align*} $$

Theorem 6.9. If a formula $\varphi (x,y)$ has c- $ \text {TP}_2$ , then a conjunction of positive instances of $\varphi (x,y)$ has IP. If a formula $\varphi (x,y)$ has IP, then a conjunction of positive and negative instances of $\varphi $ has c- $ \text {TP}_2$ . Therefore, a theory T has c- $ \text {TP}_2$ if, and only if, it has IP.

Proof. The first statement of the theorem is the only one which needs to be proved, since the implication from IP to $\text {TP}_2$ follows from the random graph example (Example 6.6; note that the instance of c- $ \text {TP}_2$ found there uses the conjunction of a positive and negative instance of the formula witnessing IP). Suppose that $\varphi (x,y)$ has $\textbf {c}_k$ - $\text {TP}_2$ for some $k<\omega $ , witnessed by a colored array $A=(a_{i,j})_{i\in \omega , j\in \textbf {c}_k}$ , for a complete quantifier-free type q. Note that we can take A to be a strongly c-indiscernible array by Proposition 3.7; local basedness will preserve the fact that the array witnesses $\textbf {c}_k$ - $\text {TP}_2$ .

The proof proceeds by induction on the number of variables in q. If q has only one color, then restricting A to elements indexed by that color would give an instance of ordinary $\text {TP}_2$ , and hence $\varphi (x,y)$ would have IP. The implication from $\text {TP}_2$ to IP was originally proved by Shelah in [Reference Shelah20, Chapter III, Section 7]; a brief, self-contained proof can be found as Proposition 3.5 of [Reference Chernikov4].Footnote ⁷

Therefore, the minimal number of variables appearing in q is 2. So assume for the base case of our induction that q is the complete quantifier-free type of two indices, stating that they have distinct colors in a particular order, say $R<G$ . Suppose $j_0\in \textbf {c}_k$ is a red index and $j_1\in \textbf {c}_k$ is a green index such that $j_0<j_1$ . Let $g\colon \omega \to \textbf {c}_k$ be the path where $g(i)=j_0$ if i is even, and $g(i)=j_1$ if i is odd. So this is a path alternating between a particular red element and a particular green element in $\textbf {c}_k$ . As g is a path through a $\textbf {c}_k$ - $\text {TP}_2$ instance, $p_g(x)=\{\varphi (x,a_{i,g(i)})\colon i<\omega \}$ is consistent. Take a complete A-type $p(x)$ extending $p_g(x)$ . Consider the formulas $\varphi (x, a_{i,j_1})$ for i even. By our choice of g, $\varphi (x,a_{i,j_0})$ is in p. But since $(j_0,j_1)\models q$ , we must have $\{\varphi (x, a_{i,j_0}), \varphi (x, a_{i,j_1})\}$ inconsistent. So $\neg \varphi (x, a_{i,j_1})\in p(x)$ . Thus the set of formulas $\{\varphi (x, a_{i,j_1})\colon i\enspace \text {is odd}\}\cup \{\neg \varphi (x, a_{i,j_1})\colon i\enspace \text {is even}\}$ is a subset of p, and hence consistent. But since A is an indiscernible array, $(a_{i, j_1})_{i\in \omega }$ is an indiscernible sequence. We conclude that $\varphi (x,y)$ has IP; this completes the base case.

For the induction, it will be helpful to name individual elements of $\textbf {c}_k$ , so for convenience, we will assume that $\varphi (x,y)$ witnesses $(\omega -\textbf {c}_k)$ - $\text {TP}_2$ . Assume for an inductive hypothesis that, for any $k\in \omega $ , if $\varphi (x,y)$ has $(\omega -\textbf {c}_k)$ - $\text {TP}_2$ given by a quantifier-free type q of at most m-many variables, then some conjunction of instances of $\varphi (x,y)$ has IP.

Now suppose $\varphi (x,y)$ witnesses $\textbf {c}_k$ - $\text {TP}_2$ with a quantifier-free type q that has $m+1$ -many variables. Assume that q implies $c_0<\dots <c_{m-2}<R<G$ , where the $c_i$ are colors which may or may not be distinct from each other and from $R,G$ . While there are cases where the last two colors may be the same, there will always be some two adjacent distinct colors, and by symmetry, we may take these to be the last two.

Let $j_0<j_1<j_2<\dots <j_{m-1}<j_{m}\in (\omega -\textbf {c}_k)$ be elements of the colors $c_0,c_1,\dots , c_{m-2},R,G$ , respectively. In the illustration below, we assume $j_s=s$ . Define the following paths $f_0,\dots , f_{m-2},h$ . For $i<m-1$ , let $f_i\colon \omega \to (\omega -\textbf {c}_k)$ be the constant function $f_i(k)=j_i$ . Let $h\colon \omega \to (\omega -\textbf {c}_k)$ be defined by $h(k)=j_{m-1}$ if k is even, and $h(k)=j_{m}$ if k is odd. Like the path g defined above, this path alternates between a red and a green element of $\omega -\textbf {c}_k$ .

Denote by $p_{\bar {f}h}(x)$ the union of the partial types $p_{f_0}(x)\cup p_{f_1}(x)\cup \dots \cup p_{f_{m-2}}(x)\cup p_h(x)$ . We consider two cases, based on whether $p_{\bar {f}h}(x)$ is consistent.

1. (1) Suppose $p_{\bar {f}h}(x)$ is consistent. Then consider a complete A-type $p(x)$ extending it. We proceed as with the base case. Since the array is q-inconsistent, our choices of $j_i$ imply that for any $k\in \omega $ , the formulas $\{\varphi (x, a_{k,j_0}), \varphi (x, a_{k,j_1}),\dots , \varphi (x, a_{k, j_{m}})\}$ are inconsistent. Yet we also have for even k,

   $$ \begin{align*}\{\varphi(x, a_{k,j_0}), \varphi(x, a_{k,j_1}),\dots, \varphi (x, a_{k, j_{m-1}})\}\subseteq p_{\bar{f}h}(x)\subseteq p(x).\end{align*} $$

   Thus, by the completeness of p, $\neg \varphi (x,a_{k,j_{m}})\in p(x)$ . Moreover, for k odd, $h(k)=j_m$ , so $\varphi (x,a_{k,j_m})\in p(x)$ . Hence we may conclude that

   $$ \begin{align*}\{\varphi(x, a_{k,j_{m}})\colon k\enspace\text{is odd}\}\cup \{\neg\varphi(x, a_{k,j_{m}})\colon k\enspace\text{is even}\}\end{align*} $$

   is a subset of p, and thus consistent. Since the sequence $(a_{k,j_{m}})_{k\in \omega }$ is indiscernible, as a consequence of array indiscernibility, we have a witness to $\varphi $ having IP.

2. (2) Suppose $p_{\bar {f}h}(x)$ is inconsistent. Then by compactness there is some even integer $K\in \omega $ such that $p_{f_0|_K}(x)\cup p_{f_1|_K}(x)\cup \dots \cup p_{f_{m-2}|_K}(x)\cup p_{h|_K}(x)$ is inconsistent. We then define a new colored array $B=(b_{i,j})_{i\in \omega , j\in (\omega -\textbf {c}_{m})}$ which witnesses $(\omega -\textbf {c}_{m})$ - $\text {TP}_2$ for the formula $\psi (x, \bar {y})=\bigwedge _{i<K}\varphi (x,y_i)$ . Note that in defining this new array we may have changed the number of colors, so the horizontal index structure is $\omega -\textbf {c}_{m}$ rather than $\omega -\textbf {c}_k$ . Since the induction hypothesis was stated for arbitrary $\textbf {c}_k$ , this change is fine.

   This new array will have r-inconsistency for a quantifier-free type r in m-many variables, allowing us to apply the inductive hypothesis. Let $j\in (\omega -\textbf {c}_{m})$ have color $e_\ell $ if and only if $\ell =j\mod m$ .

   For each level i of the array, we choose “blocks” consisting of height-K portions of the original array A determined by the paths $f_0,\dots , f_{m-1}, h$ . In brief, the blocks determined by $f_0,\dots , f_{m-1}$ are constant height-K sequences, while the blocks determined by h are height-K sequences which alternate between two columns as h does. In the following diagram, the vertical boxes depict $f_i$ blocks in the case where $K=4$ , while the gray highlighted parameters comprise one h block.

   

   More precisely, we define the new array as follows. Each $b_{i,j}$ is a K-tuple, and for $t<K$ , we denote by $b_{i,j}[t]$ the tth coordinate of $b_{i,j}$ .

   If $j\mod m=\ell $ , for $\ell <m-1$ , let

   $$ \begin{align*}b_{i,j}[t]=a_{i\cdot K+t,j_\ell}.\end{align*} $$

   If $j\mod m=m-1$ , then we take an “alternating” path, letting

   $$ \begin{align*}b_{i,j}[t]=\begin{cases} a_{i\cdot K+t, j_{m-1}}, & t \enspace \text{is even}.\\ a_{i\cdot K+t, j_m}, & t\enspace \text{is odd}. \end{cases}\end{align*} $$

   I claim that B witnesses $(\omega -\textbf {c}_{m})$ - $\text {TP}_2$ for $\psi (x,\bar {y})$ with $r=e_0<e_1<\dots <e_{m-1}$ . First we check that paths are consistent. Observe that the blocks forming the elements of B are “properly consecutive,” that is, for each $j\in (\omega -\textbf {c}_{m})$ , $b_{i,j}$ contains elements of A from only the consecutive levels

   $$ \begin{align*}i\cdot K, i\cdot K+1,\dots, i\cdot K+K-1.\end{align*} $$

   Moreover, only one element from each of these levels of A appears in $b_{i,j}$ . As a consequence, paths in the new array correspond to paths in the original: if $d\colon \omega \to (\omega -\textbf {c}_{m})$ is a path through B, there is a path $d'\colon \omega \to (\omega -\textbf {c}_k)$ such that

   $$ \begin{align*}p_{d'}(x)\vdash\{\psi(x, b_{i,d(i)})\colon i\in \omega\}.\end{align*} $$

   Since $p_{d'}(x)$ is consistent, as paths are consistent for the original $(\omega - \textbf {c}_k)$ - $\text {TP}_2$ witness, we must have that $\{\psi (x, b_{i,d(i)})\colon i\in \omega \}$ is consistent.

   Now, to check that levels are r-inconsistent, we use the strong c-indiscernibility of the original array to reduce to the inconsistency of $p_{f_0|_K}(x)\cup p_{f_1|_K}(x)\cup \dots \cup p_{f_{m-2}|_K}(x)\cup p_{h|_K}(x)$ .

   Consider $j_0',j_1',\dots ,j_{m-1}'\in (\omega -\textbf {c}_{m})$ such that $(j_0',j_1',\dots ,j_{m-1}')\models r$ . So $j_0'<j_1'<\dots <j_{m-1}'$ and $j_s'$ has color $e_s$ . We want to conclude that, for any $i<\omega $ , $\{\psi (x,b_{i,j_0'}),\dots , \psi (x, b_{i,j_{m-1}'})\}$ is inconsistent.

   (Step 1): First, we observe that we may reduce to considering the first row of the array B, that is, $\{\psi (x,b_{i,j_0'}),\dots , \psi (x, b_{i,j_{m-1}'})\}$ is inconsistent if and only if $\{\psi (x,b_{0,j_0'}),\dots , \psi (x, b_{0,j_{m-1}'})\}$ is inconsistent. This uses the strong c-indiscernibility of A: For $i\in \omega $ , the row $(b_{i,j})_{j\in (\omega -\textbf {c}_{m})}$ consists of elements from K consecutive rows in A. Since the array A is strongly c-indiscernible, it consists of an indiscernible sequence of rows, hence the type of any K consecutive rows is the same. Hence

   $$ \begin{align*}\text{tp}((b_{i,j})_{j\in (\omega-\textbf{c}_{m})})=\text{tp}((b_{0,j})_{j\in (\omega-\textbf{c}_{m})}).\end{align*} $$

   So in particular, $\text {tp}(b_{i,j_0'},\dots , b_{i,j_{m-1}'})=\text {tp}(b_{0,j_0'},\dots , b_{0,j_{m-1}'})$ . This allows us to conclude that $\{\psi (x,b_{i,j_0'}),\dots , \psi (x, b_{i,j_{m-1}'})\}$ is inconsistent if and only if $\{\psi (x,b_{0,j_0'}),\dots , \psi (x, b_{0,j_{m-1}'})\}$ is inconsistent.

   (Step 2): Now, we use the fact that $p_{f_0|_K}(x)\cup p_{f_1|_K}(x)\cup \dots \cup p_{f_{m-2}|_K}(x)\cup p_{h|_K}(x)$ is inconsistent to conclude that $\{\psi (x,b_{0,j_0'}),\dots , \psi (x, b_{0,j_{m-1}'})\}$ is inconsistent. In brief, this is simply because each formula $\psi (x, b_{0,j_w'})$ is the conjunction of precisely the $\varphi $ -instances appearing in the respective partial types determined by the first K values of the functions $f_0,\dots , f_{m-2},h$ .

   More carefully, for $s<m-1$ , observe that since $j_s'$ has the color, $e_s$ , we have $b_{0,j_s'}=(a_{0, j_s},a_{1,j_s},\dots , a_{K-1,j_s})$ . So

   $$ \begin{align*}\psi(x,b_{0,j_s'})=\bigwedge_{i<K}\varphi(x,a_{i,j_s})\equiv p_{f_s|_K}(x).\end{align*} $$

   For $s=m-1$ , we have $b_{0,j_s'}=(a_{0, j_{m-1}},a_{1,j_{m}},\dots , a_{K-2,j_{m-1}},a_{K-1,j_{m}})$ , so

   $$ \begin{align*}\psi(x,b_{0,j_s'})=\bigwedge_{\substack{i<K\\i\enspace \text{even}}}\varphi(x,a_{i,j_{m-1}})\land \bigwedge_{\substack{i<K\\i\enspace \text{odd}}}\varphi(x,a_{i,j_{m}})\equiv p_{h|_K}(x).\end{align*} $$

   All together, we have that $\{\psi (x,b_{0,j_0'}),\dots , \psi (x, b_{0,j_{m-1}'})\}$ is equivalent to

   $$ \begin{align*}p_{f_0|_K}(x)\cup p_{f_1|_K}(x)\cup\dots\cup p_{f_{m-2}|_K}(x)\cup p_{h|_K}(x),\end{align*} $$

   which was inconsistent by assumption.

   By Step 1, we conclude that $\{\psi (x,b_{i,j_0'}),\dots , \psi (x, b_{i,j_{m-1}'})\}$ is inconsistent, demonstrating the r-inconsistency of rows. So we have a witness to $(\omega -\textbf {c}_{m})$ - $\text {TP}_2$ with quantifier-free type r of length m, so by our inductive hypothesis, we have an instance of IP consisting of conjunctions of $\varphi (x,y)$ .