Content deleted Content added
FUNKYbananas (talk | contribs) i like cheese! |
m Reverted edits by FUNKYbananas (talk) to last version by SmackBot |
||
Line 1:
In [[recursion theory]], the mathematical theory of computability, '''alpha recursion''' (often written '''α recursion''') is a generalisation of [[recursion theory]] to subsets of [[admissible ordinal]]s <math>\alpha</math>. An admissible ordinal is closed under <math>\Sigma_1(L_\alpha)</math> functions. Admissible ordinals are models of [[Kripke–Platek set theory]]. In what follows <math>\alpha</math> is considered to be fixed.
The objects of study in <math>\alpha</math> recursion are subsets of <math>\alpha</math>. A is said to be <math>\alpha</math> recursively enumerable if it it is <math> \Sigma_1</math> definable over <math>L_\alpha</math>. A is recursive if both A is recursively enumerable and <math>\alpha / A</math> is recursively enumerable.
Members of <math>L_\alpha</math> are called <math>\alpha</math> 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 <math> \langle H,J,K\rangle </math> where ''H'', ''J'', ''K'' are all α-finite.
''A'' is said to be α-recusive in ''B'' if there exist <math>R_0,R_1</math> reduction procedures such that:
: <math>K \subseteq A \leftrightarrow \exists H: \exists J:[<H,J,K> \in R_0 \wedge H \subseteq B \wedge J \subseteq \alpha / B ],</math>
: <math>K \subseteq \alpha / A \leftrightarrow \exists H: \exists J:[<H,J,K> \in R_1 \wedge H \subseteq B \wedge J \subseteq \alpha / B ].</math>
If ''A'' is recursive in ''B'' this is written <math>\scriptstyle A \le_\alpha B</math>. By this definition ''A'' is recursive in <math>\scriptstyle\varnothing</math> (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 <math>\Sigma_1(L_\alpha[B])</math>.
We say ''A'' is regular if <math>\forall \beta \in \alpha: A \cap \beta \in L_\alpha</math> or in other words if every initial portion of ''A'' is α-finite.
==Results in <math>\alpha</math> recursion==
Shore's splitting theorem: Let A be <math>\alpha</math> recursively enumerable and regular. There exist <math>\alpha</math> recursively enumerable <math>B_0,B_1</math> such that <math>A=B_0 \cup B_1 \wedge B_0 \cap B_1 = \varnothing \wedge A \not\le_\alpha B_i (i<2).</math>
Shore's density theorem: Let ''A'', ''C'' be α-regular recursively enumerable sets such that <math>\scriptstyle A <_\alpha C</math> then there exists a regular α-recursively enumerable set ''B'' such that <math>\scriptstyle A <_\alpha B <_\alpha C</math>.
==References==
* Gerald Sacks, ''Higher recursion theory'', Springer Verlag, 1990
* Robert Soare, ''Recursively Enumerable Sets and Degrees'', Springer Verlag, 1987
{{Logic}}
[[Category:Recursion theory|*]]
[[Category:Mathematical logic|*R]]
| |||