Content deleted Content added
No edit summary |
Possible typo →Work in α recursion |
||
| (47 intermediate revisions by 5 users not shown) | |||
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
==Definitions==
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.▼
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>
*Members of <Math>L_{\alpha+1}</math> are called '''<math>\alpha</math>-arithmetic'''. <ref>R. Gostanian, [https://www.sciencedirect.com/science/article/pii/0003484379900251 The Next Admissible Ordinal], Annals of Mathematical Logic 17 (1979). Accessed 1 January 2023.</ref>
There are also some similar definitions for functions mapping <math>\alpha</math> to <math>\alpha</math>:<ref name="relconstr">Srebrny, Marian, [http://matwbn.icm.edu.pl/ksiazki/fm/fm96/fm96114.pdf Relatively constructible transitive models] (1975, p.165). Accessed 21 October 2021.</ref>
▲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.
*A [[partial function]] from <math>\alpha</math> to <math>\alpha</math> is '''<math>\alpha</math>-recursively-enumerable''', or '''<math>\alpha</math>-partial recursive''',<ref>W. Richter, P. Aczel, "[https://www.duo.uio.no/bitstream/handle/10852/44063/1973-13.pdf Inductive Definitions and Reflecting Properties of Admissible Ordinals]" (1974), p.30. Accessed 7 February 2023.</ref> iff its graph is <math>\Sigma_1</math>-definable on <math>(L_\alpha,\in)</math>.
▲
*Additionally, a partial function from <math>\alpha</math> to <math>\alpha</math> is '''<math>\alpha</math>-arithmetical''' iff there exists some <math>n\in\omega</math> such that the function's graph is <math>\Sigma_n</math>-definable on <math>(L_\alpha,\in)</math>.
Additional connections between recursion theory and α recursion theory can be drawn, although explicit definitions may not have yet been written to formalize them:
*The functions <math>\Delta_0</math>-definable in <math>(L_\alpha,\in)</math> play a role similar to those of the [[Primitive recursion|primitive recursive functions]].<ref name="relconstr" />
We say R is a reduction procedure if it is <math>\alpha</math> recursively enumerable and every member of R is of the form <math> \langle H,J,K \rangle </math> where ''H'', ''J'', ''K'' are all α-finite.
Line 17 ⟶ 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>
Shore's density theorem: Let ''A'', ''C'' be α-regular recursively enumerable sets such that <math>\scriptstyle A <_\alpha C</math> then there exists a regular α-recursively enumerable set ''B'' such that <math>\scriptstyle A <_\alpha B <_\alpha C</math>.
Barwise has proved that the sets <math>\Sigma_1</math>-definable on <math>L_{\alpha^+}</math> are exactly the sets <math>\Pi_1^1</math>-definable on <math>L_\alpha</math>, where <math>\alpha^+</math> denotes the next admissible ordinal above <math>\alpha</math>, and <math>\Sigma</math> is from the [[Levy hierarchy]].<ref>T. Arai, [https://www.sciencedirect.com/science/article/pii/S0168007203000204 Proof theory for theories of ordinals - I: recursively Mahlo ordinals] (1998). p.2</ref>
There is a generalization of [[Computability in the limit|limit computability]] to partial <math>\alpha\to\alpha</math> functions.<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 computational interpretation of <math>\alpha</math>-recursion exists, using "<math>\alpha</math>-Turing machines" with a two-symbol tape of length <math>\alpha</math>, that at limit computation steps take the [[limit inferior]] of cell contents, state, and head position. For admissible <math>\alpha</math>, a set <math>A\subseteq\alpha</math> is <math>\alpha</math>-recursive iff it is computable by an <math>\alpha</math>-Turing machine, and <math>A</math> is <math>\alpha</math>-recursively-enumerable iff <math>A</math> is the range of a function computable by an <math>\alpha</math>-Turing machine. <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]". Annals of Pure and Applied Logic vol. 160 (2009), pp.310--318.</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.<ref>D. Natingga, ''Embedding Theorem for the automorphism group of the α-enumeration degrees'' (p.155), PhD thesis, 2019.</ref>
==Relationship to analysis==
Some results in <math>\alpha</math>-recursion can be translated into similar results about [[second-order arithmetic]]. This is because of the relationship <math>L</math> has with the ramified analytic hierarchy, an analog of <math>L</math> for the language of second-order arithmetic, that consists of sets of integers.<ref>P. D. Welch, [https://arxiv.org/pdf/1808.03814.pdf#page=4 The Ramified Analytical Hierarchy using Extended Logics] (2018, p.4). Accessed 8 August 2021.</ref><!--"P_α = P(N) ∩ L_α"-->
In fact, when dealing with first-order logic only, the correspondence can be close enough that for some results on <math>L_\omega=\textrm{HF}</math>, the arithmetical and Levy hierarchies can become interchangeable. For example, a set of natural numbers is definable by a <math>\Sigma_1^0</math> formula iff it's <math>\Sigma_1</math>-definable on <math>L_\omega</math>, where <math>\Sigma_1</math> is a level of the Levy hierarchy.<ref>G. E. Sacks, ''Higher Recursion Theory'' (p.152). "Perspectives in Logic", Association for Symbolic Logic.</ref> More generally, definability of a subset of ω over HF with a <math>\Sigma_n</math> formula coincides with its arithmetical definability using a <math>\Sigma_n^0</math> formula.<ref>P. Odifreddi, ''Classical Recursion Theory'' (1989), theorem IV.3.22.</ref>
==References==
Line 27 ⟶ 51:
* 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), North-Holland Publishing, 1974
* J. Barwise, ''Admissible Sets and Structures''. 1975
==Inline references==
<references/>
[[Category:Computability theory]]
| |||