# Forcing with Bushy Trees

Mushfeq Khan  Department of Mathematics
University of Hawai‘i at Mānoa
Honolulu, HI 96822, USA<EMAIL_ADDRESS>and  Joseph S. Miller
Department of Mathematics
University of Wisconsin
Madison, WI 53706-1388, USA<EMAIL_ADDRESS>
(Last compilation:
Last time the following date was changed: September 2nd, 2014)

###### Abstract.

We present several results that rely on arguments involving the combinatorics
of “bushy trees”. These include the fact that there are arbitrarily slow-
growing diagonally noncomputable ($\mathrm{DNC}$) functions that compute no
Kurtz random real, as well as an extension of a result of Kumabe in which we
establish that there are $\mathrm{DNC}$ functions relative to arbitrary
oracles that are of minimal Turing degree. Along the way, we survey some of
the existing instances of bushy tree arguments in the literature.

##  1\. Introduction

In 1985, Sacks [15] asked if there exist diagonally noncomputable (or
$\mathrm{DNC}$) functions of minimal Turing degree. Kumabe answered the
question in 1993, constructing such a function and pioneering the application
of bushy tree arguments in computability theory. A draft of the proof [12] was
in private circulation by 1996, but has remained unpublished.

Arguments involving bushy trees and their combinatorics have since been
applied to several questions concerning $\mathrm{DNC}$ functions. In 2000,
Simpson and Giusto [7] asked if the reverse mathematics axiom system
$\mathrm{DNC}$ is stronger than the system $\mathrm{WWKL_{0}}$. In 2004,
Ambos-Spies, Kjos-Hanssen, Lempp, and Slaman [1] used ideas from Kumabe’s
proof to provide an affirmative answer.

In 2009, motivated by questions around Yates’s long-standing open problem
about whether every minimal degree has a strong minimal cover, Lewis
collaborated with Kumabe to produce a simplified version [13] of Kumabe’s
proof, the publication of which introduced the technique of “bushy tree
forcing” to the wider community.

A simpler variation on the technique appeared in Greenberg and Miller’s 2011
result [8] that there are arbitrarily slow-growing $\mathrm{DNC}$ functions
that compute no Martin-Löf random real.

More recently, Beros [2] has applied arguments involving bushy trees to show
that there exist $\mathrm{DNC}$ functions that compute no effectively bi-
immune set, answering a question of Jockusch and Lewis [10]. Meanwhile,
Dorais, Hirst, and Shafer [4], building on the aforementioned work of Ambos-
Spies, et al. [1], have shown that the reverse mathematics principle “there
exists a $k$ such that for every function $f$ there is a $k$-bounded function
that is $\mathrm{DNC}$ relative $f$” does not imply the existence of a
$\\{0,1\\}$-valued $\mathrm{DNC}$ function in the absence of $\Sigma^{0}_{2}$
induction, answering a question of Simpson.

We add two new results to this growing collection. Theorem 4.2 is a variation
on the Greenberg-Miller result mentioned above, stronger in one aspect, but
(necessarily) weaker in another: There are arbitrarily slow-growing
$\mathrm{DNC}$ functions that compute no Kurtz random real, although this fact
cannot be partially relativized to yield a $\mathrm{DNC}$ function relative to
an arbitrary oracle. Theorem 5.1, due to the first author, is a partial
relativization of Kumabe’s theorem. It asserts the existence of $\mathrm{DNC}$
functions relative to arbitrary oracles that are of minimal Turing degree.

One of the goals of the current paper is to study the diverse applications of
bushy tree arguments in computability theory with a view to understanding what
the similarities and differences between them are. In the case of forcing
arguments, we are particularly interested in how properties of the partial
order determine properties of the generic object (typically a $\mathrm{DNC}$
function). The definitions and combinatorial lemmas in Section 2 underly all
of the arguments we present, and encapsulate some of the similarities.

The differences can be seen to occur primarily along three “axes”. The first
of these relates to the nature of the approximation to the generic object. In
some arguments, the approximations are finite strings (what we term “basic
bushy forcing”), while others involve maintaining infinite trees. A second
major difference is in the complexity of what we label the “bad set”. These
are sets of strings that are declared to be off limits in a construction. Some
arguments (Theorem 4.2, for example) require that the bad sets be computably
enumerable, and these are not automatically amenable to partial
relativization. In others, dropping the assumption of any form of effectivity
on the bad set allows partial relativization (as in Theorem 5.1), but may
require more complicated combinatorics, or a different assumption on the
effectivity of the approximation. The third major difference is in whether the
resulting $\mathrm{DNC}$ function can be constructed pointwise below a
preimposed order function. This is possible, for example, in Theorem 4.2, but
the question of whether it is possible in Theorem 5.1 is an important open
one.

##  2\. Definitions and combinatorial lemmas

######  Definition 2.1.

Given $\sigma\in\omega^{<\omega}$, we say that a tree
$T\subseteq\omega^{<\omega}$ is _$n$ -bushy above $\sigma$_ if every element
of $T$ is comparable with $\sigma$, and for every $\tau\in T$ that extends
$\sigma$ and is not a leaf of $T$, $\tau$ has at least $n$ immediate
extensions in $T$. We will refer to $\sigma$ as the _stem_ of $T$.

Note that the set of initial segments of $\sigma$ is actually $n$-bushy above
$\sigma$ according to the definition above.

######  Definition 2.2.

Given $\sigma\in\omega^{<\omega}$, we say that a set
$B\subseteq\omega^{<\omega}$ is _$n$ -big above $\sigma$_ if there is a finite
$n$-bushy tree $T$ above $\sigma$ such that all its leaves are in $B$. If $B$
is not $n$-big above $\sigma$ then we say that $B$ is _$n$ -small_ above
$\sigma$.

We begin by establishing some of the basic combinatorial properties of bushy
trees. The first observation is that we can extend the leaves of an $n$-bushy
tree with $n$-bushy trees to obtain another $n$-bushy tree:

######  Lemma 2.3 (Concatenation property).

Suppose that $A\subseteq\omega^{<\omega}$ is $n$-big above $\sigma$. If
$A_{\tau}\subseteq\omega^{<\omega}$ is $n$-big above $\tau$ for every $\tau\in
A$, then $\bigcup_{\tau\in T}A_{\tau}$ is $n$-big above $\sigma$.

The second property that we use frequently is known as the _smallness
preservation property_. This is the _second sparse subset property_ of Kumabe
and Lewis [13], and Lemma 5.4 of Greenberg and Miller [8].

######  Lemma 2.4 (Smallness preservation property).

Suppose that $B$ and $C$ are subsets of $\omega^{<\omega}$, that
$m,n\in\omega$ and that $\sigma\in\omega^{<\omega}$. If $B$ and $C$ are
respectively $m$-small and $n$-small above $\sigma$ then $B\cup C$ is
$(n+m-1)$-small above $\sigma$.

###### Proof.

Let $T$ be an $(m+n-1)$-bushy tree above $\sigma$ with leaves in $B\cup C$. We
show that either $B$ is $m$-big above or $C$ is $n$-big above $\sigma$. Label
a leaf $\tau$ of $T$ “B” if it is in $B$, “C” otherwise. Now if $\rho$ is the
immediate predecessor of $\tau$, then $\rho$ has at least $(m+n-1)$ immediate
extensions on $T$, each of which are labeled either “B” or “C”. Then either
$m$ of these are labeled “B”, in which case we label $\rho$ “B”, or $n$ are
labeled “C”, in which case we label $\rho$ “C”. Continuing this process leads
to $\sigma$ eventually getting a label. It is clear that if $\sigma$ is
labeled “B” then $B$ is $m$-big above $\sigma$. Otherwise $C$ is $n$-big above
$\sigma$. ∎

The third property is known as the _small set closure property_ :

######  Lemma 2.5 (Small set closure property).

Suppose that $B\subset\omega^{<\omega}$ is $k$-small above $\sigma$. Let
$C=\\{\tau\in\omega^{<\omega}:\text{$B$ is $k$-big above $\tau$}\\}$. Then $C$
is $k$-small above $\sigma$. Moreover $C$ is _$k$ -closed_, meaning that if
$C$ is $k$-big above a string $\rho$, then $\rho\in C$.

###### Proof.

Suppose that $C$ is $k$-big above a string $\rho$. Then, since $B$ is $k$-big
above every $\tau\in C$, by the concatenation property, $B$ is $k$-big above
$\rho$, so $\rho\in C$. The lemma follows immediately. ∎

The small set closure property is quite useful in the context of a forcing
construction. Typically, $\sigma$ is an approximation to a function that we
are building and $B$ is a set of strings that must be avoided in order to
ensure that requirements remain met. We refer informally to the set $B$ as the
“bad set”. Throughout the construction, we may wish to maintain the property
that the bad set $B$ is $k$-small above $\sigma$ for some $k\in\omega$.
Clearly, if $B$ is $k$-big above some string $\rho$, then $\rho$ is off-limits
as well. Lemma 2.5 allows us to assume that all such strings are already in
the bad set, while preserving its smallness. From now on, whenever we deal
with a bad set that is $k$-small, we also assume that it is $k$-closed. Note
that the $k$-closure of a c.e. set of strings is also c.e.

##  3\. Basic bushy forcing

As a first illustration of the convenience afforded us by these lemmas, we
present a proof of a well-known result. Any bounded $\mathrm{DNC}$ function
(i.e., a function in $\mathrm{DNC}_{k}$ for some $k\geq 2$) computes a
function in $\mathrm{DNC}_{2}$. However, Jockusch showed in [9] that this is
not uniform.

######  Theorem 3.1 (Jockusch [9]).

For each $n\geq 2$, there is no single functional $\Gamma$ such that for all
$f\in\mathrm{DNC}_{n+1}$, $\Gamma^{f}\in\mathrm{DNC}_{n}$.

###### Proof.

Let us assume that such a $\Gamma$ exists, i.e., for all
$f\in\mathrm{DNC}_{n+1}$, $\Gamma^{f}\in\mathrm{DNC}_{n}$. The set of
sequences in $\mathrm{DNC}_{n+1}$ is a $\Pi^{0}_{1}$ class in
$(n+1)^{\omega}$, so we may obtain a functional $\Xi$ that is total on
$(n+1)^{\omega}$ and that agrees with $\Gamma$ on every member of
$\mathrm{DNC}_{n+1}$. We may also assume that $\Xi^{f}\in n^{\omega}$ for all
$f\in(n+1)^{\omega}$.

For each $m\in\omega$ and for each $i<n$, let
$\Lambda_{i,m}=\\{\sigma\in(n+1)^{<\omega}:\Xi^{\sigma}(m)=i\\}$. By the
compactness of $(n+1)^{\omega}$, there exists a finite level $k$ such that for
every string $\tau\in(n+1)^{k}$, $\Xi^{\tau}(m)$ converges. Therefore,
$\bigcup_{i<n}\Lambda_{i,m}$ is $(n+1)$-big above the empty string
$\langle\rangle$. It is now easy to see, by repeatedly applying the smallness
preservation property, that for some $i<n$, $\Lambda_{i,m}$ must be $2$-bushy
above $\langle\rangle$.

