Theories of Rogers Semilattices of Analytical Numberings

Abstract

The paper studies Rogers semilattices, i.e. upper semilattices induced by the reducibility between numberings. Under the assumption of Projective Determinacy, we prove that for every non-zero natural number $n$, there are infinitely many pairwise elementarily non-equivalent Rogers semilattices for $\Sigma^{1}_{n}$-computable families.

1 INTRODUCTION

Let $\mathcal{S}$ be a countable family of subsets of $\omega$. A numbering of $\mathcal{S}$ is a surjective map from the set of natural numbers onto $\mathcal{S}$. Since 1950s, computable numberings for families of c.e. sets have been extensively studied by computability theorists: for known results, the reader is referred to the monograph [1] and the surveys [2, 3]. Goncharov and Sorbi [4] started developing the theory of generalized computable numberings. Their approach initiated a fruitful line of research, which is focused on numberings in various recursion-theoretic hierarchies — see, e.g., [5–10].

This paper continues the investigations of Rogers semilattices in the analytical hierarchy, developed in [11–14]. We consider the following problem:

Problem 1. Let $n$ be a non-zero natural number. Are there infinitely many isomorphism types of Rogers semilattices for $\Sigma^{1}_{n}$-computable families?

We note that for the levels of the arithmetical hierarchy, the following results are known. V’yugin [15] proved that there are infinitely many pairwise elementarily non-equivalent Rogers semilattices of computable families. Badaev, Goncharov, and Sorbi [16] proved that for any natural number $n\geq 2$, there are infinitely many pairwise elementarily non-equivalent Rogers semilattices of $\Sigma^{0}_{n}$-computable families.

The paper [13] established that under the assumption of Projective Determinacy, there are at least four pairwise non-isomorphic Rogers semilattices for $\Sigma^{1}_{n}$-computable families. In this paper, we obtain the following partial solution of Problem 1. Under the assumption of Projective Determinacy (PD), there are infinitely many pairwise elementarily non-equivalent Rogers semilattices of $\Sigma^{1}_{n}$-computable families (Theorem 2). For $n=1$ and $n=2$, this result holds without assuming PD (Corollary 1).

The paper is arranged as follows. Section 2 contains the necessary preliminaries. Section 3 proves the main result. Recall that the Axiom of Dependent Choices (DC) states the following. For any non-empty set $A$ and any set of pairs $P\subseteq A\times A$, we have

$$(\forall x\in A)(\exists y\in A)P(x,y)\ \Rightarrow\ (\exists f\colon\omega\to A)(\forall n)P(f(n),f(n+1)).$$

Throughout the paper, our underlying set theory is ZF $+$ DC.

2 PRELIMINARIES

We give the necessary background on Rogers semilattices in the analytical hierarchy. For more details and bibliographic references, the reader is referred to [13].

A numbering $\nu$ is reducible to a numbering $\mu$, denoted by $\nu\leq\mu$, if there is total computable function $f(x)$ such that $\nu(k)=\mu(f(k))$ for all $k\in\omega$. As usual, we write $\nu\equiv\mu$ if $\nu\leq\mu$ and $\mu\leq\nu$.

The numbering $\nu\oplus\mu$ is defined as follows:

$$(\nu\oplus\mu)(2x)=\nu(x),\quad(\nu\oplus\mu)(2x+1)=\mu(x).$$

It is well-known that for any numbering $\xi$, the condition $(\nu\leq\xi\ \&\ \mu\leq\xi)$ holds if and only if $(\nu\oplus\mu\leq\xi)$.

Let $\Gamma$ be a class of some recursion-theoretic hierarchy (e.g., $\Gamma$ could be equal to $\Sigma^{0}_{1}$, $\Sigma^{-1}_{2}$, $\Sigma^{0}_{n}$, or $\Pi^{1}_{n}$). A numbering $\nu$ of a family $\mathcal{S}\subset P(\omega)$ is $\Gamma$-computable if the set $\{\langle k,x\rangle\ \colon x\in\nu(k)\}$ belongs to the class $\Gamma$. We say that a family $\mathcal{S}$ is $\Gamma$-computable if it has a $\Gamma$-computable numbering.

From now on, we assume that $\Gamma$ always belongs to $\{\Sigma^{1}_{n},\Pi^{1}_{n}\ \colon n\geq 1\}$. By $\breve{\Gamma}$ we denote the dual class:

$$\breve{\Gamma}=\begin{cases}\Sigma^{1}_{n},\quad\text{if }\Gamma=\Pi^{1}_{n},\\ \Pi^{1}_{n},\quad\text{if }\Gamma=\Sigma^{1}_{n}.\end{cases}$$

