Alpha recursion theory: Difference between revisions

Revision as of 10:36, 2 July 2007

Revision as of 02:46, 3 July 2007

Line 1:

'''Alpha recursion''' (often written <math>\'''&alpha</math>; 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 memeber of R is of the form <math> <\langle H,J,K>\rangle </math> where ''H'', ''J'', ''K'' are all <math>\&alpha</math> ;-finite.

''A'' is said to be <math>\&alpha</math> ;-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>\emptysetscriptstyle\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 <math>\&alpha</math> ;-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 = \emptyset \wedge A \not\le_\alpha B_i (i<2)</math>

Shore's Densitysplitting theorem: Let A,C be <math>\alpha</math> regular recursively enumerable setsand suchregular. that There exist <math>A <_\alpha C</math> thenrecursively there exists a regularenumerable <math>\alphaB_0,B_1</math> recursively enumerable set B such that <math>A=B_0 <_\alphacup BB_1 <_\wedge B_0 \cap B_1 = \varnothing \wedge A \not\le_\alpha CB_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>

==Reference==

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

* Robert Soare, ''Recursively Enumerable Sets and Degrees'', Springer Verlag, 1987

{{Logic}}