A Note on Computable Embeddings for Ordinals and Their Reverses

Abstract

We continue the study of computable embeddings for pairs of structures, i.e. for classes containing precisely two non-isomorphic structures. Surprisingly, even for some pairs of simple linear orders, computable embeddings induce a non-trivial degree structure. Our main result shows that although $\{\omega \cdot 2, \omega ^\star \cdot 2\}$ is computably embeddable in $\{\omega ^2, {(\omega ^2)}^\star \}$, the class $\{\omega \cdot k,\omega ^\star \cdot k\}$ is not computably embeddable in $\{\omega ^2, {(\omega ^2)}^\star \}$ for any natural number $k \ge 3$.

The first author was supported by RFBR, project number 20-31-70006. The second author was supported by BNSF DN 02/16/19.12.2016 and NSF grant DMS 1600625/2016. The authors also would like to thank Manat Mustafa for his hospitality during their visit of Nazarbayev University.

1 Introduction

The paper studies computability-theoretic complexity for classes of countable structures. A standard method of investigating this problem is to fix a particular notion of reduction $\le _r$ between classes, and then to gauge the complexity of classes via the degrees induced by $\le _r$.

One of the first examples of such reductions comes from descriptive set theory: Friedman and Stanley [9] introduced the notion of Borel embedding. Informally speaking, a Borel embedding $\varPhi$ from a class $\mathcal {K}$ into a class $\mathcal {K}'$ is a Borel measurable function, which acts as follows. Given the atomic diagram of an arbitrary structure $A\in \mathcal {K}$ as an input, $\varPhi$ outputs the atomic diagram of some structure $\varPhi (A)$ belonging to $\mathcal {K}'$. The key property of $\varPhi$ is that $\varPhi$ is injective on isomorphism types, i.e. $\mathcal {A}\cong \mathcal {B}$ if and only if $\varPhi (\mathcal {A}) \cong \varPhi (\mathcal {B})$.

Calvert, Cummins, Knight, and Miller [4] (see also [15]) developed two different effective versions of Borel embeddings. Roughly speaking, a Turing computable embedding (or tc-embedding, for short) is a Borel embedding, which is realized by a Turing functional $\varPhi$. A computable embedding is realized by an enumeration operator. It turned out that one of these notions is strictly stronger than the other: If there is a computable embedding from $\mathcal {K}$ into $\mathcal {K}'$, then there is also a tc-embedding from $\mathcal {K}$ into $\mathcal {K}'$. The converse is not true, see Sect. 2 for formal details.

A powerful tool, which helps to work with Turing computable embeddings, is provided by the Pullback Theorem of Knight, Miller, and Vanden Boom [15]. Informally, this theorem says that tc-embeddings behave well, when working with syntactic properties: one can “pull back” computable infinitary sentences from the output class $\mathcal {K}'$ to the input class $\mathcal {K}$, while preserving the complexity of these sentences.

Nevertheless, Pullback Theorem and its consequences show that sometimes tc-embeddings are too coarse: they cannot see finer structural distinctions between classes. One of the first examples of this phenomenon was provided by Chisholm, Knight, and Miller [5]: Let VS be the class of infinite $\mathbb {Q}$-vector spaces, and let ZS be the class of models of the theory $\mathrm {Th}(\mathbb {Z},S)$, where $(\mathbb {Z},S)$ is the integers with successor. Then VS and ZS are equivalent with respect to tc-embeddings, but there is no computable embedding from VS to ZS.

Another example of this intriguing phenomenon can be found in the simpler setting of classes generated by pairs of linear orderings, closed under isomorphism. Recall that by $\omega$ one usually denotes the standard ordering of natural numbers. For a linear order L, by $L^{\star }$ we denote the reverse ordering, i.e. $a\le _{L^{\star }} b$ iff $b\le _{L} a$.

Ganchev, Kalimullin and Vatev [10] gave one such example. For a structure $\mathcal {A}$, let $\tilde{\mathcal {A}}$ be the enrichment of $\mathcal {A}$ with a congruence relation $\sim$ such that every congruence class in $\tilde{\mathcal {A}}$ is infinite and $\tilde{\mathcal {A}} /_\sim \cong \mathcal {A}$. Then they showed that the class $\{\omega _S,\omega ^\star _S\}$ is tc-equivalent to the class $\{\tilde{\omega }_S, \tilde{\omega }^\star _S\}$, whereas $\{\tilde{\omega }_S, \tilde{\omega }^\star _S\}$ is not computably embeddable into $\{\omega _S,\omega ^\star _S\}$. Here $\omega _S$ and $\omega ^\star _S$ are linear orderings of type $\omega$ and $\omega ^\star$, respectively, together with the successor relation.

One can prove (see, e.g., Theorem 3.1 in [3]) the following: Let L be a computable infinite linear order with a least, but no greatest element. Then the pair $\{ L, L^{\star }\}$ is equivalent to $\{ \omega , \omega ^{\star }\}$ with respect to tc-embeddings. This result gives further evidence that, in a sense, tc-embeddings cannot work with finer algebraic properties: Here a tc-embedding $\varPhi$ can only employ the existence (or non-existence) of the least and the greatest elements. If one considers, say, the pair $\{ \omega ^{\omega }, (\omega ^{\omega })^{\star }\}$, then our $\varPhi$ is not able to “catch” limit points, limits of limit points, etc. Section 2.1 gives a further discussion of interesting peculiarities of the pair $\{\omega , \omega ^{\star }\}$.

On the other hand, when one deals with computable embeddings, even finite sums of $\omega$ (together with their reverse orders) already exhibit a quite complicated structure: Let k and $\ell$ be non-zero natural numbers. Then there is a computable embedding from $\{ \omega \cdot k, \omega ^{\star }\cdot k\}$ into $\{ \omega \cdot \ell , \omega ^{\star }\cdot \ell \}$ if and only if k divides $\ell$ (Theorem 5.2 of [3]). In other words, in this particular setting the only possible computable embeddings are the simplest ones—by appending a fixed number of copies of an input order together. We note that it is quite non-trivial to prove that all other embeddings $\varPsi$ (e.g., a computable embedding from $\{ \omega \cdot 3, \omega ^{\star }\cdot 3\}$ to $\{ \omega \cdot 4, \omega ^{\star }\cdot 4\}$) are not possible—our proofs fully employ the peculiarities inherent to enumeration operators. These peculiarities have topological nature: indeed, one can establish the lack of continuous operators $\varPsi$ (in the Scott topology).