Let $\mathcal{S}$ be a $\Gamma$-computable family. By $Com_{\Gamma}(\mathcal{S})$ we denote the set of all $\Gamma$-computable numberings of $\mathcal{S}$. Since the relation $\equiv$ is a congruence on the structure $(Com_{\Gamma}(\mathcal{S});\leq,\oplus)$, we use the same symbols $\leq$ and $\oplus$ on numberings and on their $\equiv$-equivalence classes.

The quotient structure $\mathcal{R}_{\Gamma}(\mathcal{S}):=(Com_{\Gamma}(\mathcal{S})/_{\displaystyle{\equiv}};\leq,\oplus)$ is an upper semilattice. We say that $\mathcal{R}_{\Gamma}(\mathcal{S})$ is the Rogers semilattice of the $\Gamma$-computable family $\mathcal{S}$.

The following lemma allows us to proceed from a class $\Gamma$ to its dual $\breve{\Gamma}$, while preserving all the properties of our Rogers semilattices.

Lemma 1 (see, e.g., Lemma 3.1 of [13]). Let $\mathcal{S}$ be a $\Gamma$-computable family. Consider the family $\textrm{Dual}(\mathcal{S})=\{\omega\setminus A\ \colon A\in\mathcal{S}\}.$ Then the family $\textrm{Dual}(\mathcal{S})$ is $\breve{\Gamma}$-computable. Furthermore, the Rogers semilattices $\mathcal{R}_{\Gamma}(\mathcal{S})$ and $\mathcal{R}_{\breve{\Gamma}}(\textrm{Dual}(\mathcal{S}))$ are isomorphic.

By $\leq_{\omega}$ we denote the standard ordering of natural numbers. Following [17], we use the following notations: for a number $k\in\omega$,

• $E^{1}_{2k+1}$ is the (lightface) class $\Pi^{1}_{2k+1}$, and $\Upsilon^{1}_{2k+1}$ is the class $\Sigma^{1}_{2k+1}$;

• $E^{1}_{2k+2}=\Sigma^{1}_{2k+2}$ and $\Upsilon^{1}_{2k+2}=\Pi^{1}_{2k+2}$.

Tanaka [18] developed recursion theory for subsets of $\omega$, belonging to the levels of analytical hierarchy, under the assumption of Projective Determinacy (PD). One of his results (given below) will be especially useful for us.

Let $n$ be a non-zero natural number. A set $A\subseteq\omega$ is called $E^{1}_{n}$-maximal if $A$ satisfies the following:

(a) $A\in E^{1}_{n}$, and the complement $\overline{A}=\omega\setminus A$ is infinite.

(b) For every $E^{1}_{n}$ set $C$, either $\overline{A}\cap C$ or $\overline{A}\setminus C$ is finite.

Theorem 1 (Tanaka, Theorem 3.1 and Corollary 3.4 of [18]). Assume PD. There is a $E^{1}_{n}$-maximal set.

Remark 2.1. Without assuming PD, one can prove the existence of $\Pi^{1}_{1}$-maximal and $\Sigma^{1}_{2}$-maximal sets: the $\Pi^{1}_{1}$-case is due to Kreisel and Sacks (item (C) on p. 332 in [19]); the $\Sigma^{1}_{2}$-case is due to Tanaka (see p. 113 of [18] — he does not assume PD for $\Sigma^{1}_{2}$).

The following general fact about numberings will be employed in our proofs:

Lemma 2 (essentially Proposition 3.1 from [20]). Let $\nu$, $\mu_{0}$, and $\mu_{1}$ be arbitrary numberings. If $\nu\leq\mu_{0}\oplus\mu_{1}$, then at least one of the following conditions holds:

1. $\nu\leq\mu_{0}$.

2. $\nu\leq\mu_{1}$.

3. There are numberings $\nu_{0}$ and $\nu_{1}$ such that $\nu_{0}\leq\mu_{0}$ , $\nu_{1}\leq\mu_{1}$ , and $\nu\equiv\nu_{0}\oplus\nu_{1}$ . Moreover, if the numberings $\nu$ , $\mu_{0}$ , and $\mu_{1}$ are $E^{1}_{n}$ -computable, then both $\nu_{0}$ and $\nu_{1}$ are also $E^{1}_{n}$ -computable.

3 THE MAIN RESULT

Theorem 2. Assume PD . Let $n$ be a non-zero natural number. There are $\Sigma^{1}_{n}$ -computable infinite families $\mathcal{S}_{i}$ , $i\in\omega$ , such that the elementary theories of Rogers semilattices $\mathcal{R}_{\Sigma^{1}_{n}}(\mathcal{S}_{i})$ are pairwise different.

