5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ In the first bullet, should it read $0<1$? $\endgroup$ Commented Oct 7, 2016 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$ Commented Oct 7, 2016 at 20:59

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .