Alpha recursion theory: Difference between revisions

Revision as of 20:55, 25 April 2021

Revision as of 20:56, 25 April 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<ref>K. Devlin, [https://core.ac.uk/download/pdf/30905237.pdf ''An introduction to the fine structure of the constructible hierarchy''] (p.38)</ref>, where <math>L_\xi</math> denotes a rank of Godel's [[constructible hierarchy]]. 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 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 \setminus A</math> (its complement in <math>\alpha</math>) are <math>\alpha</math> recursively enumerable.

Line 27:

* Gerald Sacks, ''Higher recursion theory'', Springer Verlag, 1990 https://projecteuclid.org/euclid.pl/1235422631

* Robert Soare, ''Recursively Enumerable Sets and Degrees'', Springer Verlag, 1987 https://projecteuclid.org/euclid.bams/1183541465

* Keith J. Devlin, [https://core.ac.uk/download/pdf/30905237.pdf ''An introduction to the fine structure of the constructible hierarchy''] (p.38)

[[Category:Computability theory]]