Proof. Recall that Badaev, Goncharov, and Sorbi [16] proved that for $m\geq 2$, there are infinitely many pairwise elementarily non-equivalent Rogers semilattices at the $\Sigma^{0}_{m}$-level. We follow the outline of their proof, while carefully ensuring that their methods are correctly transferred into the setting of the analytical hierarchy.

We employ Lemma 1, and instead of directly working with the level $\Sigma^{1}_{n}$, we build $E^{1}_{n}$-computable families $\mathcal{S}_{i}$ such that the semilattices $\mathcal{R}_{E^{1}_{n}}(\mathcal{S}_{i})$, $i\in\omega$, are pairwise elementarily non-equivalent. From now on, we use the following notation: for a family $\mathcal{S}$, $\mathcal{R}^{1}_{n}(\mathcal{S}):=\mathcal{R}_{E^{1}_{n}}(\mathcal{S})$.

Theorem 1 implies that we can fix a $E^{1}_{n}$-maximal set $M$.

First, we define auxiliary families $\mathcal{T}_{j}$, $j\geq 1$. Our final goal is the following: We will show that for $i\in\omega$, the desired family $\mathcal{S}_{i}$ can be chosen as some $\mathcal{T}_{j_{i}}$.

Let $j$ be a non-zero natural number. For a non-zero $l\leq j$, define a computable set

$$R_{l}:=\{j\cdot t+(l-1)\ \colon t\in\omega\}.$$

Clearly, the sets $R_{l}$, $1\leq l\leq j$, form a partition of $\omega$. Fix a total computable, injective function $p_{l}(x)$ such that $range(p_{l})=R_{l}$. We define:

$$M_{l}:=p_{l}(M)\cup\bigcup_{m\neq l}R_{m},\quad\mathcal{T}^{[l]}_{j}:=\{M_{l}\cup\{x\}\ \colon x\not\in M_{l}\},\quad\mathcal{T}_{j}:=\bigcup_{1\leq l\leq j}\mathcal{T}^{[l]}_{j}.$$

Note that the families $\mathcal{T}^{[l]}_{j}$, $1\leq l\leq j$, are pairwise disjoint.

Claim 3.1. Each $M_{l}$ is a $E^{1}_{n}$ -maximal set.

Proof. Without loss of generality, we may assume that $j>1$ and $l=1$. Note that $x\in M_{1}$ if and only if

$$\left(x\in\bigcup_{m\neq 1}R_{m}\right)\ \vee\ \exists y[y\in M\ \&\ p_{1}(y)=x].$$

Hence, the set $M_{1}$ is $E^{1}_{n}$. Clearly, the complement $\overline{M_{1}}=p_{1}(\overline{M})$ is an infinite set.

Let $C$ be an arbitrary $E^{1}_{n}$ set. Consider a $E^{1}_{n}$ set

$$D:=p_{1}^{-1}(C)=\{x\in\omega\ \colon\exists y[y\in C\ \&\ p_{1}(x)=y]\}.$$

Notice that $D$ is also equal to $p_{1}^{-1}(C\cap R_{1})$. Since the set $M$ is $E^{1}_{n}$-maximal, one of the following two cases holds:

(a) $\overline{M}\cap D$ is finite. Then $\overline{M_{1}}\cap C=p_{1}(\overline{M}\cap D)$ is also finite.

(b) $\overline{M}\setminus D$ is finite. Then $\overline{M_{1}}\setminus C=p_{1}(\overline{M}\setminus D)$ is finite.

Therefore, we deduce that $M_{1}$ is $E^{1}_{n}$-maximal. $\Box$

Now we want to show that every $\mathcal{T}_{j}$ is a $E^{1}_{n}$-computable family. In order to obtain this, we establish the following simple fact:

Lemma 3. Let $A$ be an arbitrary $E^{1}_{n}$ subset of $\omega$ such that $A\neq\omega$ . Then the family $\mathcal{V}:=\{A\cup\{x\}\ \colon x\not\in A\}$ is $E^{1}_{n}$ -computable.

Proof. We define a numbering $\xi$ as follows. Fix an element $b\not\in A$. For $k\in\omega$, we set $x\in\xi(k)$ if and only if $(x=k)\vee(x\in A)\vee[x=b\ \&\ k\in A].$ Clearly, the numbering $\xi$ is $E^{1}_{n}$-computable, and

$$\xi(k)=\begin{cases}A\cup\{k\},\quad\text{if }k\not\in A,\\ A\cup\{b\},\quad\text{if }k\in A.\end{cases}$$

Therefore, $\xi$ indexes precisely the family $\mathcal{V}$. $\Box$

