Alpha recursion theory: Difference between revisions

Revision as of 18:57, 15 August 2021

Revision as of 18:58, 15 August 2021

Line 1:

In [[recursion theory]], '''α recursion theory''' is a generalisation of [[recursion theory]] to subsets of [[admissible ordinal]]s <math>\alpha</math>. An admissible set is closed under <math>\Sigma_1(L_\alpha)</math> functions, where <math>L_\xi</math> denotes a rank of Godel's [[constructible hierarchy]]. <math>\alpha</math> Ifis an admissible ordinal if <math>L_{\alpha}</math> is a model of [[Kripke–Platek set theory]] then <math>\alpha</math> 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<!--subseteq L_α?--> is said to be '''<math>\alpha</math>-recursively-enumerable''' if it is <math> \Sigma_1</math> definable over <math>L_\alpha</math><!--Closest source is Rathjen's "Collapsing functions based on recursively large ordinals: A well–ordering proof for KPM"?-->. A is <math>\alpha</math>-recursive if both A and <math>\alpha \setminus A</math> (its relative complement in <math>\alpha</math>) are <math>\alpha</math>-recursively-enumerable. It's of note that <math>\alpha</math>-recursive sets are members of <math>L_{\alpha+1}</math> by definition of <math>L</math>.