On the transversals of a ceer

Abstract

We study immunity properties of the transversals of computably enumerable equivalence relations (or, briefly, ceers), where a transversal is a set which picks at most one element from every equivalence class of the given equivalence relation. Among transversals, a particular role is played by the principal transversal, whose members are the least elements of the various equivalence classes. While hyperimmunity of the principal transversal implies hyperimmunity of every infinite transversal, we show that this fails both for immunity and hyperhyperimmunity. In both cases, counterexamples are taken from the class of interval ceers, that is, ceers whose equivalence classes are either singletons or intervals of maximal length consisting of consecutive elements of some given c.e. set. We also look into the class of hyperdark ceers, that is, those ceers with infinitely many classes, whose infinite transversals are all hyperimmune, analyzing how this property relates to other computability theoretic properties of the infinite transversals. We make some preliminary observations on the hyperhyperdark ceers, that is, those ceers with infinitely many classes, whose infinite transversals are all hyperhyperimmune.

1. Introduction

Computably enumerable equivalence relations (ceers) have been an active field of research in recent years. Interest in ceers has been motivated by the richness of their degree structure under computable reducibility (or, simply, $c$ -reducibility, denoted by $\leq_{c}$ , see Definition 1.1) on equivalence relations on the set $ω$ of natural numbers, but also by their potential applications to computable algebra and word problems of computably enumerable (or, briefly, c.e.) structures.

A seminal paper by Kasymov and Khoussainov [1] (see also Gavryushkin et al. [2]) has shown that the word problem of a finitely generated c.e. algebra is a ceer whose principal transversal (see Definition 1.3) is not hyperimmune: in fact, it cannot even lie in the $c$ -degree of a ceer having hyperimmune principal transversal, see Delle Rose et al. [3] This has revealed that the principal transversal of a ceer, and more generally the infinite transversals of a ceer (we may assume to restrict our attention to ceers with infinitely many equivalence classes: these ceers will be called infinite) embody properties which can be profitably used to classify (in particular, modulo $c$ -reducibility) the relative complexity of word problems of c.e. structures, and to understand which ceers may be (at least up to $c$ -equivalence) the word problem of a c.e. structure.

Among the properties of the infinite transversals, one should look at immunity properties. This is not only due to results such as those in Kasymov and Khoussainov [1], Gavryushkin et al. [2], and Delle Rose et al. [3], relating hyperimmunity of the principal transversal to the impossibility of realizing the word problem of any finitely generated c.e. algebra, but it is also due to other interesting computability theoretic circumstances. For instance, it is observed in Delle Rose et al. [3] that if the principal transversal of a ceer is hyperimmune, then all infinite transversals are hyperimmune (infinite ceers with this property are called hyperdark in Delle Rose et al. [3]). An interesting question is whether this is true also for immunity and hyperhyperimmunity. We show that this is not the case. In fact, there exist ceers with finite equivalence classes, such that the principal transversal is immune, but not all infinite transversals are immune (therefore these ceers are light in the terminology of Andrews and Sorbi [4]: see Remark 1.4; infinite ceers whose infinite transversals are all immune are called dark in Andrews and Sorbi [4]). And there exist ceers with finite equivalence classes whose principal transversal is hyperhyperimmune, but not all infinite transversals are hyperhyperimmune (infinite ceers whose infinite transversals are all hyperhyperimmune are called hyperhyperdark in Delle Rose et al. [3]). In both cases, suitable counterexamples can be found in the class of interval ceers (see Definition 2.1), that is, those ceers in which the equivalence classes are either singletons or intervals of maximal length comprised of consecutive elements of some given c.e. set.

It is easy to see that the property of ceers of being dark is invariant under $c$ -equivalence, that is, a ceer $R$ is dark if and only if $S$ is dark for every ceer $S$ such that $R \equiv_{c} S$ . It follows from Delle Rose et al. [3] that also the property of being hyperdark is invariant under $c$ -equivalence. In our last section, we show that, instead, this is not the case for hyperhyperdarkness: indeed, we show that each ceer $R$ with infinitely many equivalence classes is $c$ -equivalent (in fact, even isomorphic, see Definition 5.3) to a ceer which is not hyperhyperdark.

In Section 2, we recall the basic definitions about unidimensional ceers (i.e. ceers whose equivalence classes, with the exception of at most one class, are all singletons: see again Definition 2.1) and interval ceers, and study some of their computability theoretic properties. In particular, we investigate how the relative complexity (under $1$ -reducibility or Turing reducibility) of a pair of c.e. sets is mirrored by the relative complexity (under $c$ -reducibility) of the corresponding pair of unidimensional ceers, or the corresponding pair of interval ceers; moreover, we look at when ceers of this form are decidable, and we compare the relative complexity, under $c$ -reducibility, of the interval ceer and the unidimensional ceer originated by the same c.e. set. In Section 3, we present ceers with finite equivalence classes having immune principal transversal, but such that not all infinite transversals are immune; and we also present ceers with finite equivalence classes having hyperhyperimmune principal transversal, but such that not all infinite transversals are hyperhyperimmune. In Section 4, we study some special classes of hyperdark ceers: we separate these classes under inclusion, using counterexamples to inclusions provided by suitable unidimensional or interval ceers. Finally, in Section 5, we focus on hyperhyperdark ceers, showing that the property of being a hyperhyperdark ceer is not invariant under $c$ -equivalence nor under isomorphisms. Moreover, we observe that there are ceers whose entire $c$ -degrees avoid any hyperhyperdark ceer.

1.1. Notations, references, and background material

Let $E q r e l (ω)$ denote the collection of the equivalence relations on the set $ω$ of natural numbers. Let $I n f$ be the collection of the relations in $E q r e l (ω)$ possessing infinitely many equivalence classes. The complement $E q r e l (ω) ∖ I n f$ will be denoted by $F i n$ . Let $I n f C l$ (respectively, $F i n C l$ ) denote the collection of the relations in $E q r e l (ω)$ , whose equivalence classes are all infinite (respectively, whose equivalence classes are all finite). Finally, let $C e e r s$ be the collection of all ceers on $ω$ . If $R \in E q r e l (ω)$ and $F$ are a set of numbers, then denote $[F]_{R} = {x : (\exists y \in F) (x R y)}$ ; moreover, for every $m \in ω$ , the symbol $[m]_{R}$ denotes the $R$ -equivalence class of $m$ : clearly, $[m]_{R} = [{m}]_{R}$ . We denote by $Id$ the equality relation on $ω$ , and by ${Id}_{1}$ the trivial ceer having just one equivalence class.

We will consider the following reducibility notion to measure the relative complexity of the equivalence relations on $ω$ .

Definition 1.1
Given $R, S \in E q r e l (ω)$ , we say that $R$ is computably reducible (or, simply, $c$ -reducible) to $S$ (denoted by $R \leq_{c} S$ ) if there exists a computable function $f$ such that:
$(\forall x, y) (x R y \Leftrightarrow f (x) S f (y)) .$
We call $f$ a reducing function from $R$ to $S$ : we often write in this case $f : R \leq_{c} S$ .

The relation $\leq_{c}$ is a reducibility preordering on $E q r e l (ω)$ , and gives rise to a degree structure, whose elements are referred to as $c$ -degrees: the $c$ -degree of an equivalence relation $R$ is denoted by $\deg_{c} (R)$ , and we write $R \equiv_{c} S$ to denote $R \leq_{c} S$ and $S \leq_{c} R$ .
Remark 1.2. Gao and Gerdes [5]

For every $R \in E q r e l (ω)$ , $R$ is decidable if and only if $R \leq_{c} Id$ , and if $R \in I n f$ then $R$ is decidable if and only if $R \equiv_{c} Id$ .

Definition 1.3
Let $R \in E q r e l (ω)$ . We say that a set of numbers $T$ is a transversal of $R$ if for every $m$ , $| T \cap [m]_{R} | \leq 1$ , where $| X |$ denotes the cardinality of a given set $X$ . Let $Tr (R)$ denote the class of all transversals of $R$ . The principal transversal of $R$ is the transversal $T_{R} = {min [m]_{R} : m \in ω}$ .

We warn the reader that many authors (see e.g. Nies [6]) define a transversal to be any set such that $| T \cap [m]_{R} | = 1$ for every number $m$ . Gao and Gerdes [5] use the term “transversal” to denote what we have called above “principal transversal.”
Remark 1.4
It is immediate to see that for every $R \in E q r e l (ω)$ , we have $R \equiv_{T} T_{R}$ , and $R$ has an infinite c.e. transversal if and only if $Id \leq_{c} R$ : see Andrews and Sorbi [4], where ceers to which $Id$ is $c$ -reducible are called light.

The reader is referred to Gao and Gerdes [5], Andrews et al. [7], and Andrews and Sorbi [4] for the basic notions and techniques in the theory of ceers; a survey paper on universal ceers is Andrews et al. [8]; the more specialized papers [9,10] are dedicated to the structure of the $c$ -degrees of ceers. For applications of ceers to c.e. structures, see the excellent survey papers by Selivanov [11] and Khoussainov [12]; on the relationships between ceers and word problems, the reader is invited to look at the already quoted papers [1,2], and Delle Rose et al. [3]; other related papers are Fokina et al. [13] and Delle Rose et al. [14]