Claim 3.2. For every $j\geq 1$ , the family $\mathcal{T}_{j}$ is $E^{1}_{n}$ -computable.

Proof. Clearly, it is sufficient to show that each $\mathcal{T}^{[l]}_{j}$, where $1\leq l\leq j$, has a $E^{1}_{n}$-computable numbering. This fact follows from Lemma 3. $\Box$

Now we establish a series of (technical) claims, which help us to witness the desired elementary differences.

Claim 3.3. Let $j\geq 1$ and $1\leq l\leq j$. Let $\nu$ be an arbitrary $E^{1}_{n}$-computable numbering of $\mathcal{T}_{j}$. Then the index set $I^{[l]}_{j}(\nu):=\{k\in\omega\ \colon\nu(k)\in\mathcal{T}^{[l]}_{j}\}$ is $\Delta^{1}_{n}$.

Proof. Fix two different elements $b$ and $c$ from $\overline{M_{l}}$. Then it is easy to see that

$$\nu(k)\not\in\mathcal{T}^{[l]}_{j}\ \Leftrightarrow\ b\in\nu(k)\ \&\ c\in\nu(k).$$

Hence, the set $I^{[l]}_{j}(\nu)$ is $\Upsilon^{1}_{n}$. On the other hand, the index sets $I^{[m]}_{j}$, $1\leq m\leq j$, form a partition of $\omega$. Therefore, we deduce that $I^{[l]}_{j}(\nu)\in\Delta^{1}_{n}$. $\Box$

Claim 3.4. Let $j\geq 1$ and $1\leq l\leq j$. Let $\nu$ be an arbitrary $E^{1}_{n}$-computable numbering of $\mathcal{T}_{j}$. Suppose that $\nu$ is equal to $\nu_{0}\oplus\nu_{1}$, where $\nu_{0}$ and $\nu_{1}$ are arbitrary numberings. Then there is a number $i\in\{0,1\}$ such that all but finitely many elements of $\mathcal{T}^{[l]}_{j}$ have $\nu_{i}$-indices. Proof. By Claim 3.3, the index set $I^{[l]}_{j}(\nu)$ is $\Delta^{1}_{n}$. Consider the sets

$$Q_{0}:=\{k\ \colon 2k\in I^{[l]}_{j}(\nu)\},\quad Q_{1}:=\{k\ \colon 2k+1\in I^{[l]}_{j}(\nu)\}.$$

Clearly, each $Q_{i}$ is $\Delta^{1}_{n}$, and furthermore, $Q_{i}$ is equal to $I^{[l]}_{j}(\nu_{i})$.

Consider the sets $V_{i}$, $i\in\{0,1\}$, defined as follows:

$$x\in V_{i}\ \Leftrightarrow\ (x\in M_{l})\ \vee\ \exists k[k\in Q_{i}\ \&\ x\in\nu_{i}(k)].$$

It is easy to see that each $\nu_{i}$ is a $E^{1}_{n}$-computable numbering, and hence, the sets $V_{i}$ are $E^{1}_{n}$. Clearly, $V_{i}\supseteq M_{l}$.

Since every set from $\mathcal{T}^{[l]}_{j}$ has a $(\nu_{0}\oplus\nu_{1})$-index, we deduce that $V_{0}\cup V_{1}=\omega$. This fact and the $E^{1}_{n}$-maximality of $M_{l}$ together imply that there is at least one $V_{i}$ with $V_{i}=^{\ast}\omega$. Thus, only finitely many sets $M_{l}\cup\{x\}$ from $\mathcal{T}^{[l]}_{j}$ (namely, precisely those with $x\in\omega\setminus V_{i}$) do not have $\nu_{i}$-indices. $\Box$

The key idea behind the desired elementary differences is the following: one needs to carefully work with minimal pairs.

Definition 1 (see p. 145 of [16]). Let $\mathcal{V}$ be a $E^{1}_{n}$-computable family. We say that two $E^{1}_{n}$-computable numberings $\nu_{0}$ and $\nu_{1}$ of $\mathcal{V}$ induce a minimal pair inside $\mathcal{R}^{1}_{n}(\mathcal{V})$ if there is no $E^{1}_{n}$-computable numbering $\mu$ of $\mathcal{V}$ with $\mu\leq\nu_{0}$ and $\mu\leq\nu_{1}$.

The next lemma provides a sufficient condition, which allows us to find two $E^{1}_{n}$-computable numberings of $\mathcal{T}_{j}$ that do not induce a minimal pair.

From now on, we treat a binary string $\sigma\in 2^{<\omega}$ of a non-zero length $m$ as a tuple $(\sigma(1),\sigma(2),\dots,\sigma(m))$. The length of $\sigma$ is denoted by $|\sigma|$.