We specify a partial computable function $\varphi$. On input $m$, $\varphi$
searches for a $2$-bushy tree $T$ above $\langle\rangle$ such that for every
leaf $\tau$ of $T$, $\Xi^{\tau}(m)$ converges to the same value, say $i$, and
when it finds such a tree, itself outputs $i$. By the argument above, such a
tree must exist, and so $\varphi(m)$ is defined for each $m$. Let $e$ be the
index for $\varphi$, and let $T_{e}$ be the $2$-bushy tree that $\varphi$
finds on input $e$. Since $T_{e}$ is $2$-bushy, there is a leaf $\tau$ of
$T_{e}$ that is $\mathrm{DNC}$, and so there is an $f\in(n+1)^{\omega}$
extending $\sigma$ that is $\mathrm{DNC}_{n+1}$. But then
$\Xi^{f}(e)=\Xi^{\tau}(e)=\varphi_{e}(e)$, which is a contradiction. ∎

Finitely iterating this strategy yields the following stronger result:

######  Theorem 3.2.

For each $n\geq 2$, there is no finite set of functionals
$\Gamma_{0},\Gamma_{1},...,\Gamma_{k}$ such that for all
$f\in\mathrm{DNC}_{n+1}$, there exists a $j\leq k$ such that
$\Gamma_{j}^{f}\in\mathrm{DNC}_{n}$.

###### Proof.

Let us assume that such a set of functionals exists. We define a new
functional $\Xi$ as follows: on input $e$, $\Xi$ simulates $\Gamma_{0}$
through $\Gamma_{k}$ on input $e$ and outputs the result of whichever one
converges first. Clearly, $\Xi$ is total on the class of $\mathrm{DNC}_{n+1}$
sequences, so we can assume that $\Xi$ is total on $(n+1)^{\omega}$. We then
proceed exactly as in the proof of Theorem 3.1, obtaining a string
$\sigma_{0}$ that is $\mathrm{DNC}_{n+1}$ and an $e\in\omega$ such that
$\Xi^{\sigma_{0}}(e)=\varphi_{e}(e)$. Then
$\Xi^{\sigma_{0}}(e)=\Gamma_{j}^{\sigma_{0}}(e)$ for some $j\leq k$. It
follows that $\Gamma_{j}$ fails to compute a $\mathrm{DNC}_{n}$ function on
any $f\in\mathrm{DNC}_{n+1}$ extending $\sigma_{0}$. We now repeat the same
process above $\sigma_{0}$ with the reduced list of functionals
$\\{\Gamma_{1},...,\Gamma_{k}\\}\setminus\\{\Gamma_{j}\\}$, obtaining a
$\mathrm{DNC}_{n+1}$ string $\sigma_{1}$ extending $\sigma_{0}$ that
diagonalizes against one of the remaining functionals. After $k+1$ iterations,
we will have obtained a contradiction. ∎

The previous proof points the way towards more sophisticated constructions
involving bushy trees where we satisfy countably many requirements. The next
result is our first example of such a construction. It features a simpler
variant of bushy tree forcing, which we term _basic bushy forcing_. In this
type of forcing, the approximation to the generic object is a finite string.

######  Theorem 3.3 (Ambos-Spies, Kjos-Hanssen, Lempp, and Slaman [1]).

There is a $\mathrm{DNC}$ function that computes no computably bounded
$\mathrm{DNC}$ function.

###### Proof.

The forcing conditions are pairs $(\sigma,B)$, where
$\sigma\in\omega^{<\omega}$, $B\subset\omega^{<\omega}$ and:

  * •

for some $k\in\omega$, $B$ is $k$-small above $\sigma$ (and without loss of
generality, $k$-closed)

  * •

$B$ is _upward closed_ (i.e., if $\gamma$ is in $B$, then all extensions of
$\gamma$ are in $B$).

The string $\sigma$ is an approximation to $f$ and the set $B$ is a “bad set”,
i.e., a set of strings that must be avoided in order to ensure that
requirements remain satisfied.

A condition $(\sigma,B)$ _extends_ another condition $(\tau,C)$ if
$\tau\preceq\sigma$ and $C\subseteq B$. Let $\mathbb{P}$ denote this partial
order. Now if $\mathcal{G}$ is a filter on $\mathbb{P}$, then for any two
elements $(\sigma,B)$ and $(\tau,C)$ of $\mathcal{G}$, $\sigma$ and $\tau$ are
comparable. Hence,
$f_{\mathcal{G}}=\bigcup\\{\sigma:(\sigma,B)\in\mathcal{G}\\}\in\omega^{\leq\omega}$.
In fact, we can ensure that $f_{\mathcal{G}}$ is total:

######  Claim 3.4.

If $\mathcal{G}$ is sufficiently generic with respect to $\mathbb{P}$, then
$f_{\mathcal{G}}$ is total.

###### Proof.

We show that the collection
$\mathcal{T}_{m}=\\{(\sigma,B)\in\mathbb{P}:|\sigma|\geq m\\}$ is dense in
$\mathbb{P}$. Suppose $(\sigma,B)\in\mathbb{P}$, where $|\sigma|<m$. Then $B$
is $k$-small above $\sigma$ for some $k\in\omega$. Clearly, the set
$C=\\{\tau\in\omega^{<\omega}:|\tau|\geq m\\}$ is $k$-big above $\sigma$. Let
$\tau$ be any string in $C\setminus B$. Then $(\tau,B)\in\mathbb{P}$. ∎

######  Claim 3.5.

If $\mathcal{G}$ is any filter on $\mathbb{P}$, then for all
$(\sigma,B)\in\mathcal{G}$, $f_{\mathcal{G}}$ has no initial segment in $B$.

###### Proof.

Suppose that $f_{\mathcal{G}}$ has an initial segment $\tau$ in $B$. Then
there is a $(\rho^{\prime},C^{\prime})\in\mathcal{G}$ such that
$\rho^{\prime}$ extends $\tau$. Let $(\rho,C)$ be a common extension of
$(\rho^{\prime},C^{\prime})$ and $(\sigma,B)$. Since $B$ is upward closed,
$\rho\in B$. But $B\subseteq C$, so $\rho\in C$. This is a contradiction,
since it follows that $C$ is $k$-big above $\rho$ for all $k\in\omega$. ∎

If $\Gamma$ is a functional and $h$ a computable function such that $\Gamma$
is $h$-valued (in other words, whenever $\Gamma$ converges with any oracle on
input $e$, its output is less than $h(e)$), let $\mathcal{D}_{\Gamma,h}$
denote the set of $(\sigma,B)\in\mathbb{P}$ such that for all
$g\in[\sigma]\setminus[B]^{\prec}$, $\Gamma^{g}$ is not a $\mathrm{DNC}_{h}$
function.

######  Claim 3.6.

For each computable function $h$, and $h$-valued functional $\Gamma$,
$\mathcal{D}_{\Gamma,h}$ is dense in $\mathbb{P}$.

###### Proof.

Suppose $(\sigma,B)\in\mathbb{P}$ and that $B$ is $k$-small above $\sigma$. As
in the proof of Theorem 3.1, we specify a partial computable function
$\varphi$. On input $m$, $\varphi$ searches for a $k$-bushy tree $T$ above
$\sigma$ such that for every leaf $\tau$ of $T$, $\Gamma^{\tau}(m)$ converges
to the same value $i<h(m)$. Upon finding such a tree, $\varphi$ outputs $i$.
Let $e$ be the index of $\varphi$.

There are now two cases. If the set $A=\\{\tau:\Gamma^{\tau}(e)\downarrow\\}$
is $(h(e)\cdot k)$-small above $\sigma$, then $A\cup B$ is $(h(e)\cdot
k+k-1)$-small above $\sigma$. Then $(\sigma,A\cup B)\in\mathbb{P}$ and extends
$(\sigma,B)$. Note that we have forced $\Gamma$ to be partial on any
$g\in[\sigma]\setminus[A\cup B]^{\prec}$. Hence, $(\sigma,A\cup
B)\in\mathcal{D}_{\Gamma,h}$.

On the other hand, if $A$ is $(h(e)\cdot k)$-big above $\sigma$, then for some
$i<h(e)$, $\\{\tau:\Gamma^{\tau}(e)\downarrow=i\\}$ is $k$-big above $\sigma$.
So $\varphi(e)$ is defined. In this case, we extend $\sigma$ to any $\tau$ not
in $B$ such that $\Gamma^{\tau}(e)\downarrow=\varphi(e)$. This forces
$\Gamma^{g}$ to fail to be $\mathrm{DNC}$ on any $g$ extending $\tau$. Hence,
$(\tau,B)\in\mathcal{D}_{\Gamma,h}$. ∎

Finally, we observe that the set of finite strings that are not
$\mathrm{DNC}$, which we denote by $B_{\mathrm{DNC}}$, cannot be $2$-big above
the empty string $\langle\rangle$, since any $2$-bushy tree contains a string
that is $\mathrm{DNC}$. So $(\langle\rangle,B_{\mathrm{DNC}})\in\mathbb{P}$.
Let $\mathcal{G}$ be a filter on $\mathbb{P}$ containing
$(\langle\rangle,B_{\mathrm{DNC}})$ that meets $\mathcal{T}_{m}$ for every
$m\in\omega$ and $\mathcal{D}_{\Gamma,h}$ for every computable function $h$
and $h$-valued functional $\Gamma$ (note that this is a countable collection
of dense sets).

By Claim 3.4, $f_{\mathcal{G}}$ is total. By Claim 3.5 and the fact that
$(\langle\rangle,B_{\mathrm{DNC}})\in\mathcal{G}$, $f_{\mathcal{G}}$ is a
$\mathrm{DNC}$ function. If $f_{\mathcal{G}}$ computes a function in
$\mathrm{DNC}_{h}$ for some computable function $h$, then it does so via an
$h$-valued functional $\Gamma$. Claim 3.6 shows that this is not the case.
This concludes the proof of Theorem 3.3.∎

We note that while the bad sets in the previous proof are c.e., we do not make
use of this fact. Given an oracle $X$, let $B^{X}_{\mathrm{DNC}}$ denote the
set of finite strings that are not $\mathrm{DNC}$ _relative to $X$_. Note that
$B^{X}_{\mathrm{DNC}}$ is not necessarily c.e., but is nevertheless $2$-small
above $\langle\rangle$. This suggests that we could use the same sort of
techniques to construct a function that is $\mathrm{DNC}$ relative to $X$. As
an example, we prove a theorem that implies the main result in [1], and is
slightly stronger.

######  Theorem 3.7.

Fix an order function $h$. Suppose $X$ computes no $\mathrm{DNC}_{h}$
function. Then there is an $f$ that is $\mathrm{DNC}$ relative to $X$ such
that $f\oplus X$ computes no $\mathrm{DNC}_{h}$ function.

###### Proof.

