- Alpha recursion theory
In
recursion theory , the mathematical theory of computability, alpha recursion (often written α recursion) is a generalisation ofrecursion theory to subsets ofadmissible ordinal s alpha. An admissible ordinal is closed under Sigma_1(L_alpha) functions. Admissible ordinals are models ofKripke–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:
: K subseteq A leftrightarrow exists H: exists J: [
in R_0 wedge H subseteq B wedge J subseteq alpha / B ] , : K subseteq alpha / A leftrightarrow exists H: exists J: [
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 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 forall eta in alpha: A cap eta in L_alpha 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 A=B_0 cup B_1 wedge B_0 cap B_1 = varnothing wedge A otle_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.
References
* Gerald Sacks, "Higher recursion theory", Springer Verlag, 1990
* Robert Soare, "Recursively Enumerable Sets and Degrees", Springer Verlag, 1987
Wikimedia Foundation. 2010.