ON UNSUPERSTABLE THEORIES IN GDST

Abstract

We study the $\kappa $-Borel-reducibility of isomorphism relations of complete first-order theories by using coloured trees. Under some cardinality assumptions, we show the following: For all theories T and T’, if T is classifiable and T’ is unsuperstable, then the isomorphism of models of T’ is strictly above the isomorphism of models of T with respect to $\kappa $-Borel-reducibility.

1 Introduction

The interaction between Generalized Descriptive Set Theory (GDST) and Classification theory has been one of the biggest motivation to study the Borel reducibility in the Generalized Baire spaces. One of the main questions is to determine if there is a counterpart of Shelah’s Main Gap Theorem in the Generalized Baire Spaces (provable in ZFC). In [9] Mangraviti and Motto Ros study this for classifiable shallow theories. In [6] Hyttinen, Weinstein (né Kulikov), ¹ and Moreno showed the consistency of a counterpart of Shelah’s Main Gap Theorem in the Borel reducibility hierarchy of the isomorphism relations (see preliminaries); indeed, it can be forced.

Fact 1.1 (Hyttinen–Kulikov–Moreno [6, Theorem 7]).

Suppose that $\kappa =\kappa ^{<\kappa }=\lambda ^+$ , $2^\lambda>2^\omega $ , and $\lambda ^{<\lambda }=\lambda $ . There is a forcing notion $\mathbb {P}$ which forces the following statement:

“If $T_1$ is a classifiable theory and $T_2$ is not, then the isomorphism relation of $T_1$ is Borel reducible to the isomorphism relation of $T_2$ , and there are $2^\kappa $ equivalence relations strictly between them.”

In the same article the authors proved the following in ZFC.

Fact 1.2 (Hyttinen–Kulikov–Moreno [6, Corollary 2]).

Suppose that $\kappa =\kappa ^{<\kappa }=\lambda ^+$ and $\lambda ^{\omega }=\lambda $ . If $T_1$ is classifiable and $T_2$ is stable unsuperstable, then the isomorphism relation of $T_1$ is Borel reducible to the isomorphism relation of $T_2$ .

In this article we will extend Fact 1.2 to unsuperstable theories, i.e., the unstable case.

Theorem A. Suppose that $\kappa =\kappa ^{<\kappa }=\lambda ^+$ is such that $\lambda ^\omega =\lambda $ . If $T_1$ is classifiable and $T_2$ is unsuperstable, then the isomorphism relation of $T_1$ is Borel reducible to the isomorphism relation of $T_2$ .

To prove Theorem A we will use the coloured trees tools developed in [5] by Hyttinen and Weinstein (né Kulikov), and the tools used by Shelah in [11], to construct models of unsuperstable theories. In [5] Hyttinen and Weinstein (né Kulikov) used the coloured trees to construct models of an already fixed stable unsuperstable theory in the context of the Generalized Baire spaces. In [11] Shelah used ordered trees with $\omega +1$ levels to construct non-isomorphic models of unsuperstable theories.

The objective of Hyttinen and Weinstein (né Kulikov) was to use elements of $\kappa ^\kappa $ to construct models of the theory $T_{\omega +\omega }$ , which is a stable unsuperstable theory. The difficulties with this construction appear when we want to apply it to unstable theories. Hyttinen and Weinstein (né Kulikov) constructed coloured trees for all the elements of $\kappa ^\kappa $ , such that the classes of the isomorphism of coloured trees are characterized by the classes of the equivalence modulo non-stationary. This is relevant when we construct a Borel reduction. In [4], similar trees were used to construct models of stable unsuperstable theories. In [4] the authors used the isolation of types on stable theories (see $F^f_\omega $ in [12, Chapter 4]). This is a limitation for unstable theories.

On the other hand, the objective of Shelah was to use stationary sets to construct as many models as possible for unsuperstable theories. Even though for each unsuperstable theory, Shelah constructs $2^\kappa $ models, this construction does not define a Borel reduction. The problem comes when the ordered trees are constructed.

In Section 3 we will combine Hyttinen–Kulikov’s construction with Shela’s construction. We use coloured trees to construct ordered trees; by doing this, we ensure that the construction of the models will define a continuous reduction. To construct the ordered trees from coloured trees we will use similar ideas to ones used by Abraham in [1] to construct a rigid Aronszajn tree.

In [2] Fernandes, Moreno, and Rinot showed that the isomorphism relation of unsuperstable theories can be forced to be analytically complete for $\kappa $ a successor cardinal. We will extend this result to inaccessible cardinals.

Theorem B. Suppose that $\kappa =\kappa ^{<\kappa }$ is an inaccessible cardinal. There exists a $<\kappa $ -closed $\kappa ^+$ -cc forcing extension in which: If T is unsuperstable, then the isomorphism relation of T is analytically complete.

1.1 Organization of this paper

In Section 2 we recall the notion of ordered trees of Shelah [11] and the notion of a $({<}\kappa , bs)$ -stable $(\kappa , bs,bs)$ -nice linear order. The notion of colorable orders is introduced and its properties are studied. The notion of colorable linear orders is introduced to construct ordered trees in Section 3. In this section we prove the existence of a $({<}\kappa , bs)$ -stable $(\kappa , bs,bs)$ -nice $\kappa $ -colorable linear order, which is crucial for constructing ordered trees from the coloured trees of Hyttinen–Kulikov [5].

In Section 3 we recall the notion of coloured trees of Hyttinen–Kulikov [5]. We use a $({<}\kappa , bs)$ -stable $(\kappa , bs,bs)$ -nice $\kappa $ -colorable linear order to construct an ordered coloured tree $A^f$ . An ordered coloured tree is both, an ordered tree as in [11] and a coloured tree as in [5]. We prove that $f\ =^\beta _\omega \ g$ holds if and only if $A^f\cong A^g$ .

In Section 4 we use the ordered coloured trees to construct generalized Ehrenfeucht–Mostowski models. In this section we prove Theorem A and Theorem B.

1.2 Preliminaries

During this paper we will work under the general assumption that $\kappa $ is a regular uncountable cardinal that satisfies $\kappa =\kappa ^{<\kappa }$ and for all $\gamma <\kappa $ , $\gamma ^\omega <\kappa $ . We will work only with first-order countable complete theories in a countable language, unless something else is stated.

Let us recall some definitions and results on Generalized Descriptive Set Theory (from now on GDST); for more on GDST see [4]. We will only review the definitions and results that are relevant for the article.

The generalized Baire space is the set $\kappa ^\kappa $ endowed with the bounded topology; in this topology the basic open sets are of the form

$$ \begin{align*}[\zeta]=\{\eta\in \kappa^\kappa\mathrel{|}\zeta\subseteq \eta\},\end{align*} $$

where $\zeta \in \kappa ^{<\kappa }$ . The collection of $\kappa $ -Borel subsets of $\kappa ^\kappa $ is the smallest set that contains the basic open sets and is closed under union and intersection both of length $\kappa $ . A $\kappa $ -Borel set is any set of this collection.

A function $f\colon \kappa ^\kappa \rightarrow \kappa ^\kappa $ is $\kappa $ -Borel, if for every open set $A\subseteq \kappa ^\kappa $ the inverse image $f^{-1}[A]$ is a $\kappa $ -Borel subset of X. Let $E_1$ and $E_2$ be equivalence relations on $\kappa ^\kappa $ . We say that $E_1$ is $\kappa $ -Borel reducible to $E_2$ if there is a $\kappa $ -Borel function $f\colon \kappa ^\kappa \rightarrow \kappa ^\kappa $ that satisfies

$$ \begin{align*}(\eta,\xi)\in E_1\iff (f(\eta),f(\xi))\in E_2.\end{align*} $$

We call f a reduction of $E_1$ to $E_2$ and we denote this by $E_1\hookrightarrow _B E_2$ . We will use this notation instead of ( $\leq _B$ ), because we will deal with the equivalence relations $=_S^\beta $ (Definition 1.3) and the notation could become heavy for the reader. In case f is continuous, we say that $E_1$ is continuously reducible to $E_2$ and we denote it by $E_1\hookrightarrow _c E_2$ .

A subset $X\subseteq \kappa ^\kappa $ is a $\Sigma _1^1(\kappa )$ set of $\kappa ^\kappa $ if there is a closed set $Y\subseteq \kappa ^\kappa \times \kappa ^\kappa $ such that the projection $\operatorname {\mathrm {pr}}(Y):=\{x\in \kappa ^\kappa \mathrel {|} \exists y\in \kappa ^\kappa ,~(x,y)\in Y\}$ is equal to X. These definitions also extend to the product space $\kappa ^\kappa \times \kappa ^\kappa $ . An equivalence relation E is $\Sigma _1^1$ -complete if E is a $\Sigma _1^1(\kappa )$ set and every $\Sigma _1^1(\kappa )$ equivalence relation R is Borel reducible to E.

The generalized Cantor space is the subspace $2^\kappa $ . Since in this article we will only work with $\kappa $ -Borel and $\Sigma _1^1(\kappa )$ sets, we will omit $\kappa $ , and refer to them as Borel and $\Sigma _1^1$ .

Definition 1.3. Given $S\subseteq \kappa $ and $\beta \leq \kappa $ , we define the equivalence relation $=_S^\beta \ \subseteq \ \beta ^\kappa \times \beta ^\kappa $ , as follows:

$$ \begin{align*}\eta\mathrel{=^\beta_S}\xi \iff \{\alpha<\kappa\mathrel{|} \eta(\alpha)\neq\xi(\alpha)\}\cap S \text{ is non-stationary}.\end{align*} $$

We will denote by $=_\mu ^\beta $ the relation $=_S^\beta $ when $S=\{\alpha <\kappa \mathrel {|} cf(\alpha )=\mu \}$ . Let us denote by $CUB$ the club filter on $\kappa $ and $=^\beta _{CUB}$ the relation $=_S^\beta $ when $S=\kappa $ .

Definition 1.4. Let $\mathcal {L}=\{Q_m\mathrel {|} m\in \omega \}$ be a countable relational language. Fix a bijection $\pi $ between $\kappa ^{<\omega }$ and $\kappa $ . For every $\eta \in \kappa ^\kappa $ define the structure $\mathcal {A}_\eta $ with domain $\kappa $ as follows. For every tuple $(a_1,a_2,\ldots , a_n)$ in $\kappa ^n$ ,

$$ \begin{align*}(a_1,a_2,\ldots , a_n)\in Q_m^{\mathcal{A}_\eta}\Leftrightarrow Q_m \text{ has arity } n \text{ and }\eta(\pi(m,a_1,a_2,\ldots,a_n))>0.\end{align*} $$

Definition 1.5. Assuming T is a first-order theory in a relational countable language, we define the isomorphism relation, $\cong _T~\subseteq \kappa ^\kappa \times \kappa ^\kappa $ , as the relation

$$ \begin{align*}\{(\eta,\xi)|(\mathcal{A}_\eta\models T, \mathcal{A}_\xi\models T, \mathcal{A}_\eta\cong \mathcal{A}_\xi)\text{ or } (\mathcal{A}_\eta\not\models T, \mathcal{A}_\xi\not\models T)\}.\end{align*} $$

2 Ordered trees

2.1 Background

In [11], Shelah used ordered trees to construct non-isomorphic models. That construction was focused on obtaining non-isomorphic models. This is the reason why we have to modify the trees to adapt the construction to the generalized Cantor space and such that for all $f,g\in 2^\kappa $ , f and g are $=_\omega ^2$ -equivalent if and only if the constructed models are isomorphic. Let us start by reviewing the trees used by Shelah.

Let $\gamma $ be a countable ordinal, and we will denote by $K_{tr}^\gamma $ the class of ordered trees with $\gamma +1$ levels.

Definition 2.1. Let $K_{tr}^\gamma $ be the class of models $(A,\prec , (P_n)_{n\leq \gamma },<, h)$ , where:

1. (1) There is a linear order $(I,<_I)$ such that $A\subseteq I^{\leq \gamma }$ .

2. (2) A is closed under initial segment.

3. (3) $\prec $ is the initial segment relation.

4. (4) $h(\eta ,\xi )$ is the maximal common initial segment of $\eta $ and $\xi $ .

5. (5) Let $lg(\eta )$ be the length of $\eta $ (i.e., the domain of $\eta $ ) and $P_n=\{\eta \in A\mathrel {|} lg(\eta )=n\}$ for $n\leq \gamma $ .

6. (6) For every $\eta \in A$ define $Suc_A(\eta )$ as $\{\xi \in A\mathrel {|} \eta \prec \xi \wedge lg(\xi )=lg(\eta )+1\}$ . $<$ is $\bigcup _{\eta \in A}(<{\mathbin \upharpoonright } Suc_A(\eta ))$ , i.e., if $\xi <\zeta $ , then there is $\eta \in A$ such that $\xi ,\zeta \in Suc_A(\eta )$ .

7. (7) For every $\eta \in A\backslash P_\gamma $ , $<{\mathbin \upharpoonright } Suc_A(\eta )$ is the induced linear order from I, i.e.,

   $$ \begin{align*}\eta^\frown \langle x\rangle<\eta^\frown \langle y\rangle \Leftrightarrow x<_I y.\end{align*} $$

8. (8) If $\eta $ and $\xi $ have no immediate predecessor and $\{\zeta \in A\mathrel {|} \zeta \prec \eta \}=\{\zeta \in A\mathrel {|} \zeta \prec \xi \}$ , then $\eta =\xi $ .

To construct the models of unsuperstable theories, Shelah study the types of the ordered trees. To do this study, the notions of $\kappa $ -representation and $CUB$ -invariant are crucial.

Definition 2.2 ( $\kappa $ -representation).

Let A be an arbitrary set of size at most $\kappa $ . The sequence $\mathbb {A}=\langle A_\alpha \mathrel {|} \alpha <\kappa \rangle $ is a $\kappa $ -representation of A, if $\langle A_\alpha \mathrel {|} \alpha <\kappa \rangle $ is an increasing continuous sequence of subsets of A, for all $\alpha <\kappa $ , $|A_\alpha |<\kappa $ , and $\bigcup _{\alpha <\kappa }A_\alpha =A$ .

Definition 2.3 ( $CUB$ -invariant).

A function $\mathcal {H}$ is $CUB$ -invariant if the following holds:

• • The domain of $\mathcal {H}$ is the class of $\kappa $ -representations of the models of some model class K, where K contains only models of size at most $\kappa $ .

• • If $\mathbb {I}_1$ and $\mathbb {I}_2$ are $\kappa $ -representations of $\mathcal {I}_1, \mathcal {I}_2\in K$ , respectively, and $\mathcal {I}_1\cong \mathcal {I}_2$ , then $\mathcal {H}(\mathbb {I}_1)=^2_{CUB}\mathcal {H}(\mathbb {I}_2)$ .

Let us define for every $\mathcal {H}$ $CUB$ -invariant and $A\in K_{tr}^\omega $ , $\mathcal {H}(A)$ as the $=^2_{CUB}$ -equivalence class of any $\mathbb {A}$ , $\kappa $ -representation, i.e., $[\mathcal {H}(\mathbb {A})]_{=^2_{CUB}}$ .