The forcing partial order is the same as before. If $\Gamma$ is an $h$-valued
functional, let $\mathcal{D}_{\Gamma}$ denote the set of
$(\sigma,B)\in\mathbb{P}$ such that for all
$f\in[\sigma]\setminus[B]^{\prec}$, $\Gamma^{f\oplus X}$ is not a
$\mathrm{DNC}_{h}$ function. We show that $\mathcal{D}_{\Gamma}$ is dense in
the partial order. Suppose $(\sigma,B)$ is a condition where $B$ is $k$-small
above $\sigma$.

First, if there are $x,l\in\omega$ such that

$C_{x}=\\{\tau\in\omega^{<\omega}:\Gamma^{\tau\oplus
X}(x)\operatorname{\downarrow}\\}$

is $l$-small above $\sigma$, then the condition $(\sigma,B\cup C_{x})$ extends
$(\sigma,B)$ and forces the divergence of $\Gamma^{f_{\mathcal{G}}\oplus
X}(x)$. Therefore, let us assume that for each $x,l\in\omega$, $C_{x}$ is
$l$-big above $\sigma$.

Next, if there exists an $x\in\omega$ such that $\varphi_{x}(x)$ converges and

$N_{x}=\\{\tau\in\omega^{<\omega}:\Gamma^{\tau\oplus
X}(x)\operatorname{\downarrow}=\varphi_{x}(x)\\}$

is $k$-big above $\sigma$, then there is a $\tau$ extending $\sigma$ not in
$B$ such that $\Gamma^{\tau\oplus
X}(x)\operatorname{\downarrow}=\varphi_{x}(x)$, and so the condition
$(\tau,B)$ extends $(\sigma,B)$ and forces that $f_{\mathcal{G}}$ is not
$\mathrm{DNC}$. Therefore, let us assume that for each $x\in\omega$, either
$\varphi_{x}(x)$ diverges or $N_{x}$ is $k$-small above $\sigma$.

We now describe how to compute a $\mathrm{DNC}_{h}$ function from $X$, which
yields a contradiction. On input $x$, search for a $k$-bushy tree $T$ above
$\sigma$ such that for every leaf $\tau$ of $T$, $\Gamma^{\tau\oplus X}(x)$
converges to the same value $j<h(x)$, then output $j$. Since for each $x$,
$C_{x}$ is $(h(x)\cdot k)$-big above $\sigma$, such a tree $T$ exists. So the
$X$-computable function just described is total. Moreover, it disagrees with
$\varphi_{x}(x)$ whenever it is defined, since $N_{x}$ is $k$-small above
$\sigma$.

Therefore, $\mathcal{D}_{\Gamma}$ is dense. Let $\mathcal{G}$ be a generic
filter including the condition $(\langle\rangle,B^{X}_{\mathrm{DNC}})$. Then
$f_{\mathcal{G}}$ has the required properties. ∎

With a stronger assumption, the technique in the proof of Theorem 3.7 yields a
stronger conclusion: If $X$ computes no computably bounded $\mathrm{DNC}$
function, then there is an $f$ that is $\mathrm{DNC}$ relative to $X$ such
that $f\oplus X$ computes no computably bounded $\mathrm{DNC}$ function. We
omit the proof.

An analysis of the amount of bushiness we require above $\sigma$ in the
diagonalization argument of Claim 3.6 yields the following:

######  Theorem 3.8 (Ambos-Spies, et al. [1]).

For each order function $h$ there is an order function $j$ and a function
$f\in\mathrm{DNC}_{j}$ that computes no function in $\mathrm{DNC}_{h}$.

###### Proof.

If $j$ is an order function, let $j^{n}$ denote the space

$\prod_{m<n}\\{0,1,...,j(m)-1\\},$

and let $j^{<\omega}$ and $j^{\omega}$ be defined in the obvious way.

We now fix a computable function $h$ and let $(\Gamma_{i})_{i\in\omega}$ be an
effective enumeration of all $h$-valued Turing functionals. We define an order
function $j$ by recursion. In order to define $j$, we will also define an
auxiliary computable function $q:\omega^{<\omega}\times\omega^{2}$, the
definition of which will refer to the index of the function $j$. This is
possible because we can assume, by the recursion theorem, that we have access
to the index of $j$ in advance.

On input $x$, $\varphi_{q(\sigma,i)}$ searches for a $|\sigma|$-bushy tree $T$
above $\sigma$ contained in $j^{<\omega}$ such that for every leaf $\tau$ of
$T$, $\Gamma_{i}^{\tau}(x)$ converges to the same value $k<h(x)$, and upon
finding such a tree, itself outputs $k$. Now let $\bar{q}=\max_{i<n,\sigma\in
j^{n}}q(\sigma,i)$. We define $j(n)$ to be the larger of $\max_{i<n}j(i)$ and
$((h(\bar{q}(n))+1)\cdot n)+2$.

The forcing conditions are now pairs $(\sigma,B)$ where $B\subseteq
j^{<\omega}$ and $\sigma\in j^{<\omega}\setminus B$. We require that $B$ be
upward-closed and $|\sigma|$-small above $\sigma$. By the small set closure
property, we may assume that $B$ is $|\sigma|$-closed. For $\sigma\in
j^{<\omega}$, let $[\sigma]_{j}$ denote $\\{X\in j^{\omega}:\sigma\prec X\\}$.

######  Claim 3.9.

Let $\mathcal{D}_{i}$ denote the set of $(\sigma,B)\in\mathbb{P}$ such that
for all $g\in[\sigma]_{j}\setminus[B]^{\prec}$, $\Gamma_{i}^{g}$ is not a
$\mathrm{DNC}_{h}$ function. Then for each $i\in\omega$, $\mathcal{D}_{i}$ is
dense in $\mathbb{P}$.

###### Proof.

Suppose that $(\sigma,B)\in\mathbb{P}$. By suitably extending $\sigma$, we can
assume that $|\sigma|>i$. Let $n=|\sigma|$ and

$A=\\{\tau\in j^{<\omega}:\Gamma_{i}^{\tau}(q(\sigma,i))\downarrow\\}.$

As in the proof of Claim 3.6, there are two cases.

If $A$ is $(h(q(\sigma,i))\cdot n)$-small above $\sigma$, then letting
$c=(h(q(\sigma,i))\cdot n+n-1)$, $A\cup B$ is $c$-small above $\sigma$. Let
$C$ be the $c$-closure of $A\cup B$. Since $j(n)\geq(h(q(\sigma,i))+1)\cdot
n>c$ and $j$ is nondecreasing, $j^{c}$ is $c$-big above $\sigma$. Let $\tau$
be any string extending $\sigma$ in $j^{c}\setminus C$. Then $(\tau,C)$ is a
condition. Further, $\Gamma_{i}^{f}$ is partial on any
$f\in[\tau]_{j}\setminus[C]^{\prec}$, so $(\tau,C)\in\mathcal{D}_{i}$.

On the other hand, if $A$ is $(h(q(\sigma,i))\cdot n)$-big above $\sigma$,
then for some $k<h(q(\sigma,i))$, the set $\\{\tau\in
j^{<\omega}:\Gamma_{i}^{\tau}(q(\sigma,i))\downarrow=k\\}$ is $n$-big above
$\sigma$. It follows that $\varphi_{q(\sigma,i)}(q(\sigma,i))$ is defined. So
there is a $\tau\in j^{<\omega}\setminus B$ extending $\sigma$ such that
$\Gamma_{i}^{\tau}(q(\sigma,i)))=\varphi_{q(\sigma,i)}(q(\sigma,i))$. Then
$(\tau,B)\in\mathbb{P}\cap\mathcal{D}_{i}$. ∎

This concludes the proof of Theorem 3.8.∎

######  Theorem 3.10.

Given any order function $g$, there is an order function $h$ and an
$f\in\mathrm{DNC}_{g}$ such that $f$ computes no $\mathrm{DNC}_{h}$ function.

###### Proof.

We define $h$ inductively. Let $n_{0}=0$ and let $h(0)=2$. At the $i$th stage
of the construction, suppose we have defined it up to $n_{i}$. Let $k\geq
n_{i}+1$ be the least such that $g(k)\geq(h(n_{i})+1)\cdot g(n_{i})$. Let
$q(\sigma)$ be the computable function such that if $\sigma\in g^{k}$, then
$q(\sigma)\geq k$, and $\varphi_{q(\sigma)}(n)$ searches for a
$g(n_{i})$-bushy tree $T$ above $\sigma$ contained in $g^{<\omega}$ such that
for every leaf $\tau$ of $T$, $\Phi_{i-1}^{\tau}$ converges to the same value
$l<h(n_{i})$. Let $m=\max_{\sigma\in g^{k}}q(\sigma)$. Let $h(n)=h(n_{i})$ for
all $n$ such that $n_{i}<n\leq m$ and let $h(m+1)=h(m)+1$. Finally, let
$n_{i+1}=m+1$, ensuring that $h$ is unbounded. The fact that $k\geq n_{i}+1$
ensures that $h$ is total.

It remains to construct $f$. Let $B_{0}=B_{\mathrm{DNC}}$ and let
$\sigma_{0}\in g^{1}\setminus B_{\mathrm{DNC}}$. Assume inductively that
$\sigma_{i}\in g^{n_{i}}\setminus B_{i}$ and that $B_{i}$ is $g(n_{i})$-small
above $\sigma_{i}$. Let $k$ and $q$ be defined as above and extend $\sigma$ to
a string $\rho\in g^{k}\setminus B_{i}$. For $j<h(q(\rho))$, let

$A_{j}=\\{\tau\in
g^{<\omega}:\Phi^{\tau}_{i}(q(\rho))\operatorname{\downarrow}=j\\}.$

If $A_{j}$ is $g(n_{i})$-big above $\rho$ for some $j$, then
$\varphi_{q(\rho)}(q(\rho))$ is defined. If
$\varphi_{q(\rho)}(q(\rho))=j^{\prime}$ then there is a $\tau\in
A_{j^{\prime}}\setminus B_{i}$ extending $\rho$ such that
$\Phi_{i-1}^{\tau}(q(\rho))=\varphi_{q(\rho)}(q(\rho))$. Otherwise,
$C=(\bigcup_{j<h(q(\rho))}A_{j})\cup B_{i}$ is $(h(q(\rho))+1)\cdot
g(n_{i})$-small above $\rho$. Since $g(k)\geq(h(n_{i})+1)\cdot
g(n_{i})=(h(q(\rho))+1)\cdot g(n_{i})$, $C$ is $g(k)$-small above $\rho$. So
let $B_{i+1}=C$ and let $\sigma_{i+1}$ be any string in $g^{n_{i+1}}\setminus
B_{i+1}$ extending $\rho$. Finally, let $f=\bigcup_{i\in\omega}\sigma_{i}$. ∎

By alternating the strategies of Theorems 3.8 and 3.10, one can also show:

######  Theorem 3.11.

Given any order function $g_{0}$, there is another order function $g_{1}$ and
functions $f_{0}\in\mathrm{DNC}_{g_{0}}$ and $f_{1}\in\mathrm{DNC}_{g_{1}}$
such that $f_{0}$ computes no $\mathrm{DNC}_{g_{1}}$ function and $f_{1}$
computes no $\mathrm{DNC}_{g_{0}}$ function.

##  4\. Bushy tree forcing

