Alpha recursion theory: Difference between revisions

Revision as of 01:30, 28 March 2017

Revision as of 14:36, 10 October 2017

Line 1:

In [[recursion theory]], '''α recursion theory''' is a generalisation of [[recursion theory]] to subsets of [[admissible ordinal]]s <math>\alpha</math>. An admissible ordinalset is closed under <math>\Sigma_1(L_\alpha)</math> functions. AdmissibleIf ordinals<math>L_{\alpha}</math> is a are modelsmodel of [[Kripke–Platek set theory]] is an admissible ordinal. 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 <math>\alpha</math> recursively enumerable.