For a given set of numbers $A$, let $O^A$ be the hyperjump of $A$. It is possible to iterate inductively the hyperjump of a set, through the computable ordinals, in a way that the $\alpha$-th hyperjump is computably stronger than any $\beta$-th hyperjump for $\beta < \alpha$. It is even possible to keep iterating it through the ordinals which becomes computable in a previous iterations of the hyperjump. Formally, let us do the following inductive definition of an order $<$ on the natural numbers, together with sets $J_a^A$ for any $a$ in the field of the order $<$ (these elements $a$ are meant to be notations for ordinals) :

  • Let $J_1^A$ be the set $A$ and $J_2^A$ be the set $O^A$. Define $1 < 2$.
  • If $a$ is in the field of $<$, let $J_{2^a}^A = O^{J_a^A}$. Define $a < 2^a$ and $b < 2^a$ for any $b < a$.
  • If $a$ is in the field of $<$ and if $e$ is the code of a computable functional such that $\varphi_e(0, J^A_a) = a$ and $\varphi_e(n, J^A_a) < \varphi_{e}(n+1, J^A_a)$, then $J^A_{3^e5^a}$ is the disjoint union of the sets $J^A_{m_i}$ for $m_i = \varphi_e(i, J^A_a)$. We define $b < 3^e5^a$ for any $b < \varphi_e(i, J^A_a)$ for some $i$.

There is a smallest ordinal $\lambda^A$ which does not have a corresponding code in the field of $<$. It seems clear (even though I haven't gone through the details carefully) that $\lambda^A$ should be recursively inaccessible.

Sacks showed that for any countable admissible ordinal $\alpha$, there is a set $A$ such that $\alpha$ is the smallest ordinal non-computable ordinal in $A$.

My question is : Is it known/true that any countable recursively inaccessible ordinal is of the form $\lambda^A$ for some set $A$ ? (with $\lambda^A$ defined as above).

  • $\begingroup$ In the first bullet, should it read $0<1$? $\endgroup$ – Pedro Sánchez Terraf Oct 7 '16 at 20:11
  • $\begingroup$ I corrected that typo. the first notations are 1 and 2, to be consistent with 2^a as a notation for the successor of a $\endgroup$ – Archimondain Oct 7 '16 at 20:59

Well assuming that $\lambda^A$ is always the first recursively admissible which is bigger than $\omega_1^A$, which I think should be true, I think my question is after all not so interesting:

Either there is a largest recursively inaccessible smaller than $\omega_1^A$, in which case $\lambda^A$ is a successor in the recursively inaccessible ordinals, or $\omega_1^A$ is a limit of recursively inaccessible. In this case it is itself also recursively inaccessible (as an admissible being a limit of admissible). Thus $\lambda^A$ is also a successor in the recursively inaccessible ordinals.

It would follow that $\lambda^A$ is never meta-recursively inaccessible : a recursively inaccessible being a limit of recursively inaccessible.

| cite | improve this answer | |

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.