Recall (see e.g., Soare [15] or Rogers [16]: other excellent references for general computability are the textbooks [17 –19]) that an infinite set of natural numbers is immune if it does not contain any infinite c.e. set. Other stronger immunity notions have been widely considered in classical computability theory, and we briefly recall their definitions. We say that a set $X \subseteq ω$ is intersected by a disjoint sequence (or array) $(X_{n})_{n \in ω}$ of subsets of $ω$ (disjoint means that $X_{n} \cap X_{m} = \emptyset$ if $n \neq m$ ) if, for all $n$ , $X_{n} \cap X \neq \emptyset$ . An infinite set is hyperimmune if it is infinite, and not intersected by any strong disjoint array, that is, a disjoint array $(F_{n})_{n \in ω}$ of finite sets, presented by their canonical indices (hence $F_{n} = D_{f (n)}$ for some computable function $f$ ). Similarly, an infinite set is hyperhyperimmune if it is infinite, and not intersected by any weak disjoint array, that is, a disjoint array $(F_{n})_{n \in ω}$ of finite sets, presented by their c.e. indices (hence $F_{n} = W_{f (n)}$ for some computable function $f$ ).

Finally, recall that a coinfinite c.e. set $A$ is simple (respectively, hypersimple and hyperhypersimple) if its complement $A^{c}$ is immune (respectively, hyperimmune and hyperhyperimmune).
2. Unidimensional ceers and interval ceers

This section is dedicated to two classes of ceers which have been introduced and first investigated by Gao and Gerdes [5]: these ceers will play an important role in the rest of the paper.

Definition 2.1
If $A \subseteq ω$ then $R_{A}$ denotes the equivalence relation:
$x R_{A} y \Leftrightarrow (x, y \in A \lor x = y) .$
Moreover, $F_{A}$ denotes the equivalence relation
$x F_{A} y \Leftrightarrow (x = y \lor (x < y & [x, y] \subseteq A) \lor (y < x & [y, x] \subseteq A))$
(where, given numbers $x, y$ the familiar symbol $[x, y]$ denotes the closed interval ${z \in ω : x \leq z \leq y}$ ).
Proposition 2.2
Let $A$ be any set. (1)
If $A = ω$ then $R_{A} = F_{A} = {Id}_{1}$ . If $A = \emptyset$ then $R_{A} = F_{A} = Id$ .
(2)
$R_{A}$ and $F_{A}$ lie in $I n f$ if and only if $A$ is coinfinite; in fact, if $A$ is coinfinite then $F_{A} \in F i n C l$ .
(3)
$F_{A}$ provides a partition of $ω$ into closed consecutive intervals.
(4)
$A \equiv_{T} R_{A}$ and $F_{A} \leq_{T} A$ .
(5)
If $A$ is c.e. then $R_{A}$ and $F_{A}$ are ceers.

Proof.
Immediate.
Remark 2.3
Examples of c.e. sets $A$ such that $A ≰_{T} F_{A}$ will follow from Corollary 2.8.
Remark 2.4
The equivalence relations of the form $R_{A}$ are often called unidimensional. The equivalence relations of the form $F_{A}$ will be called interval equivalence relations. Unidimensional ceers and interval ceers have been extensively studied in Gao and Gerdes [5]. For unidimensional ceers, see also Andrews et al. [7] and Ng and Yu [20]: in the latter paper, the ceers of the form $R_{A}$ (more precisely, those for which $A$ is infinite and coinfinite) are called “set-induced.”

In many of the examples throughout the paper, we will consider interval ceers of the form $F_{B}$ , where $B \in {S (A), I (A)}$ for some c.e. set $A$ , according to the following definition.
Definition 2.5
Let $A$ be any set. Define
$\begin{aligned} S (A) & = {3 n + 1 : n \in A}, \\ I (A) & = {3 n + 1, 3 n + 2 : n \in A} . \end{aligned}$

Lemma 2.6
For every $A \subseteq ω$ , (1)
$Id \leq_{c} F_{I (A)}$ and $Id \leq_{c} F_{S (A)}$ ;
(2)
$S (A) \equiv_{T} A \equiv_{T} I (A)$ .

Proof.
Observe that neither of $S {(A)}^{c}$ and $I {(A)}^{c}$ is immune as ${3 n : n \in ω}$ is an infinite computable subset of both sets. Therefore $Id \leq_{c} F_{I (A)}$ and $Id \leq_{c} F_{S (A)}$ by Remark 1.4.

The rest of the verification is trivial. In fact we have: $A \leq_{1} S (A)$ , $A \leq_{1} I (A)$ ; if $A \neq ω$ then $S (A) \leq_{m} A$ , $I (A) \leq_{m} A$ ; and $S (A) \leq_{1} I (A)$ . To show for instance that $S (A) \leq_{1} I (A)$ , let $g (n) = 3 n$ , so $range (g) \subseteq I {(A)}^{c}$ , and let $f$ be the computable function such that $f (3 n + 1) = 3 n + 1$ , $f (3 n) = g (2 n)$ , $f (3 n + 2) = g (2 n + 1)$ : clearly, $f$ $1$ -reduces $S (A)$ to $I (A)$ .

Intuitively, $S (A)$ can be regarded as a sparse version of $A$ , which “shatters” $F_{S (A)}$ within $Id$ , to the point of making $F_{S (A)} = Id$ , and no information about $A$ can be recovered from $F_{S (A)}$ . On the other hand, $I (A)$ can be regarded as a version of $A$ , which “isolates” inside $F_{I (A)}$ the information about $A$ .
Lemma 2.7
For every set $A$ , we have (1)
$F_{S (A)} = Id$ ;
(2)
$A \leq_{T} F_{I (A)}$ ;
(3)
$F_{I (A)} \leq_{c} Id$ if and only if $A$ is decidable.

Proof.
Let $A$ be any set. (1)
Since no two elements in $S (A)$ are consecutive, every equivalence class of $F_{S (A)}$ is a singleton;
(2)
obvious, in fact, $A \leq_{1} F_{I (A)}$ ;
(3)
remember (Remark 1.2) that $R$ is decidable if and only if $R \leq_{c} Id$ : therefore, the implication from right to left comes from $F_{I (A)} \leq_{T} I (A)$ (Proposition 2.2(4)), and $I (A) \leq_{T} A$ (Lemma 2.6(2)); the converse implication follows immediately from item (2) and, again, Remark 1.2.

Corollary 2.8
For every undecidable set $A$ , we have that $S (A) ≰_{T} F_{S (A)}$ .
Proof.
It easily follows from the fact that $F_{S (A)}$ is decidable by Lemma 2.7(1), and $A \equiv_{T} S (A)$ by Lemma 2.6.

In general, the decidability of $F_{A}$ only depends on the decidability of a certain subset of $A$ . For any set $X$ , we define
$X + 1 = {x + 1 : x \in X} .$

Theorem 2.9
If $A$ is any set, then $F_{A}$ is decidable if and only if the subset of $A$
$(A ∖ {0}) \cap (A + 1)$
is decidable.
Proof.
Notice that the principal transversal of $F_{A}$ is given by
$T_{F_{A}} = {0} \cup A^{c} \cup (A^{c} + 1),$
hence
$(T_{F_{A}})^{c} = (A ∖ {0}) \cap (A + 1) .$
If $(A ∖ {0}) \cap (A + 1)$ is decidable, then $T_{F_{A}}$ is decidable as well, hence $F_{A}$ is decidable by Remark 1.4.

Conversely, assume that $F_{A}$ is decidable. Notice that
$(A ∖ {0}) \cap (A + 1) = {x : x > 0 & x F_{A} (x - 1)},$
hence $(A ∖ {0}) \cap (A + 1)$ is decidable.
2.1. Unidimensional ceers, interval ceers, and $1$ -reducibility

The present subsection includes some observations on how the relative complexity (under $1$ -reducibility or Turing reducibility) of a pair of c.e. sets $A, B$ is mirrored by the relative complexity (under $c$ -reducibility) of the pair $R_{A}, R_{B}$ , or the pair $F_{A}, F_{B}$ .

We begin with defining the injective version of $c$ -reducibility.

Definition 2.10
Given $R, S \in E q r e l (ω)$ , define $R \leq_{c, 1} S$ if $R \leq_{c} S$ via a 1-1 computable function. Clearly, if $R \leq_{c, 1} S$ then $R \leq_{c} S$ .

We next show some useful cases of when one has $R \leq_{c, 1} S$ .
Lemma 2.11
(1)
If $R, S$ are ceers, and $R \leq_{c} S$ via a computable function $f$ such that $[f (x)]_{S}$ is infinite for every $x$ (this is the case for instance if $S \in I n f C l$ ), then $R \leq_{c, 1} S$ .
(2)
If $A \subseteq ω$ , $R \in E q r e l (ω)$ , and $f : R_{A} \leq_{c} R$ is a $c$ -reduction such that the image under $f$ of the $R_{A}$ -equivalence class $A$ contains an infinite c.e. set (this is the case, for instance, if $A$ is an undecidable c.e. set), then $R_{A} \leq_{c, 1} R$ .

Proof.
The proofs of both items are straightforward.

