Content deleted Content added
moved previous edit slightly for better ease of reading (and added link to partial functions webpage) |
No edit summary |
||
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> is an admissible ordinal if <math>L_{\alpha}</math> is a model of [[Kripke–Platek set theory]]. In what follows <math>\alpha</math> is considered to be fixed.
==Definitions==
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>
Line 27 ⟶ 28:
We say ''A'' is regular if <math>\forall \beta \in \alpha: A \cap \beta \in L_\alpha</math> or in other words if every initial portion of ''A'' is α-finite.
==
Shore's splitting theorem: Let A be <math>\alpha</math> recursively enumerable and regular. There exist <math>\alpha</math> recursively enumerable <math>B_0,B_1</math> such that <math>A=B_0 \cup B_1 \wedge B_0 \cap B_1 = \varnothing \wedge A \not\le_\alpha B_i (i<2).</math>
Line 36 ⟶ 37:
There is a generalization of [[Computability in the limit|limit computability]] to partial <math>\alpha\to\alpha</math> functions.<math>\alpha</math>.<ref>S. G. Simpson, "Degree Theory on Admissible Ordinals", pp.170--171. Appearing in J. Fenstad, P. Hinman, ''Generalized Recursion Theory: Proceedings of the 1972 Oslo Symposium'' (1974), ISBN 0 7204 22760.</ref>
A problem in α-recursion theory which is open (as of 2019) is the embedding conjecture for admissible ordinals, which is whether for all admissible <math>\alpha</math>, the automorphisms of the <math>\alpha</math>-enumeration degrees embed into the automorphisms of the <math>\alpha</math>-enumeration degrees. (Natingga, ''Embedding Theorem for the automorphism group of the α-enumeration degrees'', p.155, 2019)
==Relationship to analysis==
| |||