Bounded $\mathrm{DNC}$ functions, being of PA degree, compute Martin-Löf
random reals. Kučera [11] showed that there is an order function $h$ such that
every Martin-Löf random real computes a $\mathrm{DNC}_{h}$ function. Theorem
3.3 then implies that there are unbounded $\mathrm{DNC}$ functions that
compute no Martin-Löf random real. Greenberg and Miller established a stronger
version of this fact:

######  Theorem 4.1 (Greenberg and Miller [8]).

For each order function $h$, there is an $f\in\mathrm{DNC}_{h}$ that computes
no Martin-Löf random real.

The proof uses basic bushy forcing, and does not require that the bad sets be
c.e. In fact, the same technique could be used to show that for each order
function $h$ and each oracle $X$, there is an $f\in\mathrm{DNC}^{X}_{h}$ that
computes no Martin-Löf random real. Our main result in this section cannot be
partially relativized in this manner (it strongly depends on the fact that the
bad sets are c.e.) but improves upon the Greenberg-Miller theorem in a
different way. Recall that a real is _Kurtz random_ (sometimes also called
_weakly random_) if it is not contained in any measure $0$ $\Pi^{0}_{1}$
class.

######  Theorem 4.2.

For each order function $h$, there is an $f\in\mathrm{DNC}_{h}$ that computes
no Kurtz random real.

Theorem 4.2 is our first example of _bushy tree forcing_ , where the
conditions consist of trees, not just finite strings. The atomic step in the
forcing is based on the following result of Downey, Greenberg, Jockusch,
Milans [5], which we prove here for convenience.

######  Theorem 4.3 (Downey, et al. [5]).

There is no single functional $\Gamma$ such that $\Gamma^{f}$ is Kurtz random
for all $f\in\mathrm{DNC}_{3}$.

###### Proof.

Suppose that such a functional $\Gamma$ exists. As before, we may assume that
$\Gamma$ is total. It will be convenient to assume that $\Gamma$ satisfies the
following additional property:

  * •

If $\sigma\in 3^{<\omega}$ and $\Gamma^{\sigma}(n)$ converges, then
$\Gamma^{\sigma}(n)$ converges within $|\sigma|$ steps and for all
$n^{\prime}<n$, $\Gamma^{\sigma}(n^{\prime})$ also converges.

It is not difficult to see that this assumption can be made without any loss
of generality and that if $\Gamma$ satisfies this property, then
$\Gamma^{\sigma}=\tau$ is a computable relation for $\sigma\in 3^{<\omega}$
and $\tau\in 2^{<\omega}$.

We build a computable $2$-bushy subtree $S$ of $3^{\omega}$ with no leaves
such that the image of $\Gamma$ on $S$ (denoted by $\Gamma(S)$) has measure
$0$. The tree $S$ will be obtained as the union of a sequence
$\\{\langle\rangle\\}=S_{0}\subset S_{1}\subset S_{2}...$ of finite
regular111All the leaves are of the same length. binary subtrees of
$3^{<\omega}$. Let $\Gamma(S_{i})$ denote the set of reals

$\bigcup\\{[\Gamma^{\sigma}]:\sigma\text{ is a leaf of $S_{i}$}\\}.$

In constructing $S_{i+1}$, we want to ensure that
$\mu(\Gamma(S_{i+1}))\leq(3/4)\mu(\Gamma(S_{i}))$. Let
$L=\\{\sigma_{0},\sigma_{1},...,\sigma_{|L|-1}\\}$ be the set of leaves of
$S_{i}$ and let $m=\max\\{|\Gamma^{\sigma}|:\sigma\in L\\}$. Our assumption on
$\Gamma$ above allows us to find $m$ computably. Let $l$ be large enough so
that for all $\tau\in 3^{l}$, $|\Gamma^{\tau}|\geq m+(2^{|L|}+1)$. In other
words, $l$ is large enough so that we obtain at least $2^{|L|}+1$ _additional_
bits of convergence by extending a leaf of $S_{i}$ to any ternary string of
length $l$. Note that such an $l$ exists by the compactness of $3^{\omega}$
and that we can find it computably. Let $T_{j}=\\{\tau\in
3^{l}:\tau\succ\sigma_{j}\\}$.

Suppose that $k$ is a position corresponding to one of the additional bits of
convergence, i.e., $m\leq k<m+2^{|L|}+1$. Since each $T_{j}$ is $3$-big above
$\sigma_{j}$, by the smallness preservation property, either $\\{\tau\in
T_{j}:\Gamma^{\tau}(k)=1\\}$ is $2$-big above $\sigma_{j}$ (in which case, we
say that we can _force_ the $k^{\textrm{th}}$ bit to be $1$ above
$\sigma_{j}$) or $\\{\tau\in T_{j}:\Gamma^{\tau}(k)=0\\}$ is $2$-big above
$\sigma_{j}$ (we say that we can force the $k^{\textrm{th}}$ bit to be $0$
above $\sigma_{j}$). This allows us to obtain a binary sequence $\rho_{k}$ of
length $|L|$, where $\rho_{k}(j)=1$ if we can force the $k^{\textrm{th}}$ bit
to be $1$ above $\sigma_{j}$, and $0$ otherwise. Moreover, we can computably
find $2$-big sets above $\sigma_{j}$ that force the $k^{\textrm{th}}$ bit one
way or another, so we can compute $\rho_{k}$, given $k$.

By the pigeonhole principle, there exist $r$ and $s$ such that $m\leq
r,s<m+2^{|L|}+1$ and $\rho_{r}=\rho_{s}$. Note that for each $j<|L|$, even
though we can force the $r^{\textrm{th}}$ and $s^{\textrm{th}}$ bits in the
same way above $\sigma_{j}$, we may not be able to do so _simultaneously_. We
adopt the following strategy above each $\sigma_{j}$: If we can force the
$r^{\textrm{th}}$ bit to be $1$ above $\sigma_{j}$, we do so, by extending
$\sigma_{j}$ to a finite $2$-bushy tree $B_{j}$ with leaves in $3^{l}$ such
that for every leaf $\tau$ of $B_{j}$, $\Gamma^{\tau}(r)=1$. Otherwise,
$\rho_{r}(j)=\rho_{s}(j)=0$, so we force the $s^{\textrm{th}}$ bit to be $0$
above $\sigma_{j}$. The regular binary tree of height $l$ that results is
$S_{i+1}$.

For any leaf $\tau$ of $S_{i+1}$, it is _not_ the case that the
$r^{\textrm{th}}$ bit of $\Gamma^{\tau}$ is $0$ and the $s^{\textrm{th}}$ bit
is $1$: Say $\tau$ extends $\sigma_{j}$. By our choice of strategy, if the
$r^{\textrm{th}}$ bit is $0$, then it must be the case that we could not have
forced it to be $1$ above $\sigma_{j}$, and so we would have forced the
$s^{\textrm{th}}$ bit to be $0$ above $\sigma_{j}$.

Let $P=\\{X\in\Gamma(S_{i}):X(r)=0\text{ and }X(s)=1\\}$. Then
$\mu(P)=(1/4)\mu(\Gamma(S_{i}))$, since $r,s\geq m$. Clearly,
$\Gamma(S_{i+1})\subseteq\Gamma(S_{i})\setminus P$, so
$\mu(\Gamma(S_{i+1}))\leq(3/4)\mu(\Gamma(S_{i}))$, as desired.

Let $S=\bigcup_{i\in\omega}S_{i}$. Then
$\mu(\Gamma(S))=\mu(\bigcap_{i\in\omega}\Gamma(S_{i}))=0$. Let $f$ be any path
through $S$ that is $\mathrm{DNC}_{3}$. Then $\Gamma^{f}\in\Gamma(S)$. But
$\Gamma(S)$ is a null $\Pi^{0}_{1}$ class, which implies that $\Gamma^{f}$ is
not Kurtz random, contradicting our initial assumption. ∎

Note that the construction in Theorem 4.3 starts with a $3$-bushy tree and
produces a $2$-bushy subtree with no leaves.

######  Definition 4.4.

Let $j$ be an order function. We say that a tree $T\subseteq\omega^{<\omega}$
is _$j$ -bushy_ above a string $\sigma\in\omega^{<\omega}$ if every element of
$T$ is comparable with $\sigma$ and for each $\tau$ extending $\sigma$ that is
not a leaf of $T$, there are at least $j(|\tau|)$ many immediate extensions of
$\tau$. We say $T$ is _exactly $j$-bushy above $\sigma$_ if for each nonleaf
$\tau$, there are exactly $j(|\tau|)$ immediate extensions of $\tau$ in $T$.

###### Proof of Theorem 4.2.

The forcing conditions have the form $(\sigma,T,B)$, where
$\sigma\in\omega^{<\omega}$, $T$ is a computable subtree of
$\omega^{<\omega}$, $B\subset T$ and:

  * •

$T$ is exactly $j$-bushy above $\sigma$ for some order function $j$

  * •

$B$ is c.e. and upward-closed in $T$ (i.e., if $\tau\in B$ then $\rho$
extending $\tau$ on $T$ is also in $B$)

  * •

$B$ is $j(|\sigma|)$-small above $\sigma$ (and, without loss of generality,
$j(|\sigma|)$-closed).

A condition $(\sigma,T,B)$ _extends_ another condition $(\tau,S,C)$ if
$\sigma\succeq\tau$, $T\subseteq S$ and $B\cap T\supseteq C\cap T$. Let
$\mathbb{P}$ denote this partial order. As before, if $\mathcal{G}$ is a
filter on $\mathbb{P}$, then
$f_{\mathcal{G}}=\bigcup\\{\sigma:(\sigma,T,B)\in\mathcal{G}\\}\in\omega^{\leq\omega}$.
It is not difficult to verify that if $\mathcal{G}$ is sufficiently generic,
then $f_{\mathcal{G}}$ is total and if $(\sigma,T,B)\in\mathcal{G}$, then
$f_{\mathcal{G}}$ contains no initial segment in $B$.

If $\Gamma$ is any functional, let $\mathcal{D}_{\Gamma}$ denote the set of
$(\sigma,T,B)\in\mathbb{P}$ such that either

  * •

$g\in[T]\smallsetminus[B]^{\prec}$ implies that $\Gamma^{g}$ is total, or

  * •

there is an $n\in\omega$ such that $g\in[T]\smallsetminus[B]^{\prec}$ implies
that $\Gamma^{g}(n)\operatorname{\uparrow}$.

######  Claim 4.5.

$\mathcal{D}_{\Gamma}$ is dense in $\mathbb{P}$.

###### Proof.

Suppose $(\sigma,T,B)\in\mathbb{P}$, where $T$ is exactly $j$-bushy above
$\sigma$. Let $C_{x}=\\{\tau\in
T:\Gamma^{\tau}(x)\operatorname{\downarrow}\\}$. Note that $C_{x}$ is c.e. and
upward closed in $T$. As usual, there are two cases.

