File:DS interpenetration swift hohenberg.gif

In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals ${\displaystyle \alpha }$. An admissible ordinal is closed under ${\displaystyle \Sigma _{1}(L_{\alpha })}$ functions. Admissible ordinals are models of Kripke–Platek set theory. In what follows ${\displaystyle \alpha }$ is considered to be fixed.

The objects of study in ${\displaystyle \alpha }$ recursion are subsets of ${\displaystyle \alpha }$. A is said to be ${\displaystyle \alpha }$ recursively enumerable if it is ${\displaystyle \Sigma _{1}}$ definable over ${\displaystyle L_{\alpha }}$. A is recursive if both A and ${\displaystyle \alpha /A}$ (its complement in ${\displaystyle \alpha }$) are ${\displaystyle \alpha }$ recursively enumerable.

Members of ${\displaystyle L_{\alpha }}$ are called ${\displaystyle \alpha }$ finite and play a similar role to the finite numbers in classical recursion theory.

We say R is a reduction procedure if it is recursively enumerable and every member of R is of the form ${\displaystyle \langle H,J,K\rangle }$ where H, J, K are all α-finite.

A is said to be α-recusive in B if there exist ${\displaystyle R_{0},R_{1}}$ reduction procedures such that:

${\displaystyle K\subseteq A\leftrightarrow \exists H:\exists J:[\langle H,J,K\rangle \in R_{0}\wedge H\subseteq B\wedge J\subseteq \alpha /B],}$

${\displaystyle K\subseteq \alpha /A\leftrightarrow \exists H:\exists J:[\langle H,J,K\rangle \in R_{1}\wedge H\subseteq B\wedge J\subseteq \alpha /B].}$

If A is recursive in B this is written ${\displaystyle \scriptstyle A\leq _{\alpha }B}$. By this definition A is recursive in ${\displaystyle \scriptstyle \varnothing }$ (the empty set) if and only if A is recursive. However A being recursive in B is not equivalent to A being ${\displaystyle \Sigma _{1}(L_{\alpha }[B])}$.

We say A is regular if ${\displaystyle \forall \beta \in \alpha :A\cap \beta \in L_{\alpha }}$ or in other words if every initial portion of A is α-finite.

Results in ${\displaystyle \alpha }$ recursion

Shore's splitting theorem: Let A be ${\displaystyle \alpha }$ recursively enumerable and regular. There exist ${\displaystyle \alpha }$ recursively enumerable ${\displaystyle B_{0},B_{1}}$ such that ${\displaystyle A=B_{0}\cup B_{1}\wedge B_{0}\cap B_{1}=\varnothing \wedge A\not \leq _{\alpha }B_{i}(i<2).}$

Shore's density theorem: Let A, C be α-regular recursively enumerable sets such that ${\displaystyle \scriptstyle A<_{\alpha }C}$ then there exists a regular α-recursively enumerable set B such that ${\displaystyle \scriptstyle A<_{\alpha }B<_{\alpha }C}$.

References

• Gerald Sacks, Higher recursion theory, Springer Verlag, 1990
• Robert Soare, Recursively Enumerable Sets and Degrees, Springer Verlag, 1987