Alpha recursion theory: Difference between revisions

Revision as of 13:05, 14 April 2011

Revision as of 22:27, 9 February 2012

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 α-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:[<\langle H,J,K> \rangle \in R_0 \wedge H \subseteq B \wedge J \subseteq \alpha / B ],</math>

: <math>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 ].</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 A being recursive in B is not equivalent to A being <math>\Sigma_1(L_\alpha[B])</math>.