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 (its complement in ) 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 (the empty set) 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 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 .