Alpha recursion theory


In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals. An admissible set is closed under functions. If is a model of Kripke–Platek set theory then is an admissible ordinal. In what follows is considered to be fixed.
The objects of study in recursion are subsets of. A is said to be recursively enumerable if it is definable over. A is recursive if both A and are recursively enumerable.
Members of are called 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 where H, J, K are all α-finite.
A is said to be α-recursive in B if there exist reduction procedures such that:
If A is recursive in B this is written. By this definition A is recursive in if and only if A is recursive. However A being recursive in B is not equivalent to A being.
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 recursively enumerable and regular. There exist recursively enumerable 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.