Alpha recursion theory: Difference between revisions

Revision as of 22:11, 22 August 2007

Revision as of 23:56, 15 September 2007

Line 1:

In [[recursion theory]], the mathematical theory of computability, '''alpha recursion''' (often written '''&alpha;α 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.

Line 5:

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 &alpha;α-finite.

''A'' is said to be &alpha;α-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>

Line 15:

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 &alpha;α-finite.

==Results in <math>\alpha</math> recursion==

Line 21:

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 &alpha;α-regular recursively enumerable sets such that <math>\scriptstyle A <_\alpha C</math> then there exists a regular &alpha;α-recursively enumerable set ''B'' such that <math>\scriptstyle A <_\alpha B <_\alpha C</math>.

==ReferenceReferences==

* Gerald Sacks, ''Higher recursion theory'', Springer Verlag, 1990

Line 29:

{{Logic}}

[[Category:Recursion theory|*]]

[[Category:Mathematical logic|*R]]