Alpha recursion theory

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

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

Members of $L_\alpha$ are called $\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 $\alpha$ recursively enumerable and every member of R is of the form $\langle H,J,K \rangle$ where H, J, K are all α-finite.

A is said to be α-recursive in B if there exist $R_0,R_1$ reduction procedures such that:

$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 ],$

$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 $\scriptstyle A \le_\alpha B$. By this definition A is recursive in $\scriptstyle\varnothing$ (the empty set) if and only if A is recursive. However A being recursive in B is not equivalent to A being $\Sigma_1(L_\alpha[B])$.

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

Results in $\alpha$ recursion

Shore's splitting theorem: Let A be $\alpha$ recursively enumerable and regular. There exist $\alpha$ recursively enumerable $B_0,B_1$ such that $A=B_0 \cup B_1 \wedge B_0 \cap B_1 = \varnothing \wedge A \not\le_\alpha B_i (i<2).$

Shore's density theorem: Let A, C be α-regular recursively enumerable sets such that $\scriptstyle A <_\alpha C$ then there exists a regular α-recursively enumerable set B such that $\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