1 Introduction
The Turing degrees,
$\mathcal {D}_T$
, measure the computability-theoretic complexity of sets of natural numbers. By coding, they can be used to measure the complexity of other mathematical objects. For example, a real number r in the unit interval can be coded by a function
$n_r:\mathbb {Q}^+\rightarrow \mathbb {Q}$
that takes as input a positive
$\varepsilon $
and outputs a rational number q within
$\varepsilon $
of r. We call
$n_r$
a name for r. A real number is thus associated with a set of names, which are discrete objects and hence have Turing degree. It is not difficult to see that every real number has a name of least Turing degree: the degree of its binary expansion. In this way, we can associate a Turing degree to every real number r. In many cases, however, the Turing degrees are not sufficient to measure the complexity of objects studied in effective mathematics. An early example of this phenomenon was given by Richter [Reference Richter19], who proved that we cannot associate a Turing degree to every countable linear ordering. In fact, the only countable linear orderings that have a Turing degree are the ones with computable presentations. In search for an answer to a similar question—“Does every continuous function on the unit interval have a name of least Turing degree?”—Miller [Reference Miller15] introduced the continuous degrees to measure of the complexity of continuous functions, and, more generally, points in computable metric spaces. He proved that the Turing degrees properly embed into the continuous degrees, and that the continuous degrees, in turn, properly embed into the enumeration degrees.
Enumeration reducibility,
$\leq _e$
, and the enumeration degrees,
$\mathcal {D}_e$
, were introduced by Friedberg and Rogers [Reference Friedberg and Rogers5]. They form a natural extension of the Turing degrees: by mapping the Turing degree of a set A to the enumeration degree of
we get an embedding
$\iota $
of
$\mathcal {D}_T$
into
$\mathcal {D}_e$
. The image of a Turing degree is called a total enumeration degree. So, the enumeration degrees turn out to be sufficient to capture the effective content of a continuous function on the unit interval: there is a least enumeration degree such that the total degrees bounding it are exactly (the images of) the Turing degrees of names of the continuous function. The enumeration degrees of continuous functions give us a proper subclass of the enumeration degrees: the continuous enumeration degrees.
The study of the continuous enumeration degrees has revealed an important connection between degree theory and topology. All proofs that nontotal continuous enumeration degrees exists—in other words, that the continuous degrees are a proper extension of the Turing degrees—have used nontrivial topological theorems. Miller’s original proof [Reference Miller15] uses a variant of Brouwer’s fixed point theorem for multivalued functions on the Hilbert cube. Levin’s construction of a neutral measure [Reference Levin13] uses Sperner’s lemma and was shown by Day and Miller [Reference Day and Miller4] to also produce a nontotal continuous degree. More recently, Kihara and Pauly [Reference Kihara and Pauly12] and independently Hoyrup (unpublished) use facts from topological dimension theory to prove the existence of a nontotal continuous enumeration degree. The connection can be followed in the reverse direction as well. For example, a structural property of the continuous enumeration degrees was the main tool in Kihara and Pauly’s [Reference Kihara and Pauly12] solution to the second level Borel isomorphism problem; they constructed an uncountable Polish space which is neither second-level Borel isomorphic to the unit interval nor to the Hilbert cube.
Andrews et al. [Reference Andrews, Igusa, Miller and Soskova2] have recently given several characterizations of the continuous enumeration degrees as a subclass of the enumeration degrees, including a characterization via a simple structural property: an enumeration degree
$\mathbf {a}$
is almost total if and only if for every total enumeration degree
$\mathbf {x}\nleq \mathbf {a}$
we have that
$\mathbf {x}\lor \mathbf {a}$
is a total degree. An enumeration degree is continuous if and only if it is almost total. The total enumeration degrees were shown to be definable by Cai et al. [Reference Cai, Ganchev, Lempp, Miller and Soskova3], and so the continuous enumeration degrees also form a definable subclass of the enumeration degrees.
Another class of enumeration degrees that has been studied extensively is the class of Kalimullin pairs or
$\mathcal {K}$
-pairs,Footnote
1
introduced by Kalimullin [Reference Kalimullin10]. A pair of sets
$\{A,B\}$
form a
$\mathcal {K}$
-pair relative to U if and only if there is some set
$W\leq _e U$
such that
$A\times B\subseteq W$
and
.
$\mathcal {K}$
-pairs lie at the heart of most natural definability results in the enumeration degrees. Kalimulin [Reference Kalimullin10] proved that they have a natural structural definition—they are the degrees
$\{\mathbf {a}, \mathbf {b}\}$
that form a robust minimal pair relative to a degree
$\mathbf {u}$
: for all
$\mathbf {x}\geq \mathbf {u}$
we have that
$\mathbf {x} = (\mathbf {a}\lor \mathbf {x})\land (\mathbf {b}\lor \mathbf {x})$
. He then used them to define the enumeration jump operator. Ganchev and Soskova [Reference Ganchev and Soskova6] proved that
$\mathcal {K}$
-pairs are definable in
$\mathcal {D}(\leq \mathbf {0}_e)$
, the substructure of the
$\Sigma ^0_2$
enumeration degrees, and used them to prove the first order definability of a series of subclasses of
$\mathcal {D}(\leq \mathbf {0}_e)$
, including the total
$\Delta ^0_2$
enumeration degrees [Reference Ganchev and Soskova7], the downwards properly
$\Sigma ^0_2$
enumeration degrees, the upwards properly
$\Sigma ^0_2$
enumeration degrees [Reference Ganchev and Soskova6], and the Low
$_n$
and High
$_n$
enumeration degrees, for all
[Reference Ganchev and Soskova8]. A special type of
$\mathcal {K}$
-pairs—the maximal
$\mathcal {K}$
-pairs—were used by Cai et al. [Reference Cai, Ganchev, Lempp, Miller and Soskova3] to define the total enumeration degrees.
In this paper we study the relationship between the continuous degrees and
$\mathcal {K}$
-pairs more closely. We give several new characterizations of continuous degrees, leading up to our main new characterization: an enumeration degree is continuous if and only if it is not half of a nontrivial
$\mathcal {K}$
-pair relative to any enumeration degree. This new characterization gives a simpler first order definition of the continuous enumeration degrees in terms of quantifier complexity. In the language with
$\leq $
and
$\lor $
, the definition via almost total degrees is
$\Pi _3$
, while the definition via
$\mathcal {K}$
-pairs is
$\Pi _2$
. It also allows for an interesting structural dichotomy in the enumeration degrees. Recall that an enumeration degree
$\mathbf {a}$
is a strong quasiminimal cover of
$\mathbf {b}$
if and only if
$\mathbf {a}>\mathbf {b}$
and for all total enumeration degrees
$\mathbf {x}$
, if
$\mathbf {x}\leq \mathbf {a}$
then
$\mathbf {x} \leq \mathbf {b}$
. The characterization of the continuous degrees as almost total, along with properties of nontrivial
$\mathcal {K}$
-pairs allow us to derive the following:
Theorem 1.1. For every enumeration degree
$\mathbf {a}$
, exactly one of the following two properties holds:
-
(1) The degree
$\mathbf {x}$
is continuous, so for every total enumeration degree
$\mathbf {x}\nleq \mathbf {a}$
,
$\mathbf {a} \lor \mathbf {x}$
is total. -
(2) There is a total enumeration degree
$\mathbf {x}\nleq \mathbf {a}$
such that
$\mathbf {a} \lor \mathbf {x}$
is a strong quasiminimal cover of
$\mathbf {x}$
.
A subclass of the enumeration degrees that is larger than the continuous enumeration degrees is the cototal degrees. A degree is cototal if it contains a cototal set, that is, a set A, such that
. This class arises naturally in many areas of effective mathematics, including graph theory [Reference Andrews, Ganchev, Kuyper, Lempp, Miller, Soskova and Soskova1], symbolic dynamics [Reference McCarthy14] and computable structure theory [Reference McCarthy14]. The cototal enumeration degrees also reveal a topological connection: Kihara et al. [Reference Kihara, Ng and Pauly11] showed that the cototal enumeration degrees are the degrees of points in computably
$G_{\delta }$
topological spaces. Miller and Soskova [Reference Miller and Soskova17] prove that they form a dense substructure of the enumeration degrees, viewed as an upper-semilattice with jump operation. We study the connection between cototal sets and
$\mathcal {K}$
-pairs. Our investigation leads us to a conjecture that, if true, would yield the first order definability of the cototal enumeration degrees within the structure of the enumeration degrees.
We end with an alternative characterization of the continuous degrees in terms of the relation “PA above” extended to enumeration oracles, introduced by Miller and Soskova [Reference Miller and Soskova16]. This new characterization opens up many questions for future work on this topic.
2 Preliminaries
We start by giving formal definitions of standard notions used throughout this paper. For a more thorough exposition on degree theory, we refer the reader to Odifreddi [Reference Odifreddi18].
2.1 Enumeration reducibility and the enumeration degrees
Definition 2.1 (Friedberg and Rogers [Reference Friedberg and Rogers5])
$A\leq _e B$
if and only if there is a c.e. set W such that
$$\begin{align*}A = W(B) = \{x \colon (\exists v)\;{\left\langle{x,v}\right\rangle}\in W\ \&\ D_v\subseteq B\}. \end{align*}$$
Here
$D_v$
denotes the finite set with code v in the standard coding of finite sets. The set W is called an enumeration operator and the pair
${\left \langle {x,D_v}\right \rangle }$
is called an axiom for x in W.
We will abuse notation and think of an enumeration operator interchangeably as a c.e. set of numbers or as a set of axioms
${\left \langle {x,D}\right \rangle }$
, where D is a finite set.
Enumeration reducibility gives rise to a degree structure as usual: A is enumeration equivalent,
$\equiv _e$
, to B if
$A\leq _e B$
and
$B\leq _e A$
; the enumeration degree of a set A is
$d_e(A) = \{B \colon A\equiv _e B\}$
. The preorder
$\leq _e$
on sets induces a partial order on the enumeration degrees,
$\mathcal {D}_e$
. The least enumeration degree
$\mathbf {0}_e$
consists of all c.e. sets. We can supply
$\mathcal {D}_e$
with a least upper bound operation by setting
, where
. We can also define a jump operator:
, where
and
is some fixed computable enumeration of all c.e. sets, or equivalently enumeration operators.
As mentioned above, the Turing degrees can be embedded into the enumeration degrees. The reason should now be clear: it follows easily from the definition of enumeration reducibility that
$A\leq _T B$
if and only if
.
Definition 2.2. A set A is total if
(i.e., if
). An enumeration degree is total if it contains a total set.
The set of total enumeration degrees as an upper semilattice with jump operation is an isomorphic copy of the Turing degrees.
Selman [Reference Selman20] provided a useful alternative way to think about enumeration reducibility. An enumeration of a set A is a total function
with range equal to A. The definition of enumeration reducibility given above can be restated as follows: A is enumeration reducible to B if there is a uniform way to compute an enumeration of A from an enumeration of B. Selman proved that the uniformity condition is not necessary.
Theorem 2.3 (Selman [Reference Selman20])
$A\leq _e B$
if and only if every enumeration of B computes an enumeration of A.
2.2 The continuous degrees
A computable presentation of a metric space
$\mathcal {M}$
consists of a fixed dense sequence
on which the metric is computable as a function on indices. Metric spaces with computable presentations include Cantor space
, Baire space
, the continuous functions on the unit interval
$\mathcal {C}[0,1]$
, the Hilbert cube
, and many others. For a computable presentation of
$\mathcal {C}[0,1]$
, for example, we fix an effective enumeration of the polygonal functions having segments with rational endpoints. A name for a point x in a computable metric space is a function
that gives a way to approximate x via the sequence
$Q^{\mathcal {M}}$
: it takes a rational number
$\varepsilon>0$
as input and produces an index
$n_x(\varepsilon )$
such that
$d_{\mathcal {M}}(x, q_{n_x(\varepsilon )}) < \varepsilon $
. Such names can easily be coded as elements of Baire space. For points
$x,y$
in (possibly different computably presented metric spaces), we say that x reduces to y if every name for y uniformly computes a name for x. This reducibility induces a degree structure, the continuous degrees. Miller [Reference Miller15] proves that there are universal computably presented metric spaces: every continuous degree contains an element of
$\mathcal {C}[0,1]$
and, more importantly for our purposes, also an element of
.
In order to understand the embedding of the continuous degrees into the enumeration degrees, we use the fact that the Hilbert cube
is universal. We take the usual metric on the Hilbert cube:
. A dense set witnessing that
is computable is, for example, a computable enumeration of the rational sequences with finite support. Given
, consider the set
Miller [Reference Miller15] proved that enumerating
$C_{\alpha }$
is just as difficult as computing a name for
$\alpha $
. Thus the map
$\alpha \mapsto C_{\alpha }$
induces an embedding of the continuous degrees into the enumeration degrees.
Definition 2.4. An enumeration degree
$\mathbf {a}$
is continuous if it contains a set of the form
$C_{\alpha }$
, where
.
Note that the ith component of
$C_{\alpha }$
is very close to a total set in structure:
, unless
$\alpha (i)$
is rational. The nonuniformity introduced by the rational components of some
suffice to produce nontotal enumeration degrees:
Theorem 2.5 (Miller [Reference Miller15])
There are nontotal continuous degrees.
We will use two of the three characterizations of continuous enumeration degrees proved in [Reference Andrews, Igusa, Miller and Soskova2]. We restate the definition of an almost total degree for convenience:
Definition 2.6. We say that an enumeration degree
$\mathbf {a}$
is almost total if whenever
$\mathbf {b}\nleq \mathbf {a}$
is total,
$\mathbf {a}\vee \mathbf {b}$
is also total.
The second characterization relies on an extension of the notion of a
$\Pi ^0_1$
class to an enumeration oracle. We will use
${\left \langle {A}\right \rangle }$
to indicate that we are treating A as an enumeration oracle rather than a Turing oracle.
Definition 2.7. Let
. Call
a
$\Sigma ^0_1{\left \langle {A}\right \rangle }$
class if there is a set
$W \leq _e A$
, such that
. A
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class is the complement of a
$\Sigma ^0_1{\left \langle {A}\right \rangle }$
class.
Note that a
class is just a
$\Pi ^0_1[A]$
class in the usual sense. Further, note that the elements of a
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class are infinite binary sequences, hence total objects. Thus, when we say that a set enumerates a member of a
$\Pi ^0_1$
class, we mean that the set enumerates
, for some X such that the binary sequences representing X is in the
$\Pi ^0_1$
class.
Definition 2.8. A set
is codable if there is a nonempty
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class
such that for every
$X\in P$
, A is c.e. relative to X.
Theorem 2.9 (Andrews et al. [Reference Andrews, Igusa, Miller and Soskova2])
Fix
. The following are equivalent
-
(1) The enumeration degree of A is almost total;
-
(2) A is codable;
-
(3) A has continuous enumeration degree.
2.3 Kalimullin pairs
Consider once again the definition of a relativized Kalimullin pair.
Definition 2.10 (Kalimullin [Reference Kalimullin10])
A pair of sets of natural numbers
$\{A,B\}$
is a Kalimullin pair (
$\mathcal {K}$
-pair) relative to a set U if there is a set
$W\leq _e U$
such that
$A\times B\subseteq W$
and
.
It is very easy to come up with an example of a
$\mathcal {K}$
-pair relative to any U: if
$B\leq _e U$
, then for every set A we have that
$\{A, B\}$
is a
$\mathcal {K}$
-pair relative to U as witnessed by
. Similarly, if
$A\leq _e U$
.
$\mathcal {K}$
-pairs of this sort are not interesting; we call the trivial. Nontrivial
$\mathcal {K}$
-pairs exist: a standard example of a
$\mathcal {K}$
-pair relative to
is given by a the pair
, where A is any semicomputable set. Semicomputable sets were introduced and studied by Jockusch [Reference Jockusch9]. He showed that A is semicomputable if and only if A is a left cut in some computable linear ordering on
. He also showed that every nonzero Turing degree contains a semicomputable set that is neither c.e. nor co-c.e.
$\mathcal {K}$
-pairs have many interesting properties. For example, if we fix A and consider the set
$\mathcal {K}(A) =\{B \colon \{A,B\} \text { is a } \mathcal {K}\text{-pair}\}$
, then
$\mathcal {K}(A)$
is an ideal with respect to
$\leq _e$
. In particular, being half of a
$\mathcal {K}$
-pair is a degree notion. We summarize the properties that we will use in the following theorem.
Theorem 2.11 (Kalimullin [Reference Kalimullin10])
Let
$\{A,B\}$
be a nontrivial
$\mathcal {K}$
-pair relative to U as witnessed by W.
-
(1)
and
. -
(2)
and
. -
(3)
and
are strong quasiminimal covers of
$d_e(U)$
We will also need the structural definition of
$\mathcal {K}$
-pairs as robust minimal pairs.
Theorem 2.12 (Kalimullin [Reference Kalimullin10])
A pair of sets
$\{A,B\}$
are a
$\mathcal {K}$
-pair relative to U if and only if their enumeration degrees
$\mathbf {a}$
,
$\mathbf {b}$
, and
$\mathbf {u}$
satisfy:
$$\begin{align*}(\forall\mathbf{x}\geq \mathbf{u})[(\mathbf{a}\lor \mathbf{x} )\land (\mathbf{b}\lor \mathbf{x}) = \mathbf{x}]. \end{align*}$$
3 Functions that are codable by extensions
Our first characterization of the continuous enumeration degrees, and the one that motivated this work, concerns the notion of a function codable by its extensions.
Definition 3.1. A function
is codable by extensions if for every extension
$h\supseteq f$
we have that
$G_f \leq _e G_h$
, where
$G_x$
denotes the graph of x.
Clearly, every total function is codable by extensions, because its only extension is the function itself. The notion becomes interesting when one considers graphs of nontotal functions. We prove below that the enumeration degrees of the graphs of functions that are codable by extensions are exactly the continuous enumeration degrees.
Theorem 3.2. An enumeration degree is continuous if and only if it contains the graph of a function that is codable by extensions.
Proof. Suppose that
$\mathbf {a}$
is continuous and fix an element of the Hilbert cube
so that
$\mathbf {a} = d_e(C_{\alpha })$
, where
Consider the function
such that
$$\begin{align*}f({\left\langle{n,q}\right\rangle}) = \begin{cases} 0,\quad \text{if }q<\alpha(n); \\ 1,\quad \text{if } \alpha(n)<q. \end{cases} \end{align*}$$
Note, that if
$\alpha (n) = q$
then
$f({\left \langle {n,q}\right \rangle })$
is undefined. Clearly,
$C_{\alpha }\equiv _e G_f$
. Furthermore, for any extension h of f, we have that
Hence
$G_f\equiv _e C_{\alpha }\leq _e G_h$
, and so f is codable by extensions.
For the reverse direction, let f be a function that is codable by extensions. Consider the set P of the graphs of all extensions of f. Then P is a
$\Pi ^0_1{\left \langle {G_f}\right \rangle }$
class, as
, where S is the set of finite binary strings that are not initial segments of the characteristic function of the graph of some extension of f. In other words,
$\sigma \in S$
if and only if
$$ \begin{align*} (\exists x, y, z)&\quad\left[\sigma({\left\langle{x, y}\right\rangle}) = \sigma({\left\langle{x,z}\right\rangle}) = 1\ \&\ y\neq z\right] \\ \text{or }(\exists x, y)&\quad\left[{\left\langle{x,y}\right\rangle}\in G_f\ \&\ \sigma({\left\langle{x,y}\right\rangle})= 0\right]. \end{align*} $$
Every member of the class P can enumerate
$G_f$
, hence
$G_f$
is codable and so
$G_f$
has continuous degree by Theorem 2.9. ⊣
The characterizations of the continuous degrees via functions that are codable by extensions leads to a connection with the notion of a nontrivial
$\mathcal {K}$
-pair, or rather the opposite: a continuous degree can never be a part of a nontrivial
$\mathcal {K}$
-pair relative to any set U.
Proposition 3.3. If f is codable by extensions, then
$G_f$
is not half of any relativized nontrivial
$\mathcal {K}$
-pair.
Proof. Suppose towards a contradiction that
$G_f$
is codable by extensions and the pair
$\{G_f, B\}$
is a nontrivial
$\mathcal {K}$
-pair relative to some set U. Let
$W\leq _e U$
witness this. If for some b we find that
${\left \langle {{\left \langle {x,y}\right \rangle },b}\right \rangle }\in W$
and
${\left \langle {{\left \langle {x,z}\right \rangle }, b}\right \rangle }\in W$
, where
$y\neq z$
, then
ensures that
$b\in B$
. Since
$B\nleq _e W$
, there must be some
$b\in B$
for which the above is not true and hence
$\{{\left \langle {x,y}\right \rangle } \colon {\left \langle {\left \langle {x,y}\right \rangle ,b}\right \rangle }\in W\}$
is the graph of a function h, and
$G_h\leq _e W$
. As
$G_f\times B\subseteq W$
, it follows that
$f\subseteq h$
, so
$G_f\leq _e G_h\leq _e U$
, contrary to our assumption that
$\{G_f, B\}$
is nontrivial relative to U. ⊣
A natural questions arises: does this property characterize the continuous degrees? This will be proved in Section 5.
4 Array-avoiding sets
Towards a positive answer to the question posed at the end of the previous section, we explore a combinatorial characterization of the continuous degrees.
Definition 4.1. We say that A is array-avoiding if
and for every computable sequence of finite sets
such that for every n we have that
$D_n\nsubseteq A$
, there is some
$C\supseteq A$
such that for every n we still have
$D_n\nsubseteq C$
, but also
$A\nleq _e C$
.
The property above is trivially satisfied by
, just because there cannot be a sequence of finite sets
such that for every n we have that
; for that reason we exclude it from the definition. Array-avoiding sets capture the noncontinuous degrees.
Theorem 4.2. The enumeration degree
$\mathbf {a}$
is continuous if and only if some set in
$\mathbf {a}$
is not array-avoiding, if and only if no set in
$\mathbf {a}$
is array-avoiding.
Proof. Suppose first that
$\mathbf {a}$
is continuous and fix a partial function f such that
$G_f\in \mathbf {a}$
and f is codable by extensions. We will build a computable sequence of finite sets
that ensures
$G_f$
is not array-avoiding. The sequence is quite simple: it is just a computable listing of all pairs
$\{{\left \langle {x,y}\right \rangle },{\left \langle {x,z}\right \rangle }\}$
where
$y\neq z$
. Any
$C\supseteq G_f$
that retains the property that
$D_n\nsubseteq C$
for every n is the graph of some extension of f, and hence
$G_f\leq _e C$
.
We can extend this idea to every set in the degree
$\mathbf {a}$
. Fix
$A\in \mathbf {a}$
and let
$\Gamma $
be such that
$G_f = \Gamma (A)$
. Consider the sequence
that lists finite sets
$F\cup E$
, such that
${\left \langle {{\left \langle {x,y}\right \rangle }, F}\right \rangle }\in \Gamma $
and
${\left \langle {{\left \langle {x,z}\right \rangle }, E}\right \rangle }\in \Gamma $
for some
$y\neq z$
. (Note that, assuming
, we can ensure that this is a nonempty sequence by finitely modifying
$\Gamma $
.) Clearly,
$D_n\nsubseteq A$
for every n. On the other hand, if
$C\supseteq A$
and C still has the property that
$D_n\nsubseteq C$
for all n, then
$\Gamma (C)$
is the graph of a function
$h\supseteq g$
and hence
$A\leq _e G_f\leq _e G_h\leq _e C$
.
For the reverse direction, suppose that A is not array-avoiding. Let
be a computable sequence of sets that witnesses this. In other words, if
$C\supseteq A$
has the property that
$D_n\nsubseteq C$
for all n, then
$A\leq _e C$
. Then A is easily seen to be codable because the set of all supersets
$C\supseteq A$
that satisfy
$D_n\nsubseteq C$
for all n is a
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class
, where
$\sigma \in S$
if and only if
$\sigma (x) = 0$
for some
$x\in A$
or
$D_n\subseteq {x} \colon {\sigma (x) = 1}$
for some n. It is nonempty as
$A\in P$
, and by assumption, every member of P enumerates A. ⊣
We will not give a direct proof that being array-avoiding implies being half of a nontrivial
$\mathcal {K}$
-pair, although it will follow from the work in the next section. For now, as a warm-up, we will prove that an apparent strengthening of array-avoiding is equivalent to being half of a nontrivial
$\mathcal {K}$
-pair.
Definition 4.3. We say that A is uniformly array-avoiding if
and there is a Z such that
$A\nleq _e Z$
and for every computable sequence of finite sets
such that
$D_n\nsubseteq A$
for every n, there is a
$C\supseteq A$
such that we still have
$D_n\nsubseteq C$
for every n, but also
$C\leq _e Z$
.
The proof of the nontrivial direction in the theorem below outlines the main ideas that ultimately lead to the full characterization of noncontinuous enumeration degrees as halves of nontrivial
$\mathcal {K}$
-pairs.
Theorem 4.4. A is half of a nontrivial
$\mathcal {K}$
-pair if and only if A is uniformly array-avoiding.
Proof. Suppose first that
$\{A, B\}$
is a nontrivial
$\mathcal {K}$
-pair relative to some set U as witnessed by W. We will show that A is uniformly array-avoiding with
$Z=W$
. Nontriviality ensures that
$A\nleq _e W$
. Now let
be a computable sequence of finite sets such that
$D_n\nsubseteq A$
for all n. Consider the set
$$\begin{align*}B_0 = \{b \colon (\exists n)\; D_n\times\{b\}\subseteq W\}. \end{align*}$$
Then
$B_0\subseteq B$
and
$B_0\leq _e W$
. But
$B\nleq _e W$
, so we can pick some element
$b\in B\setminus B_0$
. Now, consider the set
$C = \{a \colon {\left \langle {a,b}\right \rangle }\in W\}$
. The set C extends A and satisfies the property that for every n the set
$D_n\nsubseteq C$
(or else
$b\in B_0$
). On the other hand,
$C\leq _e W$
. Hence A is uniformly array-avoiding.
Now let A be uniformly array-avoiding as witnessed by Z. We will build sets B and W such that
$A,B\nleq _e W$
,
$A\times B\subseteq W$
, and
. The construction proceeds by stages. At stage n, we build finite sets
$B_n$
,
$B_n^-$
, and
$W_n$
satisfying the following four conditions:
-
(1)
$B_n\subseteq B_{n+1}$
,
$B^{-}_n\subseteq B^{-}_{n+1}$
,
$W_n\subseteq W_{n+1}$
; -
(2)
; -
(3)
; -
(4)
${\left \langle {a,b}\right \rangle }\in W_n\Rightarrow (a\in A \lor b\in B_n)$
.
We let
$B = \bigcup _n B_n$
and
$W = \bigcup _n W_n$
. Properties (1), (3), and (4) ensure that
$\{A, B\}$
is a
$\mathcal {K}$
-pair relative to W. What remains is to ensure that
$A,B\nleq _e W$
. In order to do this, we ensure that our construction of the sets B and W satisfies the requirements
$A\neq \Gamma _k(W)$
and
$B\neq \Gamma _k(W)$
for every k, where
is some effective listing of all enumeration operators. During the construction to every element
$x\in B_n$
we will associate a superset
$C_x\supseteq A$
such that
$C_x\leq _e Z$
. Unless otherwise stated
. The set
$C_x$
may be shrunk infinitely many times, but will always be a superset of A. We will also associate to every
$y\in B_n^-$
a finite set
$T_y\subseteq A$
. Once defined,
$T_y$
will not be changed. (In fact,
$T_y$
will be the yth column of W. We will not use this fact here, but it will be needed in Proposition 6.3.)
We start the construction by setting
. Suppose we have constructed
$B_n$
,
$B_n^-$
, and
$W_n$
and consider the set
By property
$(1)$
, it follows that for every n we have that
$X_{n+1}\subseteq X_n$
. We will ensure that
$W_{n+1}\subseteq X_n$
, and so
$W\subseteq X_n$
for every n. We have two cases, depending on whether we are at an even or an odd stage.
Suppose that
${n = 2k}$
. We ensure that
$A\neq \Gamma _k(W)$
, where
is some effective listing of all enumeration operators. Note that
$X_n \leq _e \bigoplus _{x\in B_n} C_x\leq _e Z$
, so
$A \neq \Gamma _k(X_n)$
. Fix an element a that witnesses this difference.
Case 1. If
$a\in A$
, then we set
$W_n^* = W_n$
. Note, that
$W\subseteq X_n$
ensures that we have satisfied our requirement.
Case 2. If
$a\in \Gamma _k(X_n)$
, fix an axiom
${\left \langle {a,D}\right \rangle }\in \Gamma _k$
such that
$D\subseteq X_n$
. We set
$W_n^* = W_n\cup D$
. We will ensure that
$W_n^*\subseteq W_{n+1}$
, hence once again we will have satisfied our requirement.
We set
. Note that
$B_{n+1}$
does not contain any element from
$B_n^-$
, because if
${\left \langle {a,y}\right \rangle }\in X_n$
and
$y\in B_n^-$
then
$a\in T_y\subseteq A$
. We set
$B_{n+1}^- = B_n^-$
and set
. It is straightforward to check that properties (1)–(4) still hold.
Suppose that
${n = 2k+1}$
. In this case, we would like to ensure that
$B\neq \Gamma _k(W)$
. If
$\Gamma _k(X_n)$
is finite, then we do not need to do anything; by a close inspection of the even stages, B will be infinite. So suppose that
$\Gamma _k(X_n)$
is infinite and fix
$z\in \Gamma _k(X_n)\setminus B_n\cup B_n^-$
. We would like to use this z to create a difference. Pick an axiom
${\left \langle {z, D}\right \rangle }\in \Gamma _k$
such that
$D\subseteq X_n$
. If we can enumerate z into
$B_{n+1}^-$
and D into
$W_{n+1}$
then this would accomplish the desired difference. Unfortunately, this might be in conflict with our desire to preserve properties
$(2)$
and
$(4)$
, namely it could be that
${\left \langle {a, z}\right \rangle }\in D$
for some
. So, we will be more careful and consider the following two cases:
Case 1. There is an axiom
${\left \langle {z,D}\right \rangle }\in \Gamma _k$
such that for all
${\left \langle {a,x}\right \rangle }\in D$
:
-
(1) if
$x\in B_n\cup \{z\}$
, then
${\left \langle {a,x}\right \rangle }\in W_n$
or
$a\in A$
; -
(2) if
$x\in B_n^-$
, then
$a\in T_x$
.
Note that these conditions ensure that
$D\subseteq X_n$
. In this case, we can proceed with our original plan: we set
$W_n^* = W_n\cup D$
and
$B_{n+1} = B_n\cup \{b \colon (\exists {\left \langle {a,b}\right \rangle }\in D)\; a\notin A\}$
. We set
$B_{n+1}^- = B_n^-\cup \{z\}$
and
$T_z = {a} \colon {{\left \langle {a,z}\right \rangle }\in W_n^*}$
. Note that
$T_z\subseteq A$
by our choice of D. Finally, we set
. Once again it is easy to see that properties (1)–(4) still hold.
Case 2. Every axiom
${\left \langle {z,D}\right \rangle }\in \Gamma _k$
such that
$$\begin{align*}(\forall x\in B^-_n)\; \text{if } {\left\langle{a,x}\right\rangle}\in D, \text{ then } a\in T_x, \end{align*}$$
has the property that
$\{a \colon (\exists x\in B_n\cup \{z\})\; {\left \langle {a,x}\right \rangle }\in D\setminus W_n\}\nsubseteq A$
. In that case, the sequence
listing all such sets—which is nonempty as
$z\in \Gamma _k(X_n)$
—is a computable sequence of finite sets such that for all m, we have that
$F_m\nsubseteq A$
. By the uniform array-avoidance of A, there is a
$C\supseteq A$
such that
$C\leq _e Z$
and C still has the property that
$F_m\nsubseteq C$
for all m. We set
$C_z = C$
and for every
$x\in B_n$
we give the parameter
$C_x$
a new value namely
$(C_{x}\cap C)\cup \{a \colon {\left \langle {a,x}\right \rangle }\in W_n\}$
and we set
$B_{n+1} =B_n\cup \{z\}$
. This ensures that
$z\notin \Gamma _k(X_{n+1})$
, as every axiom for z in
$\Gamma _k$
that satisfies the restriction imposed by
$B_n^-$
on
$X_{n+1}$
contains an element
${\left \langle {a,x}\right \rangle }$
such that
$x\in B_{n+1}$
and
${\left \langle {a,x}\right \rangle }\notin W_n\cup C$
. We have thus satisfied our requirement. We set
$B_{n+1}^- = B_n^-$
and
. ⊣
5 Forcing with
$\Pi ^0_1{\left \langle {A}\right \rangle }$
classes
We use the main ideas from the proof of Theorem 4.4 to show the link between
$\mathcal {K}$
-pairs and the noncontinuous degrees.
Theorem 5.1. If A does not have continuous degree, then A is half of a nontrivial relativized
$\mathcal {K}$
-pair.
Proof. We will use a forcing notion
$\mathcal {F}$
to construct B and W, so that
$B\times A\subseteq W$
,
, and
$A,B\nleq _e W$
. A forcing condition p has the form
, where
,
is a sequence of finite binary strings such that for all
$i\geq |\beta |$
,
, and P is a nonempty
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class, satisfying a certain list of properties that we describe below. We think of P as subset of
, that is, every element
$X\in P$
codes a sequence of sets
(in fact,
$X = \bigoplus _k X_k$
). We let
$P_i$
consist of the i-th projection of the elements in P, that is,
It is not difficult to see that each
$P_i$
is also a
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class, although that will not be relevant for the construction. We think of each element
$X\in P$
as providing a bound on W, in the sense that
$W\subseteq X$
for some
$X\in P$
. We think of
$ \beta $
as an initial segment of the set B. Every
$\sigma _i$
codes a finite set
$D_i = \{x \colon \sigma _i(x) = 1\}$
. We approximate W by
. We ask that, in addition, forcing conditions satisfy the following properties:
-
(1) If
$\beta (i) = 0$
, then
$D_i\subseteq A$
and
. -
(2) If
$\beta (i) \neq 0$
, then for every
$X\in P_i$
, we have that
$\sigma _i\preceq X$
and
$A\subseteq X$
. -
(3) If
$X\in P$
and
$Y\subseteq X$
is such that if we write Y as
$\bigoplus _iY_i$
, then for every i we have that the above two conditions hold, that is,-
• if
$\beta (i) = 0$
, then
and -
• if
$\beta (i)\neq 0$
, then
$\sigma _i\preceq Y_i$
and
$A\subseteq Y_i$
;
then
$Y\in P$
. -
Note that the forcing condition ensures that
$W_p\subseteq X$
for all
$X\in P$
.
We say that a condition
extends a condition
, written as
$q\leq p$
, if
-
•
$\beta \preceq \gamma $
; -
• for all i,
$\sigma _i \preceq \tau _i$
; -
• each
$X\in Q$
is a subset of some
$Y\in P$
.
We build a sequence of conditions
$p_0\geq p_1 \geq p_2 \geq \cdots $
. In the end,
and
$W = \bigcup _{n} W_{p_n}$
will be the required sets. Note that property (2) of a condition ensures that if
$i\in B$
, then
$\sigma _i$
is an initial segment of a superset of A. Hence if we ensure that
$\sigma _i$
grows unboundedly in length for all
$i\in B$
, then we automatically get that
$B\times A\subseteq W$
. On the other hand, property (1) ensures that
. We only need to further ensure that
$A, B\nleq _e W$
.
The initial condition is
, where S is the
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class consisting of all supersets of A. Suppose that we have built
. We describe how to extend
$p_n$
to
. We have two cases depending on the parity of n.
Suppose that
${n = 2k}$
. We ensure that
$A\neq \Gamma _k(W)$
. We first check if there is an
$a\in A$
such that
$Q_a = \{X\in P \colon a\notin \Gamma _k(X)\}$
is nonempty. If there is such an a then we let
$\beta _{n+1} = \beta _n$
,
$\tau _i = \sigma _i$
for all i, and
$Q = Q_a$
. It is straightforward to see that
$p_{n+1}$
is a condition: Q is a
$\Pi ^0_1{\left \langle {A}\right \rangle }$
subclass of P so properties (1) and (2) are trivially satisfied. Property (3) is satisfied because if
$a\notin \Gamma _k(X)$
and
$Y\subseteq X$
then
$a\notin \Gamma _k(Y)$
. Furthermore, this condition forces
$a\in A\setminus \Gamma (W)$
.
If there is no
$a\in A$
such that
$Q_a$
is nonempty, then A is a subset of
$\Gamma _k(X)$
for every
$X\in P$
. Since A does not have continuous degree and hence by Theorem 2.9 is not codable, there must be some element
$X\in P$
that does not enumerate A via
$\Gamma _k$
. So
$A\subset \Gamma _k(X)$
and we can fix
$a\in \Gamma _k(X) \setminus A$
. Fix s such that
. We can think of
as
$\bigoplus _{i<m} \tau _i$
, where
$m> |\beta _n|$
and pick s large enough so that for every
$i<|\beta _n|$
we have that
$\sigma _i\prec \tau _i$
. Let
$\beta _{n+1}$
be the string of length m obtained by appending
$1$
s to
$\beta _n$
and let
for
$i\geq m$
. Notice that here we are ensuring that
$|\tau _i|>|\sigma _i|$
. Since this case will definitely be the true case every time
for all X, we will ensure that
$B\times A\subseteq W$
as discussed above. Finally we set Q to be the subclass of P, subject to the restraints in properties (1) and (2), namely
. This is nonempty
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class because
$X\in Q$
. The resulting
$p_{n+1}$
is easily seen to be a condition. Furthermore, for all
$q\leq p_{n+1}$
we have that
$a\in \Gamma _k(W_q)$
, hence this ensures that
$A\neq \Gamma _k(W)$
, as promised.
Suppose that
${n = 2k+1}$
. We ensure that
$B\neq \Gamma _k(W)$
. We first check if there is a
$b>|\beta _n|$
and
$X\in P$
such that
$b\in \Gamma _k(X)$
. If not, we do not need to make any changes to
$p_n$
at this stage, so we set
$p_{n+1} = p_n$
. The even steps ensure that B is an infinite set, hence the requirement is automatically satisfied. So suppose that there is a
$b>|\beta _n|$
such that
$b\in \Gamma _k(X)$
for some
$X\in P$
. We would like to define
$\beta _{n+1}$
so that
$\beta _{n+1}(b) = 0$
and Q so that every element in Q enumerates b via
$\Gamma _k$
. Just like in the proof of Theorem 2.9, this might not be possible because it could be that every axiom in
$\Gamma _k$
for b contains an element
${\left \langle {b, a}\right \rangle }$
, where
, so we cannot build Q satisfying condition
$(1)$
. This is why we consider two cases.
Case 1. There is an axiom
${\left \langle {b,D}\right \rangle }\in \Gamma _k$
, such that
$D\subseteq X$
for some X and for every pair
${\left \langle {i, a}\right \rangle }\in D$
we have that
$\sigma _i(a) = 1$
or
$a\in A$
. (Note that if
$\beta (i) = 0$
and
${\left \langle {i,a}\right \rangle }\in D$
, then
$\sigma _i(a) = 1$
because
$D\subseteq X$
.) In that case we can proceed with our original plan: first to ensure property (1) fix
$\tau _b$
to be the initial segment of A covering all a such that
${\left \langle {b,a}\right \rangle }\in D$
. Next we trim the elements of the
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class P to get
$P'$
so that
and for all
$i\neq b$
we have that
$P^{\prime }_i = P_i$
. Note, that we still have
$D\subseteq X'$
, where
$X'$
is obtained by this trimming process from X, by our choice of
$\tau _b$
. Furthermore,
$P'$
is a
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class. To see this, write
where
$U\leq _e A$
. We may assume that U is closed upward. Then
where
$\rho \in V$
if when we write
$\rho = \bigoplus _i \rho _i$
, we have that either
$\rho _b$
is incompatible with
$\tau _b$
, or if all strings
$\rho ^*$
that we get by replacing
$\rho _b$
by strings of the same length are in U. It is straightforward to see that
. On the other hand, if
$X\notin P'$
, but
, then by compactness there must be some level s such that all possible strings
$\rho ^*$
obtained as above from the string
must be thrown into U and so
. The set V is clearly enumeration reducible to A.
We now fix s large enough so that
and
can be written as
$ \bigoplus _{i<m}\tau _i$
, where
$m>b$
and
$\sigma _i\preceq \tau _i$
for all
$i<|\beta _n|$
or
$i = b$
. We extend
$\beta _n$
to
$\beta _{n+1}$
of length m, so that
$\beta _{n+1}(b) = 0$
and for all
$i\neq b$
such that
$|\beta _n|\leq i <m$
, we set
$\beta _{n+1}(i) = 1$
. We set
if
$i\geq m$
. We set
. Thus we have ensured that
$b\notin B$
and
$b\in \Gamma _k(W_q)$
for every
$q\leq p_n$
.
Case 2. For every
$X\in P$
, if
${\left \langle {b,D}\right \rangle }\in \Gamma _k$
and
$D\subseteq X$
, then there is a pair
${\left \langle {i, a}\right \rangle }\in D$
such that
$\sigma _i(a)\neq 1$
(so it is either undefined or equals
$0$
) and
$a\notin A$
. Consider the
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class
$Q = \{X\in P \colon b\notin \Gamma _k(X)\}$
. This is a nonempty class because by property (3) of P the sequence
$Y = \bigoplus Y_i$
where
if
$\beta _n(i) = 0$
and otherwise
$$\begin{align*}Y_i(x) =\begin{cases} \sigma_i(x),\quad \text{if } x<|\sigma_i|; \\ A(x),\quad \text{if }x\geq |\sigma_i|\end{cases} \end{align*}$$
must be a member of Q. We set
$\beta _{n+1}$
to be the string of length
$b+1$
obtained by adding
$1$
s to
$\beta _n$
and leave
$\tau _i = \sigma _i$
for all i. Once again, since
$Q\subseteq P$
and we have added no new
$0$
s to
$\beta _{n+1}$
, it is easy to see that Q satisfies properties (1) and (2). To see that it satisfies (3), we again note that if
$Y\subseteq X$
and
$b\notin \Gamma _k(X)$
then
$b\notin \Gamma _k(Y)$
and hence
$p_{n+1}$
is a condition. This condition forces
$b\in B\setminus \Gamma _k(W)$
.⊣
Putting everything together, we get:
Theorem 5.2. For a set
, the following are equivalent:
-
(1) A has continuous enumeration degree.
-
(2) The degree of A contains the graph of function that is codable by extensions.
-
(3) A is not array-avoiding.
-
(4) A is not uniformly array-avoiding.
-
(5) A is not half of a nontrivial relativized
$\mathcal {K}$
-pair.
Combining the characterization of the continuous degrees in terms of
$\mathcal {K}$
-pairs with the characterization as the almost total degrees from [Reference Andrews, Igusa, Miller and Soskova2], we get the promised structural dichotomy in the enumeration degrees.
Theorem 1.1. For every enumeration degree a , exactly one of the following twoproperties holds:
-
(1) The degree x is continuous, so for every total enumeration degree x
$\nleq$
a
,
a
$\lor$
x
is total. -
(2) There is a total enumeration degree x
$\nleq$
a
such that
a
$\lor$
x
is a strongquasiminimal cover of
x
.
Proof. The first property is exactly the definition of almost totality. If
$\mathbf {a}$
is not continuous, then by Theorem 5.2, we get that
$\mathbf {a}$
is half of a nontrivial
$\mathcal {K}$
-pair; let
$\mathbf {b}$
and
$\mathbf {u}$
be such that
$\{\mathbf {a}, \mathbf {b}\}$
is a nontrivial
$\mathcal {K}$
-pair relative to
$\mathbf {u}$
. Using forcing, it is not hard to build a total enumeration degree
$\mathbf {x}\geq \mathbf {u}$
such that
$\mathbf {a}\nleq \mathbf {x}$
and
$\mathbf {b}\nleq \mathbf {x}$
. (For example, this follows from a much more general theorem of Soskov [Reference Soskov21] about jump inversion in
$\mathcal {D}_e$
.) Note that
$\{\mathbf {a}, \mathbf {b}\}$
is a nontrivial
$\mathcal {K}$
-pair relative to
$\mathbf {x}$
. By Theorem 2.11,
$\mathbf {a}\lor \mathbf {x}$
is a strong quasiminimal cover of
$\mathbf {x}$
. ⊣
6 Cototal sets and
$\mathcal {K}$
-pairs
In this section, we briefly examine the connection between cototal sets and
$\mathcal {K}$
-pairs, ending with a conjectured definition of cototality in the enumeration degrees.
Definition 6.1. A set A is cototal if
. An enumeration degree is cototal if it contains a cototal set.
Andrews et al. [Reference Andrews, Ganchev, Kuyper, Lempp, Miller, Soskova and Soskova1] note that if A has cototal enumeration degree, then
$K_A$
is cototal representative of that degree. In fact, they show that the operator that maps
$d_e(A)$
to
is degree invariant and call it the skip operator. The skip of
$d_e(A)$
is denoted by
$d_e(A)^{\lozenge }$
, so we have that A is cototal if and only if
$d_e(A)\leq _ e d_e(A)^{\lozenge }$
.
It is straightforward to see that every total enumeration degree is cototal, as
. More generally, every continuous degree is cototal. Recall that an enumeration degree is continuous if it contains a set of the form
, for some
. It follows that every continuous degree is cototal as,
$2{\left \langle {i, q}\right \rangle }\in C_{\alpha }$
if and only if there is an
$r>q$
such that
, and similarly,
$2{\left \langle {i, q}\right \rangle }+1\in C_{\alpha }$
if and only if there is an
$r<q$
such that
.
The class of cototal enumeration degrees is strictly bigger than the continuous degrees. For example, cototal enumeration degrees can be halves of nontrivial
$\mathcal {K}$
-pairs. One way to see this is to note that every
$\Sigma ^0_2$
enumeration degree is cototal [Reference Andrews, Ganchev, Kuyper, Lempp, Miller, Soskova and Soskova1]. As we already saw, if A is semicomputable, then
is a
$\mathcal {K}$
-pair, and A can be chosen as a non-c.e. and non-co-c.e. member of any nonzero Turing degree. On the other hand, the kind of
$\mathcal {K}$
-pairs that cototal sets can be part of is restricted, as can be seen by the following result.
Proposition 6.2. If A is of cototal enumeration degree and
$\{A,B\}$
is a nontrivial
$\mathcal {K}$
-pair relative to U, then
$A\leq _e U'$
.
Proof. Suppose that A has cototal enumeration degree and that
$\{A,B\}$
is a nontrivial
$\mathcal {K}$
-pair relative to U. Then as
$A\equiv _e K_A$
, it follows that
$\{K_A, B\}$
is a nontrivial
$\mathcal {K}$
-pair relative to U. Let
$W\leq _e U$
be such that
$K_A\times B\subseteq W$
and
. By the properties of
$\mathcal {K}$
-pairs outlined in Theorem 2.11, we have that
. Of course
, so
Hence
$A\leq _e U'$
.⊣
Ideally, we would hope that the reverse statement is true as well: if A is not cototal then there are sets B and U such that
$A\nleq _e U'$
and
$\{A,B\}$
are a nontrivial
$\mathcal {K}$
-pair relative to U. Unfortunately, our current methods do not suffice to prove this statement. What we can show is much weaker.
Proposition 6.3. If A is not cototal, then there are sets B and W such that
and
$\{A,B\}$
are a nontrivial
$\mathcal {K}$
-pair relative to W.
Proof. Let
. Then A is not of continuous degree and hence by Theorem 5.2 it is uniformly array-avoiding. Let Z witness that. We will build sets B and W such that
$A,B\nleq _e W$
,
,
$A\times B\subseteq W$
, and
. The construction is a slight modification of the one in Theorem 4.4. At stage n we build finite sets
$B_n$
,
$B_n^-$
, and
$W_n$
satisfying the following four conditions:
-
(1)
$B_n\subseteq B_{n+1}$
,
$B^{-}_n\subseteq B^{-}_{n+1}$
,
$W_n\subseteq W_{n+1}$
; -
(2)
; -
(3)
; -
(4)
${\left \langle {a,b}\right \rangle }\in W_n\Rightarrow (a\in A \lor b\in B_n)$
.
We let
$B = \bigcup _n B_n$
and
$W = \bigcup _n W_n$
. Properties (1), (3), and (4) ensure that
$\{A, B\}$
is a
$\mathcal {K}$
-pair relative to W. What remains is to ensure that
$A,B\nleq _e W$
and
. In order to do this, to every
$x\in B_n$
we will associate a superset
$C_x\supseteq A$
such that
$C_x\leq _e Z$
. Unless otherwise stated,
. The set
$C_x$
may be shrunk infinitely many times, but will always be a superset of A. We will also associate to every
$y\in B_n^-$
a finite set
$T_y\subseteq A$
. Once defined,
$T_y$
will not be changed and will be the yth column of W.
We start the construction by setting
. Suppose we have constructed
$B_n$
,
$B_n^-$
, and
$W_n$
. As before, we ensure that
$W_{n+1}\subseteq X_n$
, where
From what we have said so far, it follows that we will also ensure that that
, where
In this case as well we have that
$Y_{n+1}\subseteq Y_n$
, and so
for all n.
Fix an effective listing of all enumeration operators
. We have three cases depending on the stage.
If
$ {n = 3k}$
, then we ensure that
$A\neq \Gamma _k(W)$
in exactly the same way as we did in Theorem 4.4. If
${n = 3k+1}$
, then we ensure that
$B\neq \Gamma _k(W)$
, again using the same steps as in Theorem 4.4.
Suppose that
${n = 3k+2}$
. We ensure that
. Note that
, so
$A \neq \Gamma _k(Y_n)$
. Fix an a witnessing this difference.
Case 1. If
$a\in A$
, then we do not need to do anything, as
ensures that we have satisfied our requirement. We just move on to the next stage.
Case 2. If
$a\in \Gamma _k(Y_n)$
, then fix an axiom
${\left \langle {a,D}\right \rangle }\in \Gamma _k$
such that
$D\subseteq Y_n$
. We would like to add D to
. We do this by shrinking the sets
$C_x$
and by adding elements to
$B^-_{n+1}$
: For all
${\left \langle {b,x}\right \rangle }\in D$
such that
$x\in B_n$
, we have that
$b\notin A$
and
${\left \langle {b,x}\right \rangle }\notin W_n$
, so we can remove b from
$C_x$
(without interfering with the requirements that
$A\subseteq C_x$
and
$W_{n+1}\subseteq X_{n+1}$
). For all
${\left \langle {b,y}\right \rangle }$
such that
$y\in B_n^-$
, we have that
and since
$T_y$
does not change, we can be sure that
. Finally, if
${\left \langle {b,z}\right \rangle }\in D$
and
$z\notin B_n\cup B_n^-$
, we enumerate
$z\in B_{n+1}^-$
and set
$T_z = \{c \colon {\left \langle {c,z}\right \rangle }\in W_n\}$
, which is safe because
. We set
$B_{n+1} = B_n$
and
$W_{n+1} = W_n$
. It is straightforward to check that properties (1)–(4) still hold. ⊣
There seem to be serious obstacles to modifying the construction above to get
. Nevertheless, we conjecture that the reverse is still true.
Conjecture 6.4. A degree
$\mathbf {a}$
is cototal if and only if, whenever
$\{\mathbf {a}, \mathbf {b}\}$
is a nontrivial
$\mathcal {K}$
-pair relative to
$\mathbf {u}$
we have that
$\mathbf {a}\leq \mathbf {u}'.$
7 PA relative to an enumeration oracle
In this final section of our paper, we propose two more properties that relate to the continuous and to the cototal enumeration degree. Both properties rely on the extension of the relation “PA above” to enumeration oracle.
Definition 7.1 (Miller, Soskova [Reference Miller and Soskova16])
${\left \langle {B}\right \rangle }$
is PA above
${\left \langle {A}\right \rangle }$
if B enumerates a member of every
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class.
Note that this relation is degree invariant. We write
$d_e(A)\ll d_e(B)$
if
${\left \langle {B}\right \rangle }$
is PA above
${\left \langle {A}\right \rangle }$
. Furthermore, it is an extension of the usual relation on Turing degrees, because if
$\mathbf {x}$
and
$\mathbf {y}$
are Turing degrees, then
$\mathbf {x}\ll \mathbf {y}$
if and only if
$\iota (\mathbf {x})\ll \iota (\mathbf {y})$
, that is, the relation is preserved under the embedding
$\iota \colon \mathcal {D}_T\hookrightarrow \mathcal {D}_e$
. (Recall, that
$\iota $
maps
$d_T(A)$
to
.) On nontotal enumeration degrees, however, the relation “PA above” can behave strikingly differently.
Definition 7.2. A set A is
${\left \langle {\textit {self}}\right \rangle }$
-PA if
${\left \langle {A}\right \rangle }$
is PA above
${\left \langle {A}\right \rangle }$
.
Miller and Soskova [Reference Miller and Soskova16] prove the existence of
$\Delta ^0_2 {\left \langle {\text {self}}\right \rangle }$
-PA sets. Furthermore, they show that the set of total degrees below a
${\left \langle {\text {self}}\right \rangle }$
-PA set A forms a Scott set, that is, an ideal closed with respect to the relation “PA above”.
We consider the following two new properties.
Definition 7.3. Let
.
-
(1) Say that A is PA bounded if for every set B, if
${\left \langle {B}\right \rangle }$
is PA above
${\left \langle {A}\right \rangle }$
, then
$A\leq _e B$
. -
(2) Say that there is a universal
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class if there is a
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class U such that for every member
$X\in U$
we have that
is PA above
${\left \langle {A}\right \rangle }$
.
Both properties clearly hold for total enumeration degrees, and so they exhibit the “expected” behavior of sets with respect to the relation “PA above”. We show that the two properties together characterize the continuous degrees, while the first property implies cototality.
Proposition 7.4. Fix
.
-
(1) A is PA bounded and there is a universal
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class if and only if A has continuous degree. -
(2) If A is PA bounded, then A has cototal degree.
Proof. (1) If A is continuous, then A is codable; fix a
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class P such that every member in P enumerates A. To see that A is
$PA$
bounded, note that every set B such that
${\left \langle {B}\right \rangle }$
is PA above
${\left \langle {A}\right \rangle }$
enumerates a member of the
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class P and hence enumerates A.
To see that there is a universal
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class, we build a new class R by joining each
$X\in P$
with DNC
$^X_2$
, the standard
$\Pi ^0_1[X]$
class consisting of all
$\{0,1\}$
-valued diagonally noncomputable functions relative to X. Recall that a function f is diagonally noncomputable relative to X if for every e, we have that
$\varphi ^X_e(e)\neq f(e)$
. It is not hard to see that if f is
$\{0,1\}$
-valued, then it (is the characteristic function of a set that) is PA above X.
Fix
$S\leq _e A$
such that
. We let
Then
is a
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class and every member of this class has the form
, where A is c.e. in X (equivalently
) and Y is PA above X (in the Turing sense). It follows that
is PA above
${\left \langle {A}\right \rangle }$
for every
$Z\in U$
, and so U is a universal
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class.
For the reverse direction, suppose that A is PA bounded and that there is a universal
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class U. Every member of U is PA relative to
${\left \langle {A}\right \rangle }$
, and so by boundedness enumerates A. It follows that A is codable, hence by Theorem 2.9, it has continuous degrees.
(2) Suppose that A is PA bounded. Consider a total set
above the skip of A, that is, such that
. We claim that
is PA above
${\left \langle {A}\right \rangle }$
. To see this, consider a nonempty
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class
. We may assume that
$S\leq _e A$
is closed upward. Consider the set
$E = \{\sigma \colon \forall n \exists \tau \; (|\tau | = n \ \&\ \tau \supseteq \sigma \ \&\ \tau \notin S)\}$
of strings that can be extended to an element of P. Note that
, and so it is c.e. in X. It follows that
can enumerate an element in P, proving that
is PA above
${\left \langle {A}\right \rangle }$
. By PA boundedness,
. This holds for any total set
above
, so by Selman’s theorem,
. Therefore, A has cototal degree. ⊣
It is not clear that PA boundedness characterizes the cototal enumeration degrees. We do know, at least, that cototality does not imply the existence of a universal class. As noted previously, there are
$\Delta ^0_2$
sets, hence sets of cototal degree, that are
${\left \langle {\text {self}}\right \rangle }$
-PA. This combined with the following proposition yields the desired conclusion.
Proposition 7.5. If A is
${\left \langle {\text {self}}\right \rangle }$
-PA, then A does not have a universal
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class.
Proof. Fix a
${\left \langle {\text {self}}\right \rangle }$
-PA set A. If there were a
$\Pi ^0_1{\left \langle {A}\right \rangle }$
class consisting of sets that are PA above
${\left \langle {A}\right \rangle }$
, then A would enumerate a set
such that
is PA above
${\left \langle {A}\right \rangle }$
. In that case, X would be PA (in the Turing sense) above every Y such that
. In particular, X would be PA above X. But this is impossible, as the “PA above” relation is strict when restricted to Turing oracles. ⊣
The statement above gives an alternative, though similar, proof that the degrees of
${\left \langle {\text {self}}\right \rangle }$
-PA sets are disjoint from the continuous degrees. This was originally proved by Miller and Soskova [Reference Miller and Soskova16], who show that there is a universal Martin-Löf test relative to every continuous degree, but not relative to any
${\left \langle {\text {self}}\right \rangle }$
-PA degree.
We are left with the following questions:
-
(1) Are there cototal degrees that are not PA bounded?
-
(2) Are there PA bounded degrees that are not of continuous degree? In particular, can a
${\left \langle {\text {self}}\right \rangle }$
-PA degree be PA bounded?
In very recent work Franklin et al.Footnote
2
have answered both of these questions by showing that the PA bounded degrees are exactly the continuous enumeration degrees. On the other hand, they reveal that the class of degrees whose members have universal
$\Pi ^0_1$
classes is nontrivial and worth further investigation.
Acknowledgments
The first and fourth authors were partially supported by National Science Fund of Bulgaria grant #01/18 from 23.07.2017 and by grant #02/16 from 19.12.2016. The fourth author was also supported by National Science Foundation grant DMS-1762648. The second author was supported by RFBR grant #17-51-18083. Also he is supported as federal professor in mathematics (project #1.451.2016/1.4) in Russia. The third author was partially supported by grant #358043 from the Simons Foundation.
