Alpha recursion theory: Difference between revisions

Revision as of 08:30, 15 February 2009

Revision as of 08:32, 15 February 2009

Line 1:

In [[recursion theory]], the mathematical theory of computability, '''alphaα recursion''' (often written '''α recursiontheory''') 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 is <math> \Sigma_1</math> definable over <math>L_\alpha</math>. A is recursive if both A and <math>\alpha / A</math> (its complement in <math>\alpha</math>) are recursively enumerable.