Lemma 4. Let $j\geq 1$, $m\geq j$, and let $\gamma^{[0]}_{1}$, $\gamma_{1}^{[1]}$, $\gamma^{[0]}_{2}$, $\gamma^{[1]}_{2}$, …, $\gamma^{[0]}_{m+1}$, $\gamma^{[1]}_{m+1}$ be $E^{1}_{n}$-computable numberings of the family $\mathcal{T}_{j}$. If $\gamma^{[0]}_{1}\oplus\gamma_{1}^{[1]}\equiv\gamma^{[0]}_{2}\oplus\gamma_{2}^{[1]}\equiv\dots\equiv\gamma^{[0]}_{m+1}\oplus\gamma_{m+1}^{[1]},$ then there are a $E^{1}_{n}$-computable numbering $\delta$ of $\mathcal{T}_{j}$ and a binary string $\sigma$ such that $|\sigma|=m$, $\delta\leq\gamma^{[0]}_{m+1}$, and $\delta\leq\gamma_{1}^{[\sigma(1)]}\oplus\gamma_{2}^{[\sigma(2)]}\oplus\dots\oplus\gamma_{m}^{[\sigma(m)]}$.

Proof. First, note the following: If the numbering $\gamma^{[0]}_{m+1}$ is reducible to some $\gamma_{i}^{[\rho]}$, where $1\leq i\leq m$ and $\rho\in\{0,1\}$, then one can just choose $\delta:=\gamma^{[0]}_{m+1}$, and this finishes the proof. Hence, without loss of generality, we may assume that $\gamma^{[0]}_{m+1}$ is not reducible to any of these $\gamma^{[\rho]}_{i}$.

For each non-zero number $i\leq j$, we will choose the value $\sigma(i)\in\{0,1\}$ and a numbering $\delta^{[\sigma(i)]}_{i}$ of some subfamily of $\mathcal{T}_{j}$ such that $\delta_{i}^{[\sigma(i)]}\leq\gamma^{[\sigma(i)]}_{i}$, $\delta_{i}^{[\sigma(i)]}\leq\gamma^{[0]}_{m+1}$, and the family

$$\{A\in\mathcal{T}^{[i]}_{j}\ \colon A\text{ does not have a }\delta^{[\sigma(i)]}_{i}\text{-index}\}$$

is finite. The search of the desired objects proceeds as follows. Since $\gamma^{[0]}_{m+1}\leq\gamma^{[0]}_{i}\oplus\gamma^{[1]}_{i}$, by Lemma 2, we deduce that $\gamma^{[0]}_{m+1}=\delta_{i}^{[0]}\oplus\delta^{[1]}_{i}$, where $\delta_{i}^{[\rho]}\leq\gamma_{i}^{[\rho]}$. Claim 3.4 implies that there is at least one $\rho_{i}\in\{0,1\}$ such that all but finitely many elements from $\mathcal{T}^{[i]}_{j}$ have $\delta^{[\rho_{i}]}_{i}$-indices. We choose one such $\rho_{i}$, and define $\sigma(i):=\rho_{i}$.

The choice of $\delta_{i}^{[\sigma(i)]}$, $1\leq i\leq j$, implies that

$$\delta^{\ast}:=\delta^{[\sigma(0)]}_{0}\oplus\delta^{[\sigma(1)]}_{1}\oplus\dots\oplus\delta^{[\sigma(j)]}_{j}\leq\gamma^{[0]}_{m+1},\quad\delta^{\ast}\leq\gamma^{[\sigma(0)]}_{0}\oplus\gamma^{[\sigma(1)]}_{1}\oplus\dots\oplus\gamma^{[\sigma(j)]}_{j}.$$

(1)

If $\delta^{\ast}$ indexes all the family $\mathcal{T}_{j}$, then we set $\delta:=\delta^{\ast}$. Otherwise, there are only finitely many sets $B_{0},B_{1},\dots,B_{r}$ from $\mathcal{T}_{j}$, which do not have $\delta^{\ast}$-indices. We put

$$\delta^{\prime}(k):=\begin{cases}B_{k},\quad\text{if }k\leq r,\\ B_{0},\quad\text{if }k>r;\end{cases}\quad\delta:=\delta^{\ast}\oplus\delta^{\prime}.$$

It is not hard to see that we still have $\delta\leq\gamma^{[0]}_{m+1}$ and $\delta\leq\gamma^{[\sigma(0)]}_{0}\oplus\gamma^{[\sigma(1)]}_{1}\oplus\dots\oplus\gamma^{[\sigma(j)]}_{j}$. Thus, it is evident that for a number $i$ with $j<i\leq m$, one can choose the value $\sigma(i)$ in an arbitrary way. Lemma 4 is proved. $\Box$

