# Recursive Non-Well-Orders that are Sneaky, but not THAT Sneaky.

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

-

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

-