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

This is a variant on Sneaky Recursive Non-Well-Orders where it was asked

Is there a recursive function $f$ such that whenever $a\in\mathcal{O}$, $f(a)$ is a Turing index for a linear non-well-order with no $H_a$ -computable descending chain?

The answer to the original question gave a single non-well-order with no hyperarithmetic descending chain at all. Instead can $f(a)$ be a non-well-order with an $H_a$-computable descending chain but no $H_b$-computable descending chain for $b <_{\mathcal{O}} a$ ?

share|cite|improve this question

Here is something close to what you ask for. Hopefully others can improve it.

Step 1. For each $a$ there is a tree $T_a\subseteq \mathbb{N}^{<\mathbb{N}}$ which has a unique path $P$, and $P\equiv_T H_a$.

To construct $T_a$, use the fact that $H_a$ is a $\Pi^0_2$ singleton, that is $$X = H_a \iff \forall n \exists k R(X\upharpoonright k, n, a),$$ where $R$ is a recursive predicate. (For details see Higher Recursion Theory by Sacks, Chapter II, page 37.) Define \begin{align*} T_a = \{ (\sigma_1, \dots, \sigma_r) : \sigma_1 \preccurlyeq \dots \preccurlyeq \sigma_r \text{ and } \forall i\leq r (\exists k \leq |\sigma_i| R(\sigma_i\upharpoonright k, i) \text{ and no } \tau\prec\sigma_i \\ \text{ with } \sigma_{i-1} \preccurlyeq \tau \text{ has this property)}\}.\end{align*} Then $T_a$ has exactly one path $P$, and $\cup P = H_a$. One can check that $P\equiv_T H_a$. This construction is recursive in $a$.

Step 2. Define $f(a)$ to be the Kleene-Brouwer ordering on the tree $T_a$.

Then $H_a$ computes a descending sequence because it computes the unique path $P$. I suspect a weaker oracle could compute a descending sequence, but if $a$ is a successor notation, $a=2^b$, then I don't know whether $H_b$ does. If $D = \overline{\sigma}^1, \overline{\sigma}^2, \dots$ is a descending sequence from $T_a$ in the KB ordering, then $\lim_{i\rightarrow \infty} \overline{\sigma}^i = P$, so $D' \geq_T H_a$.

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.