6
$\begingroup$

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$ ?

$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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