(1)
Starting from $f$ , define the value $g (x)$ of a 1-1-computable function $g$ by setting $g (x)$ to be the first number $y$ such that $f (x) S y$ , and $y \neq g (i)$ for every $i < x$ . Clearly, $g$ is a 1-1 computable function witnessing $R \leq_{c, 1} S$ : totality of $g$ is guaranteed by the fact that, for every $x$ , the equivalence class $[f (x)]_{S}$ is infinite.
(2)
Let $f$ be a computable function witnessing $R_{A} \leq_{c} R$ , and let $B$ be an infinite c.e. set contained in the $R$ -equivalence class to which $A$ is mapped by $f$ . Fix a computable enumeration ${B_{s}}_{s \in ω}$ of $B$ . Define the value $g (x)$ of a 1-1-computable function $g$ by setting
$g (x) = {\begin{cases} f (x), & if (\forall i < x) [f (x) \neq g (i)], \\ (μ ⟨ y, s ⟩ (y \in B_{s} ∖ {g (i) : i < x}))_{0}, & otherwise, \end{cases}$
where we refer to the usual Cantor pairing function $(x, y) \mapsto ⟨ x, y ⟩$ with first projection $(⟨ x, y ⟩)_{0} = x$ . Since $B$ is infinite, then $g$ is total and $1$ - $1$ . By injectivity of $f$ on the complement of $A$ , it is easy to see that for every $x$ , if $x \notin A$ then $g (x) = f (x)$ , and if $x \in A$ then $g (x) \in B$ . Thus $g : R_{A} \leq_{c, 1} R$ .

If $A$ is an undecidable c.e. set, then the image $B = f [A]$ , under a reducing function $f : R_{A} \leq_{c} R$ , is an undecidable, and thus infinite, c.e. subset of the equivalence class to which $A$ is mapped by the reducing function.

The following fact is well known, see, for example, Gao and Gerdes [5] and Andrews et al. [7]
Proposition 2.12
If $A$ and $B$ are sets and $B$ contains an infinite c.e. set, then
$A \leq_{1} B \Leftrightarrow R_{A} \leq_{c} R_{B} .$
Moreover, if $B$ is co-infinite, then
$Id \leq_{c} R_{B} \Leftrightarrow B^{c} not immune .$

Proof.
For the right-to-left implication of the first claim assume that $R_{A} \leq_{c} R_{B}$ . Direct inspection shows that the claim is true if $A$ is decidable. If $A$ is undecidable then by Lemma 2.11(2), we have that $R_{A} \leq_{c, 1} R_{B}$ , and then $A \leq_{1} B$ by the same function by which $R_{A} \leq_{c, 1} R_{B}$ .

The left-to-right implication of the second claim comes from Remark 1.4, and the observation that if $f : Id \leq_{c} R_{B}$ is a reduction, then $range (f)$ is an infinite c.e. transversal of $R_{B}$ , and thus is an infinite c.e. set contained (with the exception of at most one element) in $B^{c}$ .

The situation is quite different for interval ceers. We first observe:
Lemma 2.13
Let $A, B \subseteq ω$ : (1)
If $A$ is undecidable, then $F_{I (A)} ≰_{c} F_{S (B)}$ .
(2)
If $A, B$ are undecidable, and $A ≰_{T} B$ , then $S (A) ≰_{T} I (B)$ but $F_{S (A)} \leq_{c} F_{I (B)}$ .

Proof.
Item (1) follows from the fact that $F_{S (B)}$ is decidable (being $F_{S (B)} = Id$ by Lemma 2.7(1)), while $A \leq_{T} F_{I (A)}$ (by Lemma 2.7(2)).

For item (2), assume that $A ≰_{T} B$ : then, by Lemma 2.6(2), we have $S (A) \equiv_{T} A$ and $B \equiv_{T} I (B)$ , therefore $S (A) ≰_{T} I (B)$ . On the other hand, since $F_{S} (A) = Id$ by Lemma 2.7(1), to conclude $F_{S (A)} \leq_{c} F_{I (B)}$ it is enough to recall that $Id \leq_{c} F_{I (B)}$ , as observed in Lemma 2.6(1).
Corollary 2.14
The following hold: (1)
There exist c.e. sets $X, Y$ , such that $X \leq_{1} Y$ but $F_{X} ≰_{c} F_{Y}$ .
(2)
There exist c.e. sets $X, Y$ , such that $X ≰_{1} Y$ (in fact $X ≰_{T} Y$ ) but $F_{X} \leq_{c} F_{Y}$ .

Proof.
We first prove item (1). Take $X = I (A)$ and $Y = S (K)$ where $A$ is any undecidable c.e. set, and $K$ is any creative set. Then $X \leq_{1} Y$ (as $K \leq_{1} S (K)$ by Lemma 2.6, and thus $S (K)$ is $1$ -complete), but $F_{X} ≰_{c} F_{Y}$ by Lemma 2.13(1).

To show item (2), by Lemma 2.13(2) take $X = S (A)$ and $Y = I (B)$ , where $A, B$ are any two c.e. sets such that $A ≰_{T} B$ .
2.2. Comparing unidimensional ceers and interval ceers under $\leq_{T}$ and $\leq_{c}$

We now look at how $c$ -reducibility on unidimensional ceers and interval ceers reflects Turing reducibility on the c.e. sets originating the ceers, and at how $R_{A}$ compares to $F_{A}$ under $c$ -reducibility.

Proposition 2.15
If $A, B$ are sets such that $A ≰_{T} B$ then $R_{A} ≰_{c} R_{B}$ .
Proof.
If $R_{A} \leq_{c} R_{B}$ then $R_{A} \leq_{T} R_{B}$ . But then $A \leq_{T} B$ , since in general $X \equiv_{T} R_{X}$ by Proposition 2.2(4).

Again, the situation is different for interval ceers. Lemma 2.13 and Corollary 2.14 show:
Proposition 2.16
For any undecidable set $A$ , there exist sets $X \equiv_{T} Y \equiv_{T} A$ such that
$X \equiv_{T} Y & F_{X} ≰_{c} F_{Y} .$

Proof.
Take $X = I (A)$ and $Y = S (A)$ : the claim follows from Lemma 2.6(2) and Lemma 2.13(1).

The following theorem points out two straightforward observations showing how $R_{A}$ and $F_{A}$ compare with each other with respect to computable reducibility. In the proof we refer to Proposition 5.3 of Gao-Gerdes [5], stating that if $R$ is an undecidable ceer such that all of its equivalence classes but finitely many are singletons (notice that the ceers of the form $R_{A}$ belong to this class), and $S$ is an undecidable ceer with no undecidable equivalence class (notice that all ceers of the form $F_{A}$ belong to this class), then $R ≰_{c} S$ and $S ≰_{c} R$ .
Theorem 2.17
For every set $A$ the following hold: (1)
$R_{A} \leq_{c} F_{A}$ if and only if $A$ is decidable.
(2)
if $A$ is c.e. and coinfinite, then $F_{A} \leq_{c} R_{A}$ if and only if $F_{A}$ is decidable.

Proof.
Let us show (1). If $A$ is undecidable, then $R_{A}$ is undecidable by Proposition 2.2(4). In this case, if $F_{A}$ is decidable then $R_{A} ≰_{c} F_{A}$ . On the other hand, if $F_{A}$ is undecidable then $R_{A} ≰_{c} F_{A}$ by Proposition 5.3 of Gao and Gerdes [5]. For the other direction, assume that $A$ is decidable. Then $R_{A}$ and $F_{A}$ are both decidable by Proposition 2.2(4). Moreover, it is not difficult to see that the number of equivalence classes of $R_{A}$ is less than, or equal to, the number of equivalence classes of $F_{A}$ (notice, in particular, that they are both in $I n f$ if $A$ is coinfinite): then $R_{A} \leq_{c} F_{A}$ .

Let us now show (2). Let $A$ be any coinfinite c.e. set. If $F_{A}$ is not decidable, then by Proposition 2.2(4) $A$ is not decidable, and $R_{A}$ is not decidable. Then $F_{A} ≰_{c} R_{A}$ by Proposition 5.3 of Gao and Gerdes [5]. If $F_{A}$ is decidable then by Remark 1.2, $F_{A} \leq_{c} Id$ , and the set
${x - 1 : x > 0 & x \in A & \neg ((x - 1) F_{A} x)}$
is an infinite c.e. subset of $A^{c}$ , implying that $A^{c}$ is not immune, which by Proposition 2.12 implies that $Id \leq_{c} R_{A}$ , hence we get $F_{A} \leq_{c} R_{A}$ .

To conclude the picture, we observe that, when $A$ is a cofinite set, then $F_{A} \leq_{c} R_{A}$ if and only if $A^{c}$ is an initial segment of $ω$ (i.e. an interval of the form $[0, \dots n]$ ), as this is the only case in which the number of equivalence classes of $F_{A}$ is less than or equal to (in fact, in this case, is equal to) the number of equivalence classes of $R_{A}$ .

We conclude this section with a straightforward addition to Proposition 5.3 of Gao and Gerdes [5].
Lemma 2.18
If $R \in I n f$ is a ceer whose equivalence classes are decidable, $A$ is a c.e. set, and $R \leq_{c} R_{A}$ , then $A$ is not simple, and $R$ is decidable.
Proof.
Let $R \in I n f$ be a ceer whose equivalence classes are all decidable, and $R \leq_{c} R_{A}$ , where $A$ is a c.e. set. Then by Proposition 5.3 of Gao and Gerdes [5], $R_{A}$ is decidable or $R$ is decidable. If $R_{A}$ is decidable, then $A$ is decidable and thus not simple, and $R$ is decidable. If $R$ decidable then $Id \leq_{c} R_{A}$ , and thus $A$ is not simple by Proposition 2.12.
3. Immunity properties and principal transversals

We recall the following definitions (already anticipated in the introduction) from Andrews and Sorbi [4] and Delle Rose et al. [3]

Definition 3.1
An equivalence relation $R$ is dark (respectively, hyperdark and hyperhyperdark) if $R \in I n f$ and all of its infinite transversals are immune (respectively, hyperimmune and hyperhyperimmune).

Notice that if $R \in I n f$ then $R$ is dark if and only if $R$ is not light.

Let us use the notations $d a r k$ , $h d a r k$ , and $h h d a r k$ to denote, respectively, the collections of dark ceers, hyperdark ceers, and hyperhyperdark ceers.

We recall the following fact.
Proposition 3.2 Delle Rose et al. [3]

$h h d a r k \subset h d a r k \subset d a r k$ , with proper inclusions.

Proof.
We sketch the proof, which relies on an argument that will be further exploited in Theorem 4.2. The inclusions are obvious as hyperhyperimmunity implies hyperimmunity, which in turn implies immunity. On the other hand, well-known facts of classical computability theory allow us to conclude: if $A$ is simple but not hypersimple then $R_{A} \in d a r k ∖ h d a r k$ , and if $A$ is hypersimple but not hyperhypersimple then $R_{A} \in h d a r k ∖ h h d a r k$ . Obviously, $R_{A} \in h h d a r k$ if $A$ is hyperhypersimple, hence all the classes of ceers in the statement of this fact are nonempty.

The following fact from Delle Rose et al. [3] shows that there is no hyperhyperdark ceer in $F i n C l$ .
Proposition 3.3 Delle Rose et al. [3]

$h h d a r k \cap F i n C l = \emptyset$ .

Proof.
See Theorem 2.10 in Delle Rose et al. [3]

Many of the properties of an equivalence relation follow from the properties of its principal transversal. For instance:
Proposition 3.4 Delle Rose et al. [3]

If $R$ is an equivalence relation such that $T_{R}$ is hyperimmune then all the infinite transversals of $R$ are hyperimmune. Hence, for a ceer $R \in I n f$ we have that $R \in h d a r k$ if and only if $T_{R}$ is hyperimmune.

Proof.
See Corollary 1.8 in Delle Rose et al. [3]

Interestingly, Proposition 3.4 holds neither for immunity nor for hyperhyperimmunity. We will exhibit a ceer $R \in F i n C l$ such that $T_{R}$ is immune but not all infinite transversals are immune, and a ceer $R \in F i n C l$ such that $T_{R}$ is hyperhyperimmune but not all infinite transversals are hyperhyperimmune.

We first give two preliminary results. The former result is well known and appears as an exercise in most textbooks of computability theory.
Lemma 3.5
The following hold: (1)
The simple sets are closed under finite intersections.
(2)
The hypersimple sets are closed under finite intersections.
(3)
The hyperhypersimple sets are closed under finite intersections.

Proof.
The three claims (essentially due to Dekker [21]) come from known characterizations of the simplicity properties mentioned in the statement of the Lemma. For (2), see, for example, Exercise 5.3.8 in Soare [19]; for (3) see, for example, Exercises 10.2.16 and 10.2.17 in Soare [15].
Theorem 3.6
For every c.e. set $A$ , the following hold: (1)
$T_{F_{A}}$ is immune if and only if $A$ is simple.
(2)
$T_{F_{A}}$ is hyperimmune if and only if $A$ is hypersimple.
(3)
$T_{F_{A}}$ is hyperhyperimmune if and only if $A$ is hyperhypersimple.

Proof.
We present the proof of (3): the other cases are similar. We recall from the proof of Theorem 2.9 that
$(T_{F_{A}})^{c} = (A ∖ {0}) \cap (A + 1) .$
Assume that $A$ is hyperhypersimple. In particular, $(T_{F_{A}})^{c}$ is a c.e. set. It is also easy to see that both $A ∖ {0}$ and $A + 1$ in the description of $(T_{F_{A}})^{c}$ are hyperhypersimple. Indeed, to show that $A + 1$ is hyperhypersimple, take any weak disjoint array ${F_{n} : n \in ω}$ of finite sets and, for each $n$ , let
$G_{n} = {x - 1 : x \in F_{n}}$
as at most one $F_{n}$ may contain the number $0$ , we may assume that in fact no $F_{n}$ contains $0$ , thus $(G_{n})_{n \in ω}$ is also a weak disjoint array and hence, by hyperhypersimplicity of $A$ , there must be some $m \in ω$ with $G_{m} \subseteq A$ . Fix such an $m$ , and let $x \in F_{m}$ : we have $x - 1 \in G_{m}$ , and hence $x - 1 \in A$ , which implies that $x \in A + 1$ . This means that $F_{m} \subseteq A + 1$ , showing that $A + 1$ is hyperhypersimple. By Lemma 3.5 we have that $(T_{F_{A}})^{c}$ is hyperhypersimple and thus $T_{F_{A}}$ is hyperhyperimmune.

Assume now that $T_{F_{A}}$ is hyperhyperimmune. Then $(T_{F_{A}})^{c} = (A ∖ {0}) \cap (A + 1)$ is hyperhypersimple. On the other hand, $(A ∖ {0}) \cap (A + 1) \subseteq A$ . Since a c.e. superset of a hyperhypersimple is either hyperhypersimple or cofinite, and $A$ clearly cannot be cofinite (otherwise $T_{F_{A}}$ would be finite) we have that $A$ is hyperhypersimple.

It follows from Theorem 3.6(2) and Proposition 3.4 that if $A$ is hypersimple then $F_{A}$ is hyperdark. Contrary to this, we will now see that there exist simple sets $A$ such that $F_{A}$ is not dark (although its principal transversal is immune by Theorem 3.6(1)), and for every hyperhypersimple set $A$ , $F_{A}$ is not hyperhyperdark (although its principal transversal is hyperhyperimmune by Theorem 3.6(3)). Since $F_{A} \in F i n C l$ , this will be used to conclude that, contrary to Proposition 3.4, there exist ceers $R$ , with $R \in F i n C l$ , such that the principal transversal $T_{R}$ is immune (respectively, hyperhyperimmune), but $R$ is not dark (respectively, hyperhyperdark): see, respectively, Corollary 3.8 and 3.9.
Lemma 3.7 Gao and Gerdes [5]

If $A$ is not hypersimple then $F_{A}$ is not dark.

Proof.
See Gao and Gerdes [5].
Corollary 3.8
If $A$ is simple, but not hypersimple then $F_{A}$ is a nondark ceer whose principal transversal is immune.
Proof.
Immediate, by item (1) of Theorem 3.6 and Lemma 3.7.
Corollary 3.9
If $A$ is hyperhypersimple, then $F_{A}$ is a non-hyperhyperdark ceer whose principal transversal is hyperhyperimmune.
Proof.
If $A$ is hyperhypersimple then, by item (3) of Theorem 3.6, the principal transversal of $F_{A}$ is hyperhyperimmune. On the other hand, we have that $F_{A}$ is not hyperhyperdark, as follows from Proposition 3.3 and the fact that $F_{A} \in F i n C l$ .
Remark 3.10
Inspection of its proof shows that Theorem 3.6 works for every simplicity property $P$ such that: if $A \in P$ then both $A ∖ {0}$ and $A + 1$ are in $P$ ; if $A, B \in P$ then $A \cap B \in P$ ; and if $A \in P$ and $A \subseteq B$ , with $B$ co-infinite, then $B \in P$ . As shown by the following observations, it does not work when one considers $r$ -maximality or maximality: indeed, these properties are not closed under intersection.
Definition 3.11
A set $A$ is cohesive if it is infinite, and cannot be split into two infinite parts by a c.e. set, that is, if $B$ is c.e. then either $B \cap A$ or $B^{c} \cap A$ is finite. A set is maximal if it is c.e. and its complement is cohesive.
Definition 3.12
A set $A$ is r-cohesive if it is infinite, and cannot be split into two infinite parts by a decidable set, that is, if $B$ is decidable then either $B \cap A$ or $B^{c} \cap A$ is finite. A set is r-maximal if it is c.e. and its complement is $r$ -cohesive.
Theorem 3.13
If $A$ is $r$ -maximal then $T_{F_{A}}$ is not $r$ -cohesive.
Proof.
Let $A$ be an $r$ -maximal set. Since ${2 n : n \in ω} = ({2 n + 1 : n \in ω})^{c}$ , by $r$ -maximality of $A$ it follows that either $| {2 n : n \in ω} \cap A^{c} | < \infty$ , or otherwise $| {2 n + 1 : n \in ω} \cap A^{c} | < \infty$ .

Assume that $| {2 n : n \in ω} \cap A^{c} | < \infty$ . Then it is clear that $| {2 n + 1 : 2 n + 1 \in A^{c}} | = \infty$ and $| {2 n : 2 n > 0 & 2 n \in A & 2 n - 1 \in A^{c}} | = \infty$ . Then (by the description of $T_{F_{A}}$ in the proof of Theorem 2.9) it is easy to see that
$| T_{F_{A}} \cap {2 n + 1 : n \in ω} | = \infty,$
and
$| T_{F_{A}} \cap {2 n : n \in ω} | = \infty,$
that is, the decidable set ${2 n : n \in ω}$ splits $T_{F_{A}}$ into two infinite parts, giving that $T_{F_{A}}$ is not $r$ -cohesive.

The case $| {2 n + 1 : n \in ω} \cap A^{c} | < \infty$ proceeds in a similar way.
Corollary 3.14
If $A$ is maximal then $T_{F_{A}}$ is not cohesive, in fact, is not $r$ -cohesive.
Proof.
If $A$ is a maximal set then it is $r$ -maximal too. Then by Theorem 3.13, $T_{F_{A}}$ is not $r$ -cohesive, and therefore it is not cohesive either.

We thus have one more proof of the known exercise stating that the intersection of two maximal sets need not be $r$ -maximal. Notice that if $A$ is $r$ -maximal then clearly the two sets $A ∖ {0}$ and $A + 1$ are both $r$ -maximal, and if $A$ is maximal then both $A ∖ {0}$ and $A + 1$ are maximal.
Corollary 3.15
If $A$ is $r$ -maximal then $A ∖ {0}$ and $A + 1$ are two $r$ -maximal sets having intersection which is not $r$ -maximal. If $A$ is maximal then $A ∖ {0}$ and $A + 1$ are two maximal sets having an intersection which is not $r$ -maximal.
Proof.
Immediate, since if $A$ is $r$ -maximal, then $T_{F_{A}} = ((A ∖ {0}) \cap (A + 1))^{c}$ is not $r$ -cohesive by the previous theorem.
4. Classes of hyperdark ceers

Together with $d a r k$ , $h d a r k$ , and $h h d a r k$ , one can define also the following classes of infinite ceers:

Definition 4.1
Define (where $R$ varies in the class of ceers): (a)
$non-low = {R \in Inf : R does not have any low infinite transversal}$ .
(b)
$non-incompl = {R \in Inf : if T is an infinite transversal of R then \emptyset^{'} \leq_{T} T}$ .

An example of a ceer $R \in F i n C l \cap n o n - i n c o m p l$ is given in Lemma 2.8 of Delle Rose et al. [3]
Theorem 4.2
We have, with $\subset$ denoting proper inclusion:
$n o n - i n c o m p l \cup h h d a r k \subset n o n - l o w \subset h d a r k \subset d a r k;$
moreover $n o n - i n c o m p l ⊈ h h d a r k$ and $h h d a r k ⊈ n o n - i n c o m p l$ .
Proof.
We already know (Proposition 3.2) that $h d a r k \subset d a r k$ . With the exception of $n o n - l o w \subseteq h d a r k$ (pointed out in the proof of Theorem 2.9 of Delle Rose et al. [14]), the other inclusions are straightforward.
The inclusion $h h d a r k \subseteq n o n - l o w$ follows from the fact that if $A$ is hyperhyperimmune then $\emptyset^{'} <_{T} A^{'}$ , as shown in Theorem 6.1 of Jockusch [22].
In most of the cases concerning our classes, counterexamples witnessing proper inclusion can be found by taking suitable unidimensional ceers $R_{X}$ and recalling the following well-known facts of classical computability theory. A set $X$ is introreducible if, for every infinite subset $Y \subseteq X$ , $X \leq_{T} Y$ . In Dekker [21], it has been proven that, given any undecidable c.e. set $Y$ , there exists a hypersimple set $X \equiv_{T} Y$ whose complement $X^{c}$ is introreducible. Indeed, one can take as $X$ the Dekker deficiency set of $Y$ (Dekker [21]), namely the set ${n : (\exists m > n) [a_{m} < a_{n}]}$ , where we refer to some fixed 1-1 computable enumeration ${a_{n} : n \in ω}$ of $Y$ (whatever 1-1 computable enumeration of $Y$ we start off with, we get a set which is Turing-equivalent to $Y$ ). Moreover, it has been proven by Yates [23] that no deficiency set can be hyperhypersimple.

First, if we take $X$ to be the deficiency set of a c.e. set, which is neither low nor high, we get $R_{X} \in n o n - l o w ∖ (n o n - i n c o m p l \cup h h d a r k)$ . Indeed: –
$R_{X} \in n o n - l o w$ since every infinite transversal $A$ of $R_{X}$ coincides (with the exception of at most one element) with an infinite subset of $X^{c}$ : therefore by introreducibility, we have that $X^{c} \leq_{T} A$ , and thus $\emptyset^{'} <_{T} X^{'} \leq_{T} A^{'}$ ;
–
$R_{X} \notin n o n - i n c o m p l$ as $X^{c}$ is a transversal and $X^{c} <_{T} \emptyset^{'}$ ;
–
finally, $R_{X} \notin h h d a r k$ by Martin’s result in Corollary 3.1 of Martin [24] stating that a c.e. degree is high if and only if it contains a hyperhypersimple set, hence $X^{c}$ is not hyperhyperimmune.

To show that $n o n - i n c o m p l ⊈ h h d a r k$ take as $X$ the deficiency set of $\emptyset^{'}$ , and apply the above-quoted result by Yates.

To show that $h h d a r k ⊈ n o n - i n c o m p l$ let $X$ be a hyperhypersimple set with $X <_{T} \emptyset^{'}$ (such a set exists again by Corollary 3.1 of Martin [24]): then $R_{X} \in h h d a r k ∖ n o n - i n c o m p l$ .

Finally, it follows from Theorem 4.3 that the inclusion $n o n - l o w \subset h d a r k$ is proper.

The various inclusions of Theorem 4.2 are summarized in the following figure, where directed arrows denote proper inclusions between the various classes of ceers, and no inclusion holds if no arrow is shown:

Theorem 4.3
There is a hyperdark ceer $R \in F i n C l$ such that its principal transversal is low. It follows that $h d a r k ⊈ n o n - l o w$ .
Proof.
Let $A$ be hypersimple and low. Then $F_{A} \in F i n C l$ , and by Proposition 3.4 and Theorem 3.6, $F_{A} \in h d a r k$ . As the complement of its principal transversal is $(A ∖ {0}) \cap (A + 1)$ we have that $T_{F_{A}} \leq_{T} A$ (being $T_{F_{A}} \leq_{T} F_{A}$ by Remark 1.4, and $F_{A} \leq_{T} A$ by Lemma 2.6) and thus $T_{F_{A}}$ is low. To show the theorem, then it is enough to take $R = F_{A}$ .
Remark 4.4
It is possible to build a ceer $R \in F i n C l$ satisfying Theorem 4.3 directly by a standard priority argument with finite injury. We are not going through the full construction of such a ceer: we just observe that, to ensure hyperdarkness, it is enough to satisfy the requirements of the form
$R_{e} : ((D_{φ_{e} (n)})_{n \in ω} strong disjoint array) \Rightarrow (\forall T \in Tr (R)) (\exists n) (D_{φ_{e} (n)} \cap T = \emptyset),$
which can be done according to the following strategy.

Strategy for the hyperdarkness requirement $R_{e}$ . Wait until $φ_{e}$ halts on two distinct element $u$ and $v$ , such that $D_{φ_{e} (u)} \neq \emptyset$ and $D_{φ_{e} (v)} \neq \emptyset$ ; whenever this happens, collapse the two finite sets $D_{φ_{e} (u)}$ and $D_{φ_{e} (v)}$ within the same $R$ -equivalence class.

This single collapsing action is enough to satisfy requirement $R_{e}$ : if $(D_{φ_{e} (n)})_{n \in ω}$ is a strong disjoint array, and a set $T$ is intersected by $(D_{φ_{e} (n)})_{n \in ω}$ , then there are $t \in T \cap D_{φ_{e} (u)}$ and $t^{'} \in T \cap D_{φ_{e} (v)}$ such that $t \neq t^{'}$ (since the array is disjoint), but $t R t^{'}$ , implying that $T$ is not a transversal of $R$ . It follows that if all requirements $R_{e}$ are met, then every infinite transversal $T$ is hyperimmune, since no strong disjoint array intersects $T$ .

Unfortunately, this strategy cannot be used to diagonalize against weak disjoint arrays: in fact, in this case, we have at our disposal only c.e. indices, thus we have no way of knowing if a certain set whose index $u_{e}$ is output by $φ_{e}$ is indeed finite, and this could make us keep collapsing elements forever just for the sake of requirement $R_{e}$ , should $W_{u_{e}}$ be infinite.

However, this very same strategy would succeed if we could access oracle $\emptyset^{'}$ . Indeed, as shown below, contrary to Proposition 3.3, we have that at level $Σ_{2}^{0}$ of the arithmetical hierarchy, we have equivalence relations $R \in F i n C l$ such that all infinite transversals of $R$ are hyperhyperimmune.
Proposition 4.5
There exists a $Σ_{2}^{0}$ -equivalence relation $R \in F i n C l$ such that all infinite transversals of $R$ are hyperhyperimmune.
Proof.
Our desired equivalence relation $R \in Σ_{2}^{0}$ must satisfy the following requirements, for every $e \in ω$ ,
$\begin{aligned} F_{e} : & [e]_{R} is finite, \\ P_{e} : & ((W_{φ_{e} (n)})_{n \in ω} weak disjoint array) \Rightarrow (\forall T \in Tr (R)) (\exists n) (W_{φ_{e} (n)} \cap T = \emptyset) : \end{aligned}$
these requirements are prioritized as $F_{0} < P_{0} < F_{1} < P_{1} < \dots$ .

We define in stages a sequence of uniformly $\emptyset^{'}$ -decidable equivalence relations ${R_{s}}_{s \in ω}$ , such that $R_{0} = Id$ , and $R_{s} \subseteq R_{s + 1}$ for every $s$ (more precisely, the equivalence relation $R_{s + 1}$ , defined at stage $s + 1$ , is obtained by collapsing finitely many classes of $R_{s}$ ), and $R = ⋃_{s \in ω} R_{s}$ satisfies the claim. Given the way we define each $R_{s}$ , at each stage $s$ the values
$\begin{aligned} p (x, s) & = max [x]_{R_{s}}, \\ q (s) & = least y (\forall z > y) ([z]_{R_{s}} is a singleton)) \end{aligned}$
are finite. The strategy for $P_{e}$ is an adaptation of the hyperdarkness strategy for $R_{e}$ described earlier, but introducing and exploiting the oracle $\emptyset^{'}$ in the various computations, since we now work with weak disjoint arrays, instead of strong disjoint arrays. The construction will use one more parameter, namely $c (s)$ , which is the canonical index of a finite set comprised of all numbers $e$ such that $P_{e}$ has acted (as defined later) at some stage $t \leq s$ .

The partial functions
$\begin{aligned} M (x) & = {\begin{cases} max W_{x}, & if W_{x} is finite & W_{x} \neq \emptyset, \\ ↑ & otherwise, \end{cases} \\ m (x) & = {\begin{cases} min W_{x}, & if W_{x} \neq \emptyset, \\ ↑ & otherwise, \end{cases} \end{aligned}$
are clearly $Σ_{2}^{0}$ (remember that ${x : W_{x} finite} \in Σ_{2}^{0}$ ), and thus they are partial $\emptyset^{'}$ -computable. Let $w$ be an index such that $M = φ_{w}^{\emptyset^{'}}$ . Write $M (x, s) = φ_{w, s}^{\emptyset^{'}} (x)$ (where we refer to the approximations of oracle computations as in Definition III 1.7 of Soare [15]) so that the predicates $M (x, s) ↓$ and $M (x, s) ↓= u$ are $\emptyset^{'}$ -decidable, $M (x) ↓\Leftrightarrow (\exists s) (M (x, s) ↓)$ , and $M (x, s) ↓\Leftrightarrow (\forall t \geq s) (M (x, t) ↓= M (x))$ .

Stage $0$ . Define $R_{0} = Id$ ; thus $q (0) = - 1$ , and for every $x$ , $p (x, 0) = x$ .

Stage $s + 1$ . We say that the requirement $P_{e}$ requires attention at stage $s + 1$ , if $e \leq s$ and (1)
$e \notin D_{c (s)}$ , that is, $P_{e}$ has never acted at any $t \leq s$ ; and
(2)
there exists $u, v \leq s$ with $u \neq v$ , such that (a)
$φ_{e} (u) ↓$ (say $φ_{e} (u) = u_{e}$ ), $φ_{e} (v) ↓$ (say $φ_{e} (v) = v_{e}$ );
(b)
$M (u_{e}, s) ↓$ , $M (v_{e}, s) ↓$ (thus $W_{u_{e}}$ and $W_{v_{e}}$ are nonempty finite sets, with $M (u_{e}) = max W_{u_{e}}$ and $M (v_{e}) = max W_{v_{e}}$ ) and there exist $t \in W_{u_{e}}$ and $t^{'} \in W_{v_{e}}$ with $t \neq t^{'}$ ; notice that this implies that both $m (u_{e}), m (v_{e})$ converge too, and $m (u_{e}) = min W_{u_{e}}$ and $m (v_{e}) = min W_{v_{e}}$ ; and
(c)
$min {m (u_{e}), m (v_{e})} > max {p (i, s) : i \leq e}$ , that is
$min (W_{u_{e}} \cup W_{v_{e}}) > max {max [i]_{s} : i \leq e} .$

Case 1. If there is no $P_{e}$ which requires attention, then go directly to stage $s + 2$ ; in this case $R_{s + 1} = R_{s}$ , $q (s + 1) = q (s)$ , and $c (s + 1) = c (s)$ .

Case 2. Otherwise, let $P_{e}$ be the highest priority requirement currently requiring attention, choose the pair $u, v$ with the least code as in item (2) of requiring attention, and let $D_{c (s + 1)} = D_{c (s)} \cup {e}$ . Let $R_{s + 1}$ be the equivalence relation generated by $R_{s} \cup {(x, y) : x, y \in W_{u_{e}} \cup W_{v_{e}}}$ : clearly, in this case,
$q (s + 1) = max {q (s), M (u_{e}), M (v_{e})} .$
as the $R_{s + 1}$ -equivalence class containing $W_{u_{e}} \cup W_{v_{e}}$ contains at least two elements. We say that $P_{e}$ has acted at $s + 1$ . Go to the next stage.

At the end of the construction, the desired equivalence relation is $R = ⋃_{s} R_{s}$ .

Verification. We first prove that the sequence $(R_{s})_{s \in ω}$ is uniformly $\emptyset^{'}$ -decidable, by showing that the predicate (in $x, y, s$ ) $x R_{s} y$ , is $\emptyset^{'}$ -decidable, so that the final relation $R$ is $Σ_{2}^{0}$ since
$x R y \Leftrightarrow (\exists s) (x R_{s} y) .$
To see that this $(x, y, s)$ -predicate is $\emptyset^{'}$ -decidable, we show that there exists a $\emptyset^{'}$ -computable function $F (s) = ⟨ i_{s}^{c}, i_{s}^{q}, i_{s}^{R} ⟩$ where $i_{s}^{c}, i_{s}^{q}, i_{s}^{R}$ are (indices of) oracle Turing machines such that, with oracle $\emptyset^{'}$ , $i_{s}^{c}$ computes $c (s)$ , $i_{s}^{q}$ computes $q (s)$ , and $i_{s}^{R}$ decides $R_{s}$ . Thus, to check whether $x R_{s} y$ , one has to compute $F (s)$ (which requires oracle $\emptyset^{'}$ ), recover $i_{s}^{R}$ from $F (s)$ , and run the machine $i_{s}^{R}$ with oracle $\emptyset^{'}$ on the pair $x, y$ .

The value $F (0)$ is left to the reader. To define $F (s + 1)$ knowing already $F (s)$ , notice that all conditions in the definition of a requirement $P_{e}$ , with $e \leq s$ , requiring attention at stage $s + 1$ can be uniformly tested with oracle $\emptyset^{'}$ (for condition (1) use first $i_{s}^{c}$ to compute $c (s)$ , and see whether $e \in D_{c (s)}$ ; for (2c), use first $i_{s}^{q}$ to compute $q (s)$ , and notice that
$p (i, s) = y \Leftrightarrow (\forall z) (y < z \leq q (s) \Rightarrow \neg (i R_{s} z)) :$
thus $max [i]_{R_{s}}$ is $R_{s} \oplus \emptyset^{'}$ -computable since the universal quantifier is bounded by $q (s)$ ). This allows to decide, with oracle $R_{s} \oplus \emptyset^{'}$ , whether there is a requirement $P_{e}$ which requires attention, and to know whether Case 1 holds, that is, $R_{s + 1} = R_{s}$ , or Case 2 holds, that is, $R_{s + 1}$ comes from collapsing to the same $R_{s + 1}$ -equivalence class two finite sets $W_{u_{e}}$ and $W_{v_{e}}$ for suitable $e, u_{e}, v_{e}$ . In either case, we have $R_{s} \oplus \emptyset^{'}$ -oracle algorithms to compute $c (s + 1)$ , $q (s + 1)$ , and to decide $R_{s + 1}$ : for instance, in Case 1, we can take $i_{s + 1}^{R} = i_{s}^{R}$ , in Case 2, we can take $i_{s + 1}^{R}$ to be the index of an oracle Turing machine, which first $\emptyset^{'}$ -compute $q (s + 1)$ (using the oracle algorithms for computing the values $q (s)$ , $M (u_{e})$ and $M (v_{e})$ ), and decides $R_{s + 1}$ using that $R_{s + 1}$ is the identity on the open line $(q (s + 1), \infty)$ , whereas on the interval $[0, q (s + 1)]$ we have
$x R_{s + 1} y \Leftrightarrow x R_{s} y \lor (\exists (u, v) \in (W_{u_{e}} \cup W_{v_{e}})^{2}) (x R_{s} u & y R_{s} v)),$
which is $R_{s} \oplus \emptyset^{'}$ -decidable since the two existential quantifiers are bounded by $q (s + 1)$ . By using the oracle Turing machine $i_{s}^{R}$ (which decides $R_{s}$ with oracle $\emptyset^{'}$ ), the oracle $R_{s} \oplus \emptyset^{'}$ can be replaced, as desired, by $\emptyset^{'}$ , so as to get a suitable oracle turing machine $i_{s + 1}^{R}$ which decides $R_{s + 1}$ with oracle $\emptyset^{'}$ .

Requirement $F_{e}$ . A simple induction on the number $e$ shows that for every $e$ , there is a least stage after which $[e]_{R}$ never changes again: this follows from the fact that $[e]_{R_{s}}$ may change only by actions taken by $P$ -requirements having higher priority than $F_{e}$ (lower priority $P$ -requirements do not modify $[e]_{R_{s}}$ , as they collapse only numbers $> max [i]_{R_{s}}$ for every $i \leq e$ ), but each such requirement acts at most once. Since each action only collapses finitely many elements, we have that $[e]_{R}$ is finite. So, in the end, $R \in F i n C l$ .

Requirement $P_{e}$ . Our next claim is that all infinite transversals of $R$ are hyperhyperimmune, as a consequence of the fact that every requirement $P_{e}$ is satisfied. To see that each $P_{e}$ is satisfied, notice that if $P_{e}$ is ever allowed to act, then just this very action is enough to have that if $(W_{φ_{e} (n)})_{n \in ω}$ is a weak disjoint array, then the array does not intersect any transversal $T$ for $R$ . Indeed, whenever $P_{e}$ acts, it $R$ -collapses within a single $R$ -equivalence class two distinct sets $W_{φ_{e} (u)}$ and $W_{φ_{e} (v)}$ , so that if a set $T$ is intersected by the array $(W_{φ_{e} (n)})_{n \in ω}$ , then there are $t \in T \cap W_{φ_{e} (u)}$ and $t^{'} \in T \cap W_{φ_{e} (v)}$ such that $t \neq t^{'}$ (since the array is disjoint) but $t R t^{'}$ , implying that $T$ is not a transversal of $R$ . It remains to show that, if $(W_{φ_{e} (n)})_{n \in ω}$ is a weak disjoint array of nonempty sets (thus, in particular, $φ_{e}$ is total and unbounded, and for every $n$ , $M (φ_{e} (n)) ↓$ so that for all big enough stage $s$ , $M (φ_{e} (n), s) ↓= M (φ_{e} (n))$ ), then $P_{e}$ eventually acts. To see this, assume by induction that $s_{0}$ is a stage such that no $[i]_{R}$ , with $i \leq e$ , changes after $s_{0}$ , and no $P_{i}$ , with $i < e$ , acts after $s_{0}$ . Then either $P_{e}$ has already acted at some stage $s \leq s_{0}$ , or (by unboundedness of $φ_{e}$ and disjointness of $(W_{φ_{e} (n)})_{n \in ω}$ : this latter condition ensures that $min W_{φ_{e} (n)} > max {max [i]_{R} : i \leq e}$ , for all big enough $n$ ), there must be a stage $s > s_{0}$ so that at this stage $φ_{e}$ converges on two suitable elements $u, v$ which make $P_{e}$ receive attention at $s + 1$ , and at this stage $P_{e}$ acts.

Therefore, every infinite transversal of $R$ is hyperhyperimmune, since no weak disjoint array can intersect $T$ .
5. Hyperhyperdark ceers

As observed in Andrews and Sorbi [4], the property of being a dark ceer is degree invariant, namely if $R$ is a dark ceer then all $S$ such $S \in \deg_{c} (R)$ are dark. Similarly (as shown in Lemma 2.3 of Delle Rose et al. [3]) the property of being a hyperdark ceer is degree invariant.

Contrary to this, it turns out that the property of being a hyperhyperdark ceer is not degree invariant. The following theorem is the key step to show this result. Given an equivalence relation $E$ , let $E^{\infty}$ by the cylindrification of $E$ , defined by $⟨ i, x ⟩ E^{\infty} ⟨ j, x ⟩$ if and only if $i E j$ . It is well known that $E \equiv_{c} E^{\infty}$ : for instance, $E \leq_{c} E^{\infty}$ via the computable function $x \mapsto ⟨ x, 0 ⟩$ , and $E^{\infty} \leq_{c} E$ via the computable function $⟨ x, y ⟩ \mapsto x$ .

Theorem 5.1

For every ceer $E \in I n f$ we have $\deg_{c} (E) \cap {h h d a r k}^{c} \neq \emptyset$ .

Proof.

Let $E \in I n f$ be a ceer. We are going to show that $E^{\infty}$ has an infinite transversal which is not hyperhyperimmune. This is enough to show the claim, since $E^{\infty} \in \deg_{c} (E)$ . Let us refer to some fixed computable approximation ${E_{s} : s \in ω}$ to $E$ (see e.g., Lemma 1.4 of [8]): we use here that the sequence ${E_{s} : s \in ω}$ is a uniformly computable sequence of equivalence relations (meaning that the relation $x E_{s} y$ is decidable in $x, y, s$ ), starting with $E_{0} = Id$ , $E_{s} \subset E_{s + 1}$ for every $s$ (we may assume to always have strict inclusion, since $E \in I n f$ ), and $E = ⋃_{s} E_{s}$ . Let $a (e, s)$ be a computable function which enumerates $T_{E_{s}}$ in order of magnitude: $a (0, s) = 0$ , and $a (e + 1, s) = min {x : x > a (e, s) & (\forall y < x) \neg (y E_{s} x)}$ . Notice that $a_{e} = lim_{s} a (e, s)$ exists for every $e$ , and $a_{e}$ is the $e$ th element in order of magnitude of the principal transversal $T_{E}$ of $E$ .

Define inductively in stages a uniformly decidable sequence ${V_{e, s} : e, s \in ω}$ of finite sets as follows. For every number $e$ , let $V_{e, 0} = {⟨ e, 0 ⟩}$ (notice that $a (e, 0) = e$ ). Suppose that we have defined $V_{e, s}$ for every $e, s$ , and let $i$ be the least number such that $a (i, s + 1) \neq a (i, s)$ (by our assumptions on the fixed computable approximation of $E$ , such an $i$ exists at any stage): define

V_{e, s + 1} = {\begin{cases} V_{e, s}, & if e < i, \\ V_{e, s} \cup {⟨ a (e, s + 1), s + 1 ⟩}, & otherwise. \end{cases}

Clearly,

V_{e, s} \subseteq V_{e, s + 1}

for every

e, s \in ω

. An easy induction shows that for every

e

there exists a stage

t_{e}

such that

V_{e, s} = V_{e, t_{e}}

for every

s \geq t_{e}

: call

V_{e}

this limit value of

V_{e, s}

. Moreover,

(V_{e})_{e \in ω}

is a weak disjoint array. To show for instance disjointness, assume that

⟨ x, t ⟩ \in V_{i} \cap V_{j}

: then

⟨ x, t ⟩

has been enumerated both in

V_{i}

and

V_{j}

at stage

t

, hence

x = a (i, t)

and

x = a (j, t),

which implies

i = j

since the function

e \mapsto a (e, t)

enumerates

T_{E_{t}}

in order of magnitude.

Again by induction, one shows that for every $e$ the last element enumerated in $V_{e}$ is $⟨ a_{e}, t_{e} ⟩$ . Then the set

T = {⟨ a_{e}, t_{e} ⟩ : e \in ω}

is therefore an infinite transversal of

E^{\infty}

, which is not hyperhyperimmune since it is intersected by the weak disjoint array

(V_{e})_{e \in ω}

Corollary 5.2

The property of being a hyperhyperdark ceer is not degree invariant.

Proof.

Immediate by Theorem 5.1 and the fact that hyperhyperdark ceers do exist: for instance, we know that if $X$ is a hyperhypersimple set, then $R_{X} \in h h d a r k$ .

A finer way to compare equivalence relations is through the following notion of isorphism.

Definition 5.3

Two equivalence relations $R, S$ are said to be isomorphic (denoted by $R \approx_{c} S$ ) if there exist computable reductions $f : R \leq_{c} S$ and $g : S \leq_{c} R$ which invert each other on equivalence classes, that is,

(\forall x) [x R g (f (x)) & x S f (g (x))] .

A computable function

f : R \leq_{c} S

as above is said to be an isomorphism from $R$ to $S$ . (For a justification of this category-theoretic terminology, see Delle Rose et al. [25] Moreover, notice that, clearly,

R \equiv_{c} S

R \approx_{c} S

Remark 5.4

The property of being a hyperhyperdark ceer is not invariant under isomorphisms, since in fact $E \approx_{c} E^{\infty}$ .

There is a yet stronger notion of isomorphism.

Definition 5.5

$R$ is computably isomorphic to $S$ , if there is an isomorphism from $R$ to $S$ which is a computable permutation of $ω$ .

Notice that if $R$ and $S$ are computably isomorphic, then, in particular, $R \leq_{c, 1} S & S \leq_{c, 1} R$ (see Definition 2.10): thus, the following lemma immediately implies that the property of being a hyperhyperdark ceer is invariant under computable isomorphisms.

Lemma 5.6

Given ceers $R, S$ , if $R \leq_{c, 1} S$ , and $R \notin h h d a r k$ , then $S \notin h h d a r k$ .

Proof.

Suppose $f : R \leq_{c} S$ is a 1-1 computable function $f$ . Let $T$ be an infinite transversal of $R$ which is not hyperhyperimmune, and let $(F_{n})_{n \in ω}$ be a weak disjoint array of finite sets such that for every $n$ , $F_{n} \cap T \neq \emptyset$ . By injectivity of $f$ , we have that $(f [F_{n}])_{n \in ω}$ is a weak disjoint array of finite sets such that for every $n$ , $f [F_{n}] \cap f [T] \neq \emptyset$ , showing that $f [T]$ is not hyperhyperimmune. On the other hand, $f [T]$ is obviously an infinite transversal of $S$ , showing that $S \notin h h d a r k$ .

Our last goal is to show the following necessary condition for a $c$ -degree of a ceer to contain a hyperhyperdark ceer: given a ceer $E$ , if $\deg_{c} (E) \cap h h d a r k \neq \emptyset$ then $\deg_{c} (E) \subseteq {F i n C l}^{c}$ and $\deg_{c} (E) ⊈ I n f C l$ . In particular, only ceers having both finite and infinite equivalence classes can be hyperhyperdark. Such necessary condition follows immediately by Theorem 5.7 and Corollary 5.8.

First, we strengthen Proposition 3.3 (aka Theorem 2.10 of Delle Rose et al. [3]) by showing that no ceer which $c$ -reduces some ceer in $F i n C l$ can be hyperhyperdark.

Theorem 5.7

Let $R, S$ be ceers such that $R \in F i n C l$ and $R \leq_{c} S$ . Then $S \notin h h d a r k$ .

Proof.

Let $R \in F i n C l$ be a ceer and $S$ be a ceer such that $R \leq_{c} S$ via $f$ . Fix a computable approximation ${R_{s}}_{s \in ω}$ to $R$ as in the proof of Theorem 5.1. We define uniformly computable sequences ${P_{e, s} : e, s \in ω}$ , ${V_{e, s} : e, s \in ω}$ and ${F_{s}}_{s \in ω}$ of finite sets in stages as follows.

At stage $0$ , we let $P_{e, 0} = V_{e, 0} = \emptyset$ for every $e$ and $F_{0} = \emptyset$ . At stage $s + 1$ , let $e$ be the least index such that

P_{e, s} \subseteq ⋃_{i < e} {[P_{i, s}]}_{R_{s}}

(which always exists, since all but finitely many

P_{e, s}

are empty), then pick the least

w \in ω

such that

w \notin ⋃_{i < e} {[P_{i, s}]}_{R_{s}} and f (w) \notin F_{s}

(notice that we can always find such a

w

, as

| f^{- 1} (y) | < \infty

for every

y

), and let

P_{i, s + 1} = {\begin{cases} P_{i, s} \cup {w}, & if i = e, \\ P_{i, s}, & if i \neq e \end{cases} V_{i, s + 1} = {\begin{cases} V_{i, s} \cup {f (w)}, & if i = e, \\ V_{i, s}, & if i \neq e \end{cases}

and

F_{s + 1} = F_{s} \cup {f (w)}

An easy inductive argument, using the fact that $R \in F i n C l$ , shows: for every $e$ , there is a stage $t_{e}$ such that $P_{e, s} = P_{e, t_{e}}$ and $V_{e, s} = V_{e, t_{e}}$ for all $s \geq t_{e}$ . Thus, for every $e$ , $V_{e} = ⋃_{s \in ω} V_{e, s}$ is a finite set. Moreover, it is clear that the way in which we pick the $w$ ’s ensures that $V_{i} \cap V_{j} = \emptyset$ whenever $i \neq j$ . This shows that $(V_{e})_{e \in ω}$ is a weak disjoint array. Finally, for every $e$ , let $w_{e}$ be the last element to enter $P_{e, t_{e}}$ . The fact that $P_{e, s} = P_{e, t_{e}}$ for all $s \geq t_{e}$ , ensures that $w_{e} R w_{i}$ for all $i < e$ , meaning that ${w_{e} : e \in ω}$ is a transversal of $R$ . Then ${f (w_{e}) : e \in ω}$ is a transversal of $S$ , which is not hyperhyperimmune as $f (w_{e}) \in V_{e}$ for every $e$ . Thus, $S \notin h h d a r k$ .

To achieve our goal, it remains to make the following observation.

Corollary 5.8

If $E$ is a ceer such that $\deg_{c} (E) \subseteq I n f C l$ then $\deg_{c} (E) \subseteq {h h d a r k}^{c}$ .

Proof.

The claim is clearly true if $E \notin I n f$ . On the other hand, if $E \in I n f$ , then, by Theorem 5.1, $E^{\infty} \notin h h d a r k$ . By Lemma 2.11(1), $E^{\infty} \leq_{c, 1} E$ : then Lemma 5.6 ensures that $E \notin h h d a r k$ .

We conclude by showing that indeed there are ceers $E$ such that $\deg_{c} (E) \subseteq I n f C l$ : in order to do so, we recall and apply some known facts of the theory of ceers.

Definition 5.9

$R \in E q r e l (ω)$ is self-full if every reduction $f : R \leq_{c} R$ satisfies $[range (f)]_{R} = ω$ .

It is known that self-full ceers do exist: in fact, one can even show that every dark ceer is self-full (see Lemma 4.6 in Andrews and Sorbi [4]). Moreover, in Theorem 4.10 of Andrews and Sorbi [4], it has been proven the existence of self-full ceers which yield a partition of $ω$ into sets which are pairwise computably inseparable: thus, in particular, all equivalence classes of such ceers must be infinite. We will also use the following property of self-full ceers.

Lemma 5.10

If $R$ is a self-full ceer, and $R \equiv_{c} S$ , then every reduction from $R$ to $S$ is an isomorphism from $R$ to $S$ .

Proof.

By using Lemma 1.1 in Andrews and Sorbi [4], it is enough to show that, if $R$ is a self-full ceer, $R \equiv_{c} S$ and $f : R \leq_{c} S$ , then $[range (f)]_{S} = ω$ . Let $f : R \leq_{c} S$ and $g : S \leq_{c} R$ be computable reductions, and suppose that there exists $y$ such that $y \notin [range (f)]_{S}$ . Then $g \circ f$ is a computable reduction from $R$ to $R$ such that $g (y) \notin [range (g \circ f)]_{R}$ , contradicting that $R$ is self-full.

Putting these ingredients together, we get the promised result.

Corollary 5.11

There exist ceers $E$ such that $\deg_{c} (E) \subseteq I n f C l$ .

Proof.

It is not difficult to see that if $E$ yields a partition of $ω$ into sets which are pairwise computably inseparable, and $E \approx_{c} S$ , then also $S$ yields a partition of $ω$ into sets which are pairwise computably inseparable. To see this, suppose that $[a]_{S}$ and $[b]_{S}$ are distinct equivalence classes and $Y$ is a computable set that separates the two classes. Let $f$ be an isomorphism from $E$ to $S$ . Let $[a^{'}]_{E}$ and $[b^{'}]_{E}$ be the two $E$ -equivalence classes such that $f$ maps, and thus $m$ -reduces, $[a^{'}]_{E}$ to $[a]_{S}$ , and $[b^{'}]_{E}$ to $[b]_{S}$ . Then $f^{- 1} [Y]$ is a computable set which separates $[a^{'}]_{E}$ and $[b^{'}]_{E}$ .

Now, let us consider a ceer $E$ which is self-full and yields a partition of $ω$ into pairwise computably inseparable sets (as mentioned above, such ceers exist: see Theorem 4.10 of Andrews and Sorbi [4]). If $S$ is a ceer such that $E \equiv_{c} S$ then by Lemma 5.10 $E \approx_{c} S$ . By the previous discussion, the $S$ -equivalence classes are pairwise computably inseparable, thus they are all undecidable, and therefore $S \in I n f C l$ .

Footnotes

Acknowledgements

The authors wish to thank the anonymous referees for their useful comments and are particularly indebted to one of them for having suggested Theorem 5.1, its proof, and some of its consequences. The authors wish also to thank Dr Luca San Mauro for helpful and stimulating conversations.

ORCID iD

Andrea Sorbi

Funding

The authors disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: Irakli Chitaia was supported by Shota Rustaveli National Science Foundation of Georgia (SRNSFG) [Grant number: FR-22-16379 Algorithmic reducibilities and algebraic structures]. Valentino Delle Rose was funded by ANID Fondecyt Postdoctorado 3230263, by the National Center for Artificial Intelligence CENIA FB210017, Basal ANID, and by the project PRIN 2022 “Logical Methods in Combinatorics” No. 2022BXH4R5 of the Italian Ministry of University and Research (MIUR).

Declaration of conflicting interests

The authors declared the following potential conflicts of interest with respect to the research, authorship, and/or publication of this article: Sorbi is a member of INDAM-GNSAGA. The remaining authors have no potential conflicts of interest to declare.

References

Kasymov

NKH

Khoussainov

. Finitely generated enumerable and absolutely locally finite algebras. Vychisl Sistemy 1986; 116: 3–15.

Gavryushkin

Khoussainov

Stephan

. Reducibilities among equivalence relations induced by recursively enumerable structures. Theoret Comput Sci 2016; 612: 137–152.

Delle Rose

San Mauro

Sorbi

. Classifying word problems of finitely generated algebras via computable reducibility. Int J Algebra Comput 2023; 33: 751–768.

Andrews

Sorbi

. Joins and meets in the structure of ceers. Computability 2019; 8: 193–241.

Gao

Gerdes

. Computably enumerable equivalence relations. Stud Log 2001; 67: 27–59.

Nies

. Recursively enumerable equivalence relations modulo finite differences. Math Log Q 1994; 40: 490–518.

Andrews

Lempp

Miller

, et al. Universal computably enumerable equivalence relations. J Symbol Log 2014; 79: 60–88.

Andrews

Badaev

Sorbi

. A survey on universal computably enumerable equivalence relations. In: Day A, Fellows M, Greenberg N, et al. (eds) Computability and complexity. Essays dedicated to Rodney G. Downey on the occasion of his 60th birthday. Cham: Springer, 2017, pp.418–451.

Andrews

Schweber

Sorbi

. The theory of ceers computes true arithmetic. Ann Pure Appl Log 2020; 171: 102811.

10.

Andrews

Sorbi

. Initial segments of the degrees of ceers. J Symbol Log 2022; 87: 1260–1283.

11.

Selivanov

. Positive structures. In: Cooper SB and Goncharov SS (eds) Computability and models. New York: Springer, 2003, pp.321–350.

12.

Khoussainov

. A journey to computably enumerable structures (tutorial lectures). In: Sailing routes in the world of computation – Proceedings of the 14th conference on computability in Europe (CiE 2018), Kiel, Germany, 30 July–3 August 2018 (eds F Manea, RG Miller and D Nowotka), vol. 10936 of LNCS, 2018, pp.1–19. Cham: Springer.

13.

Fokina

Khoussainov

Semukhin

, et al. Linear orders realized by c.e. equivalence relations. J Symb Log 2016; 81: 463–482.

14.

Delle Rose

San Mauro

Sorbi

. Word problems and ceers. Math Log Q 2020; 66: 341–354.

15.

Soare

. Recursively enumerable sets and degrees. A study of computable functions and computably generated sets. Perspectives in mathematical logic. Berlin: Springer-Verlag, 1987.

16.

Rogers

H Jr

. Theory of recursive functions and effective computability. New York: McGraw-Hill, 1967.

17.

Cooper

. Computability theory. Boca Raton: Chapman & Hall/CRC Press, 2003.

18.

Odifreddi

. Classical recursion theory (Vol. I). Amsterdam: North-Holland, 1989.

19.

Soare

. Turing computability: theory and applications of computability. Berlin: Springer-Verlag, 2016.

20.

. On the degree structure of equivalence relations under computable reducibility. Notre Dame J Form Log 2019; 60: 733–761.

21.

Dekker

JCE

. A theorem on hypersimple sets. Proc Am Math Soc 1954; 5: 791–796.

22.

Jockusch

CG Jr

. The degrees of hyperhyperimmune sets. J Symbol Log 1969; 34: 489–493.

23.

Yates

CEM

. Recursively enumerable sets and retracing functions. Z Math Logik Grundlagen Math 1962; 8: 331–345.

24.

Martin

. Classes of recursively enumerable sets and degrees of unsolvability. Z Math Logik Grundlagen Math 1966; 12: 295–310.

25.

Delle Rose

San Mauro

Sorbi

. The category of equivalence relations. Algebra Log 2021; 60: 295–307. (in Russian)

On the transversals of a ceer

Abstract

1. Introduction

1.1. Notations, references, and background material

Proof. See Theorem 2.10 in Delle Rose et al. [3] Many of the properties of an equivalence relation follow from the properties of its principal transversal. For instance: Proposition 3.4 Delle Rose et al. [3]

Footnotes

Acknowledgements

ORCID iD

Funding

Declaration of conflicting interests

References

Proof.
See Theorem 2.10 in Delle Rose et al. [3]

Many of the properties of an equivalence relation follow from the properties of its principal transversal. For instance:
Proposition 3.4 Delle Rose et al. [3]