We will use some properties of formulas and types. For any $\mathcal {L}$ -structure $\mathcal {A}$ we denote by at the set of atomic formulas of $\mathcal {L}$ and by bs the set of basic formulas of $\mathcal {L}$ (atomic formulas and negation of atomic formulas). For all $\mathcal {L}$ -structures $\mathcal {A}$ , $a\in \mathcal {A}$ , and $B\subseteq \mathcal {A}$ we define

$$ \begin{align*}tp_{bs}(a,B,\mathcal{A})=\{\varphi(x,b)\mathrel{|} \mathcal{A}\models \varphi(a,b),\varphi\in bs,b\in B\}.\end{align*} $$

In the same way $tp_{at}(a,B,\mathcal {A})$ is defined.

Definition 2.4. Let $\mathcal {A}$ be a model, $a\in \mathcal {A}$ , and $B,D\subseteq \mathcal {A}$ . We say that $tp_{bs}(a,B,\mathcal {A})$ (bs,bs)-splits over $D\subseteq \mathcal {A}$ if there are $b_1,b_2\in B$ such that $tp_{bs}(b_1,D,\mathcal {A})=tp_{bs}(b_2,D,\mathcal {A})$ but $tp_{bs}(a^\frown b_1,D,\mathcal {A})\neq tp_{bs}(a^\frown b_2,D,\mathcal {A})$ .

Definition 2.5. Let $|A|\leq \kappa $ , for a $\kappa $ -representation $\mathbb {A}$ of A. Define $Sp_{bs}(\mathbb {A})$ as the set

$$ \begin{align*}\{\delta<\kappa\mathrel{|} \delta\text{ a limit ordinal, }\exists a\in A\ [\forall\beta<\delta \ (tp_{bs}(a,A_\delta,A)\text{ (bs,bs)-splits over }A_\beta)]\}.\end{align*} $$

Remark 2.6. The function $Sp_{bs}$ is $CUB$ -invariant; this was stated in [11, Remark 1.10A] and proved in [8, Lemma 8.6 and page 232 above Definition 8.8]. This is generally true under the assumption that for all $\gamma <\kappa $ , $\gamma ^\omega <\kappa $ , which is one of our cardinal assumptions on $\kappa $ above.

Definition 2.7.

• • Let $\mathcal {A}$ be a model of size at most $\kappa $ . We say that A is $(\kappa , bs,bs)$ -nice if $Sp_{bs}(\mathbb {A})\ =^2_{CUB}\ \emptyset $ .

• • $A\in K^\omega _{tr}$ of size at most $\kappa $ , is locally $(\kappa , bs,bs)$ -nice if for every $\eta \in A\backslash P^A_\omega $ , $(Suc_A(\eta ),<)$ is $(\kappa , bs,bs)$ -nice, $Suc_A(\eta )$ is infinite, and there is $\xi \in P_\omega ^A$ such that $\eta \prec \xi $ .

• • $A\in K^\omega _{tr}$ is $(<\kappa , bs)$ -stable if for every $B\subseteq A$ of size smaller than $\kappa $ ,

  $$ \begin{align*}\kappa>|\{tp_{bs}(a,B,A)\mathrel{|} a\in A\}|.\end{align*} $$

In [11], Shelah used $({<}\kappa , bs)$ -stable locally $(\kappa , bs,bs)$ -nice ordered trees to construct the models of unsuperstable theories. In [8] Hyttinen and Tuuri give a very good example of a $({<}\kappa , bs)$ -stable $(\kappa , bs,bs)$ -nice linear order, which is crucial for the construction of ordered trees.

Definition 2.8 (Hyttinen–Tuuri [8, Definition 3.2]).

Let $\mathcal {R}$ be the set of functions $f:\omega \rightarrow \kappa $ for which $\{n\in \omega \mathrel {|} f(n)\neq 0\}$ is finite. If $f,g\in \mathcal {R}$ , then $f<g$ if and only if $f(n)<g(n)$ , where n is the least number such that $f(n)\neq g(n)$ .

Fact 2.9 (Hyttinen–Tuuri [8, Lemma 8.17]).

• • The linear order $\mathcal {R}$ is $(<\kappa , bs)$ -stable and $(\kappa , bs,bs)$ -nice.

• • There is a $\kappa $ -representation $\langle R_\alpha \mathrel {|} \alpha <\kappa \rangle $ and a club $C\subseteq \kappa $ such that for all $\delta \in C$ and $\nu \in \mathcal {R}$ there is $\beta <\delta $ which satisfies the following:

  $$ \begin{align*}\forall\sigma\in R_\delta [\sigma>\nu \Rightarrow \exists\sigma'\in R_\beta\ (\sigma\ge\sigma'\ge\nu)].\end{align*} $$

2.2 Colorable orders

As it was mentioned in the previous subsection, the linear order plays a crucial role when we construct the ordered trees and therefore the models. For our purpose, constructing ordered trees from coloured trees, we will need to choose the right linear orders. The linear orders that we will use are the colorable linear orders.

Definition 2.10. Let I be a linear order of size $\kappa $ . We say that I is $\kappa $ -colorable if there is a function $F: I\rightarrow \kappa $ such that for all $B\subseteq I$ , $|B|<\kappa $ , $b\in I\backslash B$ , and $p=tp_{bs}(b,B,I)$ such that the following hold: For all $\alpha \in \kappa $ , $|\{a\in I\mathrel {|} a\models p\ \&\ F(a)=\alpha \}|=\kappa $ .

We say that F is a $\kappa $ -coloration of I, if F witnesses that I is a $\kappa $ -colorable linear order.

Notice that I is a $\kappa $ -colorable order if every type over a small set is realizable if and only if it is realizable by $\kappa $ many elements. Under the assumption $\kappa ^{<\kappa }=\kappa $ the saturated model of DLO of size $\kappa $ is $\kappa $ -colorable but it is not $(<\kappa ,bs)$ -stable (DLO is unstable). Clearly $\kappa $ -colorable orders make us think of saturation. The interesting $\kappa $ -colorable orders are those in which not all the types over small sets are realizable.

Although the saturated model of DLO of size $\kappa $ (assuming it exists due to the cardinal assumptions) is $\kappa $ -colorable, we cannot use it for our purpose. We need a $(<\kappa ,bs)$ -stable linear order. We will construct a $\kappa $ -colorable linear order that is $(<\kappa ,bs)$ -stable; therefore, it is not $\kappa $ -saturated (i.e., there are types over small sets that are not realized).

We will modify the order of Definition 2.8 to construct a $(<\kappa , bs)$ -stable $(\kappa , bs,bs)$ -nice $\kappa $ -colorable linear order.

Definition 2.11. Let $\mathbb {Q}$ be the linear order of the rational numbers. Let $\kappa \times \mathbb {Q}$ be ordered by the lexicographic order, and let $I^0$ be the set of functions $f:\omega \rightarrow \kappa \times \mathbb {Q}$ such that $f(n)=(f_1(n),f_2(n))$ , for which $\{n\in \omega \mathrel {|} f_1(n)\neq 0\}$ is finite. If $f,g\in I^0$ , then $f<g$ if and only if $f(n)<g(n)$ , where n is the least number such that $f(n)\neq g(n)$ .

Lemma 2.12. There is a $\kappa $ -representation $\langle I^0_\alpha \mathrel {|} \alpha <\kappa \rangle $ such that for all limit $\delta <\kappa $ and $\nu \in I^0$ there is $\beta <\delta $ which satisfies the following:

1. I. $\forall \sigma \in I^0_\delta \ [\sigma>\nu \Rightarrow \exists \sigma '\in I^0_\beta \ (\sigma \ge \sigma '\ge \nu )].$

2. II. If $\nu \notin I^0_\delta $ , then $\forall \sigma \in I^0_\delta \ [\sigma>\nu \Rightarrow \exists \sigma '\in I^0_\beta \ (\sigma >\sigma '>\nu )].$

Proof Let us start by defining the representation $\kappa $ -representation $\langle I^0_\alpha \mathrel {|} \alpha <\kappa \rangle $ . For all $\gamma <\kappa $ , let us define $\langle I^0_\alpha \mathrel {|} \alpha <\kappa \rangle $ by

$$ \begin{align*}I^0_\gamma=\{\nu\in I^0\mathrel{|} \nu_1(n)<\gamma\ \textit{for all } n<\omega\}\end{align*} $$

it is clear that $\langle I^0_\alpha \mathrel {|} \alpha <\kappa \rangle $ is a $\kappa $ -representation.

Let us show item II, i.e., $\nu \notin I^0_\delta $ .

Suppose $\nu \notin I^0_\delta $ . Let $\beta <\delta $ be $max\{\nu _1(i)\mathrel {|} i<n\}$ , where n is the least number such that $\nu _1(n)\ge \delta $ .

Claim 2.12.1. $\beta $ is as wanted, i.e.,

$$ \begin{align*}\forall\sigma\in I^0_\delta\ [\sigma>\nu \Rightarrow \exists\sigma'\in I^0_\beta\ (\sigma>\sigma'>\nu)].\end{align*} $$

Proof Let us suppose $\sigma \in I^0_\delta $ is such that $\sigma \ge \nu $ . By the definition of $I^0$ , there is $n<\omega $ such that $\sigma (n)>\nu (n)$ and n is the minimum number such that $\sigma (n)\neq \nu (n)$ . Since $\sigma \in I^0_\delta $ , for all $m\leq n$ , $\nu _1(m)\leq \sigma _1(m)<\delta $ . Thus for all $m\leq n$ , $\nu _1(m)<\beta $ .

Let us divide the proof in two cases, $\sigma _1(n)=\nu _1(n)$ and $\sigma _1(n)>\nu _1(n)$ .

Case 1. $\sigma _1(n)=\nu _1(n)$ .

By the density of $\mathbb {Q}$ there is r such that $\sigma _2(n)>r>\nu _2(n)$ . Let us define $\sigma '$ by

$$ \begin{align*}\sigma'(m)=\begin{cases} \nu(m), &\mbox{if } m<n,\\ (\nu_1(n), r), & \mbox{if } m=n,\\ 0, & \mbox{otherwise. } \end{cases}\end{align*} $$

Clearly $\sigma>\sigma '>\nu $ . Since $\nu _1(m)<\beta $ for all $m\leq n$ , $\sigma '\in I^0_\beta $ .

Case 2. $\sigma _1(n)>\nu _1(n)$ .

Let us define $\sigma '$ by

$$ \begin{align*}\sigma'(m)=\begin{cases} \nu(m), &\mbox{if } m<n,\\ (\nu_1(n), \nu_2(n)+1), & \mbox{if } m=n,\\ 0, & \mbox{otherwise. } \end{cases}\end{align*} $$

Clearly $\sigma>\sigma '>\nu $ . Since $\nu _1(m)<\beta $ for all $m\leq n$ , $\sigma '\in I^0_\beta $ .

The previous claim proves item II. From the proof of this claim we can see that $\sigma \neq \sigma '$ .

To prove item I, it is enough to prove the case $\nu \in I^0$ .

Suppose $\delta <\kappa $ is a limit and $\nu \in I^0_\delta $ . It is clear that there is $\beta <\delta $ such that $\nu \in I^0_\beta $ and the result follows.

Now let us used the order $I^0$ to construct a $({<}\kappa , bs)$ -stable, $(\kappa , bs,bs)$ -nice, and $\kappa $ -colorable linear order. Let us construct the linear orders $\langle I^i\mathrel {|} i<\kappa \rangle $ by induction, such that for all $i<j$ , $I^i\subseteq I^j$ . Suppose $i<\kappa $ is such that $I^i$ has been defined. For all $\nu \in I^i$ let $\nu ^{i+1}$ be such that

(1) $$ \begin{align} \nu^{i+1}\models tp_{bs}(\nu, I^i\backslash \{\nu\}, I^i)\cup\{\nu>x\}. \end{align} $$

Notice that $\nu ^{i+1}$ is a copy of $\nu $ that is smaller than $\nu $ . Let $I^{i+1}=I^i\cup \{\nu ^{i+1}\mathrel {|} \nu \in I^i\}$ .

Suppose $i<\kappa $ is a limit ordinal such that for all $j<i$ , $I^j$ has been defined, we define $I^i$ by $I^i=\bigcup _{j<i}I^j$ .

For all $i<\kappa $ , let us define the $\kappa $ -representation $\langle I^i_\alpha \mathrel {|} \alpha <\kappa \rangle $ by induction as follows:

Suppose $i<\kappa $ is such that $\langle I^i_\alpha \mathrel {|} \alpha <\kappa \rangle $ has been defined. For all $\alpha <\kappa $ ,

$$ \begin{align*}I^{i+1}_\alpha=I^i_\alpha\cup \{\nu^{i+1}\mathrel{|} \nu\in I^i_\alpha\}.\end{align*} $$

Suppose $i<\kappa $ is a limit ordinal such that for all $j<i$ , $\langle I^j_\alpha \mathrel {|} \alpha <\kappa \rangle $ has been defined, we define $\langle I^i_\alpha \mathrel {|} \alpha <\kappa \rangle $ by

$$ \begin{align*}I^i_\alpha=\bigcup_{j<i} I^j_\alpha .\end{align*} $$

Finally, let us define I as

$$ \begin{align*}I=\bigcup_{j<\kappa} I^j\end{align*} $$

and the $\kappa $ -representation $\langle I_\alpha \mathrel {|} \alpha <\kappa \rangle $ as

$$ \begin{align*}I_\alpha= I^\alpha_\alpha .\end{align*} $$

The linear order I can be constructed in a non-inductive way. For every $\nu $ in $I^0$ we define a linear order $L_\nu $ , and we use $I^0$ to glue all these linear orders. To show this construction in more detail (it will be useful in the proof of Lemma 2.23) and be able to prove the main result of this section, we will need to develop the theory of I.

Definition 2.13 (Generator).

For all $\nu \in I$ let us denote by $o(\nu )$ the least ordinal $\alpha <\kappa $ such that $\nu \in I^\alpha $ . Let us denote the generator of $\nu $ by $Gen(\nu )$ and define it by induction as follows:

• • $Gen^i(\nu )=\emptyset $ , for all $i<o(\nu )$ .

• • $Gen^i(\nu )=\{\nu \}$ , for $i=o(\nu )$ .

• • For all $i\ge o(\nu )$ ,

  $$ \begin{align*}Gen^{i+1}(\nu)=Gen^i(\nu)\cup\{\sigma\in I^{i+1}\mathrel{|} \exists \tau\in Gen^i(\nu)\ [\tau^{i+1}=\sigma]\}.\end{align*} $$

• • For all $i<\kappa $ limit,

  $$ \begin{align*}Gen^i(\nu)=\bigcup_{j<i}Gen^j(\nu).\end{align*} $$

Finally, let

