1 Introduction
The study of the complexity of equivalence relations has been a major thread of research in diverse areas of logic. The most popular way for evaluating this complexity is by defining a suitable reducibility. A reduction of an equivalence relation R on a domain X to an equivalence relation S on a domain Y is a (nice) function
$f: X\rightarrow Y$
such that
$$ \begin{align*} x\mathrel{R} y \Leftrightarrow f(x)\mathrel{S}f(y). \end{align*} $$
That is, f pushes down to an injective map on the quotient sets
$X_{R}\mapsto Y_{S}$
. It is natural to impose a bound on the complexity of the reduction f, as otherwise, if the size of
$X_R$
is not larger than the size of
$X_S$
, then the Axiom of Choice alone would guarantee the existence of a reduction from R to S; thus we would not be able to distinguish equivalence relations with the same number of equivalence classes. In the literature, there are two main definitions for this reducibility, designed to deal, respectively, with the uncountable case and the countable case:
-
• In descriptive set theory, Borel reducibility
$(\leqslant _B)$
is defined by assuming that X and Y are Polish spaces and f is Borel. -
• In computability theory, computable reducibility
$(\leqslant _c)$
is defined by assuming that
$X=Y$
coincide with the set
$\omega $
of natural numbers and f is computable.
The theory of Borel equivalence relations (as surveyed in, e.g., [Reference Gao15, Reference Hjorth17]) is a central field of modern descriptive set theory and it shows deep connections with topology, group theory, combinatorics, model theory, and ergodic theory—to name a few.
Research on computable reducibility dates back to the work of Ershov [Reference Ershov11, Reference Ershov and Griffor12] and the theory of numberings. It concentrates on two main focuses: first, to calculate the complexity of natural equivalence relations on
$\omega $
, proving, e.g., that provable equivalence in Peano Arithmetic is
$\Sigma ^0_1$
-complete [Reference Bernardi and Sorbi9], Turing equivalence on c.e. sets is
$\Sigma ^0_4$
-complete [Reference Ianovski, Miller, Ng and Nies18], and the isomorphism relations on several familiar classes of computable structures (e.g., trees, torsion abelian groups, and fields of characteristic
$0$
or p) are
$\Sigma ^1_1$
-complete [Reference Fokina, Friedman, Harizanov, Knight, McCoy and Montalbán14]; secondly, to understand the structure of the collection of equivalence relations of a certain complexity
$\Gamma $
(e.g., lying at some level of the arithmetical [Reference Coskey, Hamkins and Miller10], analytical [Reference Bazhenov, Mustafa, San Mauro and Yamaleev8], or Ershov hierarchy [Reference Bazhenov, Mustafa, San Mauro, Sorbi and Yamaleev7, Reference Ng and Hongyuan21]).
Regarding the latter focus, computably enumerable equivalence relations—known by the acronym ceers [Reference Gao and Gerdes16], or called positive equivalence relations in the Russian literature—received special attention. Historically, the emphasis was on combinatorial classes of universal ceers, i.e., ceers to which all other ceers computably reduce (see, e.g., [Reference Andrews, Badaev and Sorbi1, Reference Andrews, Lempp, Miller, Ng, San Mauro and Sorbi2]). But recently, there has been a growing interest in pursuing a systematic study of Ceers, the poset of degrees of ceers, whose structure turns out to be extremely rich. Andrews, Schweber, and Sorbi [Reference Andrews, Schweber and Sorbi4] proved that the first-order theory of Ceers is as complicated as true arithmetic (see also [Reference Andrews and Sorbi5] for a structural analysis of Ceers focused on joins, meets, and definability).
In this paper, we focus rather on
$\operatorname {\mathrm {\mathbf {ER}}}$
, the poset of degrees of all equivalence relations with domain
$\omega $
. Our interest in
$\operatorname {\mathrm {\mathbf {ER}}}$
is twofold.
On the one hand, we want to explore to what extent techniques coming from the theory of ceers can be applied to equivalence relations of arbitrary complexity. Some proofs will move smoothly from
$\mathbf {Ceers}$
to
$\operatorname {\mathrm {\mathbf {ER}}}$
(proving that the underlying results are independent from the way in which the equivalence relations are presented), but the analogy between the two structures often breaks down (see, e.g., Theorem 3.8), or new ideas will be required to recast analogous results from the setting of ceers (see, e.g., Theorem 2.21).
On the other hand, we regard
$\operatorname {\mathrm {\mathbf {ER}}}$
as a natural structure, interesting and worth studying per se. After all,
$\operatorname {\mathrm {\mathbf {ER}}}$
is to
$\operatorname {\mathrm {\mathbf {Ceers}}}$
as, e.g., the global structure of all Turing degrees (
$\mathcal {D}_T$
) is to the local structure of c.e. degrees (
$\mathcal {R}_T$
)—and we consider it only a historical anomaly that, for equivalence relations, the local structure has been analyzed in great detail with no parallel investigation of the global structure.
We add a final piece of motivation. Dealing with a seemingly distant problem (i.e., Martin’s conjecture), Bard [Reference Bard6] recently proved that
$\mathcal {D}_T$
is Borel reducible to
$\operatorname {\mathrm {\mathbf {ER}}}$
. This may be regarded as evidence that
$\operatorname {\mathrm {\mathbf {ER}}}$
is complex. In this paper, we push this analysis further by fully characterizing the complexity of the theory of
$\operatorname {\mathrm {\mathbf {ER}}}$
(Theorem 4.1).
The rest of this paper is organized as follows. In the remainder of this section, we offer a number of preliminaries to make the paper self-contained. In Section 2, we focus on first-order definability of some natural fragments of
$\operatorname {\mathrm {\mathbf {ER}}}$
and analyze when least upper bounds exist. In Section 3, we study minimal and strongly minimal covers of equivalence relations, and we also introduce generic covers. Through this study, we exhibit many disanalogies between
$\operatorname {\mathrm {\mathbf {ER}}}$
and
$\operatorname {\mathrm {\mathbf {Ceers}}}$
. Finally, in Section 4, we show that the first-order theory of
$\mathbf {ER}$
(and in fact, that of two natural fragments of
$\mathbf {ER}$
) is as complex as possible, being computably isomorphic to second-order arithmetic.
Our computability theoretic terminology and notation is standard, and as in [Reference Soare24].
1.1 Preliminary material
Throughout this subsection we assume that R and S are equivalence relations. The R-equivalence class of a natural number x is denoted by
$[x]_R$
. For a set
$A\subseteq \omega $
, the R-saturation of A (i.e.,
$\bigcup _{x\in A}[x]_R$
) is denoted by
$[A]_R$
. We denote the collection of all R-equivalence classes by
$\omega _R$
. If f is a computable function witnessing that
$R\leqslant _c S$
, then we write
$f\colon R\leqslant _c S$
. If
$f\colon R \leqslant _c S$
, then
$f^\star $
is the injective mapping from
$\omega _R$
to
$\omega _S$
induced by f. In our proofs, it will sometimes be useful to consider the orbit of a number or of an equivalence class along all iterations of a given reduction: for
$x\in \omega $
and
$X\in \omega _R$
, denote by
$\operatorname {\mathrm {orb}}_f(x)$
the set
$\{f^{(i)}(x) : i>0 \}\subseteq \omega $
and by
$\operatorname {\mathrm {orb}}_f(X)$
the set
$\{{f^\star }^{(i)}(X) : i>0 \}\subseteq \omega _R$
. The following lemma, which is immediate to prove, will be used many times in the paper, often implicitly.
Lemma 1.1. Let
$f \colon R \leqslant _c S$
. For all
$X\in \omega _R$
,
$X \leqslant _m f^\star (X)$
so also
$X\leqslant _m S$
.
Definition 1.2. For any nonempty c.e. set W and equivalence relation R, we let
$R{\restriction} W$
be the equivalence relation given by
$x \mathrel {R{\restriction} W} y$
if and only if
$h(x)\mathrel {R} h(y)$
, where
$h\colon \omega \rightarrow W$
is any computable surjection (note that up to
$\equiv _c$
, the definition does not depend on the choice of surjection h).
Remark 1.3. For any nonempty c.e. set W and equivalence relation R, observe that h (as in the definition) gives a reduction of
$R{\restriction} W$
to R, which we call the inclusion map. Also, if
$f\colon X\leqslant _c Y$
, then
$X \equiv _c Y{\restriction} \operatorname {\mathrm {range }}(f)$
.
If
$f\colon R\leqslant _c S$
and
$\operatorname {\mathrm {range}}(f) \cap X \ \,/\!\!\kern-0.9pt\!\!\!= \varnothing $
for some
$X\in \omega _S$
, then we say that f hits X; otherwise, we say that f avoids X. We say that R is self-full if every reduction of R to itself hits all elements of
$\omega _R$
. The notion of self-fullness plays a prominent role in the theory of ceers (see, e.g., [Reference Andrews, Schweber and Sorbi3–Reference Andrews and Sorbi5]). To name just a couple of examples: the degrees of self-full ceers are definable in Ceers, as they coincide with the nonuniversal degrees which are meet-irreducible; moreover, the existence of self-full strong minimal covers is fundamental to prove that the first-order theory of the degrees of light ceers is computably isomorphic to true arithmetic.
By the notation
$f\oplus g$
, we denote the following function:
$$ \begin{align*} f\oplus g(x)=\begin{cases} f(x), &\text{if } x \text{ is even},\\ g(x), &\text{if } x \text{ is odd}. \end{cases} \end{align*} $$
The uniform join
Footnote
1
$R\oplus S$
is the equivalence relation that encodes R on the evens and S on the odds, i.e.,
$x\mathrel { R\oplus S} y$
if and only if either
$x=2u, y=2v$
, and
$u\mathrel {R}v$
; or
$x=2u+1$
,
$y=2v+1$
, and
$u\mathrel {S}v$
. For the sake of exposition, we often say R-classes (respectively, S-classes) for the equivalence classes of
$R\oplus S$
consisting of even (odd) numbers. The operation
$\oplus $
is clearly associative, up to
$\equiv _c$
, so we will generally be lax and write expressions such as
$R_0\oplus \cdots \oplus R_n$
.
The following easy lemma was stated for ceers in [Reference Andrews, Schweber and Sorbi4, Fact 2.3] but goes through for arbitrary equivalence relations with exactly the same proof.
Lemma 1.4. If
$X\leqslant _c R\oplus S$
, then there are
$R_0\leqslant _c R$
and
$S_0\leqslant _c S$
such that
$X\equiv _c R_0 \oplus S_0$
.
Proof Let
$f\colon X\leqslant _c R\oplus S$
and denote
$\operatorname {\mathrm {range}}(f)$
by W. Then
$$ \begin{align*} X\equiv_c R\oplus S {\restriction} W \equiv_c R{\restriction} V_1 \oplus S {\restriction} V_2, \end{align*} $$
where
$V_1:=\{x:2x\in W\}$
and
$V_2:=\{x: 2x+1\in W\}$
.
If
$A\subseteq \omega \times \omega $
, then
$R_{/A}$
is the equivalence relation generated by the set of pairs
$R\cup A$
. We say that
$R_{/A}$
is a quotient of R, and a quotient is proper if
$R_{/A}\neq R$
. To improve readability, we often omit braces, e.g., writing
$R_{(x,y)}$
instead of
$R_{\{(x,y)\}}$
. Of particular interest for this paper will be quotients of uniform joins. A quotient
${R\oplus S}_{/A}$
is pure if it does not collapse distinct R-classes, or distinct S-classes, i.e.,
$$ \begin{align*} {R\oplus S}_{/A} {\restriction} \mathrel{\text{Evens} } \, = {R\oplus S} {\restriction} \mathrel{\text{Evens}} \mbox{ and } {R\oplus S}_{/A} {\restriction} \mathrel{\text{Odds}}\, = {R\oplus S} {\restriction} \mathrel{\text{Odds}}. \end{align*} $$
The quotient
$R\oplus S_{/A}$
is a total quotient if every odd number is equivalent to an even number and vice versa.
Lemma 1.5. Every pure quotient of
$R\oplus S$
is an upper bound of R and S.
Proof Assume that
$R\oplus S_{/A}$
is pure. It is immediate to observe that R is computably reducible to
$R\oplus S/_{A}$
via the function
$x \mapsto 2x$
and S is computably reducible to
$R\oplus S/_{A}$
via the function
$x \mapsto 2x+1$
.
Lemma 1.6. Let
$R\oplus S_{/A}$
be a total quotient of
$R\oplus S$
. Suppose that
$f\colon X\leqslant _c R\oplus S_{/A}$
and
$\operatorname {\mathrm {range }}(f)\cap \text {Odds}$
is finite. Then
$X\leqslant _c R$
.
Proof For each
$x\in \operatorname {\mathrm {range }}(f)\cap \text {Odds}$
, fix an even number
$x'$
so that
$x\mathrel {R\oplus S_{/A}} x'$
. Let
$$ \begin{align*} h(x) = \begin{cases} f(x), &\text{if } f(x) \text{ is even},\\ f(x)', &\text{if } f(x) \text{ is odd},\\ \end{cases} \end{align*} $$
and observe that h is a reduction of X to
$R\oplus S_{/A}$
with range contained in the evens, so
$x\mapsto \frac {h(x)}{2}$
is a reduction of X to R.
Let us now fix notation for some natural families of equivalence relations of natural numbers. They will serve as benchmark relations for our structural analysis of
$\operatorname {\mathrm {\mathbf {ER}}}$
. Some terminology naturally generalizes from the theory of ceers (see, e.g., [Reference Andrews and Sorbi5]).
-
• Define
$\operatorname {\mathrm {Id}}_n$
by
$x\mathrel {\operatorname {\mathrm {Id}}_n} y$
if
$x\equiv y \mod n$
. Define
$\operatorname {\mathrm {Id}}=\operatorname {\mathrm {Id}}_\omega $
by
$x\operatorname {\mathrm {Id}} y$
if
$x=y$
. For convenience in inductive arguments, we also consider
$\operatorname {\mathrm {Id}}_0$
to be the empty relation. We define
$\mathcal {I}$
to be the family of equivalence relations that are equivalent to some
$\operatorname {\mathrm {Id}}_n$
for
$1\leqslant n\in \omega $
. -
• An equivalence relation R is finite, if R has finitely many equivalence classesFootnote 2 . Otherwise R is infinite.
$\mathcal {F}$
and
$\mathcal {F}_n$
denote respectively the family of all finite equivalence relations and the family of equivalence relations with exactly n equivalence classes. Observe that each element of
$\mathcal {F}_2$
naturally encodes a set and its complement:
$E(X)\in \mathcal {F}_2$
denotes the equivalence relation consisting of exactly two classes, X and
$\overline {X}$
. -
• An equivalence relation R is light if
$\operatorname {\mathrm {Id}}\leqslant _c R$
. It is easy to see that the light equivalence relations are exactly the infinite equivalence relations which have a computable transversal, i.e., a computable sequence
$\lbrace x_i \rbrace _{i\in \omega }$
of pairwise nonequivalent numbers; -
• An equivalence relation R is dark if R is infinite and
$\operatorname {\mathrm {Id}}\not \leqslant _c R$
. -
• For each of these families, the boldface version represents the collection of
$\operatorname {\mathrm {\mathbf {ER}}}$
-degrees containing members of the class. For example,
$\boldsymbol {\mathcal {F}}$
is the set of degrees of finite equivalence relations,
$\operatorname {\mathrm {\mathbf {Dark}}}$
is the set of degrees of dark equivalence relations, etc.
As is clear from the above,
$\operatorname {\mathrm {\mathbf {ER}}}$
is partitioned into
$\boldsymbol {\mathcal {F}}$
,
$\operatorname {\mathrm {\mathbf {Light}}}$
, and
$\operatorname {\mathrm {\mathbf {Dark}}}$
. Moreover,
$\boldsymbol {\mathcal {I}}\subseteq \boldsymbol {\mathcal {F}}$
. Inside
$\operatorname {\mathrm {\mathbf {ER}}}$
, computable equivalence relations can be readily characterized.
Observation 1.7 [Reference Gao and Gerdes16, Propositions 3.3 and 3.4]
The degrees of computable equivalence relations form an initial segment of
$\mathbf {ER}$
of order type
$\omega +1$
, and are exactly
$\boldsymbol {\mathcal {I}}\cup \{\operatorname {\mathrm {\mathbf {Id}}}\}$
.
Proof First, note that
$$ \begin{align*} \operatorname{\mathrm{Id}}_1 < \cdots <\operatorname{\mathrm{Id}}_n < \operatorname{\mathrm{Id}}_{n+1} < \cdots < \operatorname{\mathrm{Id}}. \end{align*} $$
So, the family
$\mathcal {I}\cup \lbrace {\operatorname {\mathrm {Id}}} \rbrace $
of equivalence relations has order type
$\omega +1$
.
Let R be a computable equivalence relation. Then the set
$$ \begin{align*} S:=\{x : \min [x]_R=x\} \end{align*} $$
is computable. Let
$S=\{c_0<c_1<c_2<\cdots \}$
. Then the function which sends each
$[c_i]_R$
to i is a computable function giving a reduction of R to
$\operatorname {\mathrm {Id}}_{\lvert \omega _R\rvert }$
(letting
$\operatorname {\mathrm {Id}}_\omega =\operatorname {\mathrm {Id}}$
). Further, this function is onto the classes of
$\operatorname {\mathrm {Id}}_{\lvert \omega _R\rvert }$
and the inverse function on classes is also computable, so
$R\equiv _c \operatorname {\mathrm {Id}}_{\lvert \omega _R\rvert }$
.
The following is an easy, but useful fact about taking a uniform join with
$\operatorname {\mathrm {Id}}_1$
, and how it essentially “cancels out” collapsing a computable class with another class.
Lemma 1.8. If E is an equivalence relation with a computable class C, and B is any other E-class, then
$E_{/(\min C, \min B)}\oplus \operatorname {\mathrm {Id}}_1 \equiv _c E$
.
Proof To show
$E_{/(\min C, \min B)}\oplus \operatorname {\mathrm {Id}}_1 \leqslant _c E$
, let
$f\colon E_{/(\min C, \min B)}\leqslant _c E$
be defined by sending every element of C to
$\min B$
and be the identity on
$\overline C$
. Then notice that the class of C is avoided by f. This lets us extend f to a reduction of
$E_{/(\min C, \min B)}\oplus \operatorname {\mathrm {Id}}_1 \leqslant _c E$
by sending the
$\operatorname {\mathrm {Id}}_1$
-class to the class C in E. The function
$g(x)=2x$
for every
$x\notin C$
and
$g(x)=1$
for
$x\in C$
gives a reduction
$g:E\leqslant _c E_{/(\min C, \min B)}\oplus \operatorname {\mathrm {Id}}_1$
.
Note that
$\operatorname {\mathrm {\mathbf {Ceers}}}$
,
$\boldsymbol {\mathcal {F}}$
, and
$\bigcup _{i\leqslant n} \boldsymbol {\mathcal {F}}_i$
for each n are each initial segments of
$\mathbf {ER}$
. An obvious elementary difference between
$\operatorname {\mathrm {\mathbf {Ceers}}}$
and
$\operatorname {\mathrm {\mathbf {ER}}}$
is that the former degree structure is bounded and the latter is not.
Observation 1.9.
$\operatorname {\mathrm {\mathbf {ER}}}$
has a least element, but no maximal element.
Proof Every constant function computably reduces
$\operatorname {\mathrm {Id}}_1$
to any given equivalence relation. Hence,
$\operatorname {\mathrm {\mathbf {Id}}}_1$
is the least degree of
$\operatorname {\mathrm {\mathbf {ER}}}$
. On the other hand, for a given R, let X be
$\deg _T(R)$
and consider
$E(X')$
. We have that
$E(X')\nleqslant _c R$
, as otherwise
$X'$
would be
$\leqslant _m R$
by Lemma 1.1, but R is strictly Turing below
$X'$
. So,
$R<_c R\oplus E(X')$
and R is not maximal.
We now turn to some facts about dark equivalence relations. The next two lemmas are adapted from the setting of ceers [Reference Andrews and Sorbi5, Lemmas 4.6 and 4.7]. The proof is essentially the same.
Lemma 1.10. Dark equivalence relations are self-full.
Proof Let R be dark. Suppose that there is
$f\colon R \leqslant _c R$
which avoids a given
$X\in \omega _R$
. Let
$x \in X$
and consider
$\operatorname {\mathrm {orb}}_f(x)$
. From the fact that f is a self-reduction of R and
$X\notin \operatorname {\mathrm {range}}(f^\star )$
, it follows that
$\operatorname {\mathrm {orb}}_f(x)$
is a c.e. infinite transversal of R, contradicting the darkness of R.
Lemma 1.11. If R is dark, then R is not reducible to any of its proper quotients.
Proof Towards a contradiction, suppose that a dark R is reducible to one of its proper quotients
$R_{/A}$
, via some f. Note that, since R is dark,
$R_{/A}$
must be infinite. Now, let
$X,Y \in \omega _R$
be two equivalence classes that are collapsed in
$R_{/A}$
and choose
$x\in X$
and
$y\in Y$
. We claim that at least one of
$\operatorname {\mathrm {orb}}_f{(x)}$
or
$\operatorname {\mathrm {orb}}_f{(y)}$
cannot intersect
$X\cup Y$
. Indeed, suppose that
$i,j>0$
are minimal so that
$\lbrace f^{(i)}(x), f^{(j)}(y) \rbrace \subseteq X\cup Y$
, and, without loss of generality, suppose
$i\geq j$
. Since X and Y are collapsed in
$R_{/A}$
, we have that
$f^{(i)}(x)\mathrel {R_{/A}}f^{j}(y)$
. But since
$f\colon R\leqslant _c R_{/A}$
and
$R_{/A}\supseteq R$
, this would imply that
$f^{(i-j)}(x)\mathrel {R}y$
, which either contradicts
, if
$i=j$
, or contradicts the minimality of i, if
$i>j$
.
So, one can assume that
$\operatorname {\mathrm {orb}}_f(x)\cap (X\cup Y)=\varnothing $
. Now suppose that, for
$i> j$
,
$f^{(i)}(x)\mathrel {R} f^{(j)}(x)$
. Reasoning as above, we obtain that
$f^{(i-j)}(x)\mathrel {R} x$
, a contradiction. Hence,
$\operatorname {\mathrm {orb}}_f(x)$
would be a c.e. transversal of R. But this contradicts the darkness of R.
We now introduce the dark minimal equivalence relations.
Definition 1.12. An equivalence relation R is dark minimal if it is dark and its degree is minimal over
$\boldsymbol {\mathcal {F}}$
, i.e., if
$S<_c R$
then S is finite.
Dark minimal equivalence relations exist (see [Reference Andrews and Sorbi5, Theorem 4.10] for examples of dark minimal ceers) and they will occur several times in this paper, as their combinatorial properties will facilitate our study of the logical complexity of
$\operatorname {\mathrm {\mathbf {ER}}}$
. We conclude the preliminaries highlighting a couple of fundamental features of dark minimal equivalence relations.
Lemma 1.13. Let R be a dark minimal equivalence relation. Let W be a c.e. set which intersects infinitely many R-classes. Then W must intersect every R-class.
Proof Suppose W intersects infinitely many R-classes. Consider the equivalence relation
$R{\restriction} W$
and note that
$R{\restriction} W\equiv _c R$
since
$R{\restriction} W$
is not in
$\mathcal {F}$
and R is minimal over
$\mathcal {F}$
. Thus, we have reductions
$R\leqslant R{\restriction} W\leqslant R$
with the second reduction given by inclusion. Since R is dark, it is self-full by Lemma 1.10, so the reduction of R to itself through
$R{\restriction} W$
must hit every R-class. In particular, W must intersect every R class.
For the next lemma, recall that two sets of natural numbers
$A,B$
are computably separable if there is a computable set C such that
$A \subseteq C$
and
$C \cap B=\varnothing $
.
Lemma 1.14. Let R be a dark minimal equivalence relation. Then the elements of
$\omega _R$
are pairwise computably inseparable.
Proof Let C be any computable set. Either C or
$\omega \smallsetminus C$
intersects infinitely many R-classes. Thus by Lemma 1.13, either C or
$\omega \smallsetminus C$
intersects every R-class, so C cannot separate two R-classes.
2 Definability in
$\operatorname {\mathrm {\mathbf {ER}}}$
and existence of least upper bounds
A natural way of understanding the logical complexity of a structure is by exploring which of its fragments are definable. In this section, we show that many natural families of equivalence relations are first-order definable without parameters.
2.1 Defining the class of finite equivalence relations
In the case of ceers, the equivalence relations with finitely many equivalence classes are easily characterized: A ceer R has n equivalence classes if and only if
$R \equiv _c \operatorname {\mathrm {Id}}_n$
. Hence in
$\operatorname {\mathrm {\mathbf {Ceers}}}$
,
$\boldsymbol {\mathcal {F}}$
coincides with
$\boldsymbol {\mathcal {I}}$
(and therefore it has order type
$\omega $
). These form an initial segment of
$\operatorname {\mathrm {\mathbf {Ceers}}}$
and they are definable as the collection of nonuniversal ceers which are comparable to every ceer.
In
$\mathbf {ER}$
, the picture is much more delicate. For the moment, just observe that
$\mathcal {F}\not \subseteq \mathcal {I}$
: to see this, take
$E(X)$
with X noncomputable. Moreover, while
$\operatorname {\mathrm {Id}}$
bounds
$\mathcal {I}$
, no equivalence relation can bound
$\mathcal {F}$
(see the proof of Observation 1.9).
We will show that
$\boldsymbol {\mathcal {I}}$
is definable in
$\operatorname {\mathrm {\mathbf {ER}}}$
as the collection of degrees which have a least upper bound with any other degree, and from that definition will easily follow that
$\boldsymbol {\mathcal {F}}$
is also definable. To obtain this result, throughout this section we will focus on the existence of least upper bounds of equivalence relations, obtaining several structural results of independent interest.
The following lemma describes the shape of a potential least upper bound of equivalence relations. An upper bound T of equivalence relations
$R,S$
is minimal if there is no upper bound V of
$R,S$
such that
$V <_c T$
.
Lemma 2.1. Suppose
$f\colon R\leqslant _c T$
and
$g\colon S\leqslant _c T$
. Then there is a pure quotient U of
$R\oplus S$
and reductions
$f_0\colon R\leqslant _c U$
given by
$f_0(x)=2x$
and
$g_0\colon S\leqslant _c U$
given by
$g_0(x)=2x+1$
and
$h\colon U\leqslant _c T$
so that
$f=h\circ f_0$
and
$g=h\circ g_0$
.
In particular, if T is a minimal upper bound of equivalence relations R and S, then T is equivalent to a pure quotient of
$R\oplus S$
.
Proof Let
$f\colon R\leqslant _c T$
,
$g\colon S\leqslant _c T$
, and
$A:=\lbrace (2x,2y+1): f(x) \mathrel {T} g(y) \rbrace $
. Then
$R\oplus S_{/ A}$
is a pure quotient of
$R\oplus S$
. Now, observe that
$R\oplus S_{/ A}\leqslant _c T$
via the function
$h = f\oplus g$
. And observe that
$f = h\circ (x\mapsto 2x)$
and
$g= h\circ (x\mapsto 2x+1)$
.
In
$\operatorname {\mathrm {\mathbf {ER}}}$
, to have a least upper bound is a rather strong property. The next result will state that any pair of equivalence relations which are sufficiently incomparable cannot have a least upper bound.
Definition 2.2. Define
$R\leqslant _F S$
, if there is computable set A so that
$R{\restriction} A\leqslant _c S$
and
$R{\restriction} \overline {A}$
is finite.
Obviously,
$\leqslant _c$
-reducibility implies
$\leqslant _F$
-reducibility. The converse does not hold as there are
$\leqslant _c$
-incomparable
$X,Y\in \mathcal {F}$
, but
$X\equiv _F Y$
.
Theorem 2.3. If R and S are equivalence relations which are
$\leqslant _F$
-incomparable, then R and S do not have a least upper bound in
$\operatorname {\mathrm {\mathbf {ER}}}$
.
Proof. Suppose towards a contradiction that T is the least upper bound for R and S. By Lemma 2.1, we can assume that T is a pure quotient of
$R\oplus S$
. We will build by stages another pure quotient
$V (=\bigcup V_s)$
of
$R\oplus S$
such that
$T \nleqslant V$
, contradicting the supposition. To do so, we let
$V_0$
be
$R \oplus S$
and, at further stages, we will collapse R-classes and S-classes in V to diagonalize against all potential reductions from T to V. We note that we are constructing V to be c.e. in the Turing degree
$\deg _T(R)\vee \deg _T(S)\vee \deg _T(T)\vee \mathbf {0}''$
.
2.1.1 The construction
At stage s, we may restrain some
$V_s$
-classes so that, at the end of the construction, they will be V-classes. When we say that numbers are restrained, we mean that they come from restrained classes.
2.1.2 Stage
$0$
Let
$V_0:= R\oplus S$
. Do not restrain any equivalence class.
2.1.3 Stage
$e+1$
If
$\varphi _e$
is nontotal, let
$V_{e+1}:=V_e$
. Otherwise, search for a pair of distinct numbers
$(u,v)$
such that
$\varphi _e(u)\downarrow =x_e, \varphi _e(v)\downarrow =y_e$
, and
-
(a) either
, -
(b) or
and
$x_e$
and
$y_e$
have different parity and they are both unrestrained.
We will show in Claim 2.4 that such a pair will always be found. If the outcome is
$(a)$
, let
$V_{e+1}:=V_e$
and restrain the
$V_e$
-classes of
$x_e$
and
$y_e$
. If the outcome is
$(b)$
, let
$V_{e+1}:={V_e}_{/(x_e,y_e)}$
and we restrain the common
$V_{e+1}$
-class of
$x_e$
and
$y_e$
.
2.1.4 The verification
The verification relies on the following claim.
Claim 2.4. The action defined at stage
$e+1$
(i.e., the search of a pair of numbers satisfying either
$(a)$
or
$(b)$
) always terminates.
Proof Suppose that there is a stage
$e+1$
at which no pair
$(u,v)$
is found. This means that
$\varphi _e$
is total and
$\varphi _e\colon T\leqslant _c V_e$
; otherwise, we would reach outcome
$(a)$
. Next, observe that
$\varphi _e$
cannot hit infinitely many equivalence classes of both
$V_e {\restriction} \text {Evens}$
and
$V_e {\restriction} \text {Odds}$
; otherwise, since only finitely many equivalence classes are restrained at each stage and
$V_e$
coincides with
$R\oplus S_{/A}$
for a finite set A, there would be a pair of numbers of different parity which are unrestrained and we would reach outcome
$(b)$
.
So, without loss of generality, assume that
$\varphi _e$
hits only finitely many classes in
$V_e {\restriction} \text {Odds}$
. Let f be the following partial computable function:
$$ \begin{align*} f(x)= \begin{cases} \dfrac{\varphi_e(x)}{2}, &\varphi_e(x) \text{ is even,}\\ \uparrow, &\text{otherwise.} \end{cases} \end{align*} $$
We have that
$f\colon T {\restriction} \mathrm {{dom}}(f) \leqslant _c R$
and
$T {\restriction} \overline {\mathrm {{dom}}(f)}$
is finite. Thus,
$T \leqslant _F R$
. Since
$S\leqslant _c T$
and
$T \leqslant _F R$
, we obtain that
$S \leqslant _F R$
, which contradicts the fact that R and S are
$\leqslant _F$
-incomparable.
It follows from the above construction that V is a pure quotient of
$R\oplus S$
. In particular, every time we collapse an odd with an even class, we restrain all members of that class, so it cannot be part of any future collapse. Hence, by Lemma 1.5, V is an upper bound of R and S. Towards a contradiction, assume that
$T \leqslant _c V$
via some
$\varphi _i$
. Claim 2.4 ensures that the action defined at stage
$i+1$
terminates with either disproving that
$\varphi _i$
is a reduction from T to
$V_i$
or by providing two equivalence classes that will be V-collapsed to diagonalize against
$\varphi _i$
. That is, the restraints and the fact that V is a quotient of
$V_i$
guarantee that
$\varphi _i \colon T \not \leqslant _c V$
, a contradiction.
Corollary 2.5. No dark equivalence relation has a least upper bound with
$\operatorname {\mathrm {Id}}$
.
Proof It suffices to show that no dark equivalence relation R can be F-comparable with
$\operatorname {\mathrm {Id}}$
. On the one hand, note that
$\operatorname {\mathrm {Id}}{\restriction} A\equiv \operatorname {\mathrm {Id}}$
for any cofinite A and thus
$\operatorname {\mathrm {Id}}{\restriction} A \not \leqslant _c R$
since R is dark. Therefore
$\operatorname {\mathrm {Id}} \nleqslant _F R$
. On the other hand, suppose
$R{\restriction} A\leqslant _c \operatorname {\mathrm {Id}}$
with
$R{\restriction} \overline {A}$
finite. Observe that
$R{\restriction} A \not \equiv _c \operatorname {\mathrm {Id}}$
, as otherwise R would be light because
$\operatorname {\mathrm {Id}}\leqslant _c R {\restriction} A\leqslant _c R$
. So,
$R{\restriction} A<_c\operatorname {\mathrm {Id}}$
and, by Observation 1.7, this means that
$R{\restriction} A$
is finite. As
$R{\restriction} \overline {A}$
is also finite, it follows that R is finite, contradicting its darkness.
Obviously, if
$R\in \mathcal {F}$
, then R is F-reducible to any given equivalence relation S. This property does not guarantee that R has a least upper bound with every other equivalence relation (see Theorem 2.20). The next lemma says that the finite equivalence relations are the only ones which are F-comparable with any other equivalence relation.
Lemma 2.6. If R is infinite, then there is an infinite S so that R and S are
$\leqslant _F$
-incomparable.
Proof If R is dark, let S be
$\operatorname {\mathrm {Id}}$
and use Corollary 2.5. If R is light, then let S be any dark equivalence relation such that
$\{Y\in \omega _S : Y\nleqslant _m R \}$
is infinite. We will show that such S exists after verifying its
$\leqslant _F$
-incomparability with R.
Note that if
$R{\restriction} \overline {A}$
is finite, then
$R{\restriction} A$
must be light, because R is light. It follows that
$R\not \leqslant _F S$
. Next, let A be so that
$S{\restriction} \overline {A}$
is finite. There exists
$[y]_S\subseteq A$
which is not
$\leqslant _m R$
. But, by Lemma 1.1 this shows that
$S{\restriction} A\not \leqslant _c R$
.
To see that such an S exists, we begin with any dark ceer
$S_0$
and we partition
$\omega _{S_0}$
into infinitely many infinite families
$\mathcal {M}_i$
. Next, define
$$ \begin{align*} \mathcal{N}_i:=\left\{ \bigcup_{I \in \mathcal{J}} I: \mbox{ for } \mathcal{J}\subseteq \mathcal{M}_i \right\}. \end{align*} $$
Each
$\mathcal {N}_i$
is obviously uncountable and so it contains a set
$X_i$
whose m-degree does not reduce to the degree of R. Let S be a quotient of
$S_0$
such that
$X_i\in \omega _S$
, for all i. Since a quotient of a dark equivalence relation is dark, this S satisfies our requirements.
Combining the last lemma with Theorem 2.3, we immediately obtain the following.
Corollary 2.7. If R is infinite, then there is an infinite S so that R fails to have a least upper bound with S.
It might seem at this point that any pair of degrees ought to not have a least upper bound, but we now show that there are pairs of infinite degrees which have a least upper bound.
Theorem 2.8. There are incomparable equivalence relations
$R,S\notin \mathcal {F}$
which have a least upper bound.
Proof Let
$R_0$
be a dark equivalence relation with all computable classes (the existence of such equivalence relation follows from, e.g., [Reference Gao and Gerdes16, Proposition 5.6]) and let
$S_0\in \mathcal {F}\smallsetminus \mathcal {I}$
. Let
$R:=R_0\oplus \operatorname {\mathrm {Id}}$
and
$S:=S_0\oplus \operatorname {\mathrm {Id}}$
. First, we note that R and S are incomparable. Indeed, on the one hand, there must be a noncomputable S-class, since
$S_0\notin \mathcal {I}$
. By Lemma 1.1, this suffices to guarantee that
$S\not \leqslant _c R$
, as all R-classes are computable. On the other hand, suppose that
$i: R \leqslant _c S$
. Then, the following c.e. set
$$ \begin{align*} \{x : i(2x) \in \text{Odds} \mbox{ and, for all } y<x, i(2x)\ \,/\!\!\kern-0.9pt\!\!\!= i(2y)\} \end{align*} $$
would be an infinite transversal of
$R_0$
, contradicting its darkness.
Next, we will prove that
$R\oplus S\equiv _c R_0\oplus S_0\oplus \operatorname {\mathrm {Id}}$
is a least upper bound of R and S. Let U be any equivalence relation with reductions
$f_0\colon R\leqslant _c U$
and
$g\colon S\leqslant _c U$
. We claim that there is
$f_1 : R\leqslant _c U$
whose image is disjoint from the image of the
$S_0$
-classes given by g. To prove this, define the following collection of equivalence classes of R:
$$ \begin{align*} \mathcal{C}:=\{X\in\omega_R : {f_0^\star}(X)\cap \operatorname{\mathrm{range}}(g{\restriction}\text{Evens}) \neq\varnothing\}. \end{align*} $$
Let
$\mathcal {C}$
be
$\{C_0,\ldots ,C_k\}$
(
$\mathcal {C}$
is finite since
$S_0\in \mathcal {F}$
). Moreover, note that all elements of
$\mathcal {C}$
are computable. Let
$m=\max (\{\min (C_i): i\leqslant k\})$
.
The following function is constructed from
$f_0$
by suitably shifting the elements in
$\operatorname {\mathrm {Id}}$
to avoid the finite overlap with
$g{\restriction} \text {Evens}$
:
$$ \begin{align*} f_1(x):=\begin{cases} f_0(2(u+k+m)+1), &(\exists u)(x=2u+1),\\ f_0(2(i+m)+1), &(\exists i\leqslant k)(x\in C_i), \\ f_0(x), &\text{otherwise}.\\ \end{cases} \end{align*} $$
It is straightforward to check that
$f_1$
is a computable reduction from R to U which satisfies the property that
$\operatorname {\mathrm {range}}(f_1)\cap \operatorname {\mathrm {range}}(g{\restriction} \text {Evens})$
is empty. It is exactly this property which allows to combine g and
$f_1$
in a natural way so as to obtain the desired reduction from
$R_0\oplus S_0\oplus \operatorname {\mathrm {Id}}$
to U:
$$ \begin{align*} h(x):=\begin{cases} f_1(2u), &(\exists u)(x=3u),\\ g(2u), &(\exists u)(x=3u+1), \\ f_1(2u+1), &(\exists u)(x=3u+2).\\ \end{cases} \end{align*} $$
This concludes the proof.
We are now in position to show that
$\boldsymbol {\mathcal {I}}$
is definable.
Theorem 2.9.
$\boldsymbol {\mathcal {I}}$
is definable in
$\operatorname {\mathrm {\mathbf {ER}}}$
as the collection of degrees which have least upper bounds with every other degree.
Proof We first verify that every member of
$\mathcal {I}$
has a least upper bound with every other equivalence relation.
Lemma 2.10. If
$E\in \mathcal {I}$
, then E has a least upper bound with any equivalence relation R.
Proof Let
$E=\operatorname {\mathrm {Id}}_k$
. If R has at least k classes, then R is the least upper bound of
$\operatorname {\mathrm {Id}}_k$
and R, as
$\operatorname {\mathrm {Id}}_k\leqslant _c R$
. Otherwise, let
$n<k$
be
$|\omega _R|$
. We prove that
$R\oplus \operatorname {\mathrm {Id}}_{k-n}$
is the least upper bound of
$\operatorname {\mathrm {Id}}_k$
and R. First, it is immediate that both R and
$ \operatorname {\mathrm {Id}}_k$
reduce to
$R\oplus \operatorname {\mathrm {Id}}_{k-n}$
. Next, suppose that R and
$\operatorname {\mathrm {Id}}_k$
are reducible to some S and let
$f\colon R\leqslant _c S$
. Then, f can only hit n equivalence classes of S, but
$|\omega _S|\geq k$
because
$\operatorname {\mathrm {Id}}_k \leqslant _c S$
. Let
$A=\lbrace a_1,\ldots , a_{k-n} \rbrace $
be a set of representatives from
$k-n$
equivalence classes which f avoids. By letting g agree with f on elements from R and send the classes of
$\operatorname {\mathrm {Id}}_{k-n}$
to the numbers in A, we get a reduction
$g\colon R\oplus \operatorname {\mathrm {Id}}_{k-n} \leqslant _c S$
.
Corollary 2.7 guarantees that no infinite equivalence relation can have a least upper bound with every other equivalence relation. So, to prove the theorem, it suffices to show that the same is true for any finite equivalence relation which is noncomputable.
We note that the following lemma also follows from Theorem 2.20, but we include a proof here for self-containment of this section.
Lemma 2.11. If
$R\in \mathcal {F}\setminus \mathcal {I}$
, then there is
$S\in \mathcal {F}\setminus \mathcal {I}$
so that R and S do not have a least upper bound.
Proof Let
$|\omega _R|=k$
, and since
$R\notin \mathcal {I}$
, fix C to be a noncomputable R-class. Let
$\omega = X_1\cup \cdots \cup X_k$
be a partition of
$\omega $
so that each
$X_i$
is m-incomparable with all noncomputable
$Y\in \omega _R$
. Next, let S be the equivalence relation with classes
$X_i$
for
$i\leqslant k$
. Towards a contradiction, suppose that T is a least upper bound of R and S. We may assume that T is a pure quotient
$R\oplus S_{/A}$
by Lemma 2.1.
First, observe that T has exactly k classes: if there were fewer, then
$R\nleqslant _c T$
; if there were more, then we can take Z to be a pure quotient of
$R \oplus S$
which has exactly k classes and we would have
$T\not \leqslant _c Z$
. Thus C is collapsed via A with some class
$X_i$
in T.
Now, let
$f\colon T\leqslant _c R\oplus S$
, and consider the image of C in the composed reduction
$R\leqslant _c R\oplus S_{/A}\leqslant _c R\oplus S$
. Since
$C\not \leqslant _m X_j$
for any
$j\leqslant k$
, the image must be contained in the evens. Similarly, consider the image of
$X_i$
under the composed reduction
$S\leqslant _c R\oplus S_{/A}\leqslant _c R\oplus S$
. Since
$X_i\not \leqslant _m K$
for any
$K\in \omega _R$
, the image must be contained in the odds. But C and
$X_i$
are A-collapsed in T, which contradicts f being a reduction.
This completes the proof of Theorem 2.9.
The next corollary immediately follows from the definability of
$\boldsymbol {\mathcal {I}}$
.
Corollary 2.12. For all k,
-
•
$\operatorname {\mathrm {\mathbf {Id}}}_k$
is definable as the unique degree in
$\boldsymbol {\mathcal {I}}$
which has exactly
$k-1$
predecessors; -
•
$\boldsymbol {\mathcal {F}}_k$
is definable in
$\operatorname {\mathrm {\mathbf {ER}}}$
as the degrees which bound
$\operatorname {\mathrm {\mathbf {Id}}}_k$
and not
$\operatorname {\mathrm {\mathbf {Id}}}_{k+1}$
; -
•
$\boldsymbol {\mathcal {F}}$
is definable in
$\operatorname {\mathrm {\mathbf {ER}}}$
as the degrees which do not bound every member of
$\boldsymbol {\mathcal {I}}$
.
2.2 Defining the identity
In this section, we give a combinatorial characterization for the degrees which have least upper bounds with every member of
$\boldsymbol {\mathcal {F}}$
. We will then use this analysis to give a definition of the degree
$\operatorname {\mathrm {\mathbf {Id}}}$
(and thus
$\operatorname {\mathrm {\mathbf {Light}}}$
and
$\operatorname {\mathrm {\mathbf {Dark}}}$
) in
$\operatorname {\mathrm {\mathbf {ER}}}$
as a combination of its minimality over
$\boldsymbol {\mathcal {F}}$
along with the property of having least upper bounds with every degree in
$\boldsymbol {\mathcal {F}}$
.
We will need the following combinatorial lemma:
Lemma 2.13. Let R be an equivalence relation with a uniformly computable sequence
$(C_i)_{i\in \omega }$
of distinct computable R-classes. Let
$S\subset \omega $
be a finite set. Then there is a reduction of R to itself which avoids every
$C_i$
for
$i\in S$
.
Proof. We construct the reduction
$f\colon R\leqslant _c R$
in stages. At every stage s, we will construct a partial function
$f_s$
and a parameter
$X_s$
, which will be a finite subset of
$\omega $
. At stage
$s+1$
, we will ensure
$f_{s+1}(s)$
is defined.
Stage
$0$
Let
$f_0=\varnothing $
and
$X_0=S$
.
Stage
$s+1$
We distinguish three cases.
-
(1) If
$s\notin \bigcup _{n\in X_s} C_n$
, let
$f_{s+1}:=f_s\cup \{(s,s)\}$
and let
$X_{s+1}:=X_s$
. -
(2)
$s\in C_n$
for some
$n\in X_s$
and there is some
$k<s$
in
$C_n$
. Then let
$f_{s+1}:= f_s\cup \{(s,f(k))\}$
and
$X_{s+1}:=X_s$
. -
(3)
$s\in C_n$
for
$n\in X_s$
and s is
$\min (C_n)$
. Then let m be least so that
$m\notin X_s$
and
$\operatorname {\mathrm {range }} f_s\cap C_m=\varnothing $
. Let
$f_{s+1}:=f_s\cup \{(s,\min C_m)\}$
and let
$X_{s+1}:=X_s\cup m$
.
We argue by induction that every
$f_s$
is a partial reduction of R to itself and no member of
$C_n$
, for
$n\in S$
, is in the range of
$f_s$
. For each s, let
$Y_s=\bigcup _{i\in X_s}C_i$
. We note that
$f_s$
is the identity on
$\overline {Y_s}$
and
$\operatorname {\mathrm {range }}(f_s{\restriction} Y_s)\subseteq Y_s$
, so we only need to show that
$a\mathrel {R} b \leftrightarrow f_s(a)\mathrel {R} f_s(b)$
for
$a,b\in Y_s$
and that no element of
$Y_s$
is sent into a class
$C_n$
for
$n\in S$
. Note that when a number n first enters
$X_k$
for
$k<s$
, then
$C_n$
is neither in the domain nor range of
$f_{k-1}$
. Thus, for every
$n\in X_s$
, case
$(2)$
ensures that each class is sent via f to the same location. That is,
$a \mathrel {R} b\rightarrow f(a)\mathrel {R} f(b)$
for
$a,b\in Y_s$
. In case
$(3)$
, we define f for an element of a class
$C_i$
with
$i\in X_s$
, and note that we send it to a class which is not in the range of
$f_s$
. Thus, if
then
for
$a,b\in Y_s$
. Similarly, note that in case
$(3)$
, we only send these new classes to classes
$C_m$
for m outside of
$X_s$
. In particular,
$m\notin X_0$
, so we never put
$C_m$
for
$m\in S$
into the range of
$f_s$
.
The next lemma identifies a natural way in which a uniformly computable sequence of computable classes may arise.
Lemma 2.14. Let
$f\colon R\leqslant _c R$
and let
$C\in \omega _R$
be a computable R-class. Suppose that
$f^\star (C)$
is not a computable R-class. Then either there is some
$i\in \omega $
so that
$f^{(i)}$
avoids C or there is a uniformly computable sequence of distinct computable R-classes
$(C_i)_{i\in \omega }$
.
Proof Suppose that there is no
$i\in \omega $
so that
$f^{(i)}$
avoids C, and let
$C_i=\{x:f^{(i)}(x)\in C\}$
. It is immediate that this is a uniformly computable sequence of computable classes. We need only verify that they are distinct. Suppose that
$C_i=C_j$
with
$i<j$
. Further, suppose that i is minimal for such an example. Then
$i=0$
, as otherwise, we would have
$C_{i-1}=C_{j-1}$
since f is a reduction of R to R. Thus we have some
$C_{j}=C_0=C$
. But then
$f^\star (C)=f^\star (C_j)=C_{j-1}$
is computable, contrary to hypothesis.
Putting the previous two lemmas together, we get a general result about avoiding classes.
Corollary 2.15. If
$f\colon R\leqslant _c R$
and
$C\in \omega _R$
is a computable R-class so that
$f^\star (C)$
is a noncomputable R-class D, then there is some reduction
$g\colon R\leqslant _c R$
so that g avoids C. Thus also
$f\circ g$
avoids D.
Proof We have two cases from Lemma 2.14. The first possibility is that
$g=f^{(i)}$
avoids C for some i. The second possibility is that there is a uniformly computable sequence of distinct computable R-classes
$(C_i)_{i\in \omega }$
. Then we can apply Lemma 2.13 to give a reduction g which avoids C. Then
$f\circ g$
avoids D.
We now present the combinatorial condition which we will show is equivalent to having a least upper bound with every member of
$\mathcal {F}$
.
Definition 2.16. An equivalence relation R is noncomputably avoiding if, for every finite collection
$\mathcal {C}$
of noncomputable equivalence classes of R, there is a reduction
$f\colon R\leqslant _c R$
which avoids all the equivalence classes in
$\mathcal {C}$
.
First we observe that avoiding any one noncomputable class is equivalent to avoiding any finite set of noncomputable classes.
Lemma 2.17. Let R be an equivalence relation so that for any noncomputable class C, there is a reduction of R to itself that avoids C. Then R is noncomputably avoiding.
Proof We proceed by induction on k to show that for any set of size k of noncomputable classes, there is a reduction of R to itself which avoids every class in the set. For
$k=0$
, the claim is trivial. For
$k=1$
, the claim follows from the assumption about R.
Next, for
$k>1$
, let
$S=\{C_1,\ldots, C_{k+1}\}$
be a collection of noncomputable classes. By inductive hypothesis, there is a reduction
$f\colon R\leqslant _c R$
which avoids
$C_2,\ldots , C_{k+1}$
. We consider three cases depending on what type of class is sent to
$C_1$
via f: If there is no class sent to
$C_1$
via f, then f avoids every class in S. If there is a noncomputable class X sent via f to
$C_1$
, then by assumption there is a reduction
$g\colon R\leqslant _c R$
which avoids X. Then
$f\circ g$
avoids every class in S. Lastly, if a computable class X is sent via f to
$C_1$
, then Corollary 2.15 shows that there is a reduction
$g\colon R\leqslant _c R$
which avoids X. Then
$f\circ g$
avoids every class in S.
Next, we show that the property of noncomputable avoidance is degree invariant.
Observation 2.18. If R is noncomputably avoiding and
$R\equiv _c S$
, then S is also noncomputably avoiding.
Proof Let S be equivalent to some noncomputably avoiding R via
$f\colon R \leqslant _c S$
and
$g\colon S \leqslant _c R$
. Given any noncomputable S-class C, we need to build
$h\colon S\leqslant _c S$
such that h avoids C.
If
$C\notin \operatorname {\mathrm {range }}(f^\star )$
, then
$f\circ g$
is a reduction of S to itself which avoids C. So, let K be an R-class so that
$f^\star (K) = C$
. It suffices to find a reduction
$\ell $
of R to itself avoiding K. Once we have this,
$h= f\circ \ell \circ g$
is a reduction of S to itself avoiding C.
If K is noncomputable, then we use the hypothesis that R is noncomputably avoiding to give the reduction
$\ell $
, and we are done. So, suppose K is computable. Observe that
$g\circ f\colon R\leqslant _c R$
and
${(g\circ f)}^{\star }(K)$
is not computable because C is not computable. Thus, we can apply Corollary 2.15 to get a reduction
$\ell $
of R to itself avoiding the class K.
Noncomputably avoiding equivalence relations exist. For instance, any equivalence relation having all computable classes (and note that there are dark equivalence relations with this property; see, e.g., [Reference Fokina, Rossegger and San Mauro13, Lemma 3.4] or [Reference Gao and Gerdes16, Proposition 5.6]) is obviously noncomputably avoiding. A less trivial example is provided by the following observation.
Observation 2.19. The degree of universal ceers is noncomputably avoiding.
Proof Let U be a universal ceer. Let
$V=U\oplus U$
and note that
$V\equiv _c U$
since V is also a ceer. Any noncomputable class C is either contained in
$\text {Evens}$
or
$\text {Odds}$
. So, we can reduce V to the copy of U on the
$\text {Odds}$
or, respectively,
$\text {Evens}$
of V. This gives a reduction of V to itself avoiding the class C. Thus, V is noncomputably avoiding by Lemma 2.17 and U is noncomputably avoiding by Lemma 2.18.
We now give the main result of this section characterizing the degrees which have a least upper bound with every equivalence relation in
$\mathcal {F}$
.
Theorem 2.20. An equivalence relation R is noncomputably avoiding if and only if R has a least upper bound with every equivalence relation in
$\mathcal {F}$
.
Proof
$(\Rightarrow )$
Let R be noncomputably avoiding. Fix
$S\in \mathcal {F}$
and let
$k=\lvert \omega _S\rvert $
. Fix
$a_1,\ldots , a_k$
representing the k distinct S-classes. Let
$j\leqslant k$
be the minimum of k and the number of computable R-classes, and fix
$C_1,\ldots, C_j$
to be computable R-classes. We will show that
$X:=R{\restriction} \overline { \bigcup _{i\leqslant j} C_i} \oplus S$
is a least upper bound for R and S. First note that X is an upper bound for R (and trivially S) via the function
$f(x)= 2a_i+1$
if
$x\in C_i$
for
$i\leqslant j$
and otherwise
$f(x)=2x$
.
By Lemma 2.1, it suffices to show that X is reducible to any pure quotient
$R\oplus S_{/A}$
of
$R\oplus S$
. Fix a pure quotient
$R\oplus S_{/A}$
. Let
$h\colon R\leqslant _c R$
be a reduction of R to itself which avoids every noncomputable R-class which is A-collapsed with an S-class in
$R\oplus S_{/A}$
. Let
$K_1,\ldots ,K_m$
enumerate the R-classes so that
$h^\star (K_i)$
is A-collapsed with an S-class. Note that these all must be computable, and
$m\leqslant j$
. If any
$K_{i_0}$
equals some
$C_{i_1}$
for
$i_0,i_1\leqslant m$
, then reorder the K’s so that
$i_0=i_1$
.
Let g be a reduction of R to itself which swaps
$K_i$
with
$C_i$
for
$i\leqslant m$
. That is,
$$ \begin{align*} g(x)= \begin{cases} x, & x\notin \bigcup_{i\leqslant m} C_i\cup \bigcup_{i\leqslant m} K_i,\\ \min K_i, & x\in C_i,\\ \min C_i, & x\in K_i. \end{cases} \end{align*} $$
Then all R-classes which are sent via
$h\circ g$
to an R-class A-collapsed with an S-class are among the classes
$C_i$
for
$i\leqslant m$
. Thus, taking the restriction of
$h\circ g$
to the set
$\overline {\bigcup _{i\leqslant j} C_i}$
gives a reduction f of
$R{\restriction} \overline { \bigcup _{i\leqslant j} C_i}$
to R which avoids every R-class which is A-collapsed with an S-class. Then we can make a reduction
$f'$
of
$R{\restriction} \overline { \bigcup _{i\leqslant j} C_i}\oplus S$
to
$R\oplus S_{/A}$
by following f on
$R{\restriction} \overline { \bigcup _{i\leqslant j} C_i}$
and being the identity map on S-classes.
$(\Leftarrow )$
Assume that R has a least upper bound with every finite equivalence relation, and fix a noncomputable class
$A\in \omega _R$
. Let Y be a set so that Y and
$\overline {Y}$
are m-incomparable with every noncomputable R-class. Let T be the least upper bound of R and
$E(Y)$
. We will show that the existence of the least upper bound T will imply that there is a reduction
$f\colon R\leqslant _c R$
which avoids the class A. By Lemma 2.17, this suffices to show that R is noncomputably avoiding.
By Lemma 2.1, we may assume
$T=R\oplus E(Y)_{/\sim }$
, a pure quotient of
$R\oplus E(Y)$
. Since
$T\leqslant _c R\oplus E(Y)$
, we see that no noncomputable R-class C can be collapsed in T to an
$E(Y)$
-class. This is because then
$f\colon T\leqslant _c R\oplus E(Y)$
would give an m-reduction from
$C\oplus Y$
(or
$C\oplus \overline {Y}$
) to either some
$E(Y)$
-class (giving an m-reduction of C to Y or
$\overline {Y}$
) or to an R-class (giving an m-reduction of Y or
$\overline {Y}$
to an R-class). So, we know
$T=R\oplus E(Y)_{/\sim }$
where
$\sim $
collapses at most 2 R-classes, each of which must be computable, with the odd classes.
Fix any R-class
$B\ \,/\!\!\kern-0.9pt\!\!\! =A$
and let
$$ \begin{align*} S:=R\oplus E(Y)_{/(2\min A, 2\min Y +1), (2\min B,2\min \overline{Y}+1)}, \end{align*} $$
i.e., we collapse A with the Y-class in
$E(Y)$
and B with the
$\overline {Y}$
class in
$E(Y)$
. Next, consider the reduction
$g\colon T\leqslant _c S$
. Consider the two T-classes of Y and
$\overline {Y}$
(possibly collapsed also with computable R-classes). Since these do not m-reduce to any R-class, their g-images must intersect the odds. Thus, the image of the evens under g, with the exception of two classes, must avoid each class containing the odds. In other words, we have a reduction
$h\colon R{\restriction} Z\leqslant R$
where
$Z=\overline {C}$
for C the union of the (at most 2) computable R-classes which are
$\sim $
-collapsed in T with odd classes, and h avoids the classes A and B. Thus, by extending h to the computable classes, we get a reduction
$\hat {h}\colon R\leqslant _c R$
and if A has an
$\hat {h}$
-preimage, this preimage must be a computable class. If A is not in the image of
$\hat {h}$
(e.g., if
$T=R\oplus E(Y)$
and
$\sim $
does not collapse any computable R-class to an
$E(Y)$
-class), then we are done. So, suppose the class D is computable and is sent to A via
$\hat {h}$
. Then we apply Corollary 2.15 to show that there is a reduction of R to itself which avoids A.
We turn to showing that
$\operatorname {\mathrm {\mathbf {Id}}}$
is definable in
$\operatorname {\mathrm {\mathbf {ER}}}$
as the unique noncomputably avoiding degree minimal over
$\boldsymbol {\mathcal {F}}$
. From there, we define
$\operatorname {\mathrm {\mathbf {Light}}}$
and
$\operatorname {\mathrm {\mathbf {Dark}}}$
.
Theorem 2.21. In
$\operatorname {\mathrm {\mathbf {ER}}}$
,
$\operatorname {\mathrm {\mathbf {Id}}}$
is definable as the unique noncomputably avoiding degree which is minimal over
$\boldsymbol {\mathcal {F}}$
.
Proof The fact that
$\operatorname {\mathrm {Id}}$
is minimal over
$\mathcal {F}$
is easy (
$\operatorname {\mathrm {Id}}{\restriction} W \equiv _c \operatorname {\mathrm {Id}}_{\lvert W\rvert }$
for any c.e. W), and
$\operatorname {\mathrm {Id}}$
is obviously noncomputably avoiding.
We now verify that
$\mathbf {Id}$
is the only minimal noncomputably avoiding degree. Every other degree minimal over
$\boldsymbol {\mathcal {F}}$
is self-full by Lemma 1.10 and has a noncomputable class by Lemma 1.14. Clearly any self-full equivalence relation with a noncomputable class is not noncomputably avoiding.
Corollary 2.22.
$\operatorname {\mathrm {\mathbf {Light}}}$
and
$\operatorname {\mathrm {\mathbf {Dark}}}$
are definable in
$\operatorname {\mathrm {\mathbf {ER}}}$
.
Proof
$\mathbf {d}\in \operatorname {\mathrm {\mathbf {Light}}}$
if and only if
$\operatorname {\mathrm {\mathbf {Id}}}\leqslant \mathbf {d}$
.
$\mathbf {d}\in \operatorname {\mathrm {\mathbf {Dark}}}$
if and only if
$\mathbf {d}\notin \boldsymbol {\mathcal {F}}\cup \operatorname {\mathrm {\mathbf {Light}}}$
.
Having defined the degree
$\operatorname {\mathrm {\mathbf {Id}}}$
, we wonder which other degrees are definable in
$\operatorname {\mathrm {\mathbf {ER}}}$
. In particular, we ask if the degree of the universal ceer is definable:
Question 1. Is the degree of the universal ceer, or equivalently the substructure
$\operatorname {\mathrm {\mathbf {Ceers}}}$
, definable in
$\operatorname {\mathrm {\mathbf {ER}}}$
?
3 Covers and Branching
We now turn our attention to further structural properties in
$\operatorname {\mathrm {\mathbf {ER}}}$
. We consider the existence of minimal covers and strong minimal covers, and we explore which degrees are branching. Here, many of the results differ from their analogues in the theory of ceers.
In a degree structure, a minimal cover for a degree
$\mathbf {d}$
is a minimal upper bound of
$\lbrace \mathbf {d} \rbrace $
, i.e., a degree
$\mathbf {c}>\mathbf {d}$
such that there is no degree strictly between
$\mathbf {c}$
and
$\mathbf {d}$
; a minimal cover
$\mathbf {c}$
of
$\mathbf {d}$
is strong if anything strictly below
$\mathbf {c}$
is bounded by
$\mathbf {d}$
, i.e.,
$$ \begin{align*} (\forall \mathbf{b})(\mathbf{b}<\mathbf{c}\Rightarrow \mathbf{b}\leqslant \mathbf{d}). \end{align*} $$
A degree is branching if it is the meet of two incomparable degrees.
In
$\operatorname {\mathrm {\mathbf {Ceers}}}$
, not all degrees are branching. Andrews and Sorbi [Reference Andrews and Sorbi5] proved that a ceer R is self-full if and only if
$R\oplus \operatorname {\mathrm {Id}}_1$
is the unique strong minimal cover of R. Further, it has the following upward covering property: If
$X>R$
, then
$X\geq R\oplus \operatorname {\mathrm {Id}}_1$
. This implies that the degree of R cannot branch. In fact, they show that the branching degrees in
$\operatorname {\mathrm {\mathbf {Ceers}}}$
are precisely the non-self-full degrees [Reference Andrews and Sorbi5, Theorem 7.8]. In
$\mathbf {ER}$
, the situation is quite different. In this section, we will show that every degree has continuum many strong minimal covers, and therefore every degree is branching. Before proving these results, we will concentrate on the
$\oplus \operatorname {\mathrm {Id}}_k$
operation for self-full equivalence relations (where
$R\oplus \operatorname {\mathrm {Id}}_k>_c R$
). We show that though
$R\oplus \operatorname {\mathrm {Id}}_1$
is a minimal cover of any self-full equivalence relation R (Corollary 3.4), it is not always a strong minimal cover. That is, surprisingly and in contrast with the case of ceers, there are equivalence relations R such that
$R\oplus \operatorname {\mathrm {Id}}_1>_c S$
, for some S, but S is not computably reducible to R.
Theorem 3.1. If R is self-full and
$R\leqslant _c S\leqslant _c R\oplus \operatorname {\mathrm {Id}}_k$
, then there is some
$j\leqslant k$
so that
$S\equiv _c R\oplus \operatorname {\mathrm {Id}}_j$
.
Proof We prove this by induction on k. For
$k=0$
, the result is trivial. Next, let
$f\colon R\leqslant _c S$
,
$g\colon S\leqslant _c R\oplus \operatorname {\mathrm {Id}}_k$
, and suppose that S is not equivalent to
$R\oplus \operatorname {\mathrm {Id}}_j$
for any
$j\leqslant k$
.
Claim 3.2. The range of f intersects every S-class.
Proof If the range of f did not intersect every S-class, then we would have
$R\oplus \operatorname {\mathrm {Id}}_1\leqslant _c S$
. But then we could use the inductive hypothesis, since
$R\oplus \operatorname {\mathrm {Id}}_1\leqslant _c S \leqslant _c R\oplus \operatorname {\mathrm {Id}}_1\oplus \operatorname {\mathrm {Id}}_{k-1}$
. Thus, we would know that
$S\equiv _c R\oplus \operatorname {\mathrm {Id}}_1\oplus \operatorname {\mathrm {Id}}_j$
for some
$j\leqslant k-1$
, but then it would follow that
$S\equiv _c R\oplus \operatorname {\mathrm {Id}}_{j'}$
for some
$j'\leqslant k$
.
Claim 3.3. The range of g intersects every
$R\oplus \operatorname {\mathrm {Id}}_k$
-class.
Proof If the range of g did not intersect every
$R\oplus \operatorname {\mathrm {Id}}_k$
-class, then we would have
$S\leqslant _c R\oplus \operatorname {\mathrm {Id}}_{k-1}$
. But then, since
$R\leqslant _c S\leqslant _c R\oplus \operatorname {\mathrm {Id}}_{k-1}$
, we could use the inductive hypothesis to show that
$S\equiv _c R\oplus \operatorname {\mathrm {Id}}_j$
for some
$j\leqslant k-1$
.
Let
$h\colon =g\circ f$
be the composite reduction of R to
$R\oplus \operatorname {\mathrm {Id}}_k$
through S. Fix any odd number a and let
$C_i:=\{x : h\circ (\frac {h}{2})^{(i)}(x) \mathrel {R\oplus \operatorname {\mathrm {Id}}_k} a \}$
. Note that the
$C_i$
’s so defined for
$i\geq 1$
are a uniform sequence of computable R-classes. Thus Lemma 2.13 yields a contradiction by showing that R is not self-full.
Applying this to
$k=1$
, we get that if R is self-full, then
$R\oplus \operatorname {\mathrm {Id}}_1$
is a minimal cover of R.
Corollary 3.4. Let R be self-full. Then
$R\oplus \operatorname {\mathrm {Id}}_1$
is a minimal cover of R.
Now, we will show that, contrary to the case of ceers, there are self-full equivalence relations R so that
$R \oplus \operatorname {\mathrm {Id}}_1$
is not a strong minimal cover of R. To do so, we introduce generic covers of equivalence relations. Intuitively, a generic cover S of a given equivalence relation R codes R into the evens and is generic given this property.
Definition 3.5. A generic cover S of an equivalence relation R is any equivalence relation of the form
$R\oplus \operatorname {\mathrm {Id}}_{/ \operatorname {\mathrm {graph}}(f)}$
, where
$f\colon \text {Odds} \rightarrow \text {Evens}$
is
$1$
-generic over the Turing degree of R.
Clearly, R is computably reducible to any generic cover of R via the map
$x\to 2x$
. We now see how reductions into the odds must intersect the classes of S.
Lemma 3.6. Let S be a generic cover of R and
$Z\subseteq \text {Odds}$
be an infinite set which is c.e. in the Turing degree of R. Then, Z intersects every S-class infinitely. It follows that
$S\not \leqslant _c R$
.
Proof Assume that S, R, and Z are as in the statement of the lemma. In particular,
$S=R\oplus \operatorname {\mathrm {Id}}_{/\operatorname {\mathrm {graph}}(f)}$
. Observe that the following sets of strings are c.e. in
$\deg _T(R)$
,
$$ \begin{align*} V_{a,k}:=\lbrace \sigma\in \text{Evens}^{<\text{Odds}} : (\exists^k x)(x\in Z\wedge \sigma(x)=2a) \rbrace. \end{align*} $$
Further, since Z is infinite,
$V_{a,k}$
is dense in
$\text {Evens}^{<\text {Odds}}$
. Therefore f meets every
$V_{a,k}$
by genericity of f, and Z intersects the S-class of every even number, so every S class, infinitely often.
Next, suppose
$f\colon S\leqslant _c R$
and take any odd number a. Let
$Z=\{b\in \text {Odds} : f(b)\mathrel {R} f(a)\}$
. Necessarily Z is an infinite R-c.e. set since Z contains
$[a]_S\cap \text {Odds}$
(and the set
$\text {Odds}$
intersects every S-class infinitely by the above). Therefore, Z meets every S-class, contradicting that f is a reduction.
So, R is properly reducible to a generic cover of R, but the way in which S covers R is quite different from the way in which
$R\oplus \operatorname {\mathrm {Id}}_1$
covers R:
Lemma 3.7. If S is a generic cover of R, then, for all n, the only equivalence relations which reduce to both
$R\oplus \operatorname {\mathrm {Id}}_n$
and S are the equivalence relations reducible to R.
Proof Suppose that, for some equivalence relation X, there are
$f\colon X\leqslant _c R\oplus \operatorname {\mathrm {Id}}_n$
and
$g \colon X\leqslant _c S$
. Let A and B be any two X-classes. Note that
$A,B \leqslant _m R\oplus \operatorname {\mathrm {Id}}_n \equiv _T R$
by Lemma 1.1. Consider the R-c.e. sets
$\text {Odds} \cap \operatorname {\mathrm {range }}(g{\restriction} \overline {A})$
and
$\text {Odds} \cap \operatorname {\mathrm {range }}(g{\restriction} \overline {B})$
. These must both be finite, as otherwise Lemma 3.6 would show that
$g{\restriction} \overline {A}$
would hit
$g^\star (A)$
or
$g{\restriction} \overline {B}$
would hit
$g^\star (B)$
. Thus
$\operatorname {\mathrm {range }}(g)\cap \text {Odds}$
is finite. So, Lemma 1.6 shows that
$X\leqslant _c R$
.
In Ceers,
$R\oplus \operatorname {\mathrm {Id}}_1$
is a strong minimal cover (in fact, the only one) of a given self-full ceer R. Hence, any ceer which is below
$R\oplus \operatorname {\mathrm {Id}}_1$
is already reducible to R. But the dual property also holds:
$R\oplus \operatorname {\mathrm {Id}}_1$
reduces to any ceer which is above R (see [Reference Andrews and Sorbi5, Lemma 4.5] for details). The next theorem uses generic covers to show that these properties both fail in
$\operatorname {\mathrm {\mathbf {ER}}}$
.
Theorem 3.8. The following hold.
-
(1) Let R be any self-full equivalence relation. There is S such that
$R<_c S$
but
$R\oplus \operatorname {\mathrm {Id}}_1\not \leqslant _c S$
. -
(2) There exist a self-full equivalence relation R such that, for some S,
$S<_c R\oplus \operatorname {\mathrm {Id}}_1$
but
$S\not \leqslant _c R$
.
Proof
$(1)$
: Let S be a generic cover of R. S is above R and, by Lemma 3.7, we have that S is incomparable with
$R\oplus \operatorname {\mathrm {Id}}_1$
.
$(2)$
: Let
$S_0$
be any self-full equivalence relation, let R be a generic cover of
$S_0$
, and denote
$S_0\oplus \operatorname {\mathrm {Id}}_1$
by S. It is immediate that
$S\leqslant _c R\oplus \operatorname {\mathrm {Id}}_1$
as
$S_0\leqslant _c R$
. But S and R are incomparable by Lemma 3.7.
Having shown that
$R\oplus \operatorname {\mathrm {Id}}_1$
is not a strong minimal cover for some self-full R, it is natural to ask whether every self-full degree has a strong minimal cover. The next theorem answers this question affirmatively. In fact, all equivalence relations aside from
$\operatorname {\mathrm {Id}}_1$
have continuum many strong minimal covers, and such covers can be chosen to be self-full.
Theorem 3.9. Let R be any equivalence relation
$\neq \operatorname {\mathrm {Id}}_1$
. Then there are continuum many strong minimal covers of R which are self-full.
Proof In [Reference Andrews and Sorbi5, Theorem 4.10], it is proven that there is a ceer
$E_0$
which satisfies the following properties:
-
(1)
$E_0{\restriction} \text {Evens} = \operatorname {\mathrm {Id}}$
; -
(2) There are infinitely many classes which contain no even number;
-
(3) If W is any c.e. set which intersects infinitely many
$E_0$
-classes which contain no even number, then W intersects every
$E_0$
-class.
There, it is shown that such a ceer is a self-full strong minimal cover of
$\operatorname {\mathrm {Id}}$
. Here, we let
$S_0$
be the quotient of
$E_0$
formed by collapsing
$2n$
with
$2m$
if and only if
$n \mathrel {R} m$
. Note that
$S_0{\restriction} \text {Evens} = R$
.
Let
$\mathcal {S}$
be the set of quotients of
$S_0$
which collapse every
$S_0$
-class which contains no even number to exactly one
$S_0$
-class which does contain an even number. That is,
$$ \begin{align*} \mathcal{S}:=\{{S_0}_{/A} : {S_0}_{/A} {\restriction} \text{Evens} = R\text{ and } [\text{Evens}]_{{S_0}_{/A}}=\omega\}. \end{align*} $$
Since
$E_0$
, and thus also
$S_0$
, has infinitely many classes which contain no even number, and
$\lvert \omega _R\rvert>1$
, we have
$\lvert \mathcal {S}\rvert =2^{\aleph _0}$
. Thus, there are continuum many elements of
$\mathcal {S}$
which are not
$\leqslant _c R$
, and there is a continuum sized
$\leqslant _c$
-antichain in
$\mathcal {S}$
. It suffices to show that for
$S\in \mathcal {S}$
, if
$X<_c S$
, then
$X\leqslant _c R$
. It suffices by Remark 1.3 to prove that either
$S \leqslant _c S{\restriction} W$
or
$S{\restriction} W \leqslant _c R$
for any c.e. set W.
We argue by cases:
-
(1) If W intersects only finitely many
$E_0$
-classes which do not contain an even number, then we build a reduction of
$S{\restriction} W$
to R as follows:Let
$a_1,\ldots , a_n$
represent the
$E_0$
-classes which contain no even number and are intersected by W. Let
$b_1,\ldots , b_n$
be even numbers so that
$a_i \mathrel {S} b_i$
. Then define
$g(x)$
to be the first member of
$\text {Evens} \cup \{a_i : i\leqslant n\}$
found to be
$E_0$
-equivalent to x (note that we are using that
$E_0$
is a ceer). Then let
$h(x)= g(x)$
if
$g(x)$
is even and
$h(x)=b_i$
if
$g(x)=a_i$
. This gives a reduction of
$S{\restriction} W$
to S whose range is contained in the evens. So, this gives a reduction of
$S{\restriction} W$
to
$S{\restriction} \text {Evens} = R$
. -
(2) If W intersects infinitely many
$E_0$
-classes which do not contain an even number, then we know that W intersects every
$E_0$
-class. We then give a reduction of S to
$S{\restriction} W$
by sending x to the first member of W found to be
$E_0$
-equivalent to x. Since S is a quotient of
$E_0$
, this is the identity map on classes, so a reduction of S to
$S{\restriction} W$
.
Lastly, we check that S is self-full. Suppose f is a function reducing S to itself. Let W be
$\operatorname {\mathrm {range}}(f)$
. Since
$R<_c S$
, we cannot be in case (1) above, so W must intersect every
$E_0$
-class, so also every S-class.
Corollary 3.10. In
$\operatorname {\mathrm {\mathbf {ER}}}$
, every degree is branching.
Proof Every degree
$\mathbf {d}$
has two incomparable strong minimal covers. The meet of these two degrees is
$\mathbf {d}$
.
So, contrary to the case of ceers, the self-full equivalence relations cannot be characterized in terms of their strong minimal covers. We ask:
Question 2. Is the collection of self-full degrees first-order definable in
$\operatorname {\mathrm {\mathbf {ER}}}$
?
4 The complexity of the first-order theory of
$\operatorname {\mathrm {\mathbf {ER}}}$
In this last section, we characterize the complexity of
$\operatorname {\mathrm {Th}}(\operatorname {\mathrm {\mathbf {ER}}})$
, the first-order theory of
$\operatorname {\mathrm {\mathbf {ER}}}$
. Our analysis contributes to a longstanding research thread. Indeed, computability theorists have been investigating the first-order complexity of degree structures generated by reducibilities for decades.
Since a reducibility r is typically a binary relation on subsets of
$\omega $
, one can effectively translate first-order sentences regarding the corresponding degree structure
$\mathcal {D}_r$
to second-order sentences of arithmetic, obtaining a
$1$
-reduction from
$\operatorname {\mathrm {Th}}(\mathcal {D}_r)$
to
$\operatorname {\mathrm {Th}}^2(\mathbb {N})$
. Remarkably, the converse reduction often holds, e.g., the first-order theories of the following degree structures are
$1$
-equivalent (and so, by Myhill Isomorphism Theorem, computably isomorphic) to second-order arithmetic: the Turing degrees
$\mathcal {D}_T$
[Reference Simpson22]; the m-degrees
$\mathcal {D}_m$
, the
$1$
-degrees
$\mathcal {D}_1$
, the
$tt$
-degrees
$\mathcal {D}_{tt}$
, the
$wtt$
-degrees
$\mathcal {D}_{wtt}$
[Reference Nerode and Shore20]; and the enumeration degrees
$\mathcal {D}_{e}$
[Reference Slaman and Woodin23]. Here, we add
$\operatorname {\mathrm {\mathbf {ER}}}$
to this list, namely, we prove:
Theorem 4.1.
$\operatorname {\mathrm {Th}}(\operatorname {\mathrm {\mathbf {ER}}})$
is computably isomorphic to
$\operatorname {\mathrm {Th}}^2(\mathbb {N})$
.
In fact, we will show that the theorem is also true for each of the definable substructures
$\operatorname {\mathrm {\mathbf {Dark}}}$
and
$\operatorname {\mathrm {\mathbf {Light}}}$
of
$\operatorname {\mathrm {\mathbf {ER}}}$
.
4.1 Our strategy
Equivalence relations are straightforwardly encoded into subsets of
$\omega $
; hence
$\operatorname {\mathrm {Th}}(\operatorname {\mathrm {\mathbf {ER}}})\leqslant _1 \operatorname {\mathrm {Th}}^2(\mathbb {N})$
trivially holds. So, to prove Theorem 4.1, it suffices to prove the converse reduction. Our strategy for coding second-order arithmetic into
$\operatorname {\mathrm {\mathbf {ER}}}$
is based on coding all countable graphs as second-order objects into this degree structure. The justification for such approach relies on well-known facts. Second-order arithmetic is
$1$
-reducible to second-order logic on countable sets, which is in turn
$1$
-reducible to the theory of second-order countable graphs [Reference Lavrov19]. So, one can effectively translate any question about second-order arithmetic into a question about a graph which encodes the standard model of Robinson’s arithmetic Q.
Finally, let us mention that our encodings are similar to the way in which graphs are coded in
$\mathbf {Ceers}$
, as in [Reference Andrews, Schweber and Sorbi4]. But there are three major differences. Firstly, in what follows we code any countable graph, rather than just computable graphs. Secondly, we must code subsets of the set of vertices of our graph. Thirdly, since we are giving codes for subsets, we do not need to code functions between different codings of natural numbers; that means that we do not need to distinguish the natural numbers from non-standard models of Robinson’s Q as being embeddable into any other such model (thus needing to code functions), because the second-order theory distinguishes the standard model of Robinson’s Q as the only one with no proper inductive subset.
4.2 Coding graphs into Dark
To code graphs in
$\mathbf {Dark}$
, we heavily use dark minimal degrees: We fix a collection
$\{D_i: i\in \omega \}$
of pairwise nonequivalent dark minimal equivalence relations. In fact, since
$\mathbf {Ceers}$
is an initial segment of
$\operatorname {\mathrm {\mathbf {ER}}}$
, we may choose dark minimal ceers (as constructed in [Reference Andrews and Sorbi5]).
Definition 4.2. Let
$\mathbf {d_1},\mathbf {d_2}$
be two dark minimal degrees. We say that incomparable degrees
$\mathbf {a},\mathbf {b}$
are a covering pair of
$\mathbf {d_1},\mathbf {d_2}$
if, for each
$\mathbf {x}\in \{\mathbf {a},\mathbf {b}\}$
, the set of dark minimal degrees below
$\mathbf {x}$
is precisely
$\{\mathbf {d_1},\mathbf {d_2}\}$
, and there is no
$\mathbf {y}< \mathbf {a},\mathbf {b}$
so that
$\mathbf {d_1},\mathbf {d_2}< \mathbf {y}$
.
We now describe how to encode a countable graph by parameters in
$\mathbf {Dark}$
.
Definition 4.3. For any degree
$\mathbf {c}$
, let
$G_{\mathbf {c}}$
be the graph with vertex set composed of the dark minimal degrees below
$\mathbf {c}$
and edges the collection of pairs
$\mathbf {d_1},\mathbf {d_2}$
so that there are distinct
$\mathbf {a},\mathbf {b}\leqslant \mathbf {c}$
which form a covering pair of
$\mathbf {d_1},\mathbf {d_2}$
.
The next lemma provides an easy way of forming covering pairs of dark minimal equivalence relations.
Lemma 4.4. If
$D,E$
are dark minimal equivalence relations, then
$D\oplus E$
and
$D\oplus E_{/(0,1)}$
form a covering pair of D and E.
Proof It is immediate that D and E are both computably reducible to
$D\oplus E$
and
$D\oplus E_{/(0,1)}$
(the latter being a pure quotient).
We show that the only dark minimal degrees below either
$D\oplus E$
or
$D\oplus E_{/(0,1)}$
are the degrees of D and E.
Suppose
$f\colon X\leqslant _c D\oplus E$
, for a dark minimal X. Since X is dark minimal, its equivalence classes are computably inseparable by Lemma 1.14, so
$\operatorname {\mathrm {range}}(f)$
must be either contained in the evens or the odds, which implies
$X\leqslant _c D$
or
$X\leqslant _c E$
. But then
$X\equiv _c D$
or
$X\equiv _c E$
, by minimality of D and E.
On the other hand, suppose
$f\colon X\leqslant _c D\oplus E_{/(0,1)}$
, for a dark minimal X. Since the equivalence classes of X are computably inseparable by Lemma 1.14,
$\operatorname {\mathrm {range}}(f)$
is contained in either
-
(1)
$\text {Evens} \cup [1]_{D\oplus E_{/(0,1)}}$
, -
(2) or
$\text {Odds}\cup [0]_{D\oplus E_{/(0,1)}}$
.
Without loss of generality, we assume the former. Let h be the function given by
$h(x)=x$
if x is even and
$0$
if x is odd. Then
$h\circ f\colon X\leqslant _c D\oplus E_{/(0,1)}$
and
$\operatorname {\mathrm {range}}(h\circ f)\subseteq \text {Evens}$
. This induces a reduction of X to D. But then
$X\equiv _c D$
, by minimality of D.
Next, we consider the degrees strictly below
$D\oplus E$
which might bound both D and E. Suppose that
$X\leqslant _c D\oplus E$
. Then by Lemma 1.4,
$X\equiv _c D_0\oplus E_0$
where
$D_0\leqslant _c D$
and
$E_0\leqslant _c E$
. So either
-
(1)
$X\in \mathcal {F}$
, -
(2) or
$X\equiv _c D\oplus E$
, -
(3) or
$X\equiv _c D\oplus F$
for some
$F\in \mathcal {F}$
, -
(4) or
$X\equiv _c E\oplus F$
for some
$F\in \mathcal {F}$
.
In the first case, X obviously does not bound D or E. In the second, X is not strictly below
$D\oplus E$
. In cases
$(3)$
and
$(4)$
, X does not bound both D and E. To see this, suppose
$X\equiv _c D\oplus F$
for some
$F\in \mathcal {F}$
. Then any reduction of E to X gives a reduction of E to
$D\oplus F$
. But by computable inseparability of the classes of E, this reduction is either contained in the evens, giving
$E\leqslant _c D$
, or contained in the odds, giving E is finite, either way leading to a contradiction. Thus, there is no equivalence relation X which is strictly reducible to
$D\oplus E$
and bounds both D and E.
Next we observe that
$D\oplus E$
and
$D\oplus E_{/(0,1)}$
are incomparable. The fact that
$D\oplus E\not \leqslant _c D\oplus E_{/(0,1)}$
follows from darkness of
$D\oplus E$
and Lemma 1.11. The fact that
$D\oplus E_{/(0,1)}\not <_c D\oplus E$
follows from the previous paragraph.
Finally, by incomparability of
$D\oplus E$
and
$D\oplus E_{/(0,1)}$
, any degree below both would have to be strictly below
$D\oplus E$
, so cannot bound both D and E.
We are ready to show that we can uniformly code any countable graph as a second-order structure into
$\operatorname {\mathrm {\mathbf {Dark}}}$
, which, combined with the remarks offered in Section 4.1, will yield the following theorem.
Theorem 4.5. The theory of the degree structure
$\operatorname {\mathrm {\mathbf {Dark}}}$
is computably isomorphic to second-order arithmetic.
Proof We first embed any countable graph as a first-order structure into
$\operatorname {\mathrm {\mathbf {Dark}}}$
.
Lemma 4.6. For any countable graph G, there is some
$\mathbf {c}\in \operatorname {\mathrm {\mathbf {Dark}}}$
so
${G_{\mathbf {c}}\cong G}$
.
Proof We may assume that the universe of G is
$\omega $
(if G is finite, then the dark ceer C constructed below can be taken simply as the uniform join of
$D_i$
and
$D_u\oplus {D_v}_{/(0,1)}$
for pairs where
$u \mathrel {G} v$
). Recall that
$\{D_i: i\in \omega \}$
represents a collection of distinct dark minimal degrees.
Let X be the collection of equivalence relations
$$ \begin{align*} \{D_i : i\in \omega\}\cup \{{D_i\oplus D_j}_{/(0,1)} : i \mathrel{G} j\} \end{align*} $$
and fix an enumeration of
$X=(X_i)_{i\in \omega }$
. Fix S to be an immune set. Then we define C by
$\langle x,i\rangle \mathrel {C} \langle y,j\rangle $
if and only either
$i=j$
is the nth element of S and
$x \mathrel {X_n} y$
or
$i,j\notin S$
.
We now argue that C is dark and
$G_{\mathbf {c}}\cong G$
, where
$\mathbf {c}$
is the degree of C. The proof is split into several claims.
Claim 4.7. C is dark.
Proof If
$W_e$
intersects infinitely many columns of
$\omega $
, then by immunity of S, it enumerates two elements
$\langle x, i\rangle , \langle y, j\rangle $
with
$i,j\notin S$
. But then
$\langle x, i\rangle \mathrel {C} \langle y, j\rangle $
and
$W_e$
is not a transversal.
If
$W_e$
intersects only finitely many columns, then
$W_e$
is enumerating a subset of
$Y=\{\langle x, i\rangle : i\leqslant m\}$
for some m. But
$C{\restriction} Y$
is equivalent to a finite uniform join of dark ceers
$X_i$
. Thus
$W_e$
cannot be a transversal.
Next we see that the only dark minimal degrees bounded by
$\mathbf {c}$
, i.e., those which are vertices in
$G_{\mathbf {c}}$
, are
$\{D_i : i\in \omega \}$
.
Claim 4.8. If
$D\leqslant _c C$
and D is dark minimal, then
$D\equiv _c D_u$
for some u.
Proof Since D is dark minimal, its classes are computably inseparable by Lemma 1.14. So, either
$D\leqslant _c D_u$
, for some u, or
$D\leqslant _c D_i\oplus {D_j}_{/(0,1)}$
, for some pair
$i,j$
. In the former case, dark minimality of
$D_u$
ensures
$D\equiv _c D_u$
, and in the latter case Lemma 4.4 ensures
$D\equiv _c D_i$
or
$D\equiv _c D_j$
.
We now know that the map
$i\mapsto \mathbf {d}_i$
is onto
$G_{\mathbf {c}}$
. It only remains to show that it is an embedding of G.
Claim 4.9. If
$u \mathrel {G} v$
, then
$u \mathrel {G_{\mathbf {c}}} v$
.
Proof There are three columns of C, coding
$D_u, D_v$
, and
${D_u\oplus D_v}_{/(0,1)}$
. Therefore,
$D_u\oplus D_v, {D_u\oplus D_v}_{/(0,1)}$
are both
$\leqslant _c C$
. By Lemma 4.4, these form a covering pair of
$D_u$
and
$D_v$
, so we have
$u \mathrel {G_{\mathbf {c}}} v$
.
Claim 4.10. If
$u \mathrel {G_{\mathbf {c}}} v $
, then
$u \mathrel {G} v$
.
Proof Suppose that
$\mathbf {a},\mathbf {b}\leqslant \mathbf {c}$
form a covering pair of
$\mathbf {d}_u$
and
$\mathbf {d}_v$
and
$u,v$
are not adjacent in G. Let
$A\in \mathbf {a}$
,
$B\in \mathbf {b}$
,
$D_u\in \mathbf {d}_u$
, and
$D_v\in \mathbf {d}_v$
. Consider the composite reductions
$f_u\colon D_u\leqslant _c A\leqslant _c C$
and
$f_v\colon D_v\leqslant _c A\leqslant _c C$
. By computable inseparability of the classes of
$D_u$
(Lemma 1.14),
$\operatorname {\mathrm {range}}(f_u)$
must be contained in a single column of C. By incomparability of the dark minimal equivalence relations and Lemma 4.4, this column must be either
$D_u$
or
$D_u\oplus {D_w}_{/(0,1)}$
for some w with
$u \mathrel {G} w$
. In particular, the column used for
$f_u$
cannot be the same as the column used for
$f_v$
. It follows that
$D_u\oplus D_v\leqslant _c A$
. Similarly for B, contradicting that
$\mathbf {a}$
and
$\mathbf {b}$
form a covering pair of
$\mathbf {d}_u,\mathbf {d}_v$
.
This completes the proof of Lemma 4.6.
Next, we show that for any
$\mathbf {c}$
, we can code any subset of
$G_{\mathbf {c}}$
.
Lemma 4.11. Let E be a countable set of dark minimal degrees. There is a degree
$\mathbf {a}\in \operatorname {\mathrm {\mathbf {Dark}}}$
so that the set of dark minimal degrees
$\leqslant \mathbf {a}$
is exactly E.
Proof Apply the construction of the dark equivalence relation C of Lemma 4.6 to the empty graph and the collection of degrees in E. That is, let
$(E_i)_{i\in \omega }$
be dark minimal equivalence relations representing the classes in E. Then let
$\langle x, i \rangle \mathrel {C} \langle y, j \rangle $
if and only if
$i=j$
is the nth element of S (a fixed immune set) and
$x \mathrel {E_{n}} y$
or if
$i,j\notin S$
. Lemma 4.8 shows that the degrees of dark minimal equivalence relations below C are precisely E, and Lemma 4.7 shows that C is dark.
For
$\mathbf {a}\in \operatorname {\mathrm {\mathbf {Dark}}}$
, let
$M_{\mathbf {a}}$
be the set of dark minimal degrees
$\leqslant \mathbf {a}$
. Put together, we now know that every second-order countable graph is encoded as
$(G_{\mathbf {c}}, \mathcal {A})$
for some
$\mathbf {c}\in \operatorname {\mathrm {\mathbf {Dark}}}$
, where
$\mathcal {A}$
is the set of
$M_{\mathbf {a}}$
for
$\mathbf {a}\in \operatorname {\mathrm {\mathbf {Dark}}}$
which are contained in
$G_{\mathbf {c}}$
.
So,
$\operatorname {\mathrm {Th}}(\operatorname {\mathrm {\mathbf {Dark}}})$
is
$\geq _1$
the theory of second-order countable graphs. As remarked in Section 4.1, this is enough to conclude that
$\operatorname {\mathrm {Th}}(\operatorname {\mathrm {\mathbf {Dark}}})$
is computably isomorphic to second-order arithmetic. Then, Theorem 4.1 immediately follows from the fact that
$\operatorname {\mathrm {\mathbf {Dark}}}$
is definable in
$\operatorname {\mathrm {\mathbf {ER}}}$
(Corollary 2.22).
4.3 Coding graphs into Light
We now focus on light degrees, with the goal of showing that
$\operatorname {\mathrm {Th}}(\operatorname {\mathrm {\mathbf {Light}}})$
is also computably isomorphic to second-order arithmetic. The encoding of graphs in the light degrees will be as follows:
Definition 4.12. A degree
$\mathbf {e}$
is a light minimal degree if
$\operatorname {\mathrm {\mathbf {Id}}}<\mathbf {e}$
and there is no
$\mathbf {x}$
so that
$\mathbf {Id}< \mathbf {x}<\mathbf {e}$
.
Let
$\mathbf {e}_1,\mathbf {e}_2$
be two light minimal degrees. We say that
$\mathbf {a},\mathbf {b}$
are a light covering pair of
$\mathbf {e}_1,\mathbf {e}_2$
if for each
$\mathbf {x}\in \{\mathbf {a},\mathbf {b}\}$
, the set of light minimal degrees below
$\mathbf {x}$
is precisely
$\{\mathbf {e}_1,\mathbf {e}_2\}$
and there is no
$\mathbf {y}$
below
$\mathbf {a}$
and
$\mathbf {b}$
which is above
$\mathbf {e}_1,\mathbf {e}_2$
.
Definition 4.13. For a light degree
$\mathbf {c}$
, let
$H_{\mathbf {c}}$
be the graph with vertices the light minimal degrees below
$\mathbf {c}$
and edges the collection of pairs
$\mathbf {e}_1,\mathbf {e}_2$
so that there are
$\mathbf {a},\mathbf {b}\leqslant \mathbf {c}$
which form a light covering pair of
$\mathbf {e}_1,\mathbf {e}_2$
.
We now show that we can uniformly encode every second-order countable graph into
$\operatorname {\mathrm {\mathbf {Light}}}$
.
Theorem 4.14. The theory of
$\operatorname {\mathrm {\mathbf {Light}}}$
is computably isomorphic to second-order arithmetic.
Proof Rather than directly defining light covering pairs of light minimal degrees (as we did in Lemma 4.4), we inherit them from the dark case through the following map: let
$\iota $
be the map from
$\operatorname {\mathrm {Dark}}\cup \mathcal {F}$
to
$\operatorname {\mathrm {Light}}$
given by
$\iota (D)=D\oplus \operatorname {\mathrm {Id}}$
, and
$\boldsymbol {\iota }$
the induced map on degrees. The next two claims give two crucial properties of
$\iota $
.
Claim 4.15.
$\iota $
gives a homomorphism of
$\operatorname {\mathrm {Dark}}\cup \mathcal {F}$
into
$\operatorname {\mathrm {Light}}$
whose image is an initial segment.
Proof It is immediate that
$D\leqslant _c E$
implies
$\iota (D)\leqslant _c \iota (E)$
. Now, suppose
$\operatorname {\mathrm {Id}}\leqslant _c X\leqslant _c \iota (D)=D\oplus \operatorname {\mathrm {Id}}$
, for some equivalence relation X. From Lemma 1.4, it follows
$X\equiv _c D_0\oplus A$
, where
$D_0\leqslant _c D$
and
$A\leqslant _c \operatorname {\mathrm {Id}}$
. Since
$D_0$
is dark or finite, A must be light, since
$\operatorname {\mathrm {Id}}\leqslant _c X$
. So,
$A\equiv _c \operatorname {\mathrm {Id}}$
. Thus,
$X\equiv _c D_0\oplus \operatorname {\mathrm {Id}}=\iota (D_0)$
.
Claim 4.16. If D is a dark minimal ceer, then
$\iota (D)$
is of light minimal degree.
Proof Suppose
$\operatorname {\mathrm {Id}}<_c X\leqslant _c \iota (D)$
. Then by the proof of Claim 4.15,
$X\equiv _c \iota (E)$
for some
$E\leqslant D$
. But D is a ceer, so E cannot be in
$\mathcal {F}$
as that would make
$E\in \mathcal {I}$
and
$X\equiv _c \operatorname {\mathrm {Id}}$
. So,
$E\in \operatorname {\mathrm {Dark}}$
, and thus
$E\equiv _c D$
by dark minimality of D.
Lemma 4.6 guarantees that any graph G is encodable into
$\operatorname {\mathrm {\mathbf {Dark}}}$
via some
$G_{\mathbf {c}}$
. The next lemma says that we can use
$\boldsymbol {\iota }$
to transfer our coding of graphs into
$\operatorname {\mathrm {\mathbf {Dark}}}$
into an encoding in
$\operatorname {\mathrm {\mathbf {Light}}}$
.
Lemma 4.17. For any countable graph G, there is a degree
$\mathbf {c}\in \operatorname {\mathrm {Dark}}$
so that
$G_{\mathbf c}\cong G$
is isomorphic to a substructure of
$H_{\boldsymbol {\iota }(\mathbf {c})}$
Proof Fix dark minimal ceers
$D_i\in \mathbf {d}_i$
and let
$\mathbf {c}$
be as constructed in Lemma 4.6 so
$G_{\mathbf c}\cong G$
. Lemma 4.16 shows that every
$\boldsymbol {\iota }(\mathbf {d}_i)$
is in
$H_{\boldsymbol {\iota }(\mathbf {c})}$
. Let X be the subset of vertices in
$H_{\boldsymbol {\iota }(\mathbf {c})}$
comprised of
$\boldsymbol {\iota }(\mathbf {d}_i)$
for
$i\in \omega $
. We do not claim that there are no other light minimal degrees bounded by
$\boldsymbol {\iota }(\mathbf {c})$
. We now show that
$\boldsymbol {\iota }$
gives an isomorphism of
$G_{\mathbf {c}}$
with the substructure of
$H_{\boldsymbol {\iota }(\mathbf {c})}$
with universe X.
By Claim 4.15,
$\boldsymbol {\iota }$
gives a homomorphism of the degrees below
$\mathbf {c}$
onto the light degrees below
$\boldsymbol {\iota }(\mathbf {c})$
. We argue that such a homomorphism, when restricted to the dark minimal degrees and their covering pairs, is in fact an embedding.
First observe that each distinct pair of dark minimal
$D_i$
and
$D_j$
below
$\mathbf {c}$
are sent via
$\iota $
to incomparable degrees. Indeed, if
$\iota (D_i)\leqslant _c \iota (D_j)$
, then
$D_i\leqslant _c D_j\oplus \operatorname {\mathrm {Id}}$
. By the computable inseparability of the classes of
$D_i$
, the reduction is either to
$D_j$
or
$\operatorname {\mathrm {Id}}_k$
, both of which are impossible.
Now, for distinct
$D_i,D_j$
, observe that
$\iota (D_i\oplus D_j)$
and
$\iota (D_i\oplus {D_j}_{/(0,1)})$
are sent to incomparable degrees. To see this, recall that, by Lemma 4.4,
$D_i\oplus D_j$
and
$D_i\oplus {D_j}_{/(0,1)}$
are incomparable. Since neither of these have a computable class (because this would contradict the computable inseparability of the equivalence classes of
$D_i$
and
$D_j$
, granted by Lemma 1.14), it follows that neither can reduce to the other
$\oplus \operatorname {\mathrm {Id}}$
, as such a reduction could not make any use of
$\operatorname {\mathrm {Id}}$
.
Claim 4.18. If
$\mathbf {d}_i \mathrel {G_{\mathbf {c}}} \mathbf {d_j}$
, then
$\boldsymbol {\iota }(\mathbf {d}_i) \mathrel {H_{\boldsymbol {\iota }(\mathbf {c})}} \boldsymbol {\iota }(\mathbf {d}_j)$
.
Proof Let
$\mathbf {d}_i \mathrel {G_{\mathbf {c}}} \mathbf {d}_j$
. To show that
$\iota (\mathbf {d}_i) \mathrel {H_{\iota (\mathbf {c})}} \iota (\mathbf {d}_j)$
holds, we need to check that
$\iota (D_i\oplus D_j)$
and
$\iota (D_i\oplus {D_j}_{/(0,1)})$
form a light covering pair of
$\iota (D_i)$
and
$\iota (D_j)$
. It only remains to check that there is no
$Y\leqslant _c \iota (D_i\oplus D_j)$
,
$\iota (D_i\oplus {D_j}_{/(0,1)})$
such that
$\iota (D_i),\iota (D_j)\leqslant _c Y$
. Suppose that such a Y existed. Consider the composite reduction
$f_i\colon D_i\leqslant _c Y\leqslant _c D_i\oplus D_j\oplus \operatorname {\mathrm {Id}}$
. The computable inseparability of the classes of
$D_i$
and the incomparability of
$D_i$
and
$D_j$
force
$f_i$
to go into the first column. Similarly, the reduction of
$f_j\colon D_j\leqslant _c Y\leqslant _c D_i\oplus D_j\oplus \operatorname {\mathrm {Id}}$
must go into the second column. It follows that
$D_i\oplus D_j\leqslant _c Y$
. Since
$Y\leqslant _c \iota (D_i\oplus {D_j}_{/(0,1)})$
, there is a reduction
$D_i\oplus D_j\leqslant _c D_i\oplus {D_j}_{/(0,1)} \oplus \operatorname {\mathrm {Id}}$
, and thus
$\iota (D_i\oplus D_j)\leqslant _c \iota (D_i\oplus {D_j}_{/(0,1)})$
, but we have already established that these are incomparable.
Claim 4.19. If
$\boldsymbol {\iota }(\mathbf {d}_i) \mathrel {H_{\boldsymbol {\iota }(\mathbf {c})}} \boldsymbol {\iota }(\mathbf {d_j})$
, then
$\mathbf {d}_i \mathrel {G_{\mathbf {c}}} \mathbf {d}_j$
.
Proof Let
$\boldsymbol {\iota }(\mathbf {d}_i) \mathrel {H_{\boldsymbol {\iota }(\mathbf {c})}} \boldsymbol {\iota }(\mathbf {d}_j)$
, and let
$\iota (A_0)\in \mathbf {a}, \iota (B_0)\in \mathbf {b}$
be a light covering pair of
$\boldsymbol {\iota }(\mathbf {d}_i), \boldsymbol {\iota }(\mathbf {d}_j)$
. By the computable inseparability of the classes of
$D_i$
and
$D_j$
,
$D_i,D_j\leqslant _c A_0$
and
$D_i,D_j\leqslant _c B_0$
. Since
$\boldsymbol {\iota }$
is a homomorphism onto the light degrees below
$\boldsymbol {\iota }(\mathbf {c})$
, any
$\mathbf {y}$
witnessing that
$\mathbf {a},\mathbf {b}$
is not a covering pair of
$\mathbf {d}_i,\mathbf {d}_j$
would be so that
$\boldsymbol {\iota }(\mathbf {y})$
witnesses
$\mathbf {a},\mathbf {b}$
are not a light covering pair of
$\boldsymbol {\iota }(\mathbf {d}_i)$
and
$\boldsymbol {\iota }(\mathbf {d}_j)$
. Thus we have
$\mathbf {d}_i \mathrel {G_{\mathbf {c}}} \mathbf {d}_j$
.
This concludes the proof of Lemma 4.17.
Next, we show that we can code any subset of any countable set of vertices. This will be used both for encoding the second-order part of graphs and also for selecting the substructure of
$H_{\boldsymbol {\iota }(\mathbf {c})}$
which is isomorphic to G.
Lemma 4.20. Let
$\{\mathbf {b}_i : i\in \omega \}$
be a collection of distinct light minimal degrees and
$S\subseteq \omega $
. Then, there is a degree
$\mathbf {c}$
so that
$\mathbf {b}_i\leqslant \mathbf {c}$
if and only if
$i\in S$
.
Proof Fix a sequence of representatives
$L_i\in \mathbf {b}_i$
. Intuitively, we construct
$X\in \mathbf {c}$
to encode each
$L_i$
with
$i\in S$
on the columns of
$\omega $
and then generically collapse equivalence classes between columns. Enumerate
$S=\{a_0<a_1<\cdots \}$
.
First we define
$X_0$
by
$$ \begin{align*} \langle n, i \rangle \mathrel{X_0} \langle m, j \rangle \Leftrightarrow i=j \wedge (n \mathrel{L_{a_i}} m). \end{align*} $$
Let
$\operatorname {\mathrm {Col}}_i=\lbrace \langle x, i\rangle : x\in \omega \rbrace $
, i.e., the ith column of
$\omega $
. For all i, denote by
$T_i\subseteq \operatorname {\mathrm {Col}}_i$
a transversal of
$X_0$
which hits all classes contained in the ith column. Next, let
$(f_i)_{i\in \omega }$
be a (mutually)
$1$
-generic sequence of permutations of
$\omega $
over a Turing degree which computes every
$L_i$
.
Then let
$X={X_0}_{/Z}$
with
$$ \begin{align*} Z = \{(T_u[v], T_0[f_u(v)]) : u,v\in \omega\}, \end{align*} $$
where we let
$T_u[v]$
denote the vth element of
$T_u$
(i.e., Z collapses the vth class in the uth column to the
$f_u(v)$
th class in the
$0$
th column of
$X_0$
).
Claim 4.21. For all
$i\in S$
,
$L_i\leqslant _c X$
.
Proof This follows from the fact that
$X_0$
encodes each
$L_i$
for
$i\in S$
as a column, and the quotient X does not collapse equivalence classes from the same column.
Suppose towards a contradiction that
$g\colon L_j\leqslant X$
for some
$j\notin S$
.
Claim 4.22. There is some k so that
$\operatorname {\mathrm {range }}(g)\subseteq ^* \operatorname {\mathrm {Col}}_k$
.
Proof Let V be the set of finite sequences of finite injective partial maps
$(p_i)_{i\leqslant m}$
so that for some
$x,y$
, letting
$i,l,n,m$
be such that
$g(x)\mathrel {X_0} T_i[n]$
and
$g(y)\mathrel {X_0} T_l[m]$
, we have
. Observe that if
$\operatorname {\mathrm {range }}(g)$
is not almost contained in a single column, then V is dense (i.e., for any finite sequence of finite injective partial maps
$(p_i)_{i\leqslant m}$
there is a sequence
$(q_i)_{i\leqslant n}$
with
$n\geq m$
of injective partial maps so
$p_i\subseteq q_i$
for
$i\leqslant m$
, and
$(q_i)_{i\leqslant n}\in V$
). But then by genericity of
$(f_i)_{i\in \omega }$
, it will meet V, which contradicts g being a reduction of
$L_j$
to X.
Let i be fixed so that
$\operatorname {\mathrm {range }}(g)\subseteq ^* \operatorname {\mathrm {Col}}_i$
. Since
$\operatorname {\mathrm {range }}(g)$
intersects only finitely many columns, we can assume that it intersects the minimal possible number of columns. If
$\operatorname {\mathrm {range }}(g)\subseteq \operatorname {\mathrm {Col}}_i$
, then
$L_j\leqslant _c L_i$
, which is a contradiction to
$L_j$
and
$L_i$
being inequivalent light minimal equivalence relations. So, suppose that
$\operatorname {\mathrm {range }}(g)$
intersects
$\operatorname {\mathrm {Col}}_k$
for
$k\neq i$
. Let us consider the finite equivalence relation
$Y=L_j{\restriction} g^{-1}(\operatorname {\mathrm {Col}}_k)$
. If all Y-classes were computable, then we could adjust g to send each of these sets to a representative of the same class in
$\operatorname {\mathrm {Col}}_i$
contradicting that g uses the minimal possible number of columns. So
$Y\in \mathcal {F}\smallsetminus \mathcal {I}$
and
$Y\leqslant L_j$
and
$Y\leqslant L_k$
. But Theorem 2.21 shows that there is a least upper bound Z of
$\operatorname {\mathrm {Id}}$
and Y. Then
$\operatorname {\mathrm {Id}}<_c Z\leqslant L_j,L_k$
contradicting that
$L_j$
and
$L_k$
are inequivalent light minimal equivalence relations.
If
$\mathbf {a}$
is light, then let
$M_{\mathbf {a}}$
be the set of light minimal degrees below
$\mathbf {a}$
. It follows that for every second-order countable graph G, there are parameters
$\mathbf {e},\mathbf {b}$
so that
$(G,P(G))\cong (H_{\mathbf {e}}\cap M_{\mathbf {b}}, \mathcal {A})$
where
$\mathcal {A}$
is the collection of sets
$H_{\mathbf {e}}\cap M_{\mathbf {b}}\cap M_{\mathbf {a}}$
for various light degrees
$\mathbf {a}$
.
As remarked in Section 4.1, this suffices to conclude that the theory of
$\operatorname {\mathrm {\mathbf {Light}}}$
is computably isomorphic to second-order arithmetic.
Acknowledgments
Andrews was partially supported by NSF grant DMS-1600228. San Mauro was partially supported by the Austrian Science Fund, project M 2461.