Now we show how to obtain minimal pairs inside $\mathcal{R}^{1}_{n}(\mathcal{T}^{[l]}_{j})$, where $j\geq 1$ and $1\leq l\leq j$.

Fix two different numbers $a^{[0]}$ and $a^{[1]}$ from $\overline{M}$. Recall that $p_{l}$ is a computable bijection from $\omega$ onto $R_{l}$. For $\rho\in\{0,1\}$ and $k\in\omega$, set

$$\alpha_{l}^{[\rho]}(k):=\begin{cases}M_{l}\cup\{p_{l}(a^{[\rho]})\},\quad\text{if }k\in M,\\ M_{l}\cup\{p_{l}(k)\},\quad\text{if }k\not\in M.\end{cases}$$

An argument similar to that of Lemma 3 shows that $\alpha_{l}^{[\rho]}$ is a $E^{1}_{n}$-computable numbering of the family $\mathcal{T}^{[l]}_{j}$.

Claim 3.5. The numberings $\alpha^{[0]}_{l}$ and $\alpha^{[1]}_{l}$ induce a minimal pair inside $\mathcal{R}^{1}_{n}(\mathcal{T}^{[l]}_{j})$.

Proof. Towards a contradiction, assume that $\xi$ is a numbering of $\mathcal{T}^{[l]}_{j}$ such that $\xi\leq\alpha^{[0]}_{l}$ and $\xi\leq\alpha^{[1]}_{l}$. For $\rho\in\{0,1\}$, fix a computable function $f_{\rho}$ which reduces $\xi$ to $\alpha^{[\rho]}_{l}$.

For an arbitrary number $k$, the following holds:

• 1. If $f_{0}(k)=f_{1}(k)$, then $f_{0}(k)\not\in M$. Indeed, assume that $f_{0}(k)\in M$, then

  $$M_{l}\cup\{p_{l}(a^{[0]})\}=\alpha_{l}^{[0]}(f_{0}(k))=\xi(k)=\alpha_{l}^{[1]}(f_{1}(k))=M_{l}\cup\{p_{l}(a^{[1]})\},$$

  which contradicts with $a^{[0]}\neq a^{[1]}$.

• 2. If $\xi(k)\neq M_{l}\cup\{p_{l}(a^{[0]})\}$ and $\xi(k)\neq M_{l}\cup\{p_{l}(a^{[1]})\}$, then $f_{0}(k)=f_{1}(k)$. Indeed, it is clear that both $f_{0}(k)$ and $f_{1}(k)$ do not belong to $M$. Hence,

  $$M_{l}\cup\{p_{l}(f_{0}(k))\}=\alpha_{l}^{[0]}(f_{0}(k))=\xi(k)=\alpha_{l}^{[1]}(f_{1}(k))=M_{l}\cup\{p_{l}(f_{1}(k))\}.$$

  Since the function $p_{l}$ is injective, we deduce $f_{0}(k)=f_{1}(k)$.

These two facts together imply that the set $W:=\{y\in\omega\ \colon\exists k(f_{0}(k)=f_{1}(k)=y)\}$ is an infinite c.e. subset of $\overline{M}$. Clearly, this contradicts the $E^{1}_{n}$-maximality of $M$. Therefore, $\alpha^{[0]}_{l}$ and $\alpha^{[1]}_{l}$ induce a minimal pair. $\Box$

The next lemma is the last important ingredient of the proof: it gives a sufficient condition for having a lot of minimal pairs inside $\mathcal{R}^{1}_{n}(\mathcal{T}_{j})$. Before giving the lemma, for the sake of completeness, we recall a simple combinatorial fact:

Claim 3.6. Suppose that $j\geq 2^{N+k}$ , where $N\geq 1$ and $k\geq 0$ . Then there are subsets $F_{1},F_{2},\dots,F_{N}$ of the set $J:=\{1,2,\dots,j\}$ such that for any binary string $\sigma$ of length $N$ , we have

$$card(F_{1}^{\sigma(1)}\cap F_{2}^{\sigma(2)}\cap\dots\cap F_{N}^{\sigma(N)})\geq 2^{k}.$$

Here $F^{1}:=F$ and $F^{0}:=J\setminus F$.

Proof. It is sufficient to give a proof only for $j=2^{N+k}$. Then $J$ can be identified with the set $J^{\ast}$ which contains all binary strings of length $N+k$. For a non-zero $i\leq N$, we put $F_{i}:=\{\tau\in J^{\ast}\ \colon\tau(i)=1\}$. $\Box$

