Alpha recursion theory

In recursion theory, the mathematical theory of computability, alpha recursion (often written α recursion) 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 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 recursively enumerable and every member of R is of the form $langle\; H,J,K\; angle$ where "H", "J", "K" are all α-finite.

"A" is said to be α-recusive in "B" if there exist $R\_0,R\_1$ reduction procedures such that:

:

:

If "A" is recursive in "B" this is written $scriptstyle\; A\; le\_alpha\; B$. By this definition "A" is recursive in $scriptstylevarnothing$ (the empty set) if and only if "A" is recursive. However it should be noted that A being recursive in B is not equivalent to A being $Sigma\_1(L\_alpha\; [B]\; )$.

We say "A" is regular if 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

Shore's density theorem: Let "A", "C" be α-regular recursively enumerable sets such that then there exists a regular α-recursively enumerable set "B" such that .

References

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