Content deleted Content added
No edit summary |
I believe parameters may range over L_α due to similar notation in Devlin's "An introduction to the fine structure of the constructible hierarchy" |
||
Line 2:
The objects of study in <math>\alpha</math> recursion are subsets of <math>\alpha</math>. These sets are said to have some properties:
*A set <math>A\subseteq\alpha</math> is said to be <math>\alpha</math>-recursively-enumerable if it is <math> \Sigma_1</math> definable over <math>L_\alpha</math>, possibly with parameters from <math>L_\alpha</math> in the definition.<ref>P. Koepke, B. Seyfferth, [https://www.math.uni-bonn.de/people/koepke/Preprints/Ordinal_machines_and_admissible_recursion_theory.pdf Ordinal machines and admissible recursion theory (preprint)] (2009, p.315). Accessed October 12, 2021</ref>
*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>.
*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.
| |||