Lemma 5. Let $m\geq 1$ and $j\geq 2^{2^{m}+m+1}$ . There are $E^{1}_{n}$ -computable numberings $\beta^{[0]}_{1},\beta^{[1]}_{1},\beta^{[0]}_{2},\beta^{[1]}_{2},\dots,\beta^{[0]}_{2^{m}},\beta^{[1]}_{2^{m}}$ of the family $\mathcal{T}_{j}$ with the following properties:

(A) $\beta^{[0]}_{1}\oplus\beta_{1}^{[1]}\equiv\beta^{[0]}_{2}\oplus\beta_{2}^{[1]}\equiv\dots\equiv\beta^{[0]}_{2^{m}}\oplus\beta_{2^{m}}^{[1]}$.

(B) For any non-zero $i\leq 2^{m}$, the numberings $\beta^{[0]}_{i}$ and $\beta^{[1]}_{i}$ induce a minimal pair inside $\mathcal{R}^{1}_{n}(\mathcal{T}_{j})$.

(C) Consider arbitrary non-zero number $t\leq m$, set $I=\{i_{1}<_{\omega}i_{2}<_{\omega}\dots<_{\omega}i_{t}\}\subset\{1,2,\dots,2^{m}\}$, and binary string $\sigma$ with $|\sigma|=t$. Then for any $\rho\in\{0,1\}$ and any $i\in\{1,2,\dots,2^{m}\}\setminus I$, the numberings $\beta^{[\rho]}_{i}$ and $\beta^{[\sigma(1)]}_{i_{1}}\oplus\beta^{[\sigma(2)]}_{i_{2}}\oplus\dots\oplus\beta^{[\sigma(t)]}_{i_{t}}$ induce a minimal pair inside $\mathcal{R}^{1}_{n}(\mathcal{T}_{j})$.

Proof. Let $J:=\{1,2,\dots,j\}$. By Claim 3.6, we can fix subsets $F_{1},F_{2},\dots,F_{2^{m}}$ of the set $J$ such that for any binary string $\sigma$ of length $2^{m}$, we have

$$card(F_{1}^{\sigma(1)}\cap F_{2}^{\sigma(2)}\cap\dots\cap F_{2^{m}}^{\sigma(2^{m})})\geq 2^{m+1}.$$

For every non-zero $i\leq 2^{m}$ and every $\rho\in\{0,1\}$, we define a numbering

$$\beta^{[\rho]}_{i}:=\left(\bigoplus_{l\in F_{i}^{0}}\alpha^{[1-\rho]}_{l}\right)\oplus\left(\bigoplus_{l\in F_{i}^{1}}\alpha^{[\rho]}_{l}\right),$$

(2)

where the numberings $\alpha_{l}^{[0]}$ and $\alpha^{[1]}_{l}$ are the same as in Claim 3.5. We show that the numberings $\beta^{[\rho]}_{i}$ satisfy the lemma.

(A) Clearly, for every non-zero $i\leq 2^{m}$, we have $\beta^{[0]}_{i}\oplus\beta^{[1]}_{i}\equiv\bigoplus_{1\leq l\leq j}(\alpha^{[0]}_{l}\oplus\alpha^{[1]}_{l}).$

(B) Towards a contradiction, assume that there is a numbering $\xi$ of the family $\mathcal{T}_{j}$ with $\xi\leq\beta^{[0]}_{i}$ and $\xi\leq\beta^{[1]}_{i}$. Without loss of generality, we may assume that the number $1$ belongs to $F_{i}$. Hence, we have $\alpha_{1}^{[0]}\leq\beta^{[0]}_{i}$ and $\alpha^{[1]}_{1}\leq\beta^{[1]}_{i}$.

Recall that the families $\mathcal{T}^{[l]}_{j}$, $1\leq l\leq j$, are disjoint, hence $\xi\nleq\alpha^{[\rho]}_{l}$ for all $l$ and $\rho$. Since $\xi\leq\beta^{[1]}_{i}$, by Lemma 2, there are numberings $\xi_{l}$, $1\leq l\leq j$, such that $\xi_{l}$ indexes precisely the family $\mathcal{T}^{[l]}_{j}$,

$$\xi\equiv\xi_{1}\oplus\xi_{2}\oplus\dots\oplus\xi_{j},$$

and $\xi_{l}$ is reducible to an appropriate $\alpha^{[\rho]}_{l}$ taken from the decomposition of $\beta^{[1]}_{i}$ (as dictated by(1)). In particular, $\xi_{1}\leq\alpha^{[1]}_{1}$.

