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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.