The current paper continues the investigations of [3]. We show that even adding the finite sums of $\omega ^2$ (and their inverses) to the mix makes the resulting picture more combinatorially involved (compare with Theorem 5.2 mentioned above).

2 Preliminaries

We will slightly abuse the notations: both the set of natural numbers and the standard ordering of this set will be denoted by $\omega$. The precise meaning of the symbol $\omega$ will be clear from the context. We consider only computable languages, and structures with domain contained in $\omega$. We assume that any considered class of structures $\mathcal {K}$ is closed under isomorphism, modulo the restriction on domains. For a structure $\mathcal {S}$, $D(\mathcal {S})$ denotes the atomic diagram of $\mathcal {S}$. We will often identify a structure and its atomic diagram. We refer to atomic formulas and their negations as basic.

Let $\mathcal {K}_0$ be a class of $L_0$-structures, and $\mathcal {K}_1$ be a class of $L_1$-structures. In the definition below, we use the following convention: An enumeration operator $\varGamma$ is treated as a computably enumerable set of pairs $(\alpha ,\varphi )$, where $\alpha$ is a finite set of basic $(L_0\cup \omega )$-sentences, and $\varphi$ is a basic $(L_1\cup \omega )$-sentence. As usual, for a set X, we have $\varGamma (X) = \{ \varphi \,:(\alpha ,\varphi ) \in \varGamma ,\ \alpha \subseteq X \}$.

Definition 1

([4, 15]). An enumeration operator $\varGamma$ is a computable embedding of $\mathcal {K}_0$ into $\mathcal {K}_1$, denoted by $\varGamma :\mathcal {K}_0 \le _c \mathcal {K}_1$, if $\varGamma$ satisfies the following:

• 1. For any $\mathcal {A}\in \mathcal {K}_0$, $\varGamma (\mathcal {A})$ is the atomic diagram of a structure from $\mathcal {K}_1$.

• 2. For any $\mathcal {A},\mathcal {B}\in \mathcal {K}_0$, we have $\mathcal {A}\cong \mathcal {B}$ if and only if $\varGamma (\mathcal {A}) \cong \varGamma (\mathcal {B})$.

Any computable embedding has an important property of monotonicity: If $\varGamma :\mathcal {K}_0 \le _c \mathcal {K}_1$ and $\mathcal {A}\subseteq \mathcal {B}$ are structures from $\mathcal {K}_0$, then we have $\varGamma (\mathcal {A}) \subseteq \varGamma (\mathcal {B})$ [4, Proposition 1.1].

Definition 2

([4, 15]). A Turing operator $\varPhi =\varphi _e$ is a Turing computable embedding of $\mathcal {K}_0$ into $\mathcal {K}_1$, denoted by $\varPhi :\mathcal {K}_0 \le _{tc} \mathcal {K}_1$, if $\varPhi$ satisfies the following:

• 1. For any $\mathcal {A}\in \mathcal {K}_0$, the function $\varphi ^{D(\mathcal {A})}_e$ is the characteristic function of the atomic diagram of a structure from $\mathcal {K}_1$. This structure is denoted by $\varPhi (\mathcal {A})$.

• 2. For any $\mathcal {A},\mathcal {B}\in \mathcal {K}_0$, we have $\mathcal {A}\cong \mathcal {B}$ if and only if $\varPhi (\mathcal {A}) \cong \varPhi (\mathcal {B})$.

Proposition (Greenberg and, independently, Kalimullin; see [14, 15]). If $\mathcal {K}_0 \le _c \mathcal {K}_1$, then $\mathcal {K}_0 \le _{tc} \mathcal {K}_1$. The converse is not true.

Both relations $\le _c$ and $\le _{tc}$ are preorders. If $\mathcal {K}_0 \le _{tc} \mathcal {K}_1$ and $\mathcal {K}_1\le _{tc} \mathcal {K}_0$, then we say that $\mathcal {K}_0$ and $\mathcal {K}_1$ are tc-equivalent, denoted by $\mathcal {K}_0 \equiv _{tc} \mathcal {K}_1$. For a class $\mathcal {K}$, by $\deg _{tc}(\mathcal {K})$ we denote the family of all classes which are tc-equivalent to $\mathcal {K}$. Similar notations can be introduced for the c-reducibility.

We note that except the reductions $\le _c$ and $\le _{tc}$, there are many other approaches to comparing computability-theoretic complexity of classes of structures. These approaches include: transferring degree spectra and other algorithmic properties [13], $\varSigma$-reducibility [8, 17], computable functors [11, 16], Borel functors [12], primitive recursive functors [1, 7], etc.

For two $\omega$-chains $\overline{x} = {(x_i)}^\infty _{i=0}$ and $\overline{y} = {(y_j)}^\infty _{j=0}$, analogous to the relation $\subseteq ^\star$ between sets, let us denote by $\overline{x} <^\star \overline{y}$ the following infinitary sentence

$$\begin{aligned} \bigvee _{q\in \omega }\bigwedge _{i,j>q}x_i < y_j. \end{aligned}$$

The following proposition is essential for our results. It is a slight reformulation of Proposition 5.7 from [3].

Proposition 1

Suppose $\{\omega \cdot 2, \omega ^\star \cdot 2\} \le _c \{\mathcal {C},\mathcal {D}\}$ via $\varGamma$, where $\mathcal {C}$ is a linear order without infinite descending chains and $\mathcal {D}$ is an infinite order without infinite ascending chains. Let $\mathcal {A}$ and $\mathcal {B}$ be copies of $\omega$ with mutually disjoint domains. Then for any $\omega$-chains ${(x_i)}^\infty _{i=0}$ and ${(y_i)}^\infty _{i=0}$ such that $\varGamma (\mathcal {A}) \models \bigwedge _{i\in \omega } x_i<x_{i+1}$ and $\varGamma (\mathcal {B}) \models \bigwedge _{i\in \omega } y_i < y_{i+1}$ such that

$$\begin{aligned} \varGamma (\mathcal {A}+ \mathcal {B}) \models \overline{x}<^\star \overline{y}\ \vee \ \overline{y} <^\star \overline{x}. \end{aligned}$$

2.1 Further Background

This paper is focused on the degree $\deg _{tc}(\{ \omega ,\omega ^{\star }\})$. Historically speaking, the choice of this particular degree was motivated by the following open question:

Problem (Kalimullin)

It is easy to show that the pairs $\{ \omega , \omega ^{\star }\}$ and $\{ \tilde{\omega }, \tilde{\omega }^{\star }\}$ are tc-equivalent. Moreover, $\{ \omega , \omega ^{\star }\} \le _c \{ \tilde{\omega }, \tilde{\omega }^{\star }\}$. Is there a computable embedding from $\{ \tilde{\omega }, \tilde{\omega }^{\star }\}$ to $\{ \omega , \omega ^{\star }\}$?