_Case 1._ For every $\tau\in T$ extending $\sigma$ and every $x\in\omega$,
$C_{x}\cup B$ is $j(|\tau|)$-big above $\tau$. In this case, we build a
computable tree $S\subseteq T$ in stages that is exactly $j^{\prime}$-bushy
above $\sigma$ for an order function $j^{\prime}$. Let $S_{0}$ consist of just
$\sigma$ and its initial segments. Suppose inductively that we have
$l_{i}\in\omega$ and $S_{i}\subset T$ such that

  * •

For each $x<l_{i}$, $j^{\prime}(x)$ has already been defined and
$j^{\prime}(x)\leq j(x)$.

  * •

$S_{i}$ is a finite, regular $j^{\prime}$-bushy tree of height $l_{i}$ above
$\sigma$.

  * •

For every leaf $\tau$ of $S_{i}$, either
$\Gamma^{\tau}(x)\operatorname{\downarrow}$ for every $x<i$ or $\tau\in B$.

Let $\tau$ be a leaf of $S_{i}$. By assumption, $C_{i}\cup B$ is
$j(|\tau|)$-big above $\tau$, so we extend $\tau$ to a finite tree with leaves
in $C_{i}\cup B$ that is $j(|\tau|)$-bushy above $\tau$. Note that since
$C_{i}\cup B$ is c.e., we can find such a tree computably. The tree
$S^{\prime}_{i+1}$ that results from carrying out this operation above each
leaf of $S_{i}$ may not be regular, but since both $C_{i}$ and $B$ are upward
closed in $T$ and $T$ is $j$-bushy above the leaves of $S^{\prime}_{i+1}$, we
can extend them $j(l_{i})$-bushily to some common level $l_{i+1}$, retaining
the property that every leaf is in $C_{i}$ or in $B$, and producing the tree
$S_{i+1}$. We now let $j^{\prime}(x)=j(l_{i})$ for $l_{i}\leq x<l_{i+1}$. Note
that $j^{\prime}$ is nondecreasing because of our assumption that
$j^{\prime}(x)\leq j(x)$ for $x<l_{i}$.

Let $S=\cup_{i\in\omega}S_{i}$ and note that since
$j^{\prime}(|\sigma|)=j(|\sigma|)$, $B$ is already
$j^{\prime}(|\sigma|)$-closed. So the condition $(\sigma,S,B\cap S)$ extends
$(\sigma,T,B)$. Finally, if $g\in[S]\smallsetminus[B]^{\prec}$, then for every
$i$, $g\operatorname{\upharpoonright}l_{i}\in C_{i}$, so $\Gamma^{g}$ is
total.

_Case 2._ Let $\tau$ and $x$ be counterexamples to the assumption in Case 1
and let $S$ be the full subtree of $T$ above $\tau$. Let
$B^{\prime}=(C_{x}\cup B)\cap S$. Then $B^{\prime}$ is $j(|\tau|)$-small above
$\tau$, so $(\tau,S,B^{\prime})\in\mathbb{P}$ and if
$g\in[S]\smallsetminus[B^{\prime}]^{\prec}$, then $\Gamma^{g}(x)$ diverges. ∎

Let $\mathcal{H}_{\Gamma}$ be the set of all conditions $(\sigma,T,B)$ such
that if $g\in[T]\smallsetminus[B]^{\prec}$, then $\Gamma^{g}$ is not Kurtz
random.

######  Claim 4.6.

$\mathcal{H}_{\Gamma}$ is dense in $\mathbb{P}$.

###### Proof.

Let $(\sigma,T,B)\in\mathbb{P}$ and $\Gamma$ be a $\\{0,1\\}$-valued
functional. Claim 4.5 allows us to assume that $\Gamma$ is total on
$[T]\smallsetminus[B]^{\prec}$, and since $B$ is c.e., we can assume further
that $\Gamma$ is total on $[T]$. Let $j$ be the order function such that $T$
is exactly $j$-bushy above $\sigma$.

The remainder of the proof is a straightforward modification of Theorem 4.3.
We build an order function $j^{\prime}$ and an exactly $j^{\prime}$-bushy tree
$S\subseteq T$ above $\sigma$ in stages. Let $S_{0}$ consist of $\sigma$ and
its initial segments. Next, suppose inductively that we have $l_{i}\in\omega$
and $S_{i}\subset T$ such that

  * •

For each $x<l_{i}$, $j^{\prime}(x)$ has already been defined and
$j^{\prime}(x)\leq j(x)$.

  * •

$S_{i}$ is a finite, regular $j^{\prime}$-bushy tree of height $l_{i}$ above
$\sigma$.

Let $\Gamma(S_{i})$ denote $\\{\Gamma^{g}:g\in[T]\cap[S_{i}]^{\prec}\\}$.

We first extend $S_{i}$ $j(l_{i})$-bushily within $T$ to a height $q>l_{i}$
such that $j(q)\geq 2j(l_{i})$, obtaining the tree $S^{\prime}_{i+1}$. This
ensures that every level of $T$ above $q$ is $2j(l_{i})$-big above each leaf
of $S^{\prime}_{i+1}$. Clearly,
$\mu(\Gamma(S^{\prime}_{i+1}))\leq\mu(\Gamma(S_{i}))$. Let $L$ be the set of
leaves of $S^{\prime}_{i+1}$ and let $m=\max\\{|\Gamma^{\rho}|:\rho\in L\\}$.
We choose $l_{i+1}$ large enough so that for every $\tau\in T$ of length
$l_{i+1}$, $|\Gamma^{\tau}|\geq m+2^{|L|}+1$. Note that the fact that $T$ is
exactly $j$-bushy ensures that we can find $l_{i+1}$ computably.

For any leaf $\rho$ of $S^{\prime}_{i+1}$, let $T_{\rho}$ be the set of
strings of length $l_{i+1}$ in $T$ extending $\rho$. If $k$ is a position
corresponding to one of the additional bits of convergence (i.e., $m\leq
k<m+2^{|L|}+1$), we say we can force the $k^{\textrm{th}}$ bit to be
$c\in\\{0,1\\}$ above $\rho$ if $\\{\tau\in T_{\rho}:\Gamma^{\tau}(k)=c\\}$ is
$j(l_{i})$-big above $\rho$. Since $T_{\rho}$ is $2j(l_{i})$-big above $\rho$,
if we cannot force the $k^{\textrm{th}}$ bit to be $0$ above $\rho$, we can
force it to be $1$.

As in the proof of Theorem 4.3, we obtain positions $r$ and $s$ such that
above each leaf of $S^{\prime}_{i+1}$, the $r^{\textrm{th}}$ and
$s^{\textrm{th}}$ bits can be forced in the same way. We adopt the same
strategy as before for extending $S^{\prime}_{i+1}$ to $S_{i+1}$ and ensuring
that $\mu(\Gamma(S_{i+1}))\leq(3/4)\mu(\Gamma(S_{i}))$. Finally, we let
$j^{\prime}(x)=j(l_{i})$ for $l_{i}\leq x<l_{i+1}$.

Let $S=\bigcup_{i\in\omega}S_{i}$. Since $j^{\prime}(|\sigma|)=j(|\sigma|)$,
$B\cap S$ is $j^{\prime}(|\sigma|)$-small above $\sigma$. So $(\sigma,S,B\cap
S)\in\mathbb{P}$ and since
$\mu(\Gamma(S))=\mu(\bigcap_{i\in\omega}\Gamma(S_{i}))=0$, $(\sigma,S,B\cap
S)\in\mathcal{H}_{\Gamma}$. ∎

To conclude the proof of Theorem 4.2, let $\mathcal{G}$ be any filter
containing $(\langle\rangle,h^{<\omega},B_{\mathrm{DNC}})$ that meets
$\mathcal{H}_{\Gamma}$ for each functional $\Gamma$ as well as the families of
conditions that ensure totality. Then $f_{\mathcal{G}}\in\mathrm{DNC}_{h}$ and
does not compute a Kurtz random. ∎

Every hyperimmune degree contains a Kurtz random [14], so if the function we
are building is to avoid computing a Kurtz random, it must be hyperimmune-
free. This is, in fact, the case:

######  Claim 4.7.

If $\mathcal{G}$ is sufficiently generic, then $f_{\mathcal{G}}$ has
hyperimmune-free degree.

###### Proof.

Suppose $\Gamma^{f_{\mathcal{G}}}$ is a total function. Then if
$(\sigma,T,B)\in\mathcal{G}\cap\mathcal{D}_{\Gamma}$, it must be the case that
$\Gamma$ is total on $[T]\smallsetminus[B]^{\prec}$. Let $\Xi$ be the
functional that on input $x$ and oracle $\tau\in T$, computes
$\Gamma^{\tau}(x)$ until the computation converges or $\tau$ enters $B$. If
the latter occurs first, then let $\Xi^{\tau}(x)=0$. Now $\Xi$ is total on
$[T]$ and agrees with $\Gamma$ on $[T]\smallsetminus[B]^{\prec}$.

Let $j$ be the order function such that $T$ is exactly $j$-bushy above
$\sigma$. We define a computable function $m$ that majorizes
$\Gamma^{f_{\mathcal{G}}}$. To compute $m(i)$, search for a finite tree
$S_{i}\subset T$ that is $j$-bushy above $\sigma$ such that for every leaf
$\tau$ of $S_{i}$, $\Xi^{\tau}(i)\downarrow$. Note that such a finite tree
must exist by the compactness of $[T]$ and we can find it computably since $T$
is computable. Now let $m(i)$ be the maximum of the values $\Xi^{\tau}(i)$ as
$\tau$ ranges over the leaves of $S_{i}$.

Since $T$ is exactly $j$-bushy above $\sigma$ and $S_{i}$ is a subtree of $T$
that is $j$-bushy above $\sigma$, $[T]\subseteq[S_{i}]^{\prec}$. So
$f_{\mathcal{G}}\in[S_{i}]^{\prec}$ and
$\Gamma^{f_{\mathcal{G}}}(i)=\Xi^{f_{\mathcal{G}}}(i)\leq m(i)$. ∎

##  5\. A $\mathrm{DNC}^{X}$ function of minimal degree

In this section, we strengthen Kumabe’s result that there is a DNC function of
minimal degree.

######  Theorem 5.1 (Khan).

Given any oracle $X$, there is a function that is $\mathrm{DNC}$ relative to
$X$ and of minimal degree.

Kumabe and Lewis [13] provided a simplified version of Kumabe’s original
arguments [12]. Our proof reuses much of the combinatorial machinery developed
in the Kumabe-Lewis proof, but differs in several key aspects. Kumabe and
Lewis use partial trees with computable domains, hence the function they
produce is hyperimmune-free. We use partial trees with noncomputable domains,
out of necessity: by Theorem 6.1, any $\mathrm{DNC}$ function relative to
$0^{\prime}$ is hyperimmune. Further, it suffices in the Kumabe-Lewis
construction to work with bad sets of constant bushiness. This is not the case
here; our bad sets are $h$-small for some order function $h$. In our approach
to bad sets of varying bushiness, we use ideas from Cai and Greenberg’s result
in [3] that there exist degrees $\mathbf{a}$ and $\mathbf{b}$ such that
$\mathbf{a}$ is minimal and $\mathrm{DNC}$ and $\mathbf{b}$ is $\mathrm{DNC}$
relative to $\mathbf{a}$ and a strong minimal cover of $\mathbf{a}$.

