2
$\begingroup$

Is there a theory about using α-recursion to compute ordinals?

For example, consider α-recursive well orders on α, what is the supreme of their order type? Is it the next admissible ordinal after α? Is this the most natural choice?

Do we have a natural definition of iterated α-jumps? Does the α-degree of iterated α-jump of another α-degree only depend on the time of iterations, not their notations, like the ω-recursion case?

$\endgroup$
2
  • 1
    $\begingroup$ This is a rather broad question, but the short version is: yes, there is quite a lot known about this topic. For example, in general (= for a club of countable ordinals $\alpha$) the supremum of the $\alpha$-recursive well-orderings of $\alpha$ is strictly smaller than the next admissible above $\alpha$; see my answer to this MO question. $\endgroup$ Commented Oct 25, 2021 at 4:44
  • $\begingroup$ @NoahSchweber and what about α-jump? $\endgroup$ Commented Oct 25, 2021 at 7:20

1 Answer 1

1
$\begingroup$

A concept that appears a lot in the context of ordinal notations in recursion theory is a "copy", which is a set (usually of lower rank) equipped with an ordering that's isomorphic to some other set. For example, an ordinal notation with order type $\varepsilon_0$ is a copy of $(\varepsilon_0,<)$. The supremum of $\alpha$-recursive relations need not be the next admissible after $\alpha$ (mentioned in MO question #277343), such an $\alpha$ where this happens is called non-Gandy. However, Noah Schweber mentions a successful characterization of admissibility in this answer: the countable admissibles are exactly the ordinals with no copy that's computed by a copy of any smaller ordinal.

There's a standard definition of the $\alpha$-jump of $\emptyset$, or "$\emptyset^{(\alpha)}$", for recursive $\alpha$, this usually comes along with a collection of definitions for the "hyperarithmetical hierarchy". The reason this is well-defined in spite of there being multiple ordinal notations for $\alpha$ is Spector's theorem that the resulting sets are Turing equivalent regardless of notation chosen. The $\alpha$-jump may be generalized from $\emptyset$ to an arbitrary set of naturals as well, but I am not sure if Spector's theorem applies, we may instead need to define $0^{(e)}$ for ordinal notation $e$.

$\endgroup$

You must log in to answer this question.

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