$$ \begin{align*}Gen(\nu)=\bigcup_{i<\kappa}Gen^i(\nu).\end{align*} $$

Notice that $o(\nu )$ is a successor ordinal for all $\nu $ . For clarity purposes let us fix the following notation.

Notation. For all $i<\kappa $ and $\sigma \in I^i$ , we have defined $\sigma ^{i+1}$ (see (1) above) as the element generated by $\sigma $ in $I^{i+1}$ . We will also denote by $(\sigma )^{i+1}$ the element $\sigma ^{i+1}$ . This is to avoid a saturated notation, such as $\sigma ^{\prime i+1}$ when we work with the element generated by $\sigma '$ in $I^{i+1}$ .

Fact 2.14. Suppose $\nu \in I$ . For all $\sigma \in Gen(\nu )$ , $\sigma \neq \nu $ , there is $n<\omega $ and a sequence $\{\sigma _i\}_{i\leq n}$ such that the following holds:

• • $\sigma _0=\nu $ .

• • For all $j<n$ ,

  $$ \begin{align*}\sigma_{j+1}=(\sigma_j)^{o(\sigma_{j+1})}.\end{align*} $$

• • $\sigma =\sigma _n=(\sigma _{n-1})^{o(\sigma )}.$

Proof Let $\sigma \neq \nu $ be such that $\sigma \in Gen(\nu )$ . From Definition 2.13, we know that $\sigma \in Gen^{o(\sigma )}(\nu )$ and $Gen^{o(\sigma )}(\nu )\subseteq I^{o(\sigma )}$ . Let us proceed by induction on $o(\sigma )$ . Notice that $o(\nu )<o(\sigma )$ , so the induction starts with the case $o(\sigma )=o(\nu )+1$ . Since $o(\sigma )$ is a successor ordinal, the limit step of the induction is not required.

For the case $o(\sigma )=o(\nu )+1$ it is easy to see from Definition 2.13 that $\sigma =\nu ^{o(\nu )+1}$ . Thus $\sigma _0=\nu $ and $\sigma =\sigma _1=(\sigma _0)^{o(\sigma _{1})}$ is the desire sequence, and $n=1$ .

Let $o(\sigma )=i+1>o(\nu )+1$ be such that for any $\tau \in Gen^i(\nu )$ there are $n<\omega $ and a sequence $\{\tau _j\}_{j\leq n}$ such that the following holds:

• • $\tau _0=\nu $ ;

• • for all $j<n$ ,

  $$ \begin{align*}\tau_{j+1}=(\tau_j)^{o(\tau_{j+1})};\end{align*} $$

• • $\tau =\tau _n=(\tau _{n-1})^{o(\tau )}$ .

We know that $\sigma \in Gen^{o(\sigma )}(\nu )=Gen^{i+1}(\nu )$ . By Definition 2.13, there is $\tau \in Gen^i(\nu )$ such that $\tau ^{i+1}=\sigma $ . We conclude that $n+1<\omega $ and the sequence $\{\sigma _i\}_{i\leq n+1}$ defined by:

• • $\sigma _0=\tau _0=\nu $ ;

• • for all $j\leq n$ , $\sigma _j=\tau _j$ ;

• • $\sigma =\sigma _{n+1}=(\tau _{n})^{i+1}$

are as wanted.

For every $\nu \in I$ , $\sigma \in Gen(\nu )$ , and $\sigma \neq \nu $ , we call the sequence $\{\sigma _i\}_{i\leq n}$ of the previous fact, the road from $\nu $ to $\sigma $ . It is clear that for all $\nu \in I\backslash I^0$ , there is $\nu '\in I^0$ such that $\nu \in Gen(\nu ')$ . Notice that for all $\nu \in I$ , if $\sigma \in Gen(\nu )$ , then $\nu $ and $\sigma $ have the same type of basic formulas over $I^{o(\nu )}\backslash \{\nu \}$ . Even more, if $\{\sigma _i\}_{i\leq n}$ is the road from $\nu $ to $\sigma $ , then for all $i< n$ , $\sigma _i$ and $\sigma $ have the same type of basic formulas over $I^\gamma \backslash \{\sigma _i\}$ , where $o(\sigma _{i+1})=\gamma +1$ . Let us define the road from $\nu $ to $\nu $ by $\{\nu \}$ .

It is clear that I is the orders $Gen(\nu )$ , for $\nu \in I^0$ , glued by $I^0$ . Let us show the non-inductive construction of I in more detail.

Let us fix $\nu \in I^0$ , $\sigma \in Gen(\nu )$ , and let $\{\nu _i\}_{i\leq n}$ be the road from $\nu $ to $\sigma $ . Let us define $f_\sigma : \omega \rightarrow \kappa $ by

$$ \begin{align*}f_\sigma(i)=\begin{cases} o(\nu_i), &\mbox{if } i\leq n,\\ 0, & \mbox{otherwise. } \end{cases}\end{align*} $$

Notice that for all $\sigma ,\sigma '\in Gen(\nu )$ , $f_\sigma $ and $f_{\sigma '}$ are equal if and only if the road from $\nu $ to $\sigma $ is the same road from $\nu $ to $\sigma '$ . Thus $f_\sigma =f_{\sigma '}$ if and only if $\sigma =\sigma '$ . Since the road from $\nu $ to $\sigma $ is finite, $\{i<\omega \mathrel {|} f_\sigma (i)\neq 0\}$ is finite.

Let $\sigma ,\sigma '\in Gen(\nu )$ , and i the least number such that $f_\sigma (i)\neq f_{\sigma '}(i)$ . By the construction of I, $\sigma>\sigma '$ holds if and only if one of the following holds:

• • $f_\sigma (i)=0$ .

• • $f_\sigma (i)>f_{\sigma '}(i)$ .

From the previous discussion on the functions $f_\sigma $ , we can conclude that for all $\nu ,\nu '\in I^0$ , the orders and $(Gen(\nu '),<)$ are isomorphic. Even more, this holds for all $\sigma ,\sigma '\in I$ .

Definition 2.15 (Generator order).

Let $Gen$ be the set of functions $f: \omega \rightarrow \kappa $ such that the following holds:

• • $f(0)=0$ .

• • For all $n<\omega $ , $f(n)$ is either $0$ or a successor ordinal.

• • There is $n<\omega $ such that for all $m>n$ , $f(m)=0$ .

• • $f{\mathbin \upharpoonright } n+1\backslash \{0\}$ is strictly increasing.

Let $f,g\in Gen$ and i the least number such that $f(i)\neq g(i)$ . Let us define $<_{Gen}$ as follows: $g<_{Gen} f$ if and only if one of the following holds:

• • $f(i)=0$ .

• • $g(i)<f(i)$ .

From the discussion above, it is clear that for all $\nu \in I^0$ , $(Gen(\nu ),<)$ and $Gen, <_{Gen}$ are isomorphic. Therefore I is isomorphic to $I^0\times Gen$ with the lexicographic order. Notice that I is the orders $L_\nu =\{\nu \}\times Gen$ glued by $I^0$ ; in particular $L_\nu $ and $Gen(\nu )$ are isomorphic.

Now we proceed with the study of other properties of I. All the properties of I that we will prove, can be proved using $I^0\times Gen$ . Nevertheless, we will use the inductive construction in the proofs, to provide an intuitive point of view.

Fact 2.16. Let $i,\delta , \nu $ be such that $\nu \in I^i_\delta $ . Then for all $\sigma \in Gen(\nu )$ , $\sigma \in I^{o(\sigma )}_\delta $ . In particular for all $j<\kappa $

$$ \begin{align*}\sigma\notin I^j_\delta\Rightarrow \sigma\notin I^j.\end{align*} $$

Proof It follows from the construction of $I^{o(\sigma )}$ and the $\kappa $ -representation $\langle I^{o(\sigma )}_\alpha \mathrel {|} \alpha <\kappa \rangle $ .

Fact 2.17. For all $\nu ,\sigma \in I$ , $\sigma \in Gen(\nu )$ , if $\sigma '\in I$ is such that $\nu \ge \sigma '\ge \sigma $ , then $\sigma '\in Gen(\nu )$ .

Proof If $\nu =\sigma $ , the result follows. Thus we only need to prove the case $\nu \neq \sigma $ . Let us suppose towards contradiction that $\sigma '\notin Gen(\nu )$ .

Case $o(\nu )=o(\sigma ')$ . Since $\nu $ and $\sigma $ have the same type of basic formulas over $I^{o(\nu )}\backslash \{\nu \}$ , $\nu $ and $\sigma $ have the same type of basic formulas over $I^{o(\sigma ')}\backslash \{\nu \}$ . Since $\nu \ge \sigma '\ge \sigma $ , $\nu =\sigma '$ a contradiction.

Case $o(\sigma ')<o(\nu )$ . Since $\nu \ge \sigma '$ , there is $\nu '\neq \sigma '$ such that $\nu '>\nu $ , $o(\nu ')=o(\sigma ')$ and $\nu \in Gen(\nu ')$ . Thus $\nu '$ , $\sigma '$ , and $\sigma $ satisfy $\nu '\ge \sigma '\ge \sigma $ , $o(\nu ')=o(\sigma ')$ , and $\sigma \in Gen(\nu ')$ . The result follows from the previous case.

Case $o(\nu )<o(\sigma ')$ . There is $\sigma ^0\in I$ such that $\sigma ^0>\sigma '$ , $o(\sigma ^0)=o(\nu )$ and $\sigma '\in Gen(\sigma ^0)$ . If $\nu \ge \sigma ^0\ge \sigma $ , then the result follows from the previous cases. Therefore, we are only missing the case $\sigma ^0\ge \nu \ge \sigma '\ge \sigma $ . Since $\sigma ^0$ and $\sigma '$ have the same type of basic formulas of basic formulas over $I^{o(\sigma ^0)}\backslash \{\sigma ^0\}$ , $\sigma ^0=\nu $ and $\sigma '\in Gen(\nu )$ a contradiction.

From the previous fact we can conclude that for all $\nu ,\sigma \in I$ such that $\sigma \in Gen(\nu )$ , $\nu $ and $\sigma $ have the same type of basic formulas over $I\backslash Gen(\nu )$ .

Lemma 2.18. For all $i<\kappa $ , $\delta <\kappa $ a limit ordinal, and $\nu \in I^i$ , there is $\beta <\delta $ that satisfies the following:

1. I. $\forall \sigma \in I^i_\delta \ [\sigma>\nu \Rightarrow \exists \sigma '\in I^i_\beta \ (\sigma \ge \sigma '\ge \nu )].$

2. II. In particular, for all $i<\kappa $ , $\delta <\kappa $ a limit ordinal, and $\nu \in I^i\backslash I^{i}_\delta $ , there is $\beta <\delta $ that satisfies the following:

   $$ \begin{align*}\forall\sigma\in I^i_\delta\ [\sigma>\nu \Rightarrow \exists\sigma'\in I^0_\beta\ (\sigma>\sigma'>\nu)].\end{align*} $$

Proof Notice that if $\nu \in I^{i}_\delta $ , then there is $\theta <\delta $ such that $\nu \in I^{i}_\theta $ and the result follows for $\beta =\theta $ . So we only have to prove the lemma when $\nu \in I^i\backslash I^{i}_\delta $ (the second part of the lemma).

We will proceed by induction over i. The case $i=0$ is precisely Lemma 2.12 II. Let us suppose $i<\kappa $ is such that for all limit ordinal $\delta <\kappa $ and $\nu \in I^i\backslash I^{i}_\delta $ , there is $\beta <\delta $ that satisfies II. Let $\delta <\kappa $ be a limit ordinal and $\nu \in I^{i+1}\backslash I^{i+1}_\delta $ . We have two cases, $\nu \in I^i$ and $\nu \in I^{i+1}\backslash I^i$ .

Case $\nu \in I^i$ . By the induction hypothesis, we know that there is $\beta <\delta $ such that II holds. Let us prove that this $\beta $ is the one we are looking for. Let $\sigma \in I^{i+1}_\delta $ be such that $\sigma>\nu $ . The subcase $\sigma \in I^i_\delta $ follows from the way $\beta $ was chosen.

Subcase $\sigma \in I^{i+1}_\delta \backslash I^i_\delta $ . By the construction of $I^{i+1}$ , there is $\sigma _0\in I^i_\delta $ such that $\sigma =(\sigma _0)^{i+1}$ (so $\sigma _0>\sigma $ ). Thus $\sigma _0>\sigma >\nu $ , and by the way $\beta $ was chosen, there is $\sigma '\in I^0_\beta $ such that $\sigma _0> \sigma '> \nu $ . Since $\sigma _0$ and $\sigma $ have the same type of basic formulas over $I^i\backslash \{\sigma _0\}$ , $\sigma> \sigma '> \nu $ as we wanted.

Case $\nu \in I^{i+1}\backslash I^i$ . By the construction of $I^{i+1}$ , there is $\nu _0\in I^i$ such that $(\nu _0)^{i+1}=\nu $ . Since $\nu \in Gen(\nu _0)$ and $\nu \in I^{i+1}\backslash I^{i+1}_\delta $ , by Fact 2.16 $\nu _0\in I^i\backslash I^i_\delta $ . Thus, by the previous case, there is $\beta <\delta $ such that for all $\sigma \in I^{i+1}_\delta $ ,

$$ \begin{align*}\sigma>\nu_0 \Rightarrow \exists\sigma'\in I^0_\beta\ (\sigma>\sigma'>\nu_0).\end{align*} $$

Let us show that this $\beta $ is as wanted.

Claim 2.18.1. If $\sigma \in I^{i+1}_\delta $ is such that $\sigma>\nu $ , then $\sigma>\nu _0$ .

Proof Let us suppose, towards contradiction, that there is $\sigma \in I^{i+1}_\delta $ such that $\nu _0>\sigma >\nu $ . Since $\nu _0$ and $\nu $ have the same type of basic formulas over $I^i\backslash \{\nu _0\}$ , $\sigma \in I^{i+1}_\delta \backslash I^i$ . Therefore, there is $\sigma _0\in I^i$ such that $(\sigma _0)^{i+1}=\sigma $ . Since $\sigma \in Gen(\sigma _0)$ and $\sigma \in I^{i+1}_\delta $ , $\sigma _0\in I^i_\delta $ . We conclude that $\sigma _0\neq \nu _0$ . Finally, $\sigma _0$ and $\sigma $ have the same type of basic formulas over $I^i\backslash \{\sigma _0\}$ , which implies $\nu _0>\sigma _0>\sigma >\nu $ . This contradicts the fact that $\nu _0$ and $\nu $ have the same type of basic formulas over $I^i\backslash \{\nu _0\}$ .

From the previous claim, we know that for all $\sigma \in I^{i+1}_\delta $ , $\sigma>\nu $ implies $\sigma>\nu _0$ . By the way $\beta $ was chosen we conclude that for all $\sigma \in I^{i+1}_\delta $ , $\sigma>\nu $ implies the existence of $\sigma '\in I^0_\beta $ such that $\sigma>\sigma '>\nu _0>\nu $ , as we wanted.

Let us proceed with the limit case. Suppose $i<\kappa $ is a limit ordinal such that for all $j<i$ , for all limit ordinal $\delta <\kappa $ , and $\nu \in I^j\backslash I^j_\delta $ , there is $\beta <\delta $ such that II holds for j. Let $\delta <\kappa $ be a limit ordinal and $\nu \in I^i\backslash I^i_\delta $ . Since i is a limit, $o(\nu )<i$ , by the induction hypothesis, there is $\beta $ such that II holds for $o(\nu )$ .

Claim 2.18.2. $\beta $ is as wanted.

Proof Let $\sigma \in I^i_\delta $ be such that $\sigma>\nu $ .

Case $\sigma \in I^{o(\nu )}_\delta $ . This case follows from the way $\beta $ was chosen.

Case $\sigma \in I^i_\delta \backslash I^{o(\nu )}_\delta $ . There is $\sigma _0\in I^{o(\nu )}_\delta $ such that $\sigma \in Gen(\sigma _0)$ , with road to $\sigma $ equal to $\{\sigma _i\}_{i\leq n}$ such that $\sigma _1\notin I^{o(\nu )}$ . Therefore $\sigma _0$ and $\sigma $ have the same type of basic formulas over $I^\gamma \backslash \{\sigma _0\}$ , where $o(\sigma _1)=\gamma +1$ . In particular $\sigma _0$ and $\sigma $ have the same type of basic formulas over $I^{o(\nu )}\backslash \{\sigma _0\}$ . By the way $\beta $ was chosen, there is $\sigma '\in I^0_\beta \subseteq I^{o(\nu )}_\beta $ such that $\sigma _0>\sigma '>\nu $ . Since $\sigma _0$ and $\sigma $ have the same type of basic formulas over $I^{o(\nu )}\backslash \{\sigma _0\}$ , $\sigma>\sigma '>\nu $ as wanted.

As it can be seen in the previous lemma, the witness $\sigma '$ can be chosen in $I^0_\beta $ , when $\nu \notin I^i_\delta $ .

Lemma 2.19. For all $\delta <\kappa $ limit, and $\nu \in I$ , there is $\beta <\delta $ that satisfies the following:

$$ \begin{align*} \forall\sigma\in I_\delta\ [\sigma>\nu \Rightarrow \exists\sigma'\in I_\beta\ (\sigma\ge\sigma'\ge\nu)]. \end{align*} $$

Proof Let $\delta <\kappa $ be a limit ordinal, and $\nu \in I$ . We have three different cases: $\nu \in I_\delta $ , $\nu \in I^{o(\nu )}_\delta \backslash I_\delta $ , and $\nu \notin I^{o(\nu )}_\delta $ .

Case $\nu \in I_\delta $ . Since $\delta $ is a limit, $o(\nu )<\delta $ and there is $\theta <\delta $ such that $\nu \in I^{o(\nu )}_\theta $ . Let $\beta =max\{o(\nu ),\theta \}$ ; it is clear that $\beta $ is as wanted.

Case $\nu \in I^{o(\nu )}_\delta \backslash I_\delta $ . Recall $I_\delta =I^\delta _\delta $ ; clearly $\delta <o(\nu )$ . There is $\nu _0\in I_\delta $ , such that $\nu \in Gen(\nu _0)$ , with the road to $\nu $ equal to $\{\nu _i\}_{i\leq n}$ , and $\nu _1\notin I^\delta $ . Since $\nu _0\in I^\delta _\delta $ and $\delta $ is a limit, $o(\nu _0)<\delta $ and there is $\theta <\delta $ such that $\nu _0\in I^{o(\nu _0)}_\theta $ . Let $\beta =max\{o(\nu _0),\theta \}$ .

Claim 2.19.1. $\beta $ is as wanted.

Proof Let $\sigma \in I^\delta _\delta $ be such that $\sigma>\nu $ . Since $\nu _1\notin I^\delta $ , $o(\nu _1)=\gamma +1>\delta $ , and $\nu _0$ and $\nu $ have the same type of basic formulas over $I^\gamma \backslash \{\nu _0\}$ . In particular $\nu _0$ and $\nu $ have the same type of basic formulas over $I^\delta \backslash \{\nu _0\}$ , so $\sigma>\nu _0>\nu $ . Since $\nu _0\in I^\beta _\beta $ , $\sigma '=\nu _0$ is as wanted.

Case $\nu \notin I^{o(\nu )}_\delta $ . Let $\theta =max\{o(\nu ), \delta \}$ ; thus $\nu \in I^\theta $ (notice that we are talking about the order $I^\theta $ and not the element $I_\theta $ of the $\kappa $ -representation $\langle I_\alpha \mathrel {|} \alpha <\kappa \rangle $ ) and by Lemma 2.18 there is $\beta <\delta $ which satisfies the following:

$$ \begin{align*}\forall\sigma\in I^\theta_\delta [\sigma>\nu \Rightarrow \exists\sigma'\in I^0_\beta\ (\sigma>\sigma'>\nu)].\end{align*} $$

Claim 2.19.2. $\beta $ is as wanted.

Proof Let $\sigma \in I^\delta _\delta $ be such that $\sigma>\nu $ . Since $\delta \leq \theta $ , $\sigma \in I^\theta _\delta $ . Therefore, there is $\sigma '\in I^0_\beta $ such that $\sigma>\sigma '>\nu $ . The claim follows from $I^0_\beta \subseteq I^\beta _\beta =I_\beta $ .

Fact 2.20 (Hyttinen–Tuuri [8, Lemma 8.12]).

Let A be a linear order of size $\kappa $ and $\langle A_\alpha \mathrel {|} \alpha <\kappa \rangle $ a $\kappa $ -representation. Then the following are equivalent:

1. (1) A is $(\kappa , bs,bs)$ -nice.

2. (2) There is a club $C\subseteq \kappa $ , such that for all limit $\delta \in C$ , for all $x\in A$ there is $\beta <\delta $ such that one of the following holds:

   • • $\forall \sigma \in A_\delta [\sigma \ge x \Rightarrow \exists \sigma '\in A_\beta \ (\sigma \ge \sigma '\ge x)].$

   • • $\forall \sigma \in A_\delta [\sigma \leq x \Rightarrow \exists \sigma '\in A_\beta \ (\sigma \leq \sigma '\leq x)].$

The previous fact is stated as it is in [8]. Due to Lemma 2.19, the second bullet point of item (2) is not needed for our purposes. The following corollary follows from Lemma 2.19.

Corollary 2.21. I is $(\kappa , bs,bs)$ -nice.

Notice that if $\kappa $ is inaccessible, I is $(<\kappa , bs)$ -stable. This can be generalize to successors $\kappa $ .

Lemma 2.22. Suppose $\kappa =\lambda ^+$ . $I^0$ is $(<\kappa , bs)$ -stable.

Proof Recall the linear order $\mathcal {R}$ from Definition 2.8. From the general assumption on $\kappa $ , we know that $\lambda ^\omega =\lambda $ .

For all $A\subseteq I^0$ define $Pr(A)$ as the set $\{f_1\mathrel {|} f\in A\}$ . Let $A\subseteq I^0$ be such that $|A|<\kappa $ . Since $|\mathbb {Q}|=\omega $ , $|\{tp_{bs}(a,A,I^0)\mathrel {|} a\in I^0\}|\leq |\{tp_{bs}(a,Pr(A),\mathcal {R})\mathrel {|} a\in \mathcal {R}\}\times 2^\omega |$ . By Fact 2.9 and since $\lambda ^\omega =\lambda $ , $|\{tp_{bs}(a,A,I^0)\mathrel {|} a\in I\}|< \kappa $ .

Lemma 2.23. Suppose $\kappa =\lambda ^+$ . I is $(<\kappa , bs)$ -stable.

Proof Let us fix $A\subset I$ such that $|A|<\kappa $ . From Fact 2.17, for all $a\in I$ and $\nu \in I^0$ such that $a\in Gen(\nu )$ the following holds:

$$ \begin{align*}b\models tp_{bs}(a,A,I) \Leftrightarrow b\models tp_{bs}(\nu,A \backslash Gen(\nu),I)\cup tp_{bs}(a,A\cap Gen(\nu), Gen(\nu)).\end{align*} $$

Thus for all $a\in I$ and $\nu \in I^0$ with $a\in Gen(\nu )$ , the type of a is determined by $tp_{bs}(\nu ,A \backslash Gen(\nu ),I)$ and $tp_{bs}(a,A \cap Gen(\nu ), Gen(\nu ))$ . Let $A'\subseteq I^0$ be such that the following hold:

• • For all $x\in A$ there is $y\in A'$ , $x\in Gen(y)$ .

• • For all $y\in A'$ there is $x\in A$ , $x\in Gen(y)$ .