On the other hand, the reducibility $\xi\leq\beta^{[0]}_{i}$ implies that $\xi_{1}$ is reducible to $\alpha^{[0]}_{1}$. Thus, the numberings $\alpha^{[0]}_{1}$ and $\alpha^{[1]}_{1}$ do not induce a minimal pair, which contradicts Claim 3.5.

(C) Assume, towards a contradiction, that there is a numbering $\xi$ of $\mathcal{T}_{j}$ such that $\xi\leq\beta^{[\rho]}_{i}$ and $\xi\leq\beta^{[\sigma(1)]}_{i_{1}}\oplus\beta^{[\sigma(2)]}_{i_{2}}\oplus\dots\oplus\beta^{[\sigma(t)]}_{i_{t}}$. As in the proof of (B), we can choose a decomposition

$$\xi\equiv\xi_{1}\oplus\xi_{2}\oplus\dots\oplus\xi_{j},$$

where each $\xi_{l}$ indexes $\mathcal{T}^{[l]}_{j}$, and $\xi_{l}$ is reducible to an appropriate $\alpha^{[\varepsilon]}_{l}$, recovered from (1) for the numbering $\beta^{[\rho]}_{i}$.

Since $t+1\leq m+1\leq 2^{m}$, there is a number $l^{\ast}\in F_{i}^{\rho}\cap F_{i_{1}}^{1-\sigma(1)}\cap F_{i_{2}}^{1-\sigma(2)}\cap\dots\cap F_{i_{t}}^{1-\sigma(t)}.$ Since $l^{\ast}\in F_{i}^{\rho}$, we deduce that the numbering $\alpha_{l^{\ast}}^{[1]}$ occurs in the decomposition of $\beta^{[\rho]}_{i}$ provided by (1), and the numbering $\alpha^{[0]}_{l^{\ast}}$ does not occur there. Hence, $\xi_{l^{\ast}}$ is reducible to $\alpha_{l^{\ast}}^{[1]}$.

Similarly, for each non-zero $p\leq t$, only $\alpha^{[0]}_{l^{\ast}}$ (but not $\alpha^{[1]}_{l^{\ast}}$) occurs in the corresponding decomposition of $\beta^{[\sigma(p)]}_{i_{p}}$. Since $\xi$ is reducible to $\beta^{[\sigma(1)]}_{i_{1}}\oplus\dots\oplus\beta^{[\sigma(t)]}_{i_{t}}$, we deduce that $\xi_{l^{\ast}}$ is reducible to $\alpha^{[0]}_{l^{\ast}}$. Therefore, $\alpha^{[0]}_{l^{\ast}}$ and $\alpha^{[1]}_{l^{\ast}}$ do not induce a mininal pair, which contradicts Claim 3.5. Lemma 5 is proved. $\Box$

We proceed to the finishing touches of the proof. Define a computable function $h(x)$ as follows:

$$h(0):=1,\quad h(e+1):=2^{2^{h(e)}+h(e)+1}.$$

We show that for the families $\mathcal{S}_{i}:=\mathcal{T}_{h(i)}$, $i\in\omega$, their Rogers $E^{1}_{n}$-semilattices have pairwise different elementary theories.

Suppose that $i<e$. By Lemma 4, the structure $\mathcal{R}^{1}_{n}(\mathcal{S}_{i})$ satisfies the following property: for arbitrary $\gamma^{[0]}_{1}$, $\gamma_{1}^{[1]}$, $\gamma^{[0]}_{2}$, $\gamma^{[1]}_{2}$, …, $\gamma^{[0]}_{h(i)+1}$, $\gamma^{[1]}_{h(i)+1}$ with $\gamma^{[0]}_{1}\oplus\gamma_{1}^{[1]}\equiv\gamma^{[0]}_{2}\oplus\gamma_{2}^{[1]}\equiv\dots\equiv\gamma^{[0]}_{h(i)+1}\oplus\gamma_{h(i)+1}^{[1]},$ we can find a binary string $\sigma$ such that $|\sigma|=h(i)$, and the numberings $\gamma^{[0]}_{h(i)+1}$ and $\gamma_{1}^{[\sigma(1)]}\oplus\gamma_{2}^{[\sigma(2)]}\oplus\dots\oplus\gamma_{h(i)}^{[\sigma(h(i))]}$ do not induce a minimal pair.

On the other hand, since $h(e)\geq h(i+1)=2^{2^{h(i)}+h(i)+1}$, by Lemma 5, this property fails inside $\mathcal{R}^{1}_{n}(\mathcal{S}_{e})$. This concludes the proof of Theorem 2. $\Box$

Note that Remark 2.1 implies the following

Corollary 1. For the classes $\Sigma^{1}_{1}$ and $\Sigma^{1}_{2}$, Theorem 2 holds without assuming PD.