MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
I think this is just a matter of convention - the only reason why $\phi^\tau_e(n)$ would change later on would be if the algorithm read beyond $\tau$ and made a decision contingent on the absence of a value there. Since this is somewhat silly, it is safe to assume that the algorithm diverges as soon as it attempts to read beyond $\tau$. This way, the output of the algorithm will agree on any longer oracle. – François G. Dorais Jun 28 '12 at 19:33
Thank you @Francois. What you suggested totally makes sense. I think I just got confused at when to think of splitting. I referred to the previous discussion in the book, the situation is only considered when the function under current string(oracle) is undefined. Thank you for enlightening me! – Jing Zhang Jun 29 '12 at 7:44

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)|})$$.


$${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)|})$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.