This problem was a starting point of investigations of [3] and the current paper. One can attack the problem via employing model-theoretic properties of the structures (in a way similar to [5]). In particular, a naive way to distinguish these pairs would be the following. Each of the orders $\omega$ and $\omega ^{\star }$ is rigid, while both $\tilde{\omega }$ and $\tilde{\omega }^{\star }$ have continuum many automorphisms. Maybe, this fact can help us to prove that $\{ \tilde{\omega }, \tilde{\omega }^{\star }\} \nleq _c \{ \omega , \omega ^{\star }\}$? Nevertheless, this is not the case—one can show that $\{ \tilde{\omega }, \tilde{\omega }^{\star }\} \equiv _c \{ (\omega ^2, B), (\omega \cdot \omega ^{\star },B) \}$, where B is the standard block relation on a linear order. Since the structures $(\omega ^2, B)$ and $(\omega \cdot \omega ^{\star },B)$ are both rigid, it seems that studying automorphism groups does not help in this setting.

We note that quite unexpectedly (at least for us), the theory of Turing computable embeddings found applications in algorithmic learning theory. Section 3.2 of [2] establishes connections between tc-embeddings and a particular paradigm of learnability for classes of countable structures. Informally speaking, this paradigm employs a learner whose goal is, given the atomic diagram of a structure $\mathcal {A}$, to learn the isomorphism type of $\mathcal {A}$. The learner is allowed to use both positive and negative data provided by the atomic diagram. Remarkably, the family $\{\omega , \omega ^{\star }\}$ is learnable by a computable learner. We conjecture that our results can be also connected to learnability, specifically to its topological aspects (see, e.g., [6]). The reader is referred to [3] for more results on $\deg _{tc}(\{ \omega ,\omega ^{\star }\})$.

3 Positive Results

