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 \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 α-recusive 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[edit]

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.


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