Alpha recursion theory

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals . An admissible ordinal is closed under functions. Admissible ordinals are models of Kripke–Platek set theory. 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[edit]

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 .


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