Proof of the existence of hyperimmune-free degrees

Question

In Classical Recursion Theory Vol.I by P.Odifreddi, section V.5 on the Tree Method, the proof for the existence of hyperimmune-frees involves the construction of a series of trees. Some definitions first:

• Tree: a function from initial segments to initial segments (binary) s.t. (1) $T(\sigma)\downarrow \wedge \tau \subseteq\sigma \rightarrow T(\tau)\downarrow \wedge T(\tau) \subseteq T(\sigma)$; (2) if one of $T(\sigma * 0), T(\sigma * 1)$ is defined, both are defined and incompatible.
• A is a branch of tree T if $T(\sigma) \subseteq A$ for infinitely many $\sigma$'s;
• Q is a subtree of T ($Q \subseteq T$) if for every $\sigma \in ran(Q), \sigma \in ran(T)$

My question is concerning the following technical lemma:

$Lemma (Totality)$: Given $e$ and a recursive tree $T$, there is a recursive tree $Q \subseteq T$ s.t. one of the following holds:

• for every branch $A$ on $Q$, {$e$}$^A$ is not total;
• for every branch $A$ on $Q$, {$e$}$^A$ is total and $(\forall n)(\forall \sigma)(|\sigma|=n \rightarrow ${$e$}$^{Q(\sigma)}(n)\downarrow)$

Ideas in the proof: First step is to see whether the following condition is fulfilled, $(\exists \sigma \in T)(\exists x)(\forall \gamma \supseteq \sigma)(\gamma \in T \rightarrow ${$e$}$^{\gamma}(x)\uparrow)$. If it exists, the first condition the fulfilled since we can take the full subtree above $\gamma$ on $T$. If not, $Q(\emptyset)= least$ $\gamma\in T$ s.t. {$e$}$^\gamma \downarrow$, inductively, for $Q(\sigma)$ there is an extension of it $T(\gamma)$ on $T$ s.t. {$e$}$^{T(\gamma)}(|\sigma|)\downarrow$, let $Q(\sigma *i) = T(\gamma * i)$, for $i=0,1$.

But is the following assertion true? {$e$}$^A (n) \leq max_{|\sigma|=n}$ {$e$}$^{Q(\sigma)}(n)$, for any branch A on Q s.t. {$e$}$^A$ is total. The claim in the book is it is true since {$e$}$^A(n)$ is already defined on the $n^{th}$ level of the tree $Q$. However, is it reasonable to consider the possible e-splitting as well, namely, $\tau_1, \tau_2$ are two different strings s.t. {$e$}$^{\tau_1}\downarrow,$ {$e$}$^{\tau_2}\downarrow$ but they are not equal? The above construction only makes sure the existence of the value on the n$^{th}$ level, but will the value change later on?

Answer 1

You have to be careful here and realize that $Q(\sigma)$ is a function from $2^{<\omega}$ to $2^{<\omega}$ and thus $Q(\sigma)$ can be arbitrarily long even if $|\sigma|=n$.

When the construction makes use of the second case $Q(\emptyset)$ is defined so that ${e}^{Q(\emptyset)}(0)\downarrow$. Now, as you observed, if $Q$ is defined for all $\sigma$ of length $n-1$ we can define it for all $\tau=\sigma*i$ of length $n$ by setting $Q(\sigma*i)$ to be $T(\gamma*i)$ where $\gamma$ is the string with the least code satisfying $T(\gamma) \supseteq Q(\sigma)$ and ${e}^{T(\gamma)}(n)\downarrow_{|T(\gamma)|}$. Such a $\gamma$ must exist since otherwise $Q(\sigma)$ would lack any extension on $T$ causing the $e$-th functional to converge on $n$.

I've spelled out the definition of $Q$ a little more pedantically to illustrate why the claim holds. Given $Q$ built in this fashion if $A$ lies on $Q$ then $A$ (viewed as a string) equals $\cup_{k \in \omega} Q(f\restriction_k)$ for some $f \in 2^\omega$. Thus, given $n$, $A$ extends $Q(\tau)$ where $\tau=f\restriction_{n+1}$ and by construction ${e}^{Q(\tau)}(n)\downarrow_{|Q(\tau)|}$ (as $Q(\tau)=Q(\sigma*i)=T(\gamma*i) \supseteq T(\gamma)$). Hence, if $A$ on $Q$ then

$$(\exists \tau)(|\tau|=n \land {e}^{A}(n)\downarrow={e}^{Q(\tau)}(n)\downarrow_{|Q(\tau)|})$$.

Therefore,

$${e}^{A}(n)\downarrow \leq \max_{|\tau|=n} {e}^{Q(\tau)}(n)\downarrow_{|Q(\tau)|})$$ where the right hand side is well-defined since by construction if $|\tau|=n$ then ${e}^{Q(\tau)}(n)\downarrow_{|Q(\tau)|})$.