###  5.1. Definitions and notation

######  Definition 5.2.

Let $h$ be an order function. Given $\sigma\in\omega^{<\omega}$, we say that a
set $B\subseteq\omega^{<\omega}$ is _$h$ -big above $\sigma$_ if there is a
finite $h$-bushy tree $T$ above $\sigma$ such that all its leaves are in $B$.
If $B$ is not $h$-big above $\sigma$ then we say that $B$ is _$h$ -small_
above $\sigma$.

It is easy to see that the smallness preservation property, concatenation
property and small set closure property all continue to hold when one replaces
the constants governing bushiness with order functions.

For an order function $g$ and $l\in\omega$, let $w(g,l)$ denote
$\prod_{i<l}g(i)$ and let $r(g,l)$ denote $2^{3+3w_{g}(l)}$.

In order to simplify our calculations, throughout this proof we restrict
ourselves to order functions that only take values that are powers of two.

######  Definition 5.3.

Suppose $h(n)=2^{h^{\prime}(n)}$ and $g(n)=2^{g^{\prime}(n)}$ are order
functions, where $h^{\prime},g^{\prime}:\omega\rightarrow\omega$. The _middle_
of $h$ and $g$ is the order function $\mathcal{M}(h,g)$ defined by

$\mathcal{M}(h,g)(n)=2^{\lfloor\frac{h^{\prime}(n)+g^{\prime}(n)}{2}\rfloor}.$

######  Definition 5.4.

Suppose $h$ and $g$ are order functions. We say the pair $(h,g)$ _allows
splitting above $N\in\omega$_ if

  1. (1)

$h(N)\geq g(N)$,

  2. (2)

for $n\geq N$, $h(n)/g(n)$ is nondecreasing, and

  3. (3)

there is an increasing sequence $\langle l_{i}\rangle_{i\in\omega}$ of natural
numbers with $l_{0}\geq N$ such that $h(l_{i})/g(l_{i})\geq(r(h,l_{i}))^{i}$.

We say $(h,g)$ allows splitting if it allows splitting above some
$N\in\omega$. We call the sequence $\langle l_{i}\rangle$ the _splitting
levels_ for $(h,g)$.

######  Lemma 5.5.

Let $h$ and $g$ be order functions such that $(h,g)$ allows splitting. Let
$m=\mathcal{M}(h,g)$. Then $(m,g)$ and $(h,m)$ allow splitting.

###### Proof.

We provide the argument for $(m,g)$. Suppose $(h,g)$ allows splitting above
$N$ and $\langle l_{i}\rangle$ is the sequence of splitting levels for
$(h,g)$. Note that conditions (1) and (2) in the definition above are
satisfied by $(m,g)$ above $N$.

We verify condition (3). Suppose that $h(n)=2^{h^{\prime}(n)}$ and
$g(n)=2^{g^{\prime}(n)}$. Note first that for each $n\geq N$,

$\frac{m(n)}{g(n)}=2^{\lfloor\frac{h^{\prime}(n)+g^{\prime}(n)}{2}\rfloor-g^{\prime}(n)}=2^{\lfloor\frac{h^{\prime}(n)-g^{\prime}(n)}{2}\rfloor}\geq\frac{2^{\frac{h^{\prime}(n)-g^{\prime}(n)}{2}}}{2}.$

It follows that for each $i\in\omega$,

$\frac{m(l_{2i+2})}{g(l_{2i+2})}\geq\frac{2^{\frac{h^{\prime}(l_{2i+2})-g^{\prime}(l_{2i+2})}{2}}}{2}\geq\frac{(r(h,l_{2i+2}))^{\frac{2i+2}{2}}}{2}=\frac{(r(h,l_{2i+2}))^{i+1}}{2}\geq(r(m,l_{2i+2}))^{i},$

so $\langle l_{2i+2}\rangle_{i\in\omega}$ is a sequence of splitting levels
for $(m,g)$.

A similar calculation shows that $(h,m)$ allows splitting. ∎

It is not hard to verify that if $(h,g)$ allows splitting then for any
$c\in\omega$, so do $(h,2^{c}g)$ and $(\max(h/2^{c},2),g)$.

###  5.2. The partial order

The forcing conditions are of the form $(\sigma,T,B,h_{T},h_{B})$, where

  * •

the tree $T$ is partial recursive (some nodes may be terminal) and exactly
$h_{T}$-bushy above $\sigma$

  * •

$B$ includes the terminal nodes in $T$, is upward closed and is $h_{B}$-small
above $\sigma$

  * •

$(h_{T},h_{B})$ allows splitting above $|\sigma|$.

Only $\sigma$, $T$ and $B$ contribute to the ordering. Let $h_{M}$ denote
$\mathcal{M}(h_{T},h_{B})$. By extending $\sigma$ appropriately, we can assume
that $h_{M}(n)/16\geq h_{B}(n)$ for all $n\geq|\sigma|$.

Note that we have no access to the set $B$ (it is not c.e.). Since the
terminal nodes of $T$ are contained in the bad set $B$, the conditions that
force $f_{\mathcal{G}}$ to be total are dense in this partial order.

As before, we can assume that the bad set is $h_{B}$-closed. In other words,
if $\tau$ is any string in $T\setminus B$ then $B$ is $h_{B}$-small above
$\tau$.

###  5.3. Forcing $\Gamma^{f_{\mathcal{G}}}$ to be partial

Let $C_{n}=\\{\tau\in T:\Gamma^{\tau}(n)\operatorname{\downarrow}\\}$. Given a
condition $(\sigma,T,B,h_{T},h_{B})$ and a functional $\Gamma$ we say we can
_force $\Gamma^{f_{\mathcal{G}}}$ to be partial_ if there is a $\tau$ on $T$
extending $\sigma$ and an $n$ such that the set $C_{n}\cup B$ is $h_{M}$-small
above $\tau$. If this is the case, then we let $T^{\prime}$ be the full
subtree of $T$ above $\tau$. The condition $(\tau,T^{\prime},C_{n}\cup
B,h_{T},h_{M})$ extends $(\sigma,T,B,h_{T},h_{B})$, while forcing
$\Gamma^{f_{\mathcal{G}}}(n)\operatorname{\uparrow}$. From now on we assume
that we cannot force $\Gamma^{f_{\mathcal{G}}}$ to be partial. It follows that
for every $n$, and every $\tau\in T\setminus B$, $C_{n}\setminus B$ is
$h_{M}/2$-big above $\tau$. Applying this fact iteratively we obtain the
following claim:

######  Claim 5.6.

For any $\tau\in T\setminus B$ extending $\sigma$ and any $n$, there is an
$A\subset T\setminus B$, $h_{M}/2$-big above $\tau$, such that for every
$\rho\in A$, $\Gamma^{\rho}\operatorname{\upharpoonright}n$ is defined.

###  5.4. Forcing $\Gamma^{f_{\mathcal{G}}}$ to be computable

It is worth pointing out here how our argument for this case of the forcing
differs from the one in Kumabe-Lewis. As we have mentioned, the bad sets in
their argument are c.e., and they make strong use of this fact in an
_effective_ simultaneous construction of a refined subtree and a real such $Y$
that it is the image of $\Gamma$ on every path on this subtree (and hence
computable). We do not have access to the bad set, since we will ultimately
want it to include the set of strings that are non-DNC relative to $X$. So we
construct $Y$ _noneffectively_ , arguing that it is the image under $\Gamma$
of a sufficiently bushy subtree. Under the assumption that we make in this
case of the forcing, $Y$ will turn out to be computable.

######  Definition 5.7.

Let $g$ be an order function. A _$g$ -big splitting above $\tau\in T$_ is a
pair of sets $A_{0}\subset T$ and $A_{1}\subset T$, both $g$-big above $\tau$,
such that for any $\tau_{0}\in A_{0}$ and $\tau_{1}\in A_{1}$,
$\Gamma^{\tau_{0}}\mid\Gamma^{\tau_{1}}$. We say that $A_{0}$ and $A_{1}$ are
_$\Gamma$ -splitting_.

Suppose that there is a $\tau\in T\setminus B$ extending $\sigma$ such that we
cannot find any $h_{M}/16$-big splitting above $\tau$. Under this assumption,
we construct a real $Y$ with the property that for each $n\in\omega$, the set
of $\rho$ on $T$ such that
$\Gamma^{\rho}\operatorname{\upharpoonright}n=Y\operatorname{\upharpoonright}n$
is $h_{M}/4$-big above $\tau$. It follows immediately that $Y$ is computable:
to compute it up to $n$ bits, we search for an $h_{M}/4$-bushy tree $A\subset
T$ above $\tau$ every leaf of which gives the same $n$ bits of convergence via
$\Gamma$. These bits must agree with $Y$, otherwise we will have obtained an
$h_{M}/16$-big splitting above $\tau$. Further, if we let $D=\\{\rho\in
T:\Gamma^{\rho}\mid Y\\}$, then $D$ is $h_{M}/16$-small above $\tau$. It
follows that $B\cup D$ is $h_{M}$-small above $\tau$, so letting $T^{\prime}$
be the full tree above $\tau$, the condition $(\tau,T^{\prime},B\cup
D,h_{T},h_{M})$ extends $(\sigma,T,B,h_{T},h_{B})$ while forcing
$\Gamma^{f_{\mathcal{G}}}$ to be computable.

We construct $Y$ bit by bit (although not effectively), letting
$Y_{0}=\Gamma^{\tau}$. We also assume inductively that there is a set
$S_{i}\subset T\setminus B$ that is $h_{M}/4$-big above $\tau$ and for every
$\rho\in S_{i}$, $\Gamma^{\rho}\operatorname{\upharpoonright}i+|Y_{0}|=Y_{i}$.
Let $S_{0}$ consist of just $\tau$.

Given $Y_{i}$ and $S_{i}$, we proceed as follows. Above each leaf $\rho$ of
$S_{i}$, there is an $h_{M}/2$-big set of strings $A_{\rho}$ such that for
each $\nu\in A_{\rho}$, $\Gamma^{\nu}(|Y_{i}|)$ is defined. $A_{\rho}$ can
then be thinned out to a set $A^{\prime}_{\rho}$ that is $h_{M}/4$-big above
$\rho$ and such that for each $\nu\in A^{\prime}_{\rho}$,
$\Gamma^{\nu}(|Y_{i}|)$ converges to the same value $c_{\rho}$. Next, since
$S_{i}$ is $h_{M}/4$-big above $\tau$, there is a $V\subset S_{i}$,
$h_{M}/8$-big above $\tau$, such that for each $\rho\in V$, $c_{\rho}$ is the
same value, say $j$. Let $Y_{i+1}=Y_{i}j$. Note that
$V^{\prime}=\cup\\{A^{\prime}_{\rho}:\rho\in V\\}$ is $h_{M}/8$-big above
$\tau$ and for each $\nu\in V^{\prime}$, $\Gamma^{\nu}\succeq Y_{i+1}$. Let
$S_{i+1}=\\{\nu\in C:\Gamma^{\nu}\succeq Y_{i+1}\\}$. The set $C\setminus
S_{i+1}$ must be $h_{M}/16$-small above $\tau$, otherwise $C\setminus S_{i+1}$
and $V^{\prime}$ form an $h_{M}/16$-big splitting above $\tau$. It follows
that $S_{i+1}$ is $h_{M}/4$-big above $\tau$.

