Noam Greenberg: True finiteness in admissible recursion theory
Analysis of $\Pi^1_1$ sets of natural numbers, using (notations for)
computable ordinals, suggests an analogy between $\Pi^1_1$ sets and
recursively enumerable sets. The analogy is not perfect since
$\Delta^1_1$ seems to be analogous to \emph{finite} rather than
\emph{computable}. This gives rise to a theory of computability on the
recursive ordinals.
In general, one can develop a nice theory of recursive functions and
sets on any admissible ordinal $\alpha$. In this theory, ordinals below
$\alpha$ correspond to natural numbers and so are called
\emph{$\alpha$-finite}. We show that while generalizations of notions
such as computable, r.e., Turing reducibility and degrees are relatively
straightforward, $\a$-finiteness sometimes fails to capture properties
of the truly finite. This has effects on generalising some priority
arguments to $\a$, and eventually results in elementary properties of
the $\a$-r.e.\ degrees.