Clearly $|A'|\leq |A|$ , and by Fact 2.17, for all $\nu \in I^0$ , $tp_{bs}(\nu ,A\backslash Gen(\nu ),I)$ is determined by $tp_{bs}(\nu ,A'\backslash \{\nu \},I^0)$ . So for all $a\in I$ and $\nu \in I^0$ with $a\in Gen(\nu )$ , $tp_{bs}(a,A,I)$ is determined by $tp_{bs}(\nu ,A'\backslash \{\nu \},I^0)$ and $tp_{bs}(a,A\cap Gen(\nu ), Gen(\nu ))$ . Therefore $|\{tp_{bs}(a,A,I)\mathrel {|} a\in I\}|$ is bounded by

$$ \begin{align*}|\{tp_{bs}(\nu,A',I^0)\mathrel{|} \nu\in I^0\}|\ \times\ Sup(\{\alpha_\nu \mathrel{|} \nu \in I^0\}),\end{align*} $$

where

$$ \begin{align*}\alpha_\nu=|\{tp_{bs}(a,A \cap Gen(\nu), Gen(\nu))\mathrel{|} a\in Gen(\nu)\}|.\end{align*} $$

Claim 2.23.1. For all $\nu \in I^0$ , $Gen(\nu )$ with the induced order is $(<\kappa , bs)$ -stable.

Proof Recall the order $(Gen, <_{Gen})$ . By the non-inductive construction of I, it is enough to show that $(Gen, <_{Gen})$ is $({<}\kappa , bs)$ -stable.

Let $D\subseteq Gen$ be such that $|D|<\kappa $ , and let

$$ \begin{align*}\beta=sup\{f(n)+1\mathrel{|} f\in D\ \&\ n<\omega\}.\end{align*} $$

Since for all $f\in A$ , f is constant to $0$ starting at some m, $\beta <\kappa $ . On the other hand, for all $f,g\in Gen$ , f and g eventually become constants to $0$ , and the order $f<_{Gen}g$ (or $g<_{Gen}f$ ) is determined by the values of $f(i)$ and $g(i)$ , where i is the least ordinal such that $f(i)\neq g(i)$ . Therefore, for all $f\in Gen$ , $tp_{bs}(f,D,Gen)$ is entirely determined by the coordinates n of f in which $f(n)$ is smaller than $\beta +1$ . Since $\lambda ^{\omega }=\lambda $ , and $\beta <\kappa $ , $|\{tp_{bs}(f,D,Gen)\mathrel {|} f\in Gen\}|\leq |\beta ^{<\omega }|\leq \lambda < \kappa $ .

From the previous claim, we conclude that for all $\nu \in I^0$ , $\alpha _\nu <\kappa $ . Since $\kappa =\lambda ^+$ , $Sup(\{\alpha _\nu \mathrel {|} \nu \in I^0\})\leq \lambda $ . From Lemma 2.22 we know that $|\{tp_{bs}(\nu ,A',I^0)\mathrel {|} \nu \in I^0\}|<\kappa $ , so $|\{tp_{bs}(\nu ,A',I^0)\mathrel {|} \nu \in I^0\}|\leq \lambda $ . We conclude $|\{tp_{bs}(a,A,I)\mathrel {|} a\in I\}|<\kappa $ .

Theorem 2.24. There is a $({<}\kappa , bs)$ -stable $(\kappa , bs,bs)$ -nice $\kappa $ -colorable linear order.

Proof From Corollary 2.21 and Lemma 2.23, we only need to show that I is $\kappa $ -colorable. For all $\nu \in I$ let us define $Succ_I(\nu )$ as follows:

$$ \begin{align*} Succ_I(\nu)=\{\sigma\in I\mathrel{|} \sigma=\nu^{o(\sigma)}\}. \end{align*} $$

We use the same notation of ordered trees because I can be seen as an ordered tree. Notice that for all $\nu \in I$ , $|Succ_I(\nu )|=\kappa $ and either $o(\nu )=0$ , or there is a unique $\nu '\in I$ such that $\nu =(\nu ')^{o(\nu )}$ (i.e. $\nu \in Succ_I(\nu ')$ ).

Let us fix $G:\kappa \rightarrow \kappa \times \kappa $ a bijection, and $G_1$ , $G_2$ be the functions such that $G(\alpha )=(G_1(\alpha ),G_2(\alpha ))$ . For all $\nu \in I$ let us fix a bijection $g_\nu :Succ_I(\nu )\rightarrow \kappa $ . Let us define $F:I\rightarrow \kappa $ by

$$ \begin{align*} F(\nu)=\begin{cases} 0, &\mbox{if } o(\nu)=0,\\ G_1(g_{\nu'}(\nu)), & \mbox{where }(\nu')^{o(\nu)}=\nu. \end{cases} \end{align*} $$

Claim 2.24.1. F is a $\kappa $ -coloration of I.

Proof Let $B\subseteq I$ , $|B|<\kappa $ , $b\in I\backslash B$ , and $p= tp_{bs}(b,B,I)$ . Since $|B|<\kappa $ , there is $\gamma <\kappa $ such that $B\subset I^{\gamma }$ . Let $\theta =\max \{o(b), \gamma \}$ , so for all $\nu \in \{a\in Succ_I(b)\mathrel {|} o(a)>\theta \}$ , b and $\nu $ have the same type of basic formulas over $I^\theta \backslash \{b\}$ . In particular for all $\nu \in \{a\in Succ_I(b)\mathrel {|} o(a)>\theta \}$ , $\nu \models p$ . By the way F was defined, we conclude that for any $\alpha <\kappa $ , $|\{a\in Succ_I(b)\mathrel {|} o(a)>\theta \ \&\ F(a)=\alpha \}|=\kappa $ . Which implies that for any $\alpha <\kappa $ , $|\{a\in Succ_I(b)\mathrel {|} a\models p\ \&\ F(a)=\alpha \}|=\kappa $ .

3 Ordered coloured trees

3.1 Coloured trees

We will use the $\kappa $ -colorable linear order I to construct trees with $\omega +1$ levels, $A^f(I)$ , for every $f\in \kappa ^\kappa $ with the property $A^f(I) \cong A^g(I)$ if and only if $f\ =^\kappa _{\omega }\ g$ . These tress will be a mix of coloured tree and ordered trees. For clarity and to avoid misunderstandings, in this section we will denote trees by $(T,\prec )$ . Later on we will see that $\prec $ is the initial segment relation of the trees that we construct. The coloured trees that we will use in this section, are essentially the same trees used by Hyttinen and Weinstein (né Kulikov) in [5] and by Hyttinen and Moreno in [7].

Let t be a tree; for every $x\in t$ we denote by $ht(x)$ the height of x, the order type of $\{y\in t | y\prec x\}$ . Define $(t)_\alpha =\{x\in t|ht(x)=\alpha \}$ and $(t)_{<\alpha }=\cup _{\beta <\alpha }(t)_\beta $ , denote by $x{\mathbin \upharpoonright } \alpha $ the unique $y\in t$ such that $y\in (t)_\alpha $ and $y\prec x$ . If $x,y\in t$ and $\{z\in t|z\prec x\}=\{z\in t|z\prec y\}$ , then we say that x and y are $\sim $ -related, $x\sim y$ , and we denote by $[x]$ the equivalence class of x for $\sim $ .

An $\alpha , \beta $ -tree is a tree t with the following properties:

• • $|[x]|<\alpha $ for every $x\in t$ .

• • All the branches have order type less than $\beta $ in t.

• • t has a unique root.

• • If $x,y\in t$ , x and y have no immediate predecessors and $x\sim y$ , then $x=y$ .

Definition 3.1. Let $\lambda $ be a cardinal smaller than $\kappa $ , and $\beta $ a cardinal smaller than or equal to $\kappa $ . A coloured tree with $\beta $ colors is a pair $(t,c)$ , where t is a $\kappa ^+$ , $(\lambda +2)$ -tree and c is a map $c:(t)_\lambda \rightarrow \beta $ (the color function).

Two coloured trees $(t,c)$ and $(t',c')$ are isomorphic, if there is a tree isomorphism $f:t\rightarrow t'$ such that for every $x\in (t)_\lambda $ , $c(x)=c'(f(x))$ . We will denote by $\cong _{ct}$ the isomorphism of coloured trees

We will only consider trees in which every element with height less than $\lambda $ , has infinitely many immediate successors, and every maximal branch has order type $\lambda +1$ . Notice that the intersection of two distinct branches has order type less than $\lambda $ . We can see every coloured tree as a downward closed subset of $\kappa ^{\leq \lambda }$ . In this section all the coloured trees have $\lambda =\omega $ .

An ordered coloured tree with $\beta $ colors, $\beta \leq \kappa $ , is a tree $T\in K_{tr}^\omega $ with a color function $c:(t)_\omega \rightarrow \beta $ .

We will follow the construction used in [5, 7].

Let us start from coloured trees which are subsets of $(\omega \times \kappa ^4)^{\leq \omega }$ , and let us make some preparation before the actual construction. Order the set $\omega \times \kappa \times \kappa \times \kappa \times \kappa $ lexicographically, $(\alpha _1,\alpha _2,\alpha _3,\alpha _4,\alpha _5)>(\theta _1,\theta _2,\theta _3,\theta _4,\theta _5)$ if for some $1\leq k \leq 5$ , $\alpha _k>\theta _k$ and for every $i<k$ , $\alpha _i=\theta _i$ . Order the set $(\omega \times \kappa \times \kappa \times \kappa \times \kappa )^{\leq \omega }$ as a tree by initial segments.

For all $f\in \beta ^\kappa $ , define the tree $(R_f,r_f)$ as: $R_f$ be the set of all strictly increasing functions from some $n\leq \omega $ to $\kappa $ , and $r_f$ be the color function such that for each $\eta $ with domain $\omega $ , $r_f(\eta )=f(sup(rng(\eta )))$ .

For every pair of ordinals $\alpha $ and $\theta $ , $\alpha <\theta <\kappa $ , and $i<\omega $ , define

$$ \begin{align*} R(\alpha,\theta,i)=\bigcup_{i< j\leq \omega}\{\eta:[i,j)\rightarrow[\alpha,\theta)\mathrel{|} \eta \text{ strictly increasing}\}.\end{align*} $$

Definition 3.2. If $\alpha <\theta <\kappa $ and $\alpha ,\theta ,\gamma \neq 0$ , let $\{Z^{\alpha ,\theta }_\gamma |\gamma <\kappa \}$ be an enumeration of all downward closed subtrees of $R(\alpha ,\theta ,i)$ for all i, in such a way that each possible coloured tree appears cofinally often in the enumeration. Let $Z^{0,0}_0$ be the tree $(R_f,r_f)$ .

This enumeration is possible because there are at most $|\bigcup _{i<\omega }\mathcal {P}(R(\alpha ,\theta ,i))|\leq \omega \times \kappa =\kappa $ downward closed coloured subtrees. Since for all $\theta <\kappa $ , $|R(\alpha ,\theta ,i)|<\kappa $ there are at most $\kappa \times \kappa ^{<\kappa }=\kappa $ coloured trees.

Definition 3.3. Let $\beta \leq \kappa $ be a cardinal. Define for every $f\in \beta ^\kappa $ the coloured tree $(J_f,c_f)$ with $\beta $ colors, by the following construction. Let $J_f=(J_f,c_f)$ as the tree of all $\eta : s\rightarrow \omega \times \kappa ^4$ , where $s\leq \omega $ , ordered by endextension, and such that the following conditions hold for all $i,j<s$ : Denote by $\eta _i$ , $1<i<5$ , the functions from s to $\kappa $ that satisfies

$$ \begin{align*} \eta(n)=(\eta_1(n),\eta_2(n),\eta_3(n),\eta_4(n),\eta_5(n)). \end{align*} $$

1. (1) $\eta {\mathbin \upharpoonright }_n\in J_f$ for all $n<s$ .

2. (2) $\eta $ is strictly increasing with respect to the lexicographical order on $\omega \times \kappa ^4$ .

3. (3) $\eta _1(i)\leq \eta _1(i+1)\leq \eta _1(i)+1$ .

4. (4) $\eta _1(i)=0$ implies $\eta _2(i)=\eta _3(i)=\eta _4(i)=0$ .

5. (5) $\eta _1(i)<\eta _1(i+1)$ implies $\eta _2(i+1)\ge \eta _3(i)+\eta _4(i)$ .

6. (6) $\eta _1(i)=\eta _1 (i+1)$ implies $\eta _k (i)=\eta _k (i+1)$ for $k\in \{2,3,4\}$ .

7. (7) If for some $k<\omega $ , $[i,j)=\eta _1^{-1}\{k\}$ , then

   $$ \begin{align*} \eta_5\mathbin{\upharpoonright}_{[i,j)}\in Z^{\eta_2(i),\eta_3(i)}_{\eta_4(i)}. \end{align*} $$
   Note that (7) implies $Z^{\eta _2(i),\eta _3(i)}_{\eta _4(i)}\subset R(\alpha ,\theta ,i).$

8. (8) If $s=\omega $ , then either

   1. (a) there exists a natural number m such that $\eta _1(m-1)<\eta _1(m)$ , for every $k \ge m$ $\eta _1(k)=\eta _1(k+1)$ , and the color of $\eta $ is determined by $Z^{\eta _2(m),\eta _3(m)}_{\eta _4(m)}$ :

      $$ \begin{align*} c_f(\eta)=c(\eta_5\mathbin{\upharpoonright}_{[m,\omega)}), \end{align*} $$
      where c is the coloring function of $Z^{\eta _2(m),\eta _3(m)}_{\eta _4(m)}$ ,

   or

   1. (b) there is no such m and then $c_f(\eta )=f(sup(rng(\eta _5)))$ .

Notice that for every $f\in \beta ^\kappa $ and $\delta <\kappa $ with $cf(\delta )=\omega $ , there is $\eta \in J_f$ such that $rng(\eta _1)=\omega $ and $\eta _5$ is cofinal to $\delta $ . This $\eta $ can be constructed by taking $\langle \xi (i)\mathrel {|} i<\omega \rangle $ a cofinal sequence to $\delta $ , let $\eta _1=id$ ; let $\eta _2$ , $\eta _3$ , and $\eta _4$ be such that for every $i<\omega $ , $\xi {\mathbin \upharpoonright } \{i\}\in Z^{\eta _2(i),\eta _3(i)}_{\eta _4(i)}$ . Finally let $\eta _5{\mathbin \upharpoonright } \{i\}=\xi {\mathbin \upharpoonright } \{i\}$ . It is clear that $\eta \in J_f$ , $rng(\eta _1)=\omega $ , and $\eta _5$ is cofinal to $\delta $ . In particular this $\eta $ satisfies $c_f(\eta )=f(\delta )$ .

Fact 3.4 (Hyttinen–Kulikov [5, Lemma 2.5]; Hyttinen–Moreno [7, Lemma 4.7]).

Suppose $\kappa $ is such that for all $\gamma <\kappa $ , $\gamma ^\omega <\kappa $ . For every $f,g\in \beta ^\kappa $ the following holds:

$$ \begin{align*} f\ =^\beta_\omega\ g \Leftrightarrow J_f\cong_{ct} J_g, \end{align*} $$

where $\cong _{ct}$ is the isomorphism of coloured trees.

The previous fact is an important step in [5, 7] to construct a reductions from $=^2_\omega $ to the isomorphism relation of different stable unsuperstable theories. We will use the coloured trees $J_f$ to construct ordered coloured trees. Before we start with the construction of the ordered coloured trees, let us prove an important property of the coloured trees.

Lemma 3.5. For every $f\in \beta ^\kappa $ , $\theta <\beta $ , and $\eta \in (J_f)_{<\omega }$ , there is $\xi \in (J_f)_\omega $ such that $\eta \prec \xi $ and $c_f(\xi )=\theta $ .

Proof Let $f\in \beta ^\kappa $ , such that $\eta \in (J_g)_{<\omega }$ , and $n=dom(\eta )$ .

Let us construct $\xi $ , $\eta \prec \xi $ and $c_f(\xi )=\theta $ .

• • $\xi {\mathbin \upharpoonright } n=\eta $ .

• • If $n\leq m<\omega $ ,

  1. – $\xi _1(m)=\xi _1(n-1)+1$ .

  2. – $\xi _2(m)=\xi _3(n-1)+\xi _4(n-1)$ .

  3. – $\xi _3(m)=\xi _2(n)+\omega $ .

  4. – Let $\gamma $ and $\zeta $ be such that $dom(\zeta )=[n,\omega )$ , $\zeta \in Z^{\xi _2(n),\xi _3(n)}_{\gamma }$ with $c(\zeta )=\theta $ . Such $\gamma $ and $\zeta $ exist by Definition 3.2.

  5. – $\xi _4(m)=\gamma $ .

  6. – $\xi _5{\mathbin \upharpoonright }_{[n,\omega )}=\zeta $ .

By the way we defined $\xi $ , we know that $\xi \in J_f$ and $\eta \prec \xi $ . By the item (8)(a) on the construction of $J_f$ , we know that $c_f(\xi )=c(\xi _5{\mathbin \upharpoonright }_{[n,\omega )})=\theta $ .

Notice that for any $f,g\in \beta ^\kappa $ , $J_f$ and $J_g$ are isomorphic as trees but not as coloured trees. This is because f is only used to define the color function of $J_f$ .

3.2 Construction of ordered coloured trees

For each $f\in \beta ^{\kappa }$ we will use the coloured trees $J_f$ to construct ordered coloured trees, which will be the base for the construction of the models in Section 4.

Let us define the following subtrees:

$$ \begin{align*}J_f^\alpha=\{\eta\in J_f\mathrel{|} \exists\theta<\alpha~(rng(\eta)\subset \omega\times\theta^4)\}.\end{align*} $$

Notice that $J_f^0=\{\emptyset \}$ and $dom(\emptyset )=0$ . Let us denote by $\operatorname {\mathrm {acc}}(\kappa )=\{\alpha <\kappa \mathrel {|} \alpha =0 \text {or}~ \alpha \text { is a limit ordinal}\}$ . For all $\alpha \in \operatorname {\mathrm {acc}}(\kappa )$ and $\eta \in J_f^\alpha $ with $dom(\eta )=m<\omega $ define

$$ \begin{align*}W_\eta^\alpha=\{\zeta\mathrel{|} dom(\zeta)=[m,s), m\leq s\leq \omega, \eta^\frown\zeta\in J_f^{\alpha+\omega}, \eta^\frown (\zeta\mathbin{\upharpoonright} \{m\})\notin J_f^\alpha\}.\end{align*} $$

Notice that by the way $J_f$ was constructed, for every $\eta \in J_f$ with finite domain and $\alpha <\kappa $ , the set

$$ \begin{align*}\{(\theta_1,\theta_2,\theta_3,\theta_4,\theta_5)\in (\omega\times \kappa^4)\backslash (\omega\times\alpha^4)\mathrel{|} \eta^\frown (\theta_1,\theta_2,\theta_3,\theta_4,\theta_5)\in J_f^{\alpha+\omega}\}\end{align*} $$

is either empty or has size $\omega $ . Let $\sigma _\eta ^\alpha $ be an enumeration of this set, when this set is not empty.

Let us denote by $\mathcal {T}=(\kappa \times \omega \times \operatorname {\mathrm {acc}}(\kappa )\times \omega \times \kappa \times \kappa \times \kappa \times \kappa )^{\leq \omega }$ . For every $\xi \in \mathcal {T}$ there are functions $\{\xi _i\in \kappa ^{\leq \omega }\mathrel {|} 0<i\leq 8\}$ such that for all $i\leq 8$ , $dom(\xi _i)=dom(\xi )$ and for all $n\in dom(\xi )$ , $\xi (n)=(\xi _1(n),\xi _2(n),\xi _3(n),\xi _4(n),\xi _5(n),\xi _6(n),\xi _7(n),\xi _8(n))$ . For every $\xi \in \mathcal {T}$ let us denote $(\xi _4,\xi _5,\xi _6,\xi _7,\xi _8)$ by $\overline {\xi }$ .

Definition 3.6. For all $\alpha \in \operatorname {\mathrm {acc}}(\kappa )$ and $\eta \in \mathcal {T}$ with $\overline {\eta }\in J_f$ , $dom(\eta )=m<\omega $ define $\Gamma _\eta ^\alpha $ as follows:

If $\overline {\eta }\in J_f^\alpha $ , then $\Gamma _\eta ^\alpha $ is the set of elements $\xi $ of $\mathcal {T}$ such that:

1. (1) $\xi {\mathbin \upharpoonright } m=\eta ,$

2. (2) $\overline {\xi }{\mathbin \upharpoonright } dom(\xi )\backslash m \in W^\alpha _\eta ,$

3. (3) $\xi _3$ is constant on $dom(\xi )\backslash m,$

4. (4) $\xi _3(m)=\alpha $ ,

5. (5) for all $n\in dom(\xi )\backslash m$ , let $\xi _2(n)$ be the unique $r<\omega $ such that $\sigma _{\zeta }^\alpha (r)=\overline {\xi }(n)$ , where $\zeta =\overline {\xi }{\mathbin \upharpoonright } n$ .

If $\overline {\eta }\notin J_f^\alpha $ , then $\Gamma _\eta ^\alpha =\emptyset $ .

Notice that $\xi _2(n)$ and $\xi _3(n)$ can be calculated from $\overline {\xi }(n)$ and $\eta $ .

For $\eta \in \mathcal {T}$ with $\overline {\eta }\in J_f$ , $dom(\eta )=m<\omega $ define

$$ \begin{align*}\Gamma(\eta)=\bigcup_{\alpha\in \operatorname{\mathrm{acc}}(\kappa)}\Gamma_\eta^\alpha .\end{align*} $$

Finally we can define $A^f$ by induction. Let $T_f(0)=\{\emptyset \}$ and for all $n<\omega $ ,

$$ \begin{align*}T_f(n+1)=T_f(n)\cup\bigcup_{\eta\in T_f(n)~dom(\eta)=n}\Gamma(\eta),\end{align*} $$

and for $n=\omega $ ,

$$ \begin{align*}T_f(\omega)=\bigcup_{n<\omega}T_f(n).\end{align*} $$

For $0<i\leq 8$ let us denote by $s_i(\eta )=sup\{\eta _i(n)\mathrel {|} n<\omega \}$ and $s_\omega (\eta )=sup\{s_i(\eta )\mathrel {|} i\leq 8\}$ , finally

$$ \begin{align*}A^f=T_f(\omega)\cup \{\eta\in \mathcal{T}\mathrel{|} dom(\eta)=\omega, \forall m<\omega (\eta\mathbin{\upharpoonright} m\in T_f(\omega))\}.\end{align*} $$

Define the color function $d_f$ by

(2) $$ \begin{align} d_f(\eta)=\begin{cases} c_f(\overline{\eta}), &\mbox{if } s_1(\eta)< s_\omega(\eta),\\ f(s_1(\eta)), & \mbox{if } s_1(\eta)= s_\omega(\eta). \end{cases} \end{align} $$

It is clear that $A^f$ is closed under initial segments; indeed, the relations $\prec $ , $(P_n)_{n\leq \omega }$ , and h of Definition 2.1 have a canonical interpretation in $A^f$ .

Now we finish the construction of $A^f$ by using the $\kappa $ -colorable linear order I. We only have to define $<{\mathbin \upharpoonright } Suc_{A^f}(\eta )$ for all $\eta \in A^f$ with finite domain. Properly speaking, $A^f$ will not be an ordered coloured tree as in Definition 2.1, but it will be isomorphic to an ordered coloured tree as in Definition 2.1.

Let us proceed to define $<{\mathbin \upharpoonright } Suc_{A^f}(\eta )$ . Let $F:I\rightarrow \kappa $ be a $\kappa $ -coloration of I.

For any $\eta \in A^f$ with domain $m<\omega $ , we will define the order $<{\mathbin \upharpoonright } Suc_{A^f}(\eta )$ such that it is isomorphic to I and satisfies the following:

$(\ast )$ For any set $B\subset Suc_{A^f}(\eta )$ of size less than $\kappa $ , $p(x)$ a type of basic formulas over B in the variable x, and any tuple $(\theta _2,\theta _3)\in \omega \times \operatorname {\mathrm {acc}}(\kappa )$ with $\theta _3\ge \eta _3(m-1)$ , if $p(x)$ is realized in $Suc_{A^f}(\eta )$ , then there are $\kappa $ many $\gamma <\kappa $ such that $\eta ^\frown (\gamma ,\theta _2,\theta _3,\sigma ^{\theta _3}_{\overline {\eta }}(\theta _2))\models p(x)$ .

By the construction of $A^f$ , an isomorphism between $\{(\theta _1,\theta _2,\theta _3)\in \kappa \times \omega \times \operatorname {\mathrm {acc}}(\kappa )\mathrel {|} \theta _3\ge \eta _3(m-1) \}$ and I, induces an order in $Suc_{A^f}(\eta )$ .

Definition 3.7. Recall the coloration F of I in Theorem 2.24. For all $\theta , \alpha <\kappa $ , let fix bijections $\tilde {G}_\theta :\{(\theta _2,\theta _3)\in \omega \times \operatorname {\mathrm {acc}}(\kappa ) \mathrel {|} \theta _3\ge \theta \}\rightarrow \kappa $ and $\tilde {H}_\alpha :F^{-1}[\alpha ]\rightarrow \kappa $ . Notice that these functions exist because F is a $\kappa $ -coloration of I and there are $\kappa $ tuples $(\theta _2,\theta _3)$ of this form.

Let us define $\tilde {\mathcal {G}}_\theta :\{(\theta _1,\theta _2,\theta _3)\in \kappa \times \omega \times \operatorname {\mathrm {acc}}(\kappa ) \mathrel {|} \theta _3\ge \theta \}\rightarrow I$ , by $\tilde {\mathcal {G}}_\theta ((\theta _1,\theta _2,\theta _3)) =a$ where a and $\alpha $ are the unique elements that satisfy:

• • $\tilde {G}_\theta ((\theta _2,\theta _3))=\alpha $ ;

• • $\tilde {H}_\alpha (a)=\theta _1$ .

For any $\eta \in A^f$ with domain $m<\omega $ and $\eta _3(m-1)=\theta $ , the isomorphism $\tilde {\mathcal {G}}_\theta $ induces an order in $Suc_{A^f}(\eta )$ . Let us define $<{\mathbin \upharpoonright } Suc_{A^f}(\eta )$ as the induced order given by $\tilde {\mathcal {G}}_\theta $ .

Fact 3.8. Suppose $\eta \in A^f$ has domain $m<\omega $ and $\eta _3(m-1)=\theta $ . Then

$<{\mathbin \upharpoonright } Suc_{A^f}(\eta )$ satisfies ( $*$ ).

Proof Let $b\in Suc_{A^f}(\eta )$ , $(\theta _2,\theta _2)\in \omega \times \operatorname {\mathrm {acc}}(\kappa )$ such that $\theta _3\ge \eta _3(m-1)=\theta $ , and $B\subseteq Suc_{A^f}(\eta )$ have size less than $\kappa $ . Let us denote by q the type

$$ \begin{align*}tp_{bs}(\tilde{\mathcal{G}}_\theta(b_1,b_2,b_3), \tilde{\mathcal{G}}_\theta (B\cap(\kappa\times\omega\times \operatorname{\mathrm{acc}}(\kappa))), I).\end{align*} $$

By the construction of $\tilde {G}_\theta $ , since F is a $\kappa $ -coloration of I,

$$ \begin{align*}|\{a\in I\mathrel{|} a\models q \ \&\ F(a)=\tilde{G}_\theta(\theta_2,\theta_3)\}|=\kappa.\end{align*} $$

Therefore, for all a such that $a\models q$ and $F(a)=\tilde {G}_\theta (\theta _2,\theta _3)$ ,

$$ \begin{align*}\eta^\frown (\tilde{H}_{\tilde{G}_\theta((\theta_2,\theta_3))}(a),\theta_2,\theta_3,\sigma^{\theta_3}_{\overline{\eta}}(\theta_2))\models p.\\[-34pt] \end{align*} $$

It is clear that $(A^f,\prec ,(P_n)_{n\leq \omega },<, h)$ is isomorphic to a subtree of $I^{\leq \omega }$ in the sense of Definition 2.1.

Remark 3.9. Notice that for any $\eta \in A^f$ , $<{\mathbin \upharpoonright } Suc_{A^f}(\eta )$ is isomorphic to I. Therefore, for any $\zeta ,\eta \in A^f$ , $<{\mathbin \upharpoonright } Suc_{A^f}(\zeta )$ and $<{\mathbin \upharpoonright } Suc_{A^f}(\eta )$ are isomorphic. Even more, the construction of $<{\mathbin \upharpoonright } Suc_{A^f}(\eta )$ only depends on $\eta _3(m-1)$ , where $m<\omega $ is the domain of $\eta $ .

Notice that the only property we used from I to construct the ordered coloured trees was that it is a $\kappa $ -colorable linear order. Therefore the construction can be done with any $\kappa $ -colorable linear order.

Theorem 3.10. Suppose $f,g\in \beta ^\kappa $ , then $f\ =^\beta _\omega \ g$ if and only if $A^f\cong A^g$ (as ordered coloured trees).

Proof For every $f\in \beta ^\kappa $ let us define the $\kappa $ -representation $\mathbb {A}^f=\langle A^f_\alpha \mathrel {|} \alpha <\kappa \rangle $ of $A^f$ ,

$$ \begin{align*}A^f_\alpha=\{\eta\in A^f\mathrel{|} rng(\eta)\subseteq \theta\times\omega\times\theta\times\omega\times\theta^4\text{ for some }\theta<\alpha\}. \end{align*} $$

Let f and g be such that $f\ =^\beta _\omega \ g$ . Thus, there is G a coloured tree isomorphism between $J_f$ and $J_g$ . Let $C\subseteq \kappa $ be a club such that $\{\alpha \in C\mathrel {|} cf(\alpha )=\omega \}\subseteq \{\alpha <\kappa \mathrel {|} f(\alpha )=g(\alpha )\}$ . We will show that there are sequences $\{\alpha _i\}_{i<\kappa }$ and $\{F_i\}_{i<\kappa }$ with the following properties:

• • $\{\alpha _i\}_{i<\kappa }$ is a club.

• • If i is a successor, then there is $\theta \in C$ such that $\alpha _{i-1}<\theta <\alpha _i$ .

• • If $i=\gamma +n$ and n is odd, $F_i$ is a partial isomorphism between $A^f$ and $A^g$ , and $A_{\alpha _i}^f\subseteq dom(F_i)$ .

• • If $i=\gamma +n$ and n is even, $F_i$ is a partial isomorphism between $A^f$ and $A^g$ , and $A_{\alpha _i}^g\subseteq rng(F_i)$ .

• • If i is limit, then $F_i:A_{\alpha _i}^f\rightarrow A_{\alpha _i}^g$ .

• • If $i<j$ , then $F_i\subseteq F_j$ .

• • For all $\eta \in dom(F_i)$ , $G(\overline {\eta })=\overline {F_i(\eta )}$ .

We will proceed by induction over i, for the case $i=0$ , let $\alpha _0=0$ and $F_0(\emptyset )=\emptyset $ . Suppose $i=\gamma +n$ with n even is such that $F_i$ is a partial isomorphism, $A_{\alpha _i}^g\subseteq rng(F_i)$ for all $j<i$ , $F_j\subseteq F_i$ , and $G(\overline {\eta })=\overline {F_i(\eta )}$ for all $\eta \in dom(F_i)$ .

Let us choose $\alpha _{i+1}$ to be a successor ordinal such that $\alpha _{i}<\theta <\alpha _{i+1}$ holds for some $\theta \in C$ and enumerate $A^f_{\alpha _{i}}$ by $\{\eta _j\mathrel {|} j<\Omega \}$ for some $\Omega <\kappa $ . Denote by $B_j$ the set $\{x\in A^f_{\alpha _{i+1}}\backslash dom(F_i)\mathrel {|} \eta _j\prec x\}$ .

By the induction hypothesis, we know that for all $j<\Omega $ , $x\in B_j$ , $\overline {F_i(\eta _j)}\prec G(\overline {x})$ . By Remark 3.9, for all $\eta \in A^f$ and $\xi \in A^g$ , $<{\mathbin \upharpoonright } Suc_{A^f}(\eta )$ and $<{\mathbin \upharpoonright } Suc_{A^g}(\xi )$ are isomorphic. Thus, since $|A^f_{\alpha _{i}}|, |B_0|<\kappa $ , by $(\ast )$ there is an embedding $F^0_i$ from $(A^f_{\alpha _i}\cup B_0,\prec ,<)$ to $(A^g,\prec , <)$ that extends $F_i$ and for all $\eta \in dom(F^0_i)$ , $\overline {F^0_i(\eta )}=G(\overline {\eta })$ .

For the case $B_j$ for $j>0$ , let us suppose that $t<\Omega $ is such that the following hold:

• • There is a sequence of embeddings $\{F_i^j\mathrel {|} j<t\}$ , where $F^j_i$ is an embedding from $(A^f_{\alpha _i}\cup \bigcup _{l\leq j}B_l,\prec ,<)$ into $A^g$ .

• • $F_i^l\subseteq F_i^j$ holds for all $l<j<t$ .

• • For all $\eta \in dom(F^j_i)$ , $\overline {F^j_i(\eta )}=G(\overline {\eta })$ .

Since $|A^f_{\alpha _{i}}\cup \bigcup _{j< t}B_j|, |B_t|<\kappa $ , by $(\ast )$ there is an embedding $F^t_i$ from $(A^f_{\alpha _i}\cup \bigcup _{j\leq t}B_j,\prec ,<)$ to $(A^g,\prec , <)$ that extends $\bigcup _{j<t} F_i^j$ and for all $\eta \in dom(F^t_i)$ , $\overline {F^t_i(\eta )}=G(\overline {\eta })$ .

Finally $F_{i+1}=\bigcup _{j<\Omega } F_i^j$ is as wanted.

The case $i=\gamma +n$ with n odd is similar. For i limit, we define $\alpha _i=\bigcup _{j<i} \alpha _j$ and $F_{\alpha _{i}}=\bigcup _{j<i} F_j$ .

It is clear that $F=\bigcup _{j<\kappa } F_j$ witnesses that $A^f$ and $A^g$ are isomorphic as ordered trees. Let us show that $d_f(\eta )=d_g(F(\eta ))$ , and suppose $\eta \in A^f$ is a leaf. Let l be the least ordinal such that $\eta \in A^f_{\alpha _l}$ . If there is $n<\omega $ such that for all $j<l$ , $\eta {\mathbin \upharpoonright } n\notin A^f_{\alpha _j}$ , then by the way F was constructed, $d_f(\eta )=d_g(F(\eta ))$ . On the other hand, if for all $n<\omega $ there is $j<l$ such that $\eta {\mathbin \upharpoonright } n\in A^f_{\alpha _j}$ , then there is an $\omega $ -cofinal ordinal i such that $s_\omega (\eta )=\alpha _i$ and $i+1=l$ .

By the construction of $A^f$ (recall equation (2)) we know that

$$ \begin{align*}d_f(\eta)=\begin{cases} c_f(\overline{\eta}), &\mbox{if } s_1(\eta)< s_\omega(\eta),\\ f(s_1(\eta)), & \mbox{if } s_1(\eta)= s_\omega(\eta). \end{cases} \end{align*} $$

Since $s_\omega (\eta )=\alpha _i$ , either $d_f(\eta )=f(s_1(\eta ))$ (if $s_1(\eta )=\alpha _i$ ) or $d_f(\eta )=c_f(\overline {\eta })$ (if $s_1(\eta )<\alpha _i$ ).

Therefore, if $s_1(\eta )=\alpha _i$ , then $d_f(\eta )=f(\alpha _i)$ .

Let us calculate $d_f(\eta )$ , when $s_1(\eta )< s_\omega (\eta )$ . Notice that $\overline {\eta }\in J_j$ , so there is $\zeta =(\zeta _1,\zeta _2,\zeta _3,\zeta _4,\zeta _5)$ such that $\overline {\eta }=\zeta \in J_j$ .

From Definition 3.3 items (5) and (7), since $\zeta \in (J_f)_\omega \backslash J_f^{\alpha _i}$ and for all $n<\omega $ , $\zeta {\mathbin \upharpoonright } n\in J_f^{\alpha _i}$ holds,

$$ \begin{align*}sup(rng(\zeta_4))\leq sup(rng(\zeta_2))=sup(rng(\zeta_3))=sup(rng(\zeta_5)).\end{align*} $$

Since $\overline {\eta }=\zeta $ ,

$$ \begin{align*}s_7(\eta)\leq s_8(\eta)=s_6(\eta)=s_8(\eta)=sup(rng(\zeta_5).\end{align*} $$

It is easy to see that $s_2(\eta ),s_3(\eta ),s_4(\eta )\leq s_5(\eta )$ .

We conclude that $s_\omega (\eta )=s_8(\eta )=sup(rng(\zeta _5))$ and $\alpha _i=sup(rng(\zeta _5))$ . From Definition 3.3(8),

$$ \begin{align*}c_f(\overline{\eta})=c_f(\zeta)=f(sup(rng(\zeta_5)))=f(\alpha_i).\end{align*} $$

Therefore $d_f(\eta )=f(\alpha _i)$ in both cases ( $s_1(\eta )=s_\omega (\eta )$ and $s_1(\eta )<s_\omega (\eta )$ ).

By the same argument and using the definition of F, we can conclude that $d_g(F(\eta ))=g(\alpha _i)$ . Finally since i is a limit ordinal with cofinality $\omega $ , $\alpha _i$ is an $\omega $ -limit of C. Thus $d_f(\eta )=f(\alpha _i)=g(\alpha _i)=d_g(F(\eta ))$ and F is a coloured tree isomorphism.

Now let us prove that if $A^f$ and $A^g$ are isomorphic ordered coloured trees, then $f~ =^\beta _\omega ~ g$ .

Let us start by defining the following function $H_f\in \beta ^\kappa $ . For every $\alpha \in \kappa $ with cofinality $\omega $ , define $B_\alpha =\{\eta \in A^f\backslash A^f_\alpha \mathrel {|} dom(\eta )=\omega ~\wedge ~\forall n<\omega ~(\eta {\mathbin \upharpoonright } n\in A^f_\alpha )\}$ . Notice that by the construction of $A^f$ and the definition of $A^f_\alpha $ , for all $\eta \in B_\alpha $ we have $d_f(\eta )=f(s_\omega (\eta ))=f(\alpha )$ . Therefore, the value of $f(\alpha )$ can be obtained from $B_\alpha $ and $d_f$ , and we can define the function $H_f\in \beta ^\kappa $ as:

$$ \begin{align*}H_f(\alpha)=\begin{cases} f(\alpha), &\mbox{if } cf(\alpha)=\omega,\\ 0, & \mbox{otherwise. } \end{cases}\end{align*} $$

This function can be obtained from the $\kappa $ -representation $\{A^f_\alpha \}_{\alpha <\kappa }$ and $d_f$ . It is clear that $f~ =^\beta _\omega ~ H_f$ .

Claim 3.10.1. If $A^f$ and $A^g$ are isomorphic ordered coloured trees, then $H_f~ =^\beta _\omega ~ H_g$ .

Proof Let F be an ordered coloured tree isomorphism. It is easy to see that $\{F[A^f_{\alpha }]\}_{\alpha <\kappa }$ is a $\kappa $ -representation. Define $C=\{\alpha <\kappa \mathrel {|} F[A^f_\alpha ]=A^g_\alpha \}$ . Since F is an isomorphism, for all $\alpha \in C$ , $H_f(\alpha )=H_g(\alpha )$ . Therefore it is enough to show that C is $\omega $ -closed and unbounded. By the definition of $\kappa $ -representation, if $(\alpha _n)_{n<\omega }$ is a sequence of elements of C cofinal to $\gamma $ , then $A^g_\gamma =\bigcup _{n<\omega }A^g_{\alpha _n}=\bigcup _{n<\omega }F[A^f_{\alpha _n}]=F[A^f_\gamma ]$ . We conclude that C is $\omega $ -closed.

Let us finish by showing that C is unbounded. Fix an ordinal $\alpha <\kappa $ , and let us construct a sequence $(\alpha _n)_{n\leq \omega }$ such that $\alpha _\omega \in C$ and $\alpha _\omega>\alpha $ . Define $\alpha _0=\alpha $ . For every odd n, define $\alpha _{n+1}$ to be the least ordinal bigger than $\alpha _n$ such that $F[A^f_{\alpha _n}]\subseteq A^g_{\alpha +1}$ . For every even n, define $\alpha _{n+1}$ to be the least ordinal bigger than $\alpha _n$ such that $A^g_{\alpha _n}\subseteq F[A^f_{\alpha +1}]$ . Define $\alpha _\omega =\bigcup _{n<\omega }\alpha _n$ . Clearly $\bigcup _{i<\omega }F[A^f_{\alpha _{2i}}]=\bigcup _{i<\omega }A^g_{\alpha _{2i+1}}$ . We conclude that $\alpha _\omega \in C$ .

Remark 3.11. Same as in the construction of the coloured trees $J_f$ , the function $f\in \beta ^\kappa $ is only used to define the color function in the construction of $A^f$ . So if $f,g\in \beta ^\kappa $ and $\alpha $ are such that $f{\mathbin \upharpoonright }\alpha =g{\mathbin \upharpoonright }\alpha $ , then $J_f^\alpha =J_g^\alpha $ . As a consequence $f{\mathbin \upharpoonright }\alpha =g{\mathbin \upharpoonright }\alpha $ implies that $A^f_\alpha = A^g_\alpha $ .

Notice that the only property of $<{\mathbin \upharpoonright } Suc_{A^f}(\eta )$ that we used in the previous theorem was ( $*$ ). Therefore, the previous theorem can be generalized to the following corollary.

Corollary 3.12. Suppose l is a $\kappa $ -colorable linear order and $\beta \leq \kappa $ . Then for any $f\in \beta ^\kappa $ , there is an ordered coloured tree $A^f(l)$ that satisfies: For all $f,g\in \beta ^\kappa $ ,

$$ \begin{align*}f\ =^\beta_\omega\ g\ \Leftrightarrow A^f(l)\cong A^g(l).\end{align*} $$

4 The models

4.1 Generalized Ehrenfeucht–Mostowski models

In this section we will use the generalized Ehrenfeucht–Mostowski models (see [12, Chapter VII.2] or [8, Section 8]) to construct the models of unsuperstable theories, and we will use the previous constructed ordered coloured trees (from I) as the skeleton of the construction.

Definition 4.1 (Generalized Ehrenfeucht–Mostowski models).

We say that a function $\Phi $ is proper for $K_{tr}^\gamma $ , if there is a vocabulary $\mathcal {L}^1$ and for each $A\in K_{tr}^\gamma $ , there is a model $\mathcal {M}_1$ and tuples $a_s$ , $s\in A$ , of elements of $\mathcal {M}_1$ such that the following two hold:

• • Every element of $\mathcal {M}_1$ is an interpretation of some $\mu (a_s)$ , where $\mu $ is an $\mathcal {L}^1$ -term.

• • $tp_{at}(a_s, \emptyset , \mathcal {M}_1)=\Phi (tp_{at}(s, \emptyset , A))$ .

Notice that for each A, the previous conditions determine $\mathcal {M}_1$ up to isomorphism. We may assume $\mathcal {M}_1$ , $a_s$ , $s\in A$ , are unique for each A. We denote $\mathcal {M}_1$ by $EM^1(A,\Phi )$ . We call $EM^1(A,\Phi )$ an Ehrenfeucht–Mostowski model.

Suppose T is a countable complete theory in a countable vocabulary $\mathcal {L}$ , $\mathcal {L}^1$ a Skolemization of $\mathcal {L}$ , and $T^1$ the Skolemization of T by $\mathcal {L}^1$ . If there is $\Phi $ a proper function for $K_{tr}^\gamma $ , then for every $A\in K_{tr}^\gamma $ , we will denote by EM $(A,\Phi )$ the $\mathcal {L}$ -reduction of $EM^1(A,\Phi )$ . The following result ensures the existence of a proper function $\Phi $ for unsuperstable theories T and $\gamma =\omega $ .

Fact 4.2 (Shelah [11, Theorem 1.3], proof in [12, Chapter VII.3]).

Suppose $\mathcal {L}\subseteq \mathcal {L}^1$ are vocabularies, T is a complete first order theory in $\mathcal {L}$ , and $T^1$ is a complete theory in $\mathcal {L}^1$ extending T and with Skolem-functions. Suppose T is unsuperstable and $\{\phi _n(x,y_n)\mathrel {|} n<\omega \}$ witnesses this. Then there is a proper function $\Phi $ such that for all $A\in K_{tr}^\omega $ , $EM^1(A,\Phi )$ is a model of $T^1$ , and for $s\in P^A_n$ , $t\in P^A_\omega $ , $EM^1(A,\Phi )\models \phi _n(a_t,a_s)$ if and only if $A\models s\prec t$ .

The models that we will construct are of the form $EM(A,\Phi )$ .

4.2 Reduction of the isomorphism relation

Before we deal with the construction of the models and the reduction, we need to do some preparations.

Definition 4.3. For any $A\in K^\omega _{tr}$ with size $\kappa $ and $\mathbb {A}$ a $\kappa $ -representation of A, we define $S(\mathbb {A})$ as the set ordinal $\delta <\kappa $ that satisfies:

• • $\delta $ is a limit ordinal,

• • $\exists \eta \in P^A_\omega , \{\eta {\mathbin \upharpoonright } n\mathrel {|} n<\omega \}\subseteq A_\delta \ \wedge \ \forall \alpha <\delta (\{\eta {\mathbin \upharpoonright } n\mathrel {|} n<\omega \}\not \subseteq A_\alpha ).$

Fact 4.4 (Shelah [11, Fact 2.3], Hyttinen–Tuuri [8, Lemma 8.6]).

S is a $CUB$ -invariant function.

This fact allows us to define $S(A)$ for $A\in K_{tr}^\omega $ as $\big [ S(\mathbb {A})\big ]_{=^2_{CUB}}$ for any $\mathbb {A}$ $\kappa $ -representation of A.

Notice that for a function $f\in \kappa ^\kappa $ and $\mathbb {A}=\langle A^f_\alpha \mathrel {|} \alpha <\kappa \rangle $ , the $\kappa $ -representation from Theorem 3.10, $S(A^f)$ is the set of $\omega $ -cofinal ordinals $\delta $ for which there is $\eta \in (A^f)_\omega \backslash A^f_\delta $ , such that for all $n<\omega $ , $\eta {\mathbin \upharpoonright } n\in A^f_\delta $ . Thus, $S(A^f)$ does not depend on the color function. This can be fixed by restricting ourselves to the generalized Cantor space $2^\kappa $ and making a small modification to the trees $A^f$ .

Definition 4.5. Let I be the $(<\kappa , bs)$ -stable $(\kappa , bs,bs)$ -nice $\kappa $ -colorable linear order from Section 2. For every $f\in 2^\kappa $ , let $A^f$ be the tree constructed in Section 3. Define the tree $A_f\subseteq A^f$ by: $x\in A_f$ if and only if x is not a leaf of $A^f$ or x is a leaf such that $d_f(x)=1$ . Denote by $\mathcal {A}^f$ the model EM $(A_f,\Phi )$ .

Notice that for all $\eta \in A_f$ such that $\eta \notin P_\omega ^{A_f}$ , $Suc_{A_f}(\eta )$ is infinite. On the other hand by Lemma 3.5, there is $\xi \in P_\omega ^{A_f}$ such that $\eta \prec \xi $ . Therefore, since I is $(\kappa , bs,bs)$ -nice, by Fact 3.8 the trees $A_f$ are locally $(\kappa , bs,bs)$ -nice. Notice that since the branches of the trees $A_f$ have length at most $\omega +1$ and I is $(<\kappa , bs)$ -stable, then the trees $A_f$ are $(<\kappa , bs)$ -stable.

By the way the models EM $(A,\Phi )$ were defined, we know that if $A,A'\in K_{tr}^\omega $ are isomorphic, then EM $(A,\Phi )$ and EM $(A',\Phi )$ are isomorphic. Thus if $A_f$ and $A_g$ are isomorphic, then $\mathcal {A}^f$ and $\mathcal {A}^g$ are isomorphic.

Notice that since we are working under the assumption that $\kappa $ is an uncountable cardinal satisfying $\kappa ^{<\kappa }=\kappa $ , $\kappa>|\mathcal {L}^1|$ .

From Theorem 3.10 we know that for all $f,g\in 2^\kappa $ ,

$$ \begin{align*}f\ =^2_\omega\ g\ \Leftrightarrow\ A^f\cong A^g.\end{align*} $$

By using Fact 4.4 we can obtain a similar characterization of $=^2_\omega $ , with the operator S. The following lemma states this characterization and relies essentially on Fact 4.4.

Lemma 4.6. For every $f,g\in 2^\kappa $ ,

$$ \begin{align*}f\ =^2_\omega\ g \text{ if and only if }S(A_f)=S(A_g).\end{align*} $$

Proof By Fact 4.4, S is $CUB$ -invariant; therefore, it is enough to find a $\kappa $ -representation $\mathbb {A}_f$ of $A_f$ for every $f\in 2^\kappa $ , such that for all $f,g\in 2^\kappa $ , $f\ =^2_\omega \ g$ if and only $\mathbb {A}_f\ =^2_{CUB}\ \mathbb {A}_g$ .

Similar as in the proof of Theorem 3.10, for all $f\in 2^\kappa $ let us define the $\kappa $ -representation $\mathbb {A}_f=\langle A_{f,\alpha }\mathrel {|} \alpha <\kappa \rangle $ by

$$ \begin{align*}A_{f,\alpha}=\{\eta\in A_f\mathrel{|} rng(\eta)\subseteq \theta\times\omega\times\theta\times\omega\times\theta^4\text{ for some }\theta<\alpha\}. \end{align*} $$

By definition,

$$ \begin{align*}S(\mathbb{A}_f)=\{\delta<\kappa\mathrel{|} \exists\eta\in P_\omega^{A_f}, \{\eta\mathbin{\upharpoonright} n\mathrel{|} n<\omega\}\subseteq (A_{f,\delta}\ \&\ \forall \alpha<\delta(\{\eta\mathbin{\upharpoonright} n\mathrel{|} n<\omega\}\not\subseteq A_{f,\alpha})\}.\end{align*} $$

Claim 4.6.1. $\delta \in S(\mathbb {A}_f)$ if and only if $cf(\delta )=\omega $ and there is $\eta \in P_\omega ^{A_f}$ with $max(\{sup(rng(\eta _i))\mathrel {|} i\leq 8\})=\delta $ .

Proof The direction from right to left follows from Definition 4.3. The other direction follows from the definition of $S(\mathbb {A}_f)$ and $A_{f,\alpha }$ .

By the way $A_f$ was constructed, $\eta \in P_\omega ^{A_f}$ if and only if $\eta \in P_\omega ^{A^f}$ and $d_f(\eta )=1$ . By the previous claim we know that if $\delta \in S(\mathbb {A}_f)$ and $\eta \in P_\omega ^{A_f}$ witnesses it, then $\eta \in P_\omega ^{A^f}$ and $1=d_f(\eta )$ . In the same way as in the proof of Theorem 3.10, we can conclude that $d_f(\eta )=f(max\{s_1(\eta ), s_8(\eta )\})$ , so

$$ \begin{align*}1=f(max\{sup(rng(\eta_1)), sup(rng(\eta_8))\}).\end{align*} $$

Recall from the proof of Theorem 3.10 that

$$ \begin{align*}max(\{sup(rng(\eta_i))\mathrel{|} i\leq 8\})=max\{sup(rng(\eta_1)), sup(rng(\eta_8))\}.\end{align*} $$

We conclude that $1=f(\delta )$ .

Therefore we can rewrite $S(\mathbb {A}_f)$ as

$$ \begin{align*}S(\mathbb{A}_f)=\{\delta<\kappa\mathrel{|} cf(\delta)=\omega \wedge f(\delta)=1\}.\end{align*} $$

It follows that $S(\mathbb {A}_f)\ =^2_{CUB}\ S(\mathbb {A}_g)$ holds if and only if $f\ =^2_\omega \ g$ .

Now we proceed to prove that the models $\mathcal {A}^f$ are as wanted, i.e., $f\ =^2_\omega \ g$ if and only if $\mathcal {A}^f\ \cong _T \ \mathcal {A}^g$ .

Fact 4.7 (Shelah [11, Theorem 2.4]).

Suppose T is a countable complete unsuperstable theory in a countable vocabulary. If $\kappa $ is a regular uncountable cardinal, $A_1, A_2\in K_{tr}^\omega $ have size $\kappa $ , $A_1$ , $A_2$ are locally $(\kappa , bs,bs)$ -nice and $(<\kappa , bs)$ -stable, EM $(A_1,\Phi )$ is isomorphic to EM $(A_2,\Phi )$ , then $S(A_1)=S(A_2)$ .

Lemma 4.8. If T is a countable complete unsuperstable theory over a countable vocabulary, then for all $f,g\in 2^\kappa $ , $f\ =^2_\omega \ g$ if and only if $\mathcal {A}^f$ and $\mathcal {A}^g$ are isomorphic.

Proof From left to right. Suppose $f,g\in 2^\kappa $ are such that $f\ =_\omega ^2\ g$ . By Theorem 3.10 and Definition 4.5 we know that $f\ =_\omega ^2\ g$ if and only if $A_f\cong A_g$ . Finally $A_f\cong A_g$ implies that $\mathcal {A}^f$ and $\mathcal {A}^g$ are isomorphic.

From right to left. Suppose $f,g\in 2^\kappa $ are such that $\mathcal {A}^f$ and $\mathcal {A}^g$ are isomorphic. By Definition 4.5 and Fact 4.7, $S(A_f)=S(A_g)$ . From Lemma 4.6 we conclude $f\ =^2_\omega \ g$ .

Theorem 4.9. If T is a countable complete unsuperstable theory over a countable vocabulary, $\mathcal {L}$ , then $=^2_\omega \ \hookrightarrow _c\ \cong _T$ .

Proof Let us construct a continuous function $G:2^\kappa \rightarrow 2^\kappa $ with $\mathcal {A}_{G(f)}\cong EM(A_f,\Phi )$ .

By Remark 3.11, Definition 4.5, and the definition of $A_{f,\alpha }$ ,

$$ \begin{align*}f\mathbin{\upharpoonright} \alpha=g\mathbin{\upharpoonright} \alpha \Leftrightarrow A_{f,\alpha}=A_{g,\alpha}.\end{align*} $$

Let us denote by $SH(X)$ the Skolem-hull of X, i.e., $\{\mu (a)\mathrel {|} a\in X, \mu \text { an }\mathcal {L}^1 \text {-term}\}$ . For all $\alpha $ , $A\in K^\omega _{tr}$ , and a $\kappa $ -representation $\mathbb {A}=\langle A_\alpha \mathrel {|} \alpha <\kappa \rangle $ of A, let us denote by $\tilde {A}_\alpha $ the set $\{a_s\mathrel {|} s\in A_\alpha \}$ (recall the construction of $EM^1(A,\Phi )$ in Definition 4.1). Since for all $\alpha <\kappa $ ,

$$ \begin{align*}A_{f,\alpha}=A_{g,\alpha} \Leftrightarrow SH(\tilde{A}_{f,\alpha}) = SH(\tilde{A}_{g,\alpha}).\end{align*} $$

Thus

$$ \begin{align*}f\mathbin{\upharpoonright} \alpha=g\mathbin{\upharpoonright} \alpha \Leftrightarrow SH(\tilde{A}_{f,\alpha})\mathbin{\upharpoonright} \mathcal{L}=SH(\tilde{A}_{g,\alpha})\mathbin{\upharpoonright} \mathcal{L}.\end{align*} $$

For every $f\in 2^\kappa $ there is a bijection $E_f: dom(EM(A_f,\Phi ))\rightarrow \kappa $ , such that for every $f,g\in 2^\kappa $ and $\alpha <\kappa $ it holds that: If $f{\mathbin \upharpoonright } \alpha =g{\mathbin \upharpoonright } \alpha $ , then

$$ \begin{align*}E_f\mathbin{\upharpoonright} dom(SH(\tilde{A}_{f,\alpha})\mathbin{\upharpoonright} \mathcal{L})=E_g\mathbin{\upharpoonright} dom(SH(\tilde{A}_{g,\alpha})\mathbin{\upharpoonright} \mathcal{L})\end{align*} $$

(see [10]).

Let $\pi $ be the bijection in Definition 1.4, and define the function G by

$$ \begin{align*}G(f)(\alpha)=\begin{cases} 1, &\mbox{if } \alpha=\pi(m,a_1,a_2,\ldots,a_n) \text{ and }\\ & EM(A_f,\Phi)\models Q_m(E_f^{-1}(a_1),E_f^{-1}(a_2),\ldots,E_f^{-1}(a_n)),\\ 0, & \mbox{otherwise. } \end{cases} \end{align*} $$

Clearly $\mathcal {A}_{G(f)}\cong EM(A_f,\Phi )$ .

To show that $G:2^\kappa \rightarrow 2^\kappa $ is continuous, let $[\zeta {\mathbin \upharpoonright } \alpha ]$ be a basic open set and $\xi \in G^{-1}[[\zeta {\mathbin \upharpoonright } \alpha ]]$ . There is $\beta <\kappa $ such that for all $\gamma <\alpha $ , if $\gamma =\pi (m,a_1,\ldots , a_n)$ , then $E^{-1}_\xi (a_i)\in dom(SH(\tilde {A}_{\xi ,\beta }){\mathbin \upharpoonright } \mathcal {L})$ holds for all $i\leq n$ . Since for all $\eta \in [\xi {\mathbin \upharpoonright }\beta ]$ it holds that $SH(\tilde {A}_{\eta ,\beta }){\mathbin \upharpoonright } \mathcal {L}=SH(\tilde {A}_{\xi ,\beta }){\mathbin \upharpoonright } \mathcal {L}$ , for any $\gamma <\alpha $ that satisfies $\gamma =\pi (m,a_1,\ldots , a_n)$

$$ \begin{align*}EM(A_\eta,\Phi)\models Q_m(E_\eta^{-1}(a_1),E_\eta^{-1}(a_2),\ldots,E_\eta^{-1}(a_n))\end{align*} $$

if and only if

$$ \begin{align*}EM(A_\xi,\Phi)\models Q_m(E_\xi^{-1}(a_1),E_\xi^{-1}(a_2),\ldots,E_\xi^{-1}(a_n)).\end{align*} $$

We conclude that G is continuous.

4.3 Corollaries

In this section we will prove Theorem A and Theorem B. For any stationary set $X\subseteq \kappa $ , let us denote by $\diamondsuit _X$ the following principle:

There is a sequence $\{D_\alpha \subset \alpha \mathrel {|} \alpha \in X\}$ such that for all $B\subseteq \kappa $ , the set $\{\alpha \in X\mathrel {|} D_\alpha =B\cap \alpha \}$ is stationary.

Let us denote by $\diamondsuit _\omega $ the diamond principle $\diamondsuit _X$ when $X=\{\alpha <\kappa \mathrel {|} cf(\alpha )=\omega \}$ .

Fact 4.10 (Hyttinen–Kulikov–Moreno,[6, Lemma 2]).

Assume T is a countable complete classifiable theory over a countable vocabulary. If $\diamondsuit _\omega $ holds, then $\cong _T \ \hookrightarrow _c\ =^2_\omega $ .

Fact 4.11 (Friedman–Hyttinen–Kulikov [4, Theorem 77]).

If a first-order countable complete theory over a countable vocabulary T is classifiable, then $=^2_\omega \ \not \hookrightarrow _c\ \cong _T$ .

Corollary 4.12. Suppose $\kappa =\lambda ^+=2^\lambda $ and $\lambda ^\omega =\lambda $ . If $T_1$ is a countable complete classifiable theory, and $T_2$ is a countable complete unsuperstable theory, then $\cong _{T_1}\ \hookrightarrow _c\ \cong _{T_2}$ and $\cong _{T_2}\ \not \hookrightarrow _c\ \cong _{T_1}$ .

Proof Since $\lambda ^\omega =\lambda $ , $cf(\lambda )>\omega $ . By [13] we know that if $\kappa =\lambda ^+=2^\lambda $ and $cf(\lambda )>\omega $ , then $\diamondsuit _\omega $ holds. The proof follows from Theorem 4.9, Fact 4.10, and Fact 4.11.

We will finish this section with a corollary about $\Sigma ^1_1$ -completeness. Before we state the corollary we need to recall some definitions from [2], in particular the definition of $\operatorname {\mathrm {Dl}}^{*}_S(\Pi ^1_2)$ . For more on $\operatorname {\mathrm {Dl}}^{*}_S(\Pi ^1_2)$ see [2].

A $\Pi ^{1}_{2}$ -sentence $\phi $ is a formula of the form $\forall X\exists Y\varphi $ where $\varphi $ is a first-order sentence over a relational language $\mathcal L$ as follows:

• • $\mathcal L$ has a predicate symbol $\epsilon $ of arity $2$ .

• • $\mathcal L$ has a predicate symbol $\mathbb X$ of arity $m({\mathbb X})$ .

• • $\mathcal L$ has a predicate symbol $\mathbb Y$ of arity $m({\mathbb Y})$ .

• • $\mathcal L$ has infinitely many predicate symbols $(\mathbb B_n)_{n\in \omega }$ , each $\mathbb B_n$ is of arity $m(\mathbb B_n)$ .

Definition 4.13. For sets N and x, we say that N sees x iff N is transitive, p.r.-closed, and $x\cup \{x\}\subseteq N$ .

Suppose that a set N sees an ordinal $\alpha $ , and that $\phi =\forall X\exists Y\varphi $ is a $\Pi ^{1}_{2}$ -sentence, where $\varphi $ is a first-order sentence in the above-mentioned language $\mathcal L$ . For every sequence $(B_n)_{n\in \omega }$ such that, for all $n\in \omega $ , $B_n\subseteq \alpha ^{m(\mathbb B_n)}$ , we write

$$ \begin{align*}\langle \alpha,{\in}, (B_{n})_{n\in \omega} \rangle \models_N \phi\end{align*} $$

to express that the two hold:

1. (1) $(B_{n})_{n\in \omega } \in N$ .

2. (2) $\langle N,\in \rangle \models (\forall X\subseteq \alpha ^{m(\mathbb X)})(\exists Y\subseteq \alpha ^{m(\mathbb Y)})[\langle \alpha ,{\in }, X, Y, (B_{n})_{n\in \omega } \rangle \models \varphi ]$ , where:

   • • $\in $ is the interpretation of $\epsilon $ ;

   • • X is the interpretation of $\mathbb X$ ;

   • • Y is the interpretation of $\mathbb Y$ , and

   • • for all $n\in \omega $ , $B_n$ is the interpretation of $\mathbb B_n$ .

Definition 4.14. Let $\kappa $ be a regular and uncountable cardinal, and $S\subseteq \kappa $ stationary.

$\operatorname {\mathrm {Dl}}^{*}_S(\Pi ^1_2)$ asserts the existence of a sequence $\vec N=\langle N_\alpha \mathrel {|} \alpha \in S\rangle $ satisfying the following:

1. (1) For every $\alpha \in S$ , $N_\alpha $ is a set of cardinality $<\kappa $ that sees $\alpha $ .

2. (2) For every $X\subseteq \kappa $ , there exists a club $C\subseteq \kappa $ such that, for all $\alpha \in C \cap S$ , $X\cap \alpha \in N_\alpha $ .

3. (3) Whenever $\langle \kappa ,{\in },(B_n)_{n\in \omega }\rangle \models \phi $ , with $\phi $ a $\Pi ^1_2$ -sentence, there are stationarily many $\alpha \in S$ such that $|N_\alpha |=|\alpha |$ and $\langle \alpha ,{\in },(B_n\cap (\alpha ^{m(\mathbb B_n)}))_{n\in \omega }\rangle \models _{N_\alpha }\phi $ .

Fact 4.15 (Fernandes–Moreno–Rinot [2, Theorem C]).

If $\operatorname {\mathrm {Dl}}^{*}_S(\Pi ^1_2)$ holds for $S=\{\alpha <\kappa \mathrel {|} cf(\alpha )=\omega \}$ , then $=^2_\omega $ is $\Sigma ^1_1$ -complete.

Corollary 4.16. If $\operatorname {\mathrm {Dl}}^{*}_S(\Pi ^1_2)$ holds for $S=\{\alpha <\kappa \mathrel {|} cf(\alpha )=\omega \}$ , and T is a countable complete unsuperstable theory, then $\cong _T$ is $\Sigma ^1_1$ -complete.

Proof It follows from Fact 4.15 and Theorem 4.9.

Fact 4.17 (Fernandes–Moreno–Rinot [3, Lemma 4.10 and Proposition 4.14]).

There exists a $<\kappa $ -closed $\kappa ^+$ -cc forcing extension in which $\operatorname {\mathrm {Dl}}^{*}_S(\Pi ^1_2)$ holds.

Corollary 4.18. There exists a $<\kappa $ -closed $\kappa ^+$ -cc forcing extension in which for all countable complete unsuperstable theory T, $\cong _T$ is $\Sigma ^1_1$ -complete.