###  5.5. Forcing $\Gamma^{f_{\mathcal{G}}}\geq_{T}f_{\mathcal{G}}$

We work now under the additional assumption that for each $\tau\in T\setminus
B$ extending $\sigma$ there is a $h_{M}/16$-big splitting above $\tau$.

We refine $T$ to a subtree $S$ that has the _delayed splitting property_ :
above each $\tau\in S\setminus B$, there are levels $l^{\prime}>l>|\tau|$ such
that if $\rho_{0}$ and $\rho_{1}$ are any two extensions of $\tau$ on $S$ of
length $l$, and $\rho^{\prime}_{0}\succ\rho_{0}$ and
$\rho^{\prime}_{1}\succ\rho_{1}$ are extensions on $S$ of length $l^{\prime}$,
then $\Gamma^{\rho^{\prime}_{0}}\mid\Gamma^{\rho^{\prime}_{1}}$.

The statement of the following lemma has been slightly modified from the
original in order to apply to trees of varying bushiness:

######  Lemma 5.8 (Kumabe, Lewis [13]).

Let $\Gamma$ be a functional. Let $A$ be $4g$-big above $\alpha$ and $B$ be
$4h$-big above $\beta$, where $g$ and $h$ are order functions. Suppose that
above every leaf $\tau$ of $A$, there exist $\Delta_{\tau,0}$ and
$\Delta_{\tau,1}$, such that they are both $4g$-big above $\tau$ and are
$\Gamma$-splitting. Let $A^{\prime}=\cup_{\tau,i}\Delta_{\tau,i}$ and let
$v=\max\\{|\Gamma^{\rho}|:\rho\in A^{\prime}\\}$. If for every leaf $\sigma$
of $B$, $|\Gamma^{\sigma}|>v$, then there is an $A^{\prime\prime}\subseteq
A^{\prime}$ and a $B^{\prime}\subseteq B$, $g$-big above $\alpha$ and $h$-big
above $\beta$ respectively, that are $\Gamma$-splitting.

###### Proof.

Let $\sigma_{0}=\langle\rangle$ and $B_{0}=B$.

Assume inductively that we have $\sigma_{s}$ of length $s$ and $B_{s}$,
$h$-big above $\beta$, such that for all $\rho\in B_{s}$,
$\Gamma^{\rho}\succeq\sigma_{s}$.

If $\\{\tau\in A^{\prime}:\Gamma^{\tau}\mid\sigma_{s}\\}$ is $g$-big above
$\alpha$ then we are done. If not, then either

  1. (1)

$A_{1}=\\{\tau\in A^{\prime}:\Gamma^{\tau}\preceq\sigma_{s}\\}$ is $g$-big
above $\alpha$ or

  2. (2)

$A_{2}=\\{\tau\in A^{\prime}:\Gamma^{\tau}\text{ properly extends
}\sigma_{s}\\}$ is $g$-big above $\alpha$.

If (1) holds then let $V$ be the set of leaves of $A$ that have an extension
in $A_{1}$. For each $\tau\in V$, the set of strings in $A_{1}$ extending
$\tau$ must lie entirely in one of the $\Delta_{\tau,i}$. Let
$\Delta^{\prime}_{\tau}$ denote the other member of the splitting above
$\tau$. Then $\cup\\{\Delta^{\prime}_{\tau}:\tau\in V\\}$ is $g$-big above
$\alpha$ and splits with $B_{s}$.

Next, assume (2) holds, which implies that $|\sigma_{s}|<v$. If $\\{\tau\in
B:\Gamma^{\tau}\mid\sigma_{s}\\}$ is $h$-big above $\beta$, then we are done.
If not, then it must be the case that $D=\\{\tau\in
B:\Gamma^{\tau}\succeq\sigma_{s}\\}$ is $h/2$-big above $\beta$. $D$ can be
partitioned into the sets $D_{i}=\\{\tau\in
D:\Gamma^{\tau}(|\sigma_{s}|)=i\\}$, one of which must be $h/4$-big above
$\beta$, say $D_{j}$. Let $B_{s+1}=D_{j}$ and let $\sigma_{s+1}=\sigma j$ and
continue the construction. Since this process cannot continue indefinitely, we
will obtain the required splitting via one of the other alternatives. ∎

######  Claim 5.9.

Suppose $\tau_{0},...,\tau_{k}$ are nodes of length $l$ in $T\setminus B$,
$k<w_{h_{M}}(l)$ and that $h_{M}(l)/h_{B}(l)\geq r(h_{M},l)$. Then there is a
sequence of sets $A_{0},...,A_{k}$, where $A_{j}$ is $(h_{M}/2^{3+3k})$-big
above $\tau_{j}$ and which are pairwise $\Gamma$-splitting.

###### Proof.

The proof is by induction on $k$. Suppose we already have $A_{0},...,A_{k}$,
where each $A_{j}$ is $(h_{M}/2^{3+3k})$-big above $\tau_{j}$ and the
collection is pairwise $\Gamma$-splitting. Let $\tau_{k+1}$ be an additional
node of length $l$ that is not in $B$ and let $q=h_{M}/2^{3}$.

Note that since $w_{h_{M}}(l)>k+1$, $h_{B}(l)<q(l)/2^{3k+1}$. So we first
refine each $A_{j}$ to a $\Pi_{j}$ where $\Pi_{j}$ is $(q/2^{3k+1})$-big above
$\tau_{j}$ and $\Pi_{j}\cap B=\emptyset$. If $\rho$ is a leaf of $\Pi_{j}$,
then it is not in $B$ and since $q/2^{3k+1}\leq h_{M}/16$, we can find a
$q/2^{3k+1}$-bushy splitting, say $D_{\rho,0}$ and $D_{\rho,1}$, above $\rho$.
We let $\Pi^{\prime}_{j}=\cup_{i,\rho}D_{\rho,i}$.

Let $m$ be the longest length of the image of $\Gamma$ on any string in any of
the $\Pi^{\prime}_{j}$. Appealing to Claim 5.6, we let $\Delta_{0}$ be a
$q$-big set above $\tau_{k+1}$ such that each leaf of $\Delta_{0}$ gives at
least $m+1$ bits of convergence via $\Gamma$. We now apply Lemma 5.8 on
$\Pi^{\prime}_{0}$ and $\Delta_{0}$, obtaining
$A^{\prime}_{0}\subset\Pi^{\prime}_{0}$ and $\Delta_{1}\subset\Delta_{0}$,
which are $\Gamma$-splitting and where the former is $q/2^{3(k+1)}$-big above
$\tau_{0}$ and the latter is $q/4$-big above $\tau_{k+1}$. Next, we apply
Lemma 5.8 to the pair $\Pi^{\prime}_{1}$ and $\Delta_{1}$, obtaining
$A^{\prime}_{1}\subset\Pi^{\prime}_{1}$ and $\Delta_{2}\subset\Delta_{1}$,
which are $\Gamma$-splitting and where $A^{\prime}_{1}$ is $q/2^{3(k+1)}$-big
above $\tau_{1}$ and $\Delta_{2}$ is $q/4^{2}$-big above $\tau_{k+1}$. After
$k+1$ applications of Lemma 5.8, we will have obtained $A^{\prime}_{0}$
through $A^{\prime}_{k}$ and $\Delta_{k+1}$, which are pairwise
$\Gamma$-splitting. Moreover, $\Delta_{k+1}$ is $q/2^{2(k+1)}$-big above
$\tau_{k+1}$, so we can let $A^{\prime}_{k+1}=\Delta_{k+1}$. ∎

Our argument here differs once again in a crucial way from Kumabe and Lewis’s.
Suppose we have defined the delayed splitting tree $S$ up to a certain level
and let $\tau$ be one of the leaves of this finite tree. In order to continue
the construction above $\tau$, we must find a sufficiently bushy splitting
above $\tau$. In the Kumabe-Lewis argument, such a splitting will be found, or
$\tau$ will be seen to enter the bad set. In either case, the construction of
the tree $S$ is in no danger of “stalling”. Here, however, we have no access
to the bad set, so we may end up searching in vain for a splitting. In order
to get around this, we will only ask for splittings above sufficiently bushy
many leaves of the current approximation to $S$, a situation that we can
guarantee, and add the remaining leaves to the bad set. Thus, we will be
adding lots of strings to the bad set at each level of the construction. The
following lemma is critical to preserving its smallness when we do so:

######  Lemma 5.10.

Let $g$ be an order function. Suppose $A\subset\omega^{<\omega}$ is $g$-small
above $\sigma\in\omega^{<\omega}$, and suppose $\tau\in\omega^{<\omega}$
extends $\sigma$ and $A$ contains no extension of $\tau$. If $B$ is a set of
strings extending $\tau$ that is $g$-small above $\tau$, then $A\cup B$ is
$g$-small above $\sigma$.

###### Proof.

Suppose otherwise, i.e., there is a $g$-bushy tree $T$ above $\sigma$ with
leaves in $A\cup B$. Clearly, some leaves of $T$ are in $B$. Since every
string in $B$ extends $\tau$, $\tau\in T$. This means that there is a tree
$T^{\prime}$ that is $g$-bushy above $\tau$ whose leaves are in $B$, namely
the tree consisting of all strings in $T$ that are comparable with $\tau$.
This is a contradiction. ∎

Let $\langle l_{i}\rangle$ be the sequence of splitting levels for the pair
$(h_{M},h_{B})$. We begin by defining $h_{S}$. Let $j_{i}=l_{i+1}$. For
$n<j_{0}$, let $h_{S}(n)=h_{M}(n)$. For $j_{i+1}>n\geq j_{i}$, let
$h_{S}(n)=h_{M}(j_{i})/r(h_{S},j_{i})$. Then for each $i$,

$\frac{h_{S}(j_{i})}{h_{B}(j_{i})}=\frac{h_{M}(j_{i})}{h_{B}(j_{i})r(h_{S},j_{i})}\geq\frac{(r(h_{M},j_{i}))^{i+1}}{r(h_{S},j_{i})}\geq(r(h_{S},j_{i}))^{i}.$

Hence the pair $(h_{S},h_{B})$ allows splitting above $|\sigma|$.

We now describe how we build the partial recursive tree $S$. We start by
letting $S_{0}$ be an $h_{S}$-bushy subtree of $T$ above $\sigma$ with leaves
of length $l_{1}$ or less such that if $D_{0}$ is the set of leaves of $S_{0}$
of length strictly smaller than $l_{1}$, then $D_{0}$ is $h_{B}$-small above
$\sigma$. Since the terminal nodes of $T$ are contained in $B$, such a tree
must exist. We declare the nodes in $D_{0}$ terminal and the leaves of $S_{0}$
that are of length $l_{1}$ to be the _children of $\sigma$_. Throughout the
construction we will maintain the property that if $\tau\in S$ has children in
$S$, then they are all of the same length and that length is a splitting level
for the pair $(h_{M},h_{B})$.

