1 Introduction
The connections between trees and their branches are well-studied. A major result is Jockusch and Soare’s Low Basis Theorem [Reference Jockusch and Soare8] which showed that every infinite binary recursive (or co-r.e.) tree has an infinite branch of low Turing degree; similarly they showed that it also has an infinite branch of hyperimmune-free Turing degree. This shows that trees (this word denotes from now on infinite binary trees) which are recursive or co-r.e. have hyperimmune-free infinite branches. Downey [Reference Downey3] provided a tree where all branches are hyperimmune-free and some are nonrecursive. Downey’s construction left open the question whether such trees can be made to have uncountably many infinite branches.
Ng, Stephan Yang and Yu [Reference Ng, Stephan, Yang and Yu13] constructed in 2011 and 2012 recursive trees with uncountably many infinite branches such that every infinite branch is of hyperimmune-free Turing degree. They furthermore studied various related results and announced in 2012 [Reference Ng, Stephan, Yang and Yu13, Theorem 2.4] the result that there is a recursive binary tree with uncountably many infinite branches of Cantor–Bendixson rank 1 (thus removing the isolated branches makes it perfect) such that all infinite branches are hyperimmune-free and generalised low
$_1$
. They gave a proof sketch and announced the full details of the proof in the journal version which never got ready due to the construction becoming more and more lengthy and remaining incomplete. The reason was that Ng et al. [Reference Ng, Stephan, Yang and Yu13] tried to follow the proof-sketch of the initial approach of their paper [Reference Ng, Stephan, Yang and Yu13, Theorem 2.4] and intended to use the “full approximation method” which is a complicated infinite injury construction. The alternative proof in the present work uses a K-recursive guidance tree U whose infinite branches form a perfect tree of
$2$
-generic inversions of the double jumps of sets in the cone above
$K'$
. This guidance tree brought down the complexity of the construction from infinite injury to finite injury in the translation of U to the final co-r.e. tree T.
The result is from the field of classical recursion theory and it connects two major notions of the field, namely that of hyperimmune-free Turing degrees (which are those Turing degrees where all functions computed are majorised by a recursive function) with that of recursive or co-r.e. trees having uncountably many infinite branches. Recursive functions are, in easy terms, those which can be computed by a abstract machine without any bounds on computation time and storage space; alternatively one can also say, due to a result of Matiyasevich [Reference Matiyasevich11], that a recursive function is one whose graph is Diophantine, that is, satisfies that there is a polynomial p with integer coefficients in variables
$x,y,z_1,\ldots ,z_k$
such that, for all
$x,y \in \mathbb N$
,
$f(x) = y$
iff there are values for
$z_1,\ldots ,z_k \in \mathbb N$
with
$p(x,y,z_1,\ldots ,z_k)=0$
. This also works with partial-recursive functions and thus recursively enumerable sets. The classes of the infinite branches of such trees are also called
$\Pi ^0_1$
and subject to detailed studies. The authors also want to refer to standard text books on recursion theory and related fields for further reading of the background [Reference Calude1, Reference Li and Vitányi10, Reference Nies17–Reference Odifreddi19, Reference Soare22]. The main innovation of [Reference Ng, Stephan, Yang and Yu13] was to show that
$\Pi ^0_1$
-classes can be both uncountable and only have members of hyperimmune-free Turing degree. The add-on properties are introduced below one by one together with definitions or characterisations explaining them. A second conference article on this topic appeared in 2022 [Reference Ng, Stephan, Yang and Yu14] and containsmost of theproof of themain resultof this journalpaper.
Theorem 1. There is a co-r.e. tree T without finite branches which has
$2^{\aleph _0}$
many infinite branches such that the nonisolated infinite branches are all hyperimmune-free, generalised low
$_1$
, Schnorr-trivial, of minimal Turing degree, and jump traceable and form a perfect tree.
Besides the above mentioned announcement [Reference Ng, Stephan, Yang and Yu13, Theorem 2.4], the proof was never published and is also not in the follow-up works, that is, works citing the 2012 paper [Reference Hirschfeldt, Jockusch and Schupp6, Reference Hölzl and Porter7, Reference Ng and Yu15, Reference Yu25]. A result proven by Hirschfeldt et al. [Reference Hirschfeldt, Jockusch and Schupp6, Lemma 6.7] was also announced without proof [Reference Ng, Stephan, Yang and Yu13] and states that every hyperimmune-free infinite branch A on a K-recursive tree is also on a recursive tree not containing any additional infinite branches; the tree might, however, omit some of the infinite branches of the original K-recursive tree. Further results, mainly from [Reference Ng, Stephan, Yang and Yu13], are provided in Section 4. This section and the questions in the conclusion should allow to get an updated picture of which items from the conference paper [Reference Ng, Stephan, Yang and Yu13] can be considered as a proven fact and which are, due to incomplete evidence and problems with doing the proof, indeed to be left as an open question. Before this, here are some detailed explanations on the used notions.
1.1 Co-r.e. tree
This is a downward closed infinite subset of the binary strings such that the set of strings outside it is recursively enumerable. Branches are finite or infinite strings such that all finite prefixes of them are in the tree. The infinite branches of a co-r.e. tree form a
$\Pi ^0_1$
-class and the concepts of recursive tree, co-r.e. tree, and
$\Pi ^0_1$
-class are interchangeable when talking about the class of infinite branches of a tree.
Remark 2. One can prune of the finite branches of an existing recursive tree S and receives a co-r.e. tree T in which every node has either one or two successors, but which does not have any dead ends. The rule is this: Whenever
$\sigma 0, \sigma 1$
are both in the complement of the tree T, then one also enumerates
$\sigma $
into the complement of T. The infinite branches of S and T are the same. This co-r.e. tree is notationally easier to handle, due to the direct correspondence between branches and the sequence of their branching bits for all nonrecursive infinite branches in T.
1.2 Hyperimmune-free
The easiest characterisation of a set A being hyperimmune-free is that every A-recursive function is majorised by a recursive function. Formally, it means that no set
$B \leq _T A$
is hyperimmune, that is, for every infinite set
$B \leq _T A$
there is a recursive array
$I_0,I_1,\ldots $
of finite disjoint sets given by canonical indices with each
$I_k$
intersecting B. Hyperimmune sets were introduced by Post [Reference Post20]. Dekker [Reference Dekker2] showed that every nonrecursive r.e. Turing degree contains a hyperimmune set and Miller and Martin [Reference Miller and Martin12] showed that on the one hand every nonrecursive Turing degree below the halting problem K contains a hyperimmune set while on the other hand there are also nonrecursive Turing degrees without hyperimmune sets; such degrees and the sets in them are called hyperimmune-free. Jockusch and Soare [Reference Jockusch and Soare8] showed that every co-r.e. tree with an infinite branch contains actually an infinite hyperimmune-free branch.
1.3 Schnorr-trivial
Franklin and Stephan [Reference Franklin and Stephan4] gave the following characterisation which serves as a definition: A set A is Schnorr-trivial if for every
$f \leq _{tt} A$
there is a recursive function g such that
$\forall n\,\exists m\leq 2^n\,[f(n)=g(n,m)]$
.
Remark 3. The above notions have the following properties: Schnorr-trivial plus hyperimmune-free equals to a property called recursively traceable; however, the property Schnorr-trivial is easier to achieve in a construction, as one needs only to consider truth-table reductions and not to worry about Turing reductions. Furthermore, if
$\varphi _e^A$
is a truth-table reduction then it can be assumed that there is a recursive function g such that
$\varphi _e^A(x)$
needs, independently of the choice of A, at most
$g(x)$
steps and queries only below
$g(x)$
and outputs a value y with
$y < g(x)$
. Similarly, if
$\varphi _e$
is a Turing reduction and
$\varphi ^A_e(x)$
needs s steps to converge then all places queried are below s and
$\varphi ^A_e(x) < s$
. In particular, terminating computations
$\varphi _e^\sigma (x)$
query
$\sigma $
only at values in the domain
$\sigma $
. Two partial functions
$\varphi _e^\sigma $
and
$\varphi _e^\tau $
are consistent at stage s iff for all x where both
$\varphi _e^\sigma (x)$
and
$\varphi _e^\tau (x)$
output values y and z within s steps, it holds that
$y=z$
.
1.4 Jump traceable
A set A is jump traceable if there are a recursive function h and a partial-recursive function g such that
$\forall n\,\exists m\leq h(n)\,[\varphi ^A_n(n) = g(n,m)]$
. Here one uses the diagonal jump function
$n \mapsto \varphi ^A_n(n)$
in place of its domain
$A'$
and equality “=” of partial function values means that either both sides are undefined or both sides are defined and equal.
1.5 Generalised low
A set A is generalised low
$_1$
if
$A' \leq _T A \oplus K$
. This property was introduced to generalise the notion “low” in a senseful way beyond the classes of Turing degrees below the halting problem. Note that “generalised low
$_1$
” and “high” are not disjoint properties and some sets have both properties, for example, the
$1$
-generic set obtained by inverting the jump of
$K'$
. Nies showed the following proposition which allows to construct jump-traceable sets when one actually wants generalised low ones.
Proposition 4 (Nies [Reference Nies16]).
If A is jump traceable then
$A' \leq _T A \oplus K$
.
1.6 Minimal Turing degree
A set A is of minimal Turing degree iff A is not recursive and for every
$B \leq _T A$
, either B is recursive or
$A \leq _T B$
. Spector [Reference Spector23] constructed a minimal Turing degree which is below the jump
$K'$
of the halting problem K and Sacks [Reference Sacks21] constructed a minimal Turing degree below K. A sufficient criterion to show that A is minimal is to show that for every Turing reduction
$\varphi _e$
there are a co-r.e. tree S such that A is an infinite branch of S and a node
$\sigma \preceq A$
such that one of the following three conditions holds:
-
1. The function $\varphi ^A_e$
is total and every
$B \succeq \sigma $
on S satisfies that
$\varphi _e^A = \varphi _e^B$
, thus
$\varphi _e^A$
is recursive. -
2. Every $B \succeq \sigma $
on S with
$B \neq A$
satisfies that there is an x with
$\varphi _e^A(x) \neq \varphi _e^B(x)$
where both values are defined, thus
$A \leq _T \varphi _e^A$
. -
3. There is an x with $\varphi ^A_e(x)$
being undefined, thus
$\varphi _e^A$
is partial.
A tree S is e-splitting along A if it satisfies one of the three conditions and Spector [Reference Spector23] used this method to construct a minimal Turing degree.
1.7 Perfect tree
A tree is perfect iff every infinite branch is the pointwise limit of other infinite branches which are different from it; in particular perfect trees have
$2^{\aleph _0}$
many infinite branches and do not have isolated infinite branches. The tree T constructed in the main result will satisfy that its nonisolated branches form a perfect tree. Furthermore there are
$\aleph _0$
many isolated branches added to this tree. These additional recursive branches cannot be avoided as T must have low branches by the Low Basis Theorem [Reference Jockusch and Soare8] and these branches are then recursive by being both hyperimmune-free and low. As all nonisolated infinite branches are nonrecursive by the construction of T, the isolated infinite branches cannot be avoided.
Proposition 5. If V is a
$K'$
-recursive tree, then V is contained in a K-r.e. tree U such that every infinite branch A of U is also one of V and vice versa.
Proof. This is a folklore result which holds relative to any oracle, not only relative K. However, it is needed here only relative to K. By the limit lemma, there is a K-recursive approximation
$V_s$
such that for all
$\mu \in V$
,
$V_s(\mu ) = V(\mu )$
for almost all s. Now one enumerates a node
$\mu $
into U iff there is a stage
$s> |\mu |$
such that all prefixes
$\nu $
of
$\mu $
are in
$V_s$
. If A is an infinite branch of V then clearly all prefixes of A are enumerated into U and A is an infinite branch of U. If A is not an infinite branch of V there is a prefix
$\mu $
of A which is not in V and so there is a stage t such that
$V_s(\mu )=0$
for all
$s \geq t$
and then no prefix of A longer than
$|\mu |+t$
will ever be enumerated into U; thus A is not an infinite branch of U.
Proposition 6 (Based on Friedberg jump inversion theorem [Reference Friedberg5]).
There is a perfect
$K'$
-recursive tree V such that each infinite branch of it is
$2$
-generic and that all Turing degrees above
$K'$
are double jumps of infinite branches of V.
Proof. Given a set
$B \subseteq \mathbb N$
and oracle
$K'$
, one starts with the root
$\sigma _0 = \varepsilon $
and puts it into the tree. Then one checks whether there is an extension
$\eta $
of
$\sigma _n$
in
$W_e^K$
and if so then one lets
$\sigma _{n+1} = \eta B(n)$
for the first such
$\eta $
found else one lets
$\sigma _{n+1} = \sigma _n B(n)$
. This case-distinction is clearly
$K'$
-recursive. The resulting tree V is the union of this construction for all oracles B and
$V[B]$
refers to the encoded infinite branch for B. For two oracles
$B,\tilde B$
first differing at position n, the respective strings
$\sigma _{n+1}$
in the construction of
$V[B]$
and
$V[\tilde B]$
will differ exactly on the last bit and therefore
$V[B]$
and
$V[\tilde B]$
will be different infinite branches of V. The tree V will be uniformly
$K'$
-recursive.
The sets
$V[B]$
are always
$2$
-generic and
$V[B] \leq _T B \oplus K'$
, as the oracle
$K'$
can compute the tree V. Thus
$V[B]" \equiv _T V[B] \oplus K' \equiv _T B \oplus K'$
. For every B there is the infinite branch
$V[B]$
and the infinite branches
$V[B]"$
stand in a one-to-one correspondence with
$B \oplus K'$
. For every possible double jump
$B \oplus K'$
of a set there is the set
$V[B]$
with
$V[B]" \equiv _T B \oplus K'$
, thus the Turing degrees of the cone above
$K'$
are covered by all sets of the form
$B \oplus K'$
and all these sets are equal to a double jump.
Corollary 7. There is a K-r.e. tree U such that all its infinite branches are
$2$
-generic and that the Turing degrees of the double jumps of these branches cover the whole cone above
$K'$
.
2 The main result and its construction
The following theorem implies Theorem 1 and uses the above constructed trees from Proposition 6 and Corollary 7. Recall that on a tree, a node
$\sigma $
is a branching node if there are infinite branches through both
$\sigma 0$
and
$\sigma 1$
; one can follow a branch using an oracle which tells which nodes
$\sigma $
are branching nodes and the branching bits which are, in ascending sequence on the tree, the collection of first bits above each branching node.
Theorem 8. Given
$U,V$
as in Proposition 6 and Corollary 7, there is a co-r.e. tree T with uncountably many infinite branches such that the nonisolated infinite branches of T correspond to infinite branches on U and V, respectively, in a one-to-one fashion and that these infinite branches of T are each of hyperimmune-free Turing degree, of minimal Turing degree, generalised low
$_1$
, jump traceable, and Schnorr-trivial. Furthermore, the correspondence of each nonisolated infinite branch A of T to an infinite branch B of U satisfies the equality
$A \oplus K \equiv _T B \oplus K$
and B consists of the branching bits of A in T.
2.1 Construction
The construction works with markers
$c_n$
which are initialised as
$c_{n,0} = n$
and move at stages t from
$c_{n,t}$
to
$c_{n,t+1}$
; in parallel to the movement of markers, a co-r.e. tree will be constructed which has branching nodes only on levels on which a marker sits. This tree is called T and
$T_0 = \{0,1\}^*$
. Furthermore,
$u_t(k)$
is the t-th approximation to
$u(k)$
for the K-recursive enumeration
$u(0),u(1),u(2),\ldots $
of the tree U; note that this approximation exists by the limit lemma and for each k and almost all t,
$u_t(k) = u(k)$
.
Recall that a finite tree up to a level can be described by the leaf nodes in that level; furthermore, one can for each leaf describe the string of branching bits which are those bits in the path to the leaf where one has to make a choice between two possibilities in order to select the leaf to which one wants to go; those where there is only one choice are omitted from the string.
At stage t, one first considers for each
$n$
with
$c_{n,t} \leq t+1$
the finite tree
$L_n$
which contains all words
$\sigma \in T_t$
with
$dom(\sigma ) \subseteq \{0,1,\ldots ,c_{n,t}-1\}$
. The branching bits of a
$\sigma \in L_n$
are the last bits a of those prefixes
$\eta a \prec \sigma $
where both
$\eta 0,\eta 1 \in L_n$
and the branching string is the sequence of branching bits in the given order from the root to the node
$\sigma $
. One considers an extension
$H_n$
of
$L_n$
and calls it admissible when it satisfies the following conditions:
-
1. The leaves of $H_n$
have the domain
$\{0,1,\ldots ,t+1\}$
and
$H_n \subseteq T_t$
. -
2. For each leaf $\sigma $
of
$L_n$
there is exactly one
$\tau \in H_n$
extending
$\sigma $
and having domain
$\{0,1,\ldots ,t\}$
; furthermore, for the branching bits
$\mu $
of
$\sigma $
in
$L_n$
, if
${\mu \in \{u_{t+1}(0),u_{t+1}(1),\ldots ,u_{t+1}(n)\}}$
then
$\tau 0,\tau 1 \in H_n$
else only
$\tau 0 \in H_n$
. -
3. There is progress from $L_n$
to
$H_n$
in the way that certain enumeration, definability or splitting goals are obtained; more precisely there are
$\sigma ,\sigma ' \in L_n$
with the corresponding
$\tau ,\tau '$
such that
$c_{n,t} \leq t+1$
and at least one of the following conditions is satisfied:-
(a) Some element $m \leq n$
became enumerated into K between time
$c_{n,t}$
and
$t+1$
or
$u_{t+1}(m) \neq u_s(m)$
for some
$s \in \{c_{n,t},c_{n,t}+1,\ldots ,t\}$
. -
(b) There is an $e \leq n$
for which the function
$\varphi _e^\sigma $
is not defined on all of
$0,1,\ldots ,n$
within
$c_{n,t}$
steps while
$\varphi _e^\tau $
is defined on all of
$0,1,\ldots ,n$
within
$t+1$
steps. -
(c) There is an $e \leq n$
for which
$\varphi _e^\sigma (e)$
is not defined within
$c_{n,t}$
steps while
$\varphi _e^\tau (e)$
is defined within
$t+1$
steps. -
(d) For some $e \leq n$
there is an x such that
$\varphi _e^\sigma $
and
$\varphi _e^{\sigma '}$
are consistent at time
$c_{n,t}$
while
$\varphi _e^{\tau }(x),\varphi _e^{\tau '}(x)$
are defined and different for an
$x<t+1$
within
$t+1$
steps. -
(e) $|\sigma | = |\tau |$
and
$c_{n,t} = t+1$
.
-
For the least n where one can find
$L_n,H_n$
as above, one does the following:
-
1. For $m<n$
,
$c_{m,t+1} = c_{m,t}$
and
$c_{n,t+1} = t+1$
and for
$m>n$
,
$c_{m,t+1} = t+1+m-n$
. -
2. Furthermore, one lets $T_{t+1}$
consist of all the nodes which are comparable to one of the leaves of
$H_n$
, that is, one prunes off the tree all nodes which are extending some leaf
$\sigma $
of
$L_n$
but which are incomparable to all leaves of
$H_n$
.
Note that such an n is always found as the n with
$c_{n,t} = t+1$
can be selected when no smaller n qualifies.
Note that in the above, if
$H_n$
was defined at stage s, then the
$L_n$
at the next first stage t where
$c_{n,t+1}> c_{n,s+1}$
satisfies that the leaves of that
$L_n$
at stage t are one bit shorter than the leaves of the
$H_n$
at stage s. This is to make sure that when
$u_{t+1}(m) \neq u_{s+1}(m)$
for some
$m \leq n$
then the sprouting of the leaves of the old
$H_n$
can be undone for the new
$H_n$
and is not incorporated into the new
$L_n$
.
Notation 9. In the following, the final values of
$L_n$
and
$H_n$
refer to the trees with leaves of level
$c_{n,t}-1$
and
$c_{n,t}$
, respectively, where t is so large that
$c_{n,t}$
does not change at t or later.
The following proposition is true first due to the fact that when the last
$H_m$
with
$m < n$
has been defined then
$L_n=H_{m-1}$
and from then onwards, whenever
$L_n$
and
$H_n$
change, the extension of
$L_n$
extends each leaf
$\sigma $
of the old
$L_n$
uniquely to a leaf
$\tau $
of the new
$L_n$
and furthermore puts two successor leaves into
$H_n$
iff the branching bits
$\mu $
form a string in
$\{u_{t+1}(0),u_{t+1}(1),\ldots ,u_{t+1}(n)\}$
.
Proposition 10. Each leaf
$\sigma $
of
$L_n$
has two successors in
$H_n$
iff its branching string
$\eta $
is in
$\{u(0),u(1),\ldots ,u(n)\}$
and each leaf
$\sigma a$
of
$H_n$
extends in a unique way to a leaf
$\tau $
of
$L_{n+1}$
.
The above picture shows how a tree
$L_n$
gets updated due to changes in
$\{u_s(0), [3] u_s(1), [3] \ldots , [3] u_s(n)\}$
where the updates from the old s to the larger new s removes
$0$
from the list (branching string for left) and adds
$1$
into the list (branching string for right). Nodes denoted with
$L_n$
and
$H_n$
denote the leaves of these trees, where the new left leaf of
$L_n$
is above the old left leaf of
$H_n$
and the old left right leaf of
$H_n$
is enumerated into the complement of T. The new leaves of
$H_n$
have the branching strings
$0$
,
$10$
,
$11$
. Left successors have branching bit
$0$
and right successors have branching bit
$1$
at each branching which survives.
3 Proof of the properties of infinite branches
The following fact is useful. It is just based on the fact that given a K-recursive enumeration
$v(0),v(1),v(2),\ldots $
of the above tree U, one can replace it by a new enumeration
$u(\langle i,j \rangle )$
which has the following approximation: If
$v_j(i) = v_s(i)$
for
$s=j,j+1,\ldots ,j+t$
then
$u_t(\langle i,j \rangle ) = v_j(i)$
else
$u_t(\langle i,j \rangle )$
is some fixed element of U, say the root of the tree.
Fact 11. Every nonempty K-r.e. set has a K-recursive enumeration in which the enumerating function can be approximated such that it makes at most one mind change in the computation of each number in the enumeration.
Such type of enumerations are assumed for K-r.e. sets from now onwards for the rest of the proof.
Proposition 12. Every infinite branch A of T is jump traceable and, by Proposition 4, also generalised low
$_1$
.
Proof. Note that for the parameter n, it tracks only the behaviour of
$\varphi _e^A(e)$
for
$e \leq n$
, thus one can in the following always assume that
$e \leq n$
. See the construction of Theorem 8 for more details about the activities tracked in item 3.
One can see by induction that
$L_n$
has always prior to step t at most
$2^n$
leaves and that
$H_n$
(due to the branching nodes on the level of
$c_{n,t+1}$
being there) can have at most
$2^{n+1}$
leaves. Furthermore, if one enumerates the various possibilities for progress in item 3, one sees that the overall number of mind changes is bounded by
$1+(n+1) \cdot (2+2^n+2^n+4^n) \leq 8^{n+2}$
. Now taking into account that activity of smaller
$c_m$
cause
$c_n$
to act again, one gets that
$c_n$
is modified at most
$8^{n+2}$
times between any two changes of lower markers, so in total at most
$8^{(n+1)(n+2)}$
times. Now one can for each leaf
$\tau $
of each version of
$L_n$
enumerate at most one value of
$\varphi _e^\sigma (e)$
and for each infinite branch A of T where
$\varphi ^A_e(e)$
is defined,
$\varphi ^A_e(e) = \varphi _e^\sigma (e)$
for one of the leaves of the final version of
$L_n$
after the last time that the marker
$c_{n,t}$
moved, thus every infinite branch A is jump traceable with bound
$2^{3n^2+10n+6}$
.
Proposition 13. An infinite branch A of T is isolated iff there is an n such that the leaf of A restricted to final version of
$L_n$
has branching string
$\mu $
with
$\mu \notin U$
.
Proof. The reason for this is that if
$\mu $
is not in U then
$\mu \notin \{u(0),u(1),\ldots ,u(n)\}$
for all n and the final versions of
$L_n$
and
$H_n$
will have that the leaf
$\tau a \preceq A$
in
$H_n$
is of the form
$\tau 0$
and
$\tau 1 \notin H_n$
. The same will be true for all
$m \geq n$
, as in them the restriction of A to
$L_m = H_{m-1}$
will have the same branching string
$\eta $
. Thus the corresponding
$\tau $
in
$H_m$
will have the unique extension and leaf
$\tau 0$
in
$H_m$
and therefore the infinite branch A is isolated and thus recursive.
Now consider the case that all branching strings of A are in U. Then, for each
$L_m$
there is a first
$n \geq m$
such that the branching string
$\mu $
of A in
$L_m$
is in
$\{u(0),u(1),\ldots ,u(n)\}$
. It follows that the leaf
$\tau $
of
$L_n$
extended by A will also have two extensions
$\tau 0,\tau 1 \in H_n$
and so there is a branching node in T which is a leaf of
$L_n$
and a prefix of A. As this happens for infinitely many n, the infinite branch A is not isolated.
Proposition 14. Every infinite branch A of T is of hyperimmune-free Turing degree.
Proof. Let A be an infinite branch of T which is not isolated and which therefore might be nonrecursive; note that all isolated infinite branches are recursive. Now A corresponds to some
$2$
-generic infinite branch B of U where the set B is then taken as the sequence of branching bits of A in T.
For a given Turing reduction
$\varphi _e$
, consider the following set:
$W^K = \{\mu : \exists n \geq e\, [$
the final
$L_n$
has a leaf
$\sigma $
with branching string
$\mu $
and
$\varphi _e^\sigma (x)$
being undefined for some
$x < n]\}$
. This set is K-r.e.; note that when
$\varphi ^A_e(x)$
would be defined for some infinite branch K of T extending
$\sigma $
, then some progress would be possible and the
$L_n$
would not be the final one.
If an
$A = T[B]$
satisfies that there is above every
$\sigma $
some infinite branch
$\tilde A = T[\tilde B]$
of T such that
$\tilde A$
also extends
$\sigma $
and
$\varphi _e^{\tilde A}$
is not total, then there is an x with
$\varphi _e^{\tilde A}(x)$
being undefined and any
$n \geq x$
satisfies that some prefix
$\tilde \sigma $
of
$\tilde A$
is in
$L_n$
as a leaf and
$\varphi _e^{\tilde \sigma }(m)$
is undefined on some
$m \leq n$
and therefore its branching string
$\nu $
is in
$W^K$
. Thus B has above every node some extension in
$W^K$
and so B has a prefix itself which is in
$W^K$
. This implies that
$\varphi ^A_e$
is not total by the definition of
$W^K$
.
So one sees that there is a
$\sigma \preceq A$
such that for all infinite branches
$\tilde A$
of T which extend
$\sigma $
it holds that
$\varphi ^{\tilde A}_e$
is total. Thus one can, for every x, simulate the coenumeration of T and the pruning of the tree until a stage is found and a level
$\ell $
such that for all
$\tau \in \{0,1\}^\ell $
which extend
$\sigma $
and which are still in T it holds that
$\varphi _e^\tau (x)$
converges within
$\ell $
steps and then the maximum of these values is an upper bound for
$\varphi ^A_e(x)$
; as this upper bound is computed by a recursive function,
$\varphi ^A_e$
has a recursive upper bound. Thus, for each e, either
$\varphi ^A_e$
is partial (as indicated in the preceding paragraph) or
$\varphi ^A_e$
has a recursive upper bound and therefore every nonisolated infinite branch of T is of hyperimmune-free Turing degree. The isolated infinite branches are recursive and therefore of hyperimmune-free Turing degree as well.
Proposition 15. Every infinite branch A of T is Schnorr-trivial.
Proof. If
$\varphi _e$
is a truth-table reduction with bound function g for the computation time then it will happen for almost all n that
$c_{n,t}$
is eventually above
$g(n)$
; this is due to the fact that the time to enumerate the halting time of K up to n is a dominating function with respect to n. Thus one can, for all sufficiently large n, simulate the construction until the final value of the
$c_{n,t}$
is above the use and then enumerate the
$2^n$
values which are defined by the various branches of the co-r.e. tree which survive. The finitely many smaller values can be patched. Thus A is Schnorr-trivial.
Proposition 16. The double jumps
$A"$
of the infinite branches A of T form the cone above
$K'$
.
Proof. Assume A is a nonisolated infinite branch of T; then
$A = T[B]$
for some infinite branch B of U; furthermore, the bits of B are the branching bits of A in T. Note that the double jumps of the infinite branches B of V and thus U cover all Turing degrees above
$K'$
due to the B being obtained by uniform double jump inversion. Each B is
$2$
-generic and satisfies
$B" \equiv _T B \oplus K'$
. Furthermore, Marcus Triplett showed in his bachelor thesis [Reference Triplett24] that
$A" \equiv _T A' \oplus K'$
for all hyperimmune-free sets A.
The halting problem K allows to reconstruct all branching nodes of T and these allow to recover the set B from
$A \oplus K$
. Thus
$B \leq _T A \oplus K$
. As B is
$2$
-generic,
$B" \equiv _T B \oplus K' \leq _T A \oplus K' \leq _T A' \oplus K' \equiv _T A"$
. Similarly one can recover A from
$B \oplus K$
, as the set B are the branching bits of A on T and K computes the branching nodes. It follows that
$A' \leq _T (B \oplus K)' \leq _T B"$
and, as
$K'$
is the bottom element among all double jumps,
$K' \leq _T B"$
. Thus
$A" \equiv _T B"$
.
As the constructions of V and U included for every Turing degree above
$K'$
a
$2$
-generic infinite branch B of U such that the double jump
$B"$
is in the given Turing degree, one has that the double jumps of the infinite branches of T cover all Turing degrees above
$K'$
.
Proposition 17. Every nonrecursive infinite branch A of T has minimal Turing degree.
Proof. Let A be a nonrecursive infinite branch of T. Consider a total function
$\varphi _e^A$
. By the proof of Proposition 14 there is a
$\sigma $
such that all infinite branches
$\tilde A$
of T above
$\sigma $
,
$\varphi ^{\tilde A}_e$
is total.
If now there is such an infinite branch
$\tilde A$
extending
$\sigma $
which is different from A but for which
$\varphi _e^A$
and
$\varphi _e^{\tilde A}$
coincide, then it follows that above the branching node
$\sigma '$
of A and
$\tilde A$
, all infinite branches of S produce the same function
$\varphi ^A_e$
and so this function is recursive. To see this, assume otherwise. Then
$\sigma ' 0$
or
$\sigma ' 1$
would be extended into a sufficiently long prefixes of the respective A and
$\tilde A$
in order to achieve that these prefixes are mapped by
$\varphi _e$
on some value to different images and then one of the infinite branches A or
$\tilde A$
would be cut off, so they would not be both on the tree.
So one has that there is a
$\sigma " \preceq A$
such that, for all infinite branches
$\tilde A$
of S extending
$\sigma "$
, either the functions
$\varphi ^{\tilde A}_e$
are all different or are all the same.
If they are all different, one can Turing reduce A to
$\varphi _e^A$
. Whenever there are two different extensions above some
$\sigma "' \succeq \sigma "$
, one coenumerates T and simulates
$\varphi _e$
until either an e-splitting at some x above
$\sigma "' 0$
and
$\sigma "' 1$
is found so that
$\varphi _e^A(x)$
says which branch to follow or one of the two nodes
$\sigma "'0$
and
$\sigma "'1$
has been enumerated out of T. Thus
$A \equiv _T \varphi ^A_e$
by the usual e-splitting analysis.
If the infinite branches of T above
$\sigma "$
are mapped by
$\varphi _e$
all to the same image, then one can for each input x coenumerate T until a level
$\ell> |\sigma "|$
and a time t are found such that all
$\tau \in \{0,1\}^\ell \cap S_t$
which extend
$\sigma "$
satisfy that
$\varphi ^\tau _{e,t}(x)$
is a unique value y and equals to
$\varphi ^A_e(x)$
. Thus
$\varphi ^A_e$
is recursive in this case. Thus the minimality of A is verified.
Proposition 18. The nonisolated branches of T form a perfect tree.
Proof. Recall that every infinite branch B of U is
$2$
-generic and that the infinite branches of U form a perfect subtree V of U by Proposition 6 and Corollary 7.
There is a K-recursive operator which maps the infinite branch B of U to the infinite branch
$A = T[B]$
where the “branching string” of A in T is exactly the set B. This mapping is one-one and continuous. Furthermore, if
$B_0, B_1, \ldots $
converge pointwise to B and all
$B_k \neq B$
then the infinite branches
$T[B_k]$
converge pointwise to
$A = T[B]$
. Hence the nonrecursive infinite branches of U are mapped in a bijection to the nonisolated infinite branches of T and this bijection preserves pointwise limits; as the class of infinite branches of U and its image in T are both closed in the sense of topology, the limit of each convergent sequence is again an infinite branch of the corresponding tree. Thus the nonisolated infinite branches of T form a perfect subtree of T which is recursive in
$K'$
.
4 Further results
This section provides certain results which were already proven in the conference version from 2012 but never published in a journal. The results are included for the sake of completeness of the exposition of this article and some of the claimed results are left as open questions in the conclusion. So this article is based on both conference versions, that from 2012 and that from 2022.
Theorem 19. If A is an infinite branch of a recursive tree T where every infinite branch is hyperimmune-free then A is also an infinite branch of a recursive tree S with uncountably many infinite branches such that all of these are hyperimmune-free.
Proof. This can easily be seen. Let U be any tree with uncountably many infinite branches which are all of hyperimmune-free Turing degree and let
$S = T \cup U$
. Clearly S is also a recursive tree and a set B is an infinite branch of S if it is an infinite branch of one of these trees. Thus the number of these infinite branches is uncountable and all of these are of hyperimmune-free Turing degree.
Recall that a
$\Pi ^0_2$
-singleton A is a set A for which there is an index e such that A is the only set for which
$\varphi _e^A$
is total. Without loss of generality one can select this index e such that whenever
$\varphi _e^B(x)$
is defined for some oracle B and
$y<x$
then
$\varphi _e^B(y)$
is also defined.
Proposition 20. Every hyperimmune-free
$\Pi ^0_2$
-singleton is recursive.
Proof. Assume now that A is hyperimmune-free and e is an index such that
$\varphi _e^B$
is total if and only if
$B = A$
. As A is hyperimmune-free, there is a recursive function which majorises the A-recursive function measuring for each input x how much time
$\varphi ^A_e(x)$
needs to compute the result and what the largest query is. In particular, there is a recursive function f such that, for all x,
$\varphi _{e,f(x)}^A(x)$
is defined, that is, the computation converges within time
$f(x)$
and does not query A beyond
$f(x)$
. Thus A is actually the singleton of a
$\Pi ^0_1$
class, as one can define the class as the class of all oracles B where, for all x,
$\varphi ^B_{e,f(x)}(x)$
converges within time
$f(x)$
to its output and does not query values bigger than
$f(x)$
. So, A is an isolated infinite branch—indeed even the only infinite branch—of the recursive tree of all B where the use of
$\varphi _e^B(x)$
is below
$f(x)$
and thus A is recursive.
Proposition 21. Only the recursive sets are both unrelativised hyperimmune-free and hyperimmune-free relative to some PA-complete set
$B \leq _T K$
.
Proof. So assume that A is hyperimmune-free and undecidable. Then
$A \not \leq _T K$
. There is a uniformly co-r.e. sequence
$\tilde B_0,\tilde B_1,\ldots $
of all co-r.e. trees and, as B is PA-complete, there is furthermore a sequence
$B_0,B_1,\ldots $
of sets such that either
$B_e$
is an infinite branch of
$\tilde B_e$
or
$\tilde B_e$
does not have an infinite branch. Note that A is not in the list as
$A \not \leq _T B$
. Some
$A \oplus B$
recursive function computes on input e the first x where
$A(x)$
and
$B_e(x)$
differ. Since A is hyperimmune-free relative to B, this function is majorised by a B-recursive function g. Now AA is an infinite branch of the B-recursive tree T obtained by removing, for each e, all strings properly extending the prefix
$\sigma _e$
of
$B_e$
of length
$g(e)+2$
. Furthermore, as A is hyperimmune-free, there is an A-recursive function h such that
$h(x)$
is the first time
$t \geq x$
where all prefixes
$A(0)A(1)\dots A(y)$
with
$y \leq x$
satisfy that they are in the t-th approximation of T. This function h has a recursive majorant
$\ell $
as A is hyperimmune-free. Now one has that the following tree S is recursive and A is an infinite branch of it: S contains all binary strings
$\sigma $
such that for all prefixes
$\tau $
of
$\sigma $
,
$\tau $
is inside the t-th approximation of T for some
$t \in \{|\sigma |,|\sigma |+1, \ldots ,\ell (|\sigma |)\}$
. Thus all prefixes of A are in S and A is an infinite branch of S. Furthermore, if
$\sigma \notin T$
, then
$\sigma \notin T_t$
for all t from some s onwards and all
$\tau \succeq \sigma $
with
$|\tau |>s$
are not in S. Thus no
$B_e$
is an infinite branch of S. There is a co-r.e. index e of S and then
$B_e$
is an infinite branch of S, a contradiction. Thus A cannot have the following three properties at the same time: hyperimmune-free, hyperimmune-free relative to B, and nonrecursive. This completes the proof.
The next result shows some type of highness-preservation when relativising relative to a hyperimmune-free oracle A. The main reason is Martin’s Theorem that highness and domination of all recursive/A-recursive functions is the same. That is, if A is hyperimmune-free and B is high, then B computes some function f which dominates all recursive functions—thus f also dominates all A-recursive functions and furthermore
$f \leq _T A \oplus B$
, as everything computable relative to B is also computable relative to
$A \oplus B$
. By Martin’s Theorem, relativised to A, it then follows that
$(A \oplus B)' \geq A"$
. This is stated formally in the next proposition.
Proposition 22. If A is hyperimmune-free and B is high then
$A \oplus B$
is high relative to A, that is,
$(A \oplus B)' \geq _T A"$
.
Kučera and Nies [Reference Kučera and Nies9] proved that if a
$\Sigma ^0_2$
-set is strictly above K then it computes the jump of a nonrecursive hyperimmune-free set. The next result looks at the converse of this, what can be said about a
$\Sigma ^0_2$
-set B computed by the jump of any hyperimmune-free set.
Theorem 23. If A is hyperimmune-free and
$A'$
computes a
$\Sigma ^0_2$
-set B then
$B \leq _T K$
.
Proof. The set B can be approximated by a recursive function g in the sense that
$g(x,s) = 1$
for almost all x if and only if
$x \in B$
; furthermore, there is an A-recursive function f which converges for all x to
$B(x)$
, that is,
$B(x) = \lim _s f(x,s)$
. Now there is an A-recursive function h such that, for all x,
$h(x)$
is the first stage s such that, for all
$y \leq x$
, there are at least x stages
$t \leq s$
with
$f(x,t) = g(x,t)$
; note that for each x there are infinitely many such t: if
$f(x,t)$
converges to
$0$
then
$g(x,t) = 0$
for infinitely many t and if
$f(x,t)$
converges to
$1$
then
$g(x,t)$
also converges to
$1$
. There is now a recursive majorant k of h, that is,
$k(x) \geq h(x)$
for all x.
Now one defines
$\tilde g(x,s)$
as follows: If there are at least
$x+s$
many
$t \leq k(x+2s)$
with
$g(x,t) = 0$
then
$g(x,s) = 0$
else
$g(x,s) = 1$
.
If
$x \in B$
this can happen only finitely often as
$g(x,s)$
converges to
$1$
; if
$x \notin B$
then f makes only finitely often a mistake and there are at most u many t with
$f(x,t) = 0$
. It follows that there are, for
$s \geq u$
, at least
$x+2u$
many
$t \leq k(x+2s)$
where
$f(x,t) = g(x,t)$
; so there are
$x+s$
many
$t \leq k(x+2s)$
with
$g(x,t) = 0$
. Thus
$\tilde g$
witnesses that B is limit recursive, that is,
$B \leq _T K$
.
Theorem 24. If B is
$2$
-generic and
$B \leq _T K'$
then there exists a hyperimmune-free A such that
$A' \equiv _T B' \equiv _T B \oplus K$
; furthermore, A can be chosen to be Schnorr trivial.
The idea is that one takes the
$K'$
-recursive tree V from Proposition 6 and forms the union with the single tree having the set B—which is also
$K'$
-recursive—as its only and infinite branch. So one obtains again a
$K'$
-recursive tree having only
$2$
-generic infinite branches. Then one uses Corollary 7 and the main result Theorem 8 to get the corresponding trees U and T. Now there is a hyperimmune-free set A of T such that
$A \oplus K \equiv _T B \oplus K$
where B is the given infinite branch of V and, thus, U. The A constructed is also Schnorr-trivial and of minimal Turing degree. While most properties of the constructions also apply to the A mentioned here, it cannot be guaranteed that A is not isolated on the tree. This would require further tweeking, that is, if B is isolated on V one would have to create further infinite branches of V in order to make B part of a dense tree consisting entirely of
$2$
-generic sets. The old conference version from 2012 contains a relativised version of the above theorem with an alternative proof [Reference Ng, Stephan, Yang and Yu13, Theorem 4.4].
Furthermore, one can also modify V such that it only contains uncountably many infinite branches B such that each B is
$2$
-generic and hyperimmune-free relative to
$K'$
. Then one constructs from V the K-r.e. tree U (with the same infinite branches) and the recursive tree T such that the branches A of T derived from infinite branches B of V are hyperimmune-free and minimal and Schnorr-trivial. The so obtained tree T has only hyperimmune-free branches which are also hyperimmune-free relative to
$K'$
. Thus one gets the following improved version of [Reference Ng, Stephan, Yang and Yu13, Proposition 3.5].
Theorem 25. There is a recursive tree T with uncountably many infinite branches such that all of these are hyperimmune-free unrelativised as well as hyperimmune-free relative to
$K'$
.
5 Concluding remarks
The presented proof shows that one can construct a co-r.e. tree such that every branch is infinite and that every infinite branch is either isolated or has all of the following properties: nonrecursive, hyperimmune-free, generalised low
$_1$
, minimal Turing degree, Schnorr-trivial, and jump traceable. Furthermore, the nonisolated infinite branches form a perfect tree and its double jumps cover the cone above
$K'$
and each of its jumps is also the jump of a
$2$
-generic set. The key idea was to use the guidance tree U and to transform it into the final co-r.e. tree T so that every nonisolated infinite branch A of T has the branching bits from an infinite branch B of U, which guides the building of the tree. The construction could be a bit varied to get the following related results.
First, instead of taking V to be the union of all
$V[\tilde B]$
in Proposition 6, one could take a
$K'$
-recursive tree with uncountably many
$K'$
-hyperimmune-free and
$2$
-generic branches and then get the result that there is a tree T with uncountably many infinite branches such that every infinite branch is hyperimmune-free, hyperimmune-free relative to
$K'$
, jump-traceable, and jump-traceable relative to
$K'$
. It is possible to iterate this.
Second, if
$B \leq _T K'$
is
$2$
-generic then one can construct a K-r.e. tree U with B being its unique infinite branch. The resulting tree T has then exactly one nonisolated and nonrecursive branch which is
$A = T[B]$
. This gives a co-r.e. tree of Cantor–Bendixson rank
$2$
with exactly one nonisolated branch
$A = T[B]$
which is nonrecursive, hyperimmune-free, and generalised low
$_1$
and satisfies
$A \oplus K = B \oplus K$
.
Third, note that a perfect co-r.e. tree T without dead ends has always an infinite branch which is high, thus one cannot avoid the isolated branches in the construction of T which make the tree T to be a nonperfect enlargement of a perfect tree. If T would not have isolated infinite branches then all infinite branches would be hyperimmune-free and minimal, thus they would not be below the halting problem in contradiction to the Low Basis Theorem of Jockusch and Soare [Reference Jockusch and Soare8]. So the Cantor–Bendixson rank of the tree T constructed in Theorem 1 must be at least
$1$
, as was also stated without proof by Ng et al. [Reference Ng, Stephan, Yang and Yu13]. The same applies to trees with uncountably many infinite branches where the jumps of all infinite branches avoid some upper cone.
The following questions are left open. For the first, it was claimed by Nget al. [Reference Ng, Stephan, Yang and Yu13, Theorem 3.6] that a modification of the proof of the main result of this article would give the result; however, this proof is now a new proof by other means and the authors are not aware how to incorporate the Robinson guessing into it. The original proof did not work out and required more and more corrective items to make the construction work without the whole construction ever getting completed.
Open Problem 26.
-
1. Are there any hyperimmune-free sets which are hyperimmune-free relative to every low recursively enumerable set? If so, are there uncountably many of those?
-
2. Is every jump of a nonrecursive hyperimmune-free set also the jump of a $2$
-generic set? The converse is known [Reference Ng, Stephan, Yang and Yu13, Theorem 4.4]. -
3. Is the jump of every hyperimmune-free set also the jump of a hyperimmune-free Schnorr-trivial set?
Acknowledgments
The authors would like to thank the referees of the JSL as well as of previous conference versions for many helpful comments and suggestions.
Funding
K.M. Ng. has been supported by the Singapore Ministry of Education grant RG23/19 at NTU. F. Stephan. and Y. Yang. have been supported in part by the Singapore Ministry of Education Tier 2 grants AcRF MOE2019-T2-2-121/R146-000-304-112 and MOE-000538-01 as well as by the NUS Tier 1 grants AcRF R146-000-337-114 and R252-000-C17-114. L. Yu. has been supported by NSFC (Grant No. 12025103) and the Natural Science Foundation of Jiangsu Province (Grant No. BK20243060).
Open access