Let $\mathcal {A}$ be a linear ordering and let us have, for all $a \in \mathcal {A}$, the linear orderings $\mathcal {B}_a$ with mutually disjoint domains. Following Rosenstein [18], we define the generalized sum $\mathcal {C}= \sum _{a\in \mathcal {A}} \mathcal {B}_a$ as the linear ordering such that $\text {dom}(\mathcal {C}) = \bigcup _{a\in \mathcal {A}} \text {dom}(\mathcal {B}_a)$ and for any $x,y \in \mathcal {C}$, we define $x <_\mathcal {C}y$ iff $x,y \in \mathcal {B}_a$ for some $a \in \mathcal {A}$ and $x <_{\mathcal {B}_a} y$, or $x \in \mathcal {B}_a$, $y \in \mathcal {B}_{a'}$ and $a <_\mathcal {A}a'$.

Theorem 1

For any natural number $n \ge 1$,

$$\begin{aligned} \{\omega \cdot n, \omega ^\star \cdot n\} \le _c \{\omega ^2 \cdot n, {(\omega ^2)}^\star \cdot n\}. \end{aligned}$$

Proof

The same enumeration operator $\varGamma$ works for all $n \ge 1$. For a linear ordering $\mathcal {L}$ and $a \in \mathcal {L}$, let $\mathcal {L}_a$ be the linear ordering consisting of pairs (a, b), where $b \in \mathcal {L}$, and ordered by the second component as in $\mathcal {L}$. Informally, for each element a in the input linear order $\mathcal {L}$, the enumeration operator outputs $\mathcal {L}_a$. Moreover, all pairs in $\varGamma (\mathcal {L})$ are ordered lexicographically by the order induced by $\mathcal {L}$. In other words, $\varGamma (\mathcal {L}) = \sum _{a\in \mathcal {L}} \mathcal {L}_a$.

• If $\mathcal {L} \cong \omega \cdot n$, then $\varGamma (\mathcal {L}) \cong \sum _{j\in n}\sum _{i\in \omega } \omega \cdot n = \sum _{j\in n}\omega ^2 = \omega ^2 \cdot n$.

• If $\mathcal {L} \cong \omega ^\star \cdot n$, then $\varGamma (\mathcal {L}) \cong \sum _{j\in n}\sum _{i\in \omega ^\star } \omega ^\star \cdot n = \sum _{j\in n}{(\omega ^2)}^\star = {(\omega ^2)}^\star \cdot n$.

   $\square$

For the next result, we need the following notation. For a linear ordering $\mathcal {L}$ and an element a in $\mathcal {L}$, we define

$$\begin{aligned} \texttt {left}_{\mathcal {L}}(a)&= |\{b \in \text {dom}(\mathcal {L}) \mid b \le _{\mathcal {L}} a\}|\\ \texttt {right}_{\mathcal {L}}(a)&= |\{b \in \text {dom}(\mathcal {L}) \mid b \ge _{\mathcal {L}} a\}|\\ \texttt {rad}_{\mathcal {L}}(a)&= \min \{\texttt {left}_{\mathcal {L}}(a), \texttt {right}_{\mathcal {L}}(a)\}. \end{aligned}$$

Informally, we will show that there exists an enumeration operator $\varGamma$ which can “guess” whether an element a in the input linear ordering $\mathcal {L}$ has finite or infinite radius, denoted $\texttt {rad}_{\mathcal {L}}(a)$.

Theorem 2

$\{\omega \cdot 2, \omega ^\star \cdot 2\} \le _c \{\omega ^2, {(\omega ^2)}^\star \}$.

Proof

We informally describe the work of the enumeration operator $\varGamma$. Suppose we have as input the finite linear ordering $\mathcal {L} = a_0< a_1< a_2< \cdots < a_n$. For each $a_i$ in $\mathcal {L}$, $\varGamma$ outputs the pairs of the form $(a_i,a_j)$, where $a_j \le _{\mathbb {N}} \texttt {rad}_{\mathcal {L}}(a_i)$, where $\le _{\mathbb {N}}$ is the standard ordering of natural numbers. All pairs in the output structure are ordered in lexicographic order. This concludes the description of how $\varGamma$ operates. Now we have two cases to consider for the input structure $\mathcal {A}$.

Suppose that $\mathcal {A}= \mathcal {A}_1 + \mathcal {A}_2$, where $\mathcal {A}_{1}$ and $\mathcal {A}_2$ are copies of $\omega$. If $a \in \mathcal {A}_1$ is its k-th least element, then $\texttt {rad}_{\mathcal {A}}(a) = k$ and hence a contributes at most k pairs to $\varGamma (\mathcal {A})$. If $a \in \mathcal {A}_2$, then clearly $\texttt {rad}_{\mathcal {A}}(a) = \aleph _0$ and hence a contributes infinitely many pairs to $\varGamma (\mathcal {A})$, forming a linear ordering of type $\omega \cdot 2$.

We conclude that in this case

$$\begin{aligned} \varGamma (\mathcal {A}) \cong \sum _{i \in \omega }i + \sum _{i\in \omega } \omega \cdot 2 \cong \omega + \omega ^2 = \omega ^2. \end{aligned}$$

Suppose that $\mathcal {A}= \mathcal {A}_1 + \mathcal {A}_2$, where $\mathcal {A}_{1}$ and $\mathcal {A}_2$ are copies of $\omega ^\star$. If $a \in \mathcal {A}_1$, then a contributes infinitely many elements of type $\omega ^\star \cdot 2$ in $\varGamma (\mathcal {A})$. If $a \in \mathcal {A}_2$ is its k-th greatest element, then a contributes at most k pairs in $\varGamma (\mathcal {A})$. We conclude that in this case

$$\begin{aligned} \varGamma (\mathcal {A}) \cong \sum _{i\in \omega ^\star } \omega ^\star \cdot 2 + \sum _{i\in \omega ^\star } i \cong {(\omega ^2)}^\star + \omega ^\star = {(\omega ^2)}^\star . \end{aligned}$$

   $\square$

Corollary 1

For any natural number $n \ge 1$,

$$\begin{aligned} \{\omega \cdot (n+1), \omega ^\star \cdot (n+1)\} \le _c \{\omega ^2 \cdot n, {(\omega ^2)}^\star \cdot n \}. \end{aligned}$$

Proof

We use the same enumeration operator $\varGamma$ as in Theorem 2. Suppose $\mathcal {A}~=~\mathcal {A}_0 + \mathcal {A}_1 + \cdots + \mathcal {A}_n$, where each $\mathcal {A}_i$ is a copy of $\omega$. Then if $a \in \mathcal {A}_0$ is the k-th least element, then a contributes at most k pairs in $\varGamma (\mathcal {A})$. If $a \in \mathcal {A}_i$, where $i > 0$, then a contributes infinitely many pairs of the type of $\mathcal {A}$ to $\varGamma (\mathcal {A})$. It follows that

$$\begin{aligned} \varGamma (\mathcal {A})&\cong \sum _{i\in \omega }i + \underbrace{\sum _{i\in \omega } \omega \cdot (n+1) + \cdots + \sum _{i\in \omega }\omega \cdot (n+1)}_{n}\\&= \omega + \omega ^2 \cdot n = \omega ^2 \cdot n. \end{aligned}$$

Suppose $\mathcal {A}= \mathcal {A}_0 + \mathcal {A}_1 + \cdots + \mathcal {A}_n$, where each $\mathcal {A}_i$ is a copy of $\omega ^\star$. Then if $a \in A_n$ is the k-th greatest element, then a contributes at most k pairs in $\varGamma (\mathcal {A})$. If $a \in \mathcal {A}_i$, where $0 \le i < n$, then a contributes infinitely many pairs of the type of $\mathcal {A}$ to $\varGamma (\mathcal {A})$. It follows that

$$\begin{aligned} \varGamma (\mathcal {A})&\cong \underbrace{\sum _{i\in \omega ^\star }\omega ^\star \cdot (n+1) + \cdots + \sum _{i\in \omega ^\star } \omega ^\star \cdot (n+1)}_{n} + \sum _{i\in \omega ^\star } i\\&= {(\omega ^2)}^\star \cdot n + \omega ^\star = {(\omega ^2)}^\star \cdot n. \end{aligned}$$

   $\square$

Corollary 2

For any natural number $n \ge 1$,

$$\begin{aligned} \{\omega \cdot 2, \omega ^\star \cdot 2\} \le _c \{\omega ^2 \cdot n, {(\omega ^2)}^\star \cdot n \}. \end{aligned}$$

Proof

This is straightforward. Let $\varGamma$ be the enumeration operator from Theorem 2. Then for a natural number $n \ge 1$, the embedding will be obtained by the enumeration operator, which, for linear ordering $\mathcal {A}$, simply copies n number of times the linear ordering $\varGamma (\mathcal {A})$.    $\square$

4 The Case $\{\omega \cdot 3, \omega ^\star \cdot 3\} \not \le _c \{\omega ^2, {(\omega ^2)}^\star \}$

In this section, towards a contradiction, assume $\varGamma : \{\omega \cdot 3, \omega ^\star \cdot 3\} \le _c \{\omega ^2, {(\omega ^2)}^\star \}$. Let $\mathcal {B}$ be a copy of $\omega \cdot 3$ (or the reverse ordinal). In general, for a subordering $\mathcal {A}$ of $\mathcal {B}$, we may have that $\varGamma (\mathcal {A})$ is not a linear ordering. For example, we may have $x,y\in \varGamma (\mathcal {A})$, but none of the sentences $x<y$ or $y < x$ are in $\varGamma (\mathcal {A})$. Suppose $\varGamma (\mathcal {B}) \models x < y$. Then we claim that there is no extension $\mathcal {C}$ of $\mathcal {A}$ such that $\varGamma (\mathcal {C}) \models y < x$. In other words, although $\varGamma (\mathcal {A})$ does not “know” the relation between x and y, this relation is already fixed. Assume there is such an extension $\mathcal {C}$ for which $\varGamma (\mathcal {C}) \models y < x$. By compactness of enumeration operators, we may suppose that $\mathcal {C}$ extends $\mathcal {A}$ by only finitely many elements. We can find another finite extension $\mathcal {D}$ of $\mathcal {A}$ with $\text {dom}(\mathcal {D}) \cap \text {dom}(\mathcal {B}) = \text {dom}(\mathcal {A})$ and $\text {dom}(\mathcal {D}) \cap \text {dom}(\mathcal {C}) = \text {dom}(\mathcal {A})$ such that $\varGamma (\mathcal {D}) \models x< y \vee y < x$. Now we use monotonicity. If $\varGamma (\mathcal {D}) \models x < y$, then we must have $\varGamma (\mathcal {C}\cup \mathcal {D}) \models x<y\ \& \ y < x$. If $\varGamma (\mathcal {D}) \models y < x$, then we must have $\varGamma (\mathcal {B}\cup \mathcal {D}) \models x<y\ \& \ y < x$. In both cases we reach a contradiction.

Remark 1

It is safe to always suppose that if $\mathcal {A}$ is a linear ordering (or its corresponding reverse linear ordering), then $\varGamma (\mathcal {A})$ is also a linear ordering.

Let us denote by $a <^\infty b$ the computable infinitary sentence saying that there are infinitely many elements between a and b.

Proposition 2

For any infinite and coinfinite set A, if there is a copy $\mathcal {A}$ of $\omega$ with $\text {dom}(\mathcal {A}) = A$ such that $\varGamma (\mathcal {A}) \cong \omega ^2$, then there is no copy $\mathcal {B}$ of $\omega$ with $\text {dom}(\mathcal {B}) \subseteq \mathbb {N} \setminus A$ such that $\varGamma (\mathcal {B}) \cong \omega ^2$.

Proof

Assume that there are at least two copies $\mathcal {A}$ and $\mathcal {B}$ of $\omega$, with mutually disjoint domains, such that $\varGamma (\mathcal {A}) \cong \omega ^2$ and $\varGamma (\mathcal {B}) \cong \omega ^2$. Then we can fix the infinite sequences $\overline{a} = {(a_i)}^\infty _{i=0}$ and $\overline{b} = {(b_i)}^\infty _{i=0}$ such that

$$\begin{aligned}&\varGamma (\mathcal {A}) \models a_0<^\infty a_1<^\infty a_2<^\infty \cdots \\&\varGamma (\mathcal {B}) \models b_0<^\infty b_1<^\infty b_2 <^\infty \cdots \end{aligned}$$

Then by Proposition 1, we have $\varGamma (\mathcal {A}+ \mathcal {B}) \models \overline{a}<^\star \overline{b}\ \vee \ \overline{b} <^\star \overline{a}$. It follows that $\varGamma (\mathcal {A}+ \mathcal {B})$ extends a copy of $\omega ^2 \cdot 2$, which is a contradiction because by monotonicity of enumeration operators this would mean that there is a copy $\mathcal {C}$ of $\omega \cdot 3$ extending $\mathcal {A}+ \mathcal {B}$ such that $\varGamma (\mathcal {C})$ extends $\omega ^2 \cdot 2$.    $\square$

From now on, in this section, we suppose that we work with copies $\mathcal {A}$ of $\omega$ such that $\varGamma (\mathcal {A})$ has type strictly less than $\omega ^2$, i.e. there exist natural numbers n and $\ell$ such that $\varGamma (\mathcal {A}) \cong \omega \cdot n + \ell$.

Proposition 3

There exists an infinite subset D of natural numbers and a number n such that any copy $\mathcal {A}$ of $\omega$ with $\text {dom}(\mathcal {A}) \subseteq D$ is such that $\varGamma (\mathcal {A})$ has type at most $\omega \cdot n$.

Proof

Towards a contradiction, assume that for any infinite subset D of natural numbers, for any n, there exists a copy $\mathcal {A}$ of $\omega$ with $\text {dom}(\mathcal {A}) \subseteq D$ such that $\varGamma (\mathcal {A})$ is at least $\omega \cdot n$. This means that we can consider a sequence $\mathcal {A}_n$ of copies of $\omega$, with mutually disjoint domains, such that $\varGamma (\mathcal {A}_n)$ has type at least $\omega \cdot n$. Now we can partition each copy $\mathcal {A}_n$ into an infinite sum of finite parts ${(\alpha _{n,i})}^\infty _{i=0}$ such that $\mathcal {A}_n = \sum _{i\in \omega } \alpha _{n,i}$. Then we can form a new copy $\mathcal {B}$ of $\omega$ in the following way: $\mathcal {B}= \sum _{i\in \omega } \sum ^i_{n=0} \alpha _{n,i-n}.$ In other words, $\mathcal {B}= \alpha _{0,0} + \alpha _{0,1} + \alpha _{1,0} + \alpha _{0,2} + \alpha _{1,1} + \alpha _{2,0} + \alpha _{0,3} + \cdots$ Then $\mathcal {B}$ contains $\mathcal {A}_n$ for all n and by monotonicity, $\varGamma (\mathcal {B})$ has type greater than $\omega \cdot n$ for all n. We conclude that $\varGamma (\mathcal {B})$ has type at least $\omega ^2$, which is a contradiction.    $\square$

Remark 2

Proposition 3 allows us to proceed as in Section 7 of [3] and suppose that we have fixed an infinite set D and a number n such that any copy $\mathcal {A}$ of $\omega$ with $\text {dom}(\mathcal {A}) \subseteq D$ is such that $\varGamma (\mathcal {A}) \cong \omega \cdot n$. From here on, all copies of $\omega$ that we consider will have as domains coinfinite subsets of D.

Proposition 4

Let $\mathcal {A}$ and $\mathcal {B}$ be two such copies of $\omega$, with mutually disjoint domains, such that for the $\omega$-chains $\overline{a}_i = {(a_{i,j})}^\infty _{j=0}$ and $\overline{b}_i = {(b_{i,j})}^\infty _{j=0}$, where $i = 1,\dots ,n$, we have $\varGamma (\mathcal {A}) \models \overline{a}_1< \overline{a}_2< \cdots < \overline{a}_n$ and $\varGamma (\mathcal {B}) \models \overline{b}_1< \overline{b}_2< \cdots < \overline{b}_n$. Then

$$\begin{aligned} \varGamma (\mathcal {A}+\mathcal {B}) \models \overline{a}_n <^\star \overline{b}_n. \end{aligned}$$

Proof

Assume not. By Proposition 1 we would have $\varGamma (\mathcal {A}+\mathcal {B}) \models \overline{b}_n <^\star \overline{a}_n$. Let $a_{n,0} \in \varGamma (\alpha )$ for some finite part $\alpha$ of $\mathcal {A}$. Then $\mathcal {C}= \alpha +\mathcal {B}$ is a copy of $\omega$ such that $\varGamma (\mathcal {C}) \models \overline{b}_1< \overline{b}_2< \cdots< \overline{b}_n < a_{n,0}$. It follows that $\varGamma (\mathcal {C})$ extends a copy of $\omega \cdot n + 1$, which is a contradiction with Remark 2.    $\square$

Proposition 5

Let $\mathcal {A}$, $\mathcal {B}$, and $\mathcal {C}$ be copies of $\omega$. Suppose that

$$\begin{aligned} \varGamma (\mathcal {C}) \models \overline{c}_1< \overline{c}_2< \cdots < \overline{c}_n, \end{aligned}$$

where $\overline{c}_i = {(c_{i,j})}^\infty _{j=0}$ are $\omega$-chains. Then there exists an infinite subsequence ${(i_s)}^\infty _{s=0}$ such that

$$\begin{aligned} \varGamma (\mathcal {A}+ \mathcal {B}+ \mathcal {C}) \models \bigwedge _{s \in \omega } c_{n,i_s} <^\infty c_{n,i_{s+1}}. \end{aligned}$$

Proof

Assume not. Then $\varGamma (\mathcal {A}+\mathcal {B}+\mathcal {C}) \models \overline{c}_1< \cdots < \overline{c}_n + \mathcal {D}$, where $\mathcal {D}$ has the type of $\omega ^2$. Let $d \in \mathcal {D}$ be such that $d \in \varGamma (\alpha + \beta + \mathcal {C})$, where $\alpha$ and $\beta$ are finite parts of $\mathcal {A}$ and $\mathcal {B}$ respectively. Then $\alpha +\beta +\mathcal {C}$ is a copy of $\omega$, but $\varGamma (\alpha +\beta +\mathcal {C})$ extends a copy of $\omega \cdot n + 1$, which is a contradiction with Remark 2.    $\square$

Proposition 6

For any linear ordering $\mathcal {L}$ of type $\omega \cdot 3$, there is a linear ordering $\mathcal {M}$ of type $\omega \cdot 2$ with $\text {dom}(\mathcal {L}) = \text {dom}(\mathcal {M})$ and $\varGamma (\mathcal {M}) \cong \omega ^2$.

Proof

Let $\mathcal {L} = \mathcal {A}+ \mathcal {B}+ \mathcal {C}$, where $\mathcal {A}$, $\mathcal {B}$, and $\mathcal {C}$ are copies of $\omega$. By Proposition 5, consider the infinite sequence $\overline{c} \in \varGamma (\mathcal {C})$ such that

$$\begin{aligned} \varGamma (\mathcal {A}+ \mathcal {B}+ \mathcal {C}) \models \bigwedge _{i\in \omega } c_i <^\infty c_{i+1}. \end{aligned}$$

Assume that for some finite parts $\alpha$ and $\beta$ of $\mathcal {A}$ and $\mathcal {B}$ respectively, for some i, $\varGamma (\alpha + \beta + \mathcal {C}) \models c_i <^\infty c_{i+1}$. But since $\alpha + \beta + \mathcal {C}$ is a copy of $\omega$, and $\varGamma (\mathcal {C}) \cong \omega \cdot n$, then $\varGamma (\alpha + \beta + \mathcal {C})$ would extend a copy of $\omega \cdot (n+1)$, which is a contradiction with Remark 2. It follows that any such finite parts $\alpha$ and $\beta$ contribute finitely many elements to any interval of the form $(c_i,c_{i+1})$.

Let $\overline{u}_i = {(u_{i,j})}^\infty _{j=0}$ be $\omega$-chains such that we can partition $\mathcal {A}$ and $\mathcal {B}$ into finite parts such that $\mathcal {A}= \sum _{i\in \omega } \alpha _i$ and $\mathcal {B}= \sum _{i\in \omega } \beta _i$ and for all i,

$$\begin{aligned} \varGamma (\alpha _i+\beta _i+\mathcal {C}) \models \bigwedge ^i_{j=0} c_j< u_{j,i-j} < c_{j+1}. \end{aligned}$$

Then, by monotonicity, we obtain the following:

$$\begin{aligned} \varGamma (\sum _{i\in \omega }(\alpha _i+\beta _i) + \mathcal {C}) \models \bigwedge _{i\in \omega }\bigwedge _{j\in \omega }c_i< u_{i,j}< c_{i+1}. \end{aligned}$$

It follows that $\mathcal {M} = \sum _{i\in \omega }(\alpha _i+\beta _i) + \mathcal {C}$ is a copy of $\omega \cdot 2$ with $\text {dom}(\mathcal {M}) = \text {dom}(\mathcal {L})$ which produces a copy of $\omega ^2$.    $\square$

Proposition 7

Let $\mathcal {L}$ and $\mathcal {M}$ be disjoint copies of $\omega \cdot 2$ such that $\varGamma (\mathcal {L}) \cong \omega ^2$ and $\varGamma (\mathcal {M}) \cong \omega ^2$. Then there is a copy $\mathcal {N}$ of $\omega \cdot 3$ such that $\varGamma (\mathcal {N})$ extends a copy of $\omega ^2 \cdot 2$.

Proof

Let $\mathcal {L} = \mathcal {A}+ \mathcal {B}$ and $\mathcal {M} = \mathcal {C}+ \mathcal {D}$, where $\mathcal {A}$, $\mathcal {B}$, $\mathcal {C}$ and $\mathcal {D}$ are copies of $\omega$. Let us fix the $\omega$-chains $\overline{b}_i = {(b_{i,j})}^\infty _{j=0}$ and $\overline{d}_i = {(d_{i,j})}^\infty _{j=0}$ where $i = 1,\dots ,n$ such that $\varGamma (\mathcal {B}) \models \overline{b}_1< \overline{b}_2< \cdots < \overline{b}_n$ and $\varGamma (\mathcal {D}) \models \overline{d}_1< \overline{d}_2< \cdots < \overline{d}_n$. By Proposition 5, we can suppose that the $\omega$-chains $\overline{b}_n$ and $\overline{d}_n$ are such that

$$\begin{aligned}&\varGamma (\mathcal {A}+\mathcal {B}) \models \bigwedge _{i\in \omega } b_{n,i} <^\infty b_{n,i+1} \end{aligned}$$

(1)

$$\begin{aligned}&\varGamma (\mathcal {C}+\mathcal {D}) \models \bigwedge _{i\in \omega } d_{n,i} <^\infty d_{n,i+1}, . \end{aligned}$$

(2)

Now by Proposition 4 we have that

$$\begin{aligned} \varGamma (\mathcal {B}+ \mathcal {D}) \models \overline{b}_n <^\star \overline{d}_n. \end{aligned}$$

(3)

For an arbitrary partition of $\mathcal {B}$ and $\mathcal {C}$ into finite parts such that $\mathcal {B}= \sum _{i\in \omega }\beta _i$ and $\mathcal {C}= \sum _{i\in \omega } \gamma _i$, let us consider the copy $\mathcal {N}$ of $\omega \cdot 3$, where

$$\begin{aligned} \mathcal {N} = \mathcal {A}+ \sum _{i\in \omega }(\beta _i + \gamma _i)+ \mathcal {D}. \end{aligned}$$

By monotonicity, (3) implies that $\varGamma (\mathcal {N}) \models \overline{b}_n <^\star \overline{d}_n$. Now, again by monotonicity, (1) and (2) imply that $\varGamma (\mathcal {N})$ extends a copy of $\omega ^2~\cdot ~2$.    $\square$

Now we are ready to finish the proof. Consider two disjoint copies $\mathcal {L}$ and $\mathcal {M}$ of $\omega \cdot 3$ such that $\varGamma (\mathcal {L}) \cong \omega ^2$ and $\varGamma (\mathcal {M}) \cong \omega ^2$. By Proposition 6, we obtain two disjoint copies $\mathcal {L}_1$ and $\mathcal {M}_1$ of $\omega \cdot 2$ such that $\varGamma (\mathcal {L}_1) \cong \omega ^2$ and $\varGamma (\mathcal {M}_1) \cong \omega ^2$. Then by Proposition 7, from $\mathcal {L}_1$ and $\mathcal {M}_1$ we can construct a copy $\mathcal {N}$ of $\omega \cdot 3$ such that $\varGamma (\mathcal {N}) \not \cong \omega ^2$. Thus, we have proven the following theorem.

Theorem 3

$\{\omega \cdot 3, \omega ^\star \cdot 3\} \not \le _c \{\omega ^2, {(\omega ^2)}^\star \}$.

Corollary 3

For any non-zero natural number n,

$$\begin{aligned} n \ge 2 \iff \{\omega \cdot 3, \omega ^\star \cdot 3\} \le _c \{\omega ^2 \cdot n, {(\omega ^2)}^\star \cdot n\}. \end{aligned}$$

Proof

First consider the direction $(\Rightarrow )$. For each $n \ge 2$ we will show how to build an enumeration operator $\varGamma _n$. Notice that by Corollary 1 we have an enumeration operator $\varGamma _2: \{\omega \cdot 3, \omega ^\star \cdot 3\} \le _c \{\omega ^2 \cdot 2, {(\omega ^\star )}^2 \cdot 2\}$. Moreover, by Theorem 1, we have an enumeration operator $\varGamma _3 : \{\omega \cdot 3, \omega ^\star \cdot 3\} \le _c \{\omega ^2 \cdot 3, {(\omega ^\star )}^2 \cdot 3\}$.

Let $n = 2k$ for some $k \ge 1$. Then $\varGamma _{n}$ works so that, for any input $\mathcal {A}$, it outputs k disjoint copies of $\varGamma _2(\mathcal {A})$.

Let $n = 2k + 3$ for some $k \ge 0$. Then $\varGamma _n$ works so that, for any input $\mathcal {A}$, it outputs k disjoint copies of $\varGamma _2(\mathcal {A})$ together with a copy of $\varGamma _3(\mathcal {A})$. The direction $(\Leftarrow )$ is exactly Theorem 3.    $\square$

5 The General Case

Here, using the same techniques as in Sect. 4, we will obtain the following theorem.

Theorem 4

For any $k \ge 3$, $\{\omega \cdot k, \omega ^\star \cdot k\} \not \le _c \{\omega ^2, {(\omega ^2)}^\star \}$.

Again towards a contradiction, assume that we have fixed a number $k \ge 3$ and an enumeration operator $\varGamma :\{\omega \cdot k, \omega ^\star \cdot k\} \le _c \{\omega ^2, {(\omega ^2)}^\star \}$. Since Proposition 2 and Proposition 3 still apply in this more general case, we can use Remark 2 and suppose we have fixed a number n such that we always work with copies $\mathcal {A}$ of $\omega$ such that $\varGamma (\mathcal {A}) \cong \omega \cdot n$. By essentially repeating the proof of Proposition 5, we obtain the following proposition.

Proposition 8

Let $\mathcal {A}_1,\mathcal {A}_2,\dots ,\mathcal {A}_k$ be copies of $\omega$. Suppose that

$$\begin{aligned} \varGamma (\mathcal {A}_k) \models \overline{c}_1< \overline{c}_2< \cdots < \overline{c}_n, \end{aligned}$$

where $\overline{c}_i = {(c_{i,j})}^\infty _{j=0}$ are $\omega$-chains. Then there exists an infinite subsequence ${(i_s)}^\infty _{s=0}$ such that

$$\begin{aligned} \varGamma (\sum ^k_{j=1} \mathcal {A}_j) \models \bigwedge _{s \in \omega } c_{n,i_s} <^\infty c_{n,i_{s+1}}. \end{aligned}$$

The next proposition is a generalization of Proposition 6.

Proposition 9

For any linear ordering $\mathcal {L}$ of type $\omega \cdot k$, there is a linear ordering $\mathcal {M}$ of type $\omega \cdot 2$ with $\text {dom}(\mathcal {L}) = \text {dom}(\mathcal {M})$ and $\varGamma (\mathcal {M}) \cong \omega ^2$.

Proof

Let $\mathcal {L} = \sum ^k_{i=1} \mathcal {A}_i$, where $\mathcal {A}_i$ are copies of $\omega$. By Proposition 8, consider the $\omega$-chain ${(c_{i})}^\infty _{i=0}$ in $\varGamma (\mathcal {A}_k)$ such that $\varGamma (\sum ^k_{j=1} \mathcal {A}_j) \models \bigwedge _{i\in \omega } c_i <^\infty c_{i+1}$.

As in the proof of Proposition 6, for any $\ell$, let $\overline{u}_\ell = {(u_{\ell ,j})}^\infty _{j=0}$ be an $\omega$-chain such that we can partition $\mathcal {A}_i$ into finite parts with $\mathcal {A}_i = \sum _{j\in \omega } \alpha _{i,j}$, where $i = 1,2,\dots , k-1$, where for all j,

$$\begin{aligned} \varGamma (\sum ^{k-1}_{i=1}\alpha _{i,j} + \mathcal {A}_{k}) \models \bigwedge ^j_{\ell =0} c_\ell< u_{\ell ,j-\ell } < c_{\ell +1}. \end{aligned}$$

Then, by monotonicity, we obtain the following:

$$\begin{aligned} \varGamma (\sum _{j\in \omega }\sum ^{k-1}_{i=1}\alpha _{i,j} + \mathcal {A}_{k}) \models \bigwedge _{\ell \in \omega }\bigwedge _{j\in \omega }c_\ell< u_{\ell ,j}< c_{\ell +1}. \end{aligned}$$

It follows that $\mathcal {M} = \sum _{j\in \omega }\sum ^{k-1}_{i=1}\alpha _{i,j} + \mathcal {A}_{k}$ is a copy of $\omega \cdot 2$ with $\text {dom}(\mathcal {M}) = \text {dom}(\mathcal {L})$ which produces a copy of $\omega ^2$.    $\square$

Let us take two disjoint copies $\mathcal {L}$ and $\mathcal {M}$ of $\omega \cdot k$ such that $\varGamma (\mathcal {L}) \cong \omega ^2$ and $\varGamma (\mathcal {M}) \cong \omega ^2$. By Proposition 9, we obtain two disjoint copies $\mathcal {L}_1$ and $\mathcal {M}_1$ of $\omega \cdot 2$ such that $\varGamma (\mathcal {L}_1) \cong \omega ^2$ and $\varGamma (\mathcal {M}_1) \cong \omega ^2$. Then by Proposition 7, from $\mathcal {L}_1$ and $\mathcal {M}_1$ we can construct a copy $\mathcal {N}$ of $\omega \cdot 3$ such that $\varGamma (\mathcal {N})$ extends a copy of $\omega ^2 \cdot 2$. By monotonicity, any copy $\mathcal {\hat{N}}$ of $\omega \cdot k$ extending $\mathcal {N}$ will be such that $\varGamma (\mathcal {\hat{N}}) \not \cong \omega ^2$. We conclude that $\{\omega \cdot k, \omega ^\star \cdot k\} \not \le _c \{\omega ^2, {(\omega ^2)}^\star \}$.

6 Positive Results for Powers of $\omega$

Proposition 10

For any $n \ge 1$, $\{\omega ^n,{(\omega ^n)}^\star \} \le _c \{\omega ^{2n},{(\omega ^{2n})}^{\star }\}$.

Proof

Standard cartesian product construction as in [18, Definition 1.40].    $\square$

Theorem 5

$\{\omega ^2, {(\omega ^2)}^\star \} \le _c \{\omega ^3, {(\omega ^3)}^\star \}$.

Proof

The idea here is to replace each point by an interval of the form [a, b], which means that this interval will have type $\omega \cdot k + \ell$ in the first case and $\ell + \omega ^\star \cdot k$ in the second case.

We informally describe the work of the enumeration operator $\varGamma$. Let us consider some finite diagram $\delta (\overline{a})$ of the input structure $\mathcal {A}$. For each a in $\delta (\overline{a})$, $\varGamma$ executes the following steps: Find elements b and c such that $b \le _\mathcal {A}a \le _\mathcal {A}c$, where $b,c \le _{\mathbb {N}} a$, such that b is the $\le _{\mathcal {A}}$-least such element and c is the $\le _{\mathcal {A}}$-greatest such element in $\delta (\overline{a})$. For all elements d in $\delta (\overline{a})$ such that $b \le _\mathcal {A}d \le _\mathcal {A}c$, $\varGamma$ enumerates in the output structure the pair (a, d). All pairs are ordered lexicographically. This concludes the description of $\varGamma$. Now we have two cases to consider.

Suppose that $\mathcal {A}= \sum _{i\in \omega }\mathcal {A}_i$, where $\mathcal {A}_i$ are copies of $\omega$. It is easy to see that for each i, there are only finitely many elements in $\mathcal {A}_i$, which contribute finitely many pairs in $\varGamma (\mathcal {A})$. For instance, let a be the $<_{\mathbb {N}}$-least element in $\mathcal {A}\setminus \mathcal {A}_0$. It follows that in $\mathcal {A}_0$ only the elements which are $<_{\mathbb {N}}$-less than a contribute finitely many pairs in $\varGamma (\mathcal {A})$. We have

$$\begin{aligned} \varGamma (\mathcal {A})&= \sum _{a\in \mathcal {A}_0} (\omega \cdot k_{a,0} + \ell _{a,0}) + \cdots + \sum _{a \in \mathcal {A}_i} (\omega \cdot k_{a,i} + \ell _{a,i}) + \cdots \\&= \omega ^2 + \cdots + \omega ^2 + \cdots = \omega ^3. \end{aligned}$$

For the second case, suppose that $\mathcal {A}= \sum _{i\in \omega ^\star }\mathcal {A}_i$, where $\mathcal {A}_i$ are copies of $\omega ^\star$. Again, for each i, there are only finitely many elements in $\mathcal {A}_i$, which contribute finitely many pairs in $\varGamma (\mathcal {A})$. It follows that

$$\begin{aligned} \varGamma (\mathcal {A})&= \cdots + \sum _{a\in \mathcal {A}_i} (\ell _{a,i} + \omega ^\star \cdot k_{a,i} ) + \cdots + \sum _{a \in \mathcal {A}_0} ( \ell _{a,0} + \omega ^\star \cdot k_{a,0}) \\&= \cdots + {(\omega ^2)}^\star + \cdots + {(\omega ^2)}^\star = {(\omega ^3)}^\star . \end{aligned}$$

   $\square$

Using the same enumeration operator $\varGamma$ as in Theorem 5, we obtain the following corollary.

Corollary 4

For any $n \ge 1$, $\{\omega ^n, {(\omega ^n)}^\star \} \le _c \{\omega ^{2n-1}, {(\omega ^{2n-1})}^\star \}$.

Corollary 5

For any $n \ge 2$, $\{\omega ^2,{(\omega ^2)}^\star \} \le _c \{\omega ^n, {(\omega ^n)}^\star \}$.

Proof

For any natural number $n \ge 2$, we briefly describe the enumeration operator $\varGamma _n : \{\omega ^2,{(\omega ^2)}^\star \} \le _c \{\omega ^n, {(\omega ^n)}^\star \}$.

• If $n = 2k$, where $k \ge 1$, then for any input $\mathcal {A}$, $\varGamma _n$ outputs $\mathcal {A}^k$.

• If $n = 3$, then $\varGamma _3$ is the enumeration operator from Theorem 5.

• If $n = 2k+3$, where $k \ge 1$, then for any input $\mathcal {A}$, $\varGamma _n$ outputs $\varGamma _3(\mathcal {A}) \cdot \mathcal {A}^k$.

   $\square$

7 Future Work

We strongly conjecture that by employing the methods of this paper, one can prove that $\{ \omega \cdot 3, \omega ^{\star }\cdot 3\} \nleq _c \{\omega ^3, (\omega ^3)^{\star }\}$. Furthermore, it would be interesting to consider pairs of structures $\{\mathcal {A}, \mathcal {B}\}$ such that $\mathcal {A}$ and $\mathcal {B}$ are not linear orders, but still $\{\mathcal {A},\mathcal {B}\} \equiv _{tc} \{ \omega , \omega ^{\star }\}$. We note that in this case, $\mathcal {A}$ and $\mathcal {B}$ cannot be Boolean algebras (see Proposition 4.6 of [2]).