At a stage $s$ of the construction, we will have built a finite approximation
$S_{s}$ of $S$, and accumulated a set $D_{s}$ of nodes on $S_{s}$ that we have
declared terminal. $D_{s}$ will always be $h_{B}$-small above $\sigma$.

Suppose that $\tau\in S_{s}$ has a set $C_{\tau}$ of children of length
$l_{i}$ and that they are leaves of $S_{s}$. If we have not already done so,
we initiate a search for a subset $C^{\prime}_{\tau}$ of $C_{\tau}$ such that
$C_{\tau}\setminus C^{\prime}_{\tau}$ is $h_{B}$-small above $\tau$, and for
each $\rho\in C^{\prime}_{\tau}$, there is a $A_{\rho}$, $h_{S}$-bushy above
$\rho$ such that the collection $\\{A_{\rho}:\rho\in C^{\prime}_{\tau}\\}$ is
pairwise $\Gamma$-splitting.

If $\tau\notin B$ then this search must terminate. To see why this is the case
note first that $B$ is $h_{B}$-small above $\tau$. Let $\rho_{0},...,\rho_{k}$
be the strings in $C_{\tau}\setminus B$. Since $l_{i}$ is a splitting level
for $(h_{M},h_{B})$, $h_{M}(l_{i})/h_{B}(l_{i})\geq r(h_{M},l_{i})$. Moreover,
$w_{h_{M}}(l_{i})\geq w_{h_{S}}(l_{i})>k$. By Claim 5.9, there are
$A_{0},...,A_{k}$, with $A_{j}$ $h_{M}/2^{3+3k}$-big above $\rho_{j}$, that
are pairwise $\Gamma$-splitting. Now

$\frac{h_{M}(n)}{2^{3+3k}}\geq\frac{h_{M}(n)}{2^{3+3w_{h_{S}}(l_{i})}}=\frac{h_{M}(n)}{r(h_{S},l_{i})}\geq
h_{S}(n)$

for $n\geq l_{i}$, so we can refine the $A_{j}$ to subtrees that are
$h_{S}$-bushy.

If $C^{\prime}_{\tau}$ is found, then we extend each $\rho\in
C^{\prime}_{\tau}$ by $A_{\rho}$. Note that by Lemma 5.10,
$D_{s}\cup(C_{\tau}\setminus C^{\prime}_{\tau})$ is $h_{B}$-small above
$\sigma$, since $D_{s}$ initially contains no extension of $\tau$ and
$C_{\tau}\setminus C^{\prime}_{\tau}$ is $h_{B}$-small above $\tau$. So we can
add $C_{\tau}\setminus C^{\prime}_{\tau}$ to $D_{s}$.

Next, for each $\rho\in C^{\prime}_{\tau}$ we wish to extend the leaves of
$A_{\rho}$ $h_{S}$-bushily to the next splitting level for $(h_{M},h_{B})$.
Let $L_{\rho}$ be the set of leaves of $A_{\rho}$, and let
$m=\max\\{|\nu|:\nu\in L_{\rho}\\}$. Let $l$ be least splitting level for
$(h_{M},h_{B})$ greater equal to $m$. We begin a search for an
$L^{\prime}_{\rho}\subseteq L_{\rho}$ such that $L_{\rho}\setminus
L^{\prime}_{\rho}$ is $h_{B}$-small above $\rho$ and above each $\nu\in
L^{\prime}_{\rho}$ there is an $h_{S}$-bushy tree with leaves of length $l$.
Note that if $\rho\notin B$, this search must terminate. When we find such an
$L^{\prime}_{\rho}$, we extend all its elements $h_{S}$-bushily to level $l$,
declaring the new leaves to be the children of $\rho$ and add
$L_{\rho}\setminus L^{\prime}_{\rho}$ to $D_{s}$. The same argument as before
shows that $D_{s}$ remains $h_{B}$-small above $\sigma$.

The resulting tree $S$ is $h_{S}$-bushy and if we let $D=\cup_{s}D_{s}$, then
the new bad set $D\cup B$ is $2h_{B}$-small above $\sigma$. It is clear that
the construction halts above a node $\tau\in S$ if it is either in $B$ or we
have declared it to be terminal by adding it to $D$, and so $B\cup D$ contains
all the terminal nodes of $S$. By extending $\sigma$, we can ensure that
$(h_{S},2h_{B})$ allows splitting above $|\sigma|$. For such a $\sigma$, the
condition $(\sigma,S,D\cup B,h_{S},2h_{B})$ extends $(\sigma,T,B,h_{T},h_{B})$
and forces $\Gamma^{f_{\mathcal{G}}}\geq_{T}f_{\mathcal{G}}$.

##  6\. Appendix

######  Theorem 6.1 (Miller).

Every function that is $\mathrm{DNC}$ relative to $0^{\prime}$ is of
hyperimmune degree.

###### Proof.

The argument is a modification of the proof by D. A. Martin of the fact that
almost every real is of hyperimmune degree, as presented in Downey and
Hirschfeldt [6]. We construct a reduction $\Psi$ on $\omega^{\omega}$ such
that whenever $\Psi^{g}$ is total for a $g\in\omega^{\omega}$, $\Psi^{g}$ is
not computably dominated. Moreover, any function that is $\mathrm{DNC}$
relative to $0^{\prime}$ can compute such a $g$.

### Construction of $\Psi$.

The construction is comprised of subconstructions that operate simultaneously
and independently above each string. If $\tau\in\omega^{<\omega}$ is of length
$n$, then the subconstruction above $\tau$ attempts to do the following for
each extension $\tau i$ of $\tau$ _in succession_ :

  1. (1)

Reserve a number $m$ for $\tau i$ such that $\Psi^{\tau i}(m)$ has not already
been defined and $m$ has not already been reserved for any initial segment or
extension of $\tau i$.

  2. (2)

If $\varphi_{n}(m)$ converges, set $\Psi^{\tau i}(m)=\varphi_{n}(m)+1$ and
move on to $\tau(i+1)$. If $\varphi_{n}(m)$ never converges, then we say that
the subconstruction above $\tau$ _halts at $\tau i$_.

In addition, at each stage $s$ of the construction, let $T_{s}$ be the
(finite) set of strings for which $s$ has been reserved. For each
$f\in\omega^{\omega}\setminus[T_{s}]^{\prec}$, set $\Psi^{f}(s)=0$.

### Verification.

Note that if $g$ is such that no subconstruction halts at one of its initial
segments, then $\Psi^{g}$ is total: If $m$ was reserved for an initial segment
of $g$, then $\Psi^{g}(m)$ converges. Otherwise, at stage $m$ we would have
set $\Psi^{g}(m)=0$.

######  Claim 6.2.

If $\Psi^{g}$ is total, then it is not computably dominated.

###### Proof.

If $\tau\prec\tau i\prec g$ where $\tau$ is of length $n$, then the
subconstruction above $\tau$ did not halt at $\tau i$. If it halted at $\tau
j$ for some $j<i$, then $\varphi_{n}$ never converged on the number reserved
for $\tau j$. If it proceeded beyond $\tau i$, then
$\Psi^{g}(m)=\varphi_{n}(m)+1$, where $m$ is the number reserved for $\tau i$.
In either case, $\varphi_{n}$ does not dominate $\Psi^{g}$. ∎

######  Claim 6.3.

If $f$ is $\mathrm{DNC}$ relative to $0^{\prime}$ then it computes a function
$g$ such that no subconstruction halts at an initial segment of $g$.

###### Proof.

We construct $g$ by initial segments $\langle\tau_{s}\rangle_{s\in\omega}$.
Given $\tau_{s}$, let $n$ be such that $\varphi^{0^{\prime}}_{n}(n)$ converges
to $i$ if and only if the subconstruction above $\tau_{s}$ halts at
$\tau_{s}j$. Then let $\tau_{s+1}=\tau_{s}f(n)$. Finally, let
$g=\bigcup_{s}\tau_{s}$. ∎

This concludes the proof of the theorem. ∎

## References

  * [1] Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp, and Theodore A. Slaman.  Comparing DNR and WWKL.  J. Symbolic Logic, 69(4):1089–1104, 2004.
  * [2] A. A. Beros.  A DNC function that computes no effectively bi-immune set.  ArXiv e-prints, August 2013.
  * [3] Mingzhong Cai.  Elements of Classical Recursion Theory: Degree-Theoretic Properties and Combinatorial Properties.  PhD thesis, Cornell University, 2011.
  * [4] F. G. Dorais, J. L. Hirst, and P. Shafer.  Comparing the strength of diagonally non-recursive functions in the absence of $\Sigma^{0}_{2}$ induction.  ArXiv e-prints, January 2014.
  * [5] Rodney G. Downey, Noam Greenberg, Jr. Jockusch, Carl G., and Kevin G. Milans.  Binary subtrees with few labeled paths.  Combinatorica, 31(3):285–303, 2011.
  * [6] Rodney G. Downey and Denis R. Hirschfeldt.  Algorithmic randomness and complexity.  Theory and Applications of Computability. Springer, New York, 2010.
  * [7] Mariagnese Giusto and Stephen G. Simpson.  Located sets and reverse mathematics.  J. Symbolic Logic, 65(3):1451–1480, 2000.
  * [8] Noam Greenberg and Joseph S. Miller.  Diagonally non-recursive functions and effective Hausdorff dimension.  Bull. Lond. Math. Soc., 43(4):636–654, 2011.
  * [9] Carl G. Jockusch, Jr.  Degrees of functions with no fixed points.  In Logic, methodology and philosophy of science, VIII (Moscow, 1987), volume 126 of Stud. Logic Found. Math., pages 191–201. North-Holland, Amsterdam, 1989.
  * [10] Carl G. Jockusch, Jr. and Andrew E. M. Lewis.  Diagonally non-computable functions and bi-immunity.  J. Symbolic Logic, 78(3):977–988, 2013.
  * [11] Antonín Kučera.  Measure, $\Pi^{0}_{1}$-classes and complete extensions of ${\rm PA}$.  In Recursion theory week (Oberwolfach, 1984), volume 1141 of Lecture Notes in Math., pages 245–259. Springer, Berlin, 1985.
  * [12] Masahiro Kumabe.  A fixed point free minimal degree.  Unpublished, 1996.
  * [13] Masahiro Kumabe and Andrew E. M. Lewis.  A fixed-point-free minimal degree.  J. Lond. Math. Soc. (2), 80(3):785–797, 2009.
  * [14] Stuart Alan Kurtz.  Randomness and genericity in the degrees of unsolvability.  ProQuest LLC, Ann Arbor, MI, 1981.  Thesis (Ph.D.)–University of Illinois at Urbana-Champaign.
  * [15] Gerald E. Sacks.  Some open questions in recursion theory.  In Heinz-Dieter Ebbinghaus, Gert H. Müller, and Gerald E. Sacks, editors, Recursion Theory Week, volume 1141 of Lecture Notes in Mathematics, pages 333–342. Springer Berlin Heidelberg, 1985.