Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.