Alpha recursion theory
In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals [math]\displaystyle{ \alpha }[/math]. An admissible set is closed under [math]\displaystyle{ \Sigma_1(L_\alpha) }[/math] functions, where [math]\displaystyle{ L_\xi }[/math] denotes a rank of Godel's constructible hierarchy. [math]\displaystyle{ \alpha }[/math] is an admissible ordinal if [math]\displaystyle{ L_{\alpha} }[/math] is a model of Kripke–Platek set theory. In what follows [math]\displaystyle{ \alpha }[/math] is considered to be fixed.
Definitions
The objects of study in [math]\displaystyle{ \alpha }[/math] recursion are subsets of [math]\displaystyle{ \alpha }[/math]. These sets are said to have some properties:
- A set [math]\displaystyle{ A\subseteq\alpha }[/math] is said to be [math]\displaystyle{ \alpha }[/math]-recursively-enumerable if it is [math]\displaystyle{ \Sigma_1 }[/math] definable over [math]\displaystyle{ L_\alpha }[/math], possibly with parameters from [math]\displaystyle{ L_\alpha }[/math] in the definition.[1]
- A is [math]\displaystyle{ \alpha }[/math]-recursive if both A and [math]\displaystyle{ \alpha \setminus A }[/math] (its relative complement in [math]\displaystyle{ \alpha }[/math]) are [math]\displaystyle{ \alpha }[/math]-recursively-enumerable. It's of note that [math]\displaystyle{ \alpha }[/math]-recursive sets are members of [math]\displaystyle{ L_{\alpha+1} }[/math] by definition of [math]\displaystyle{ L }[/math].
- Members of [math]\displaystyle{ L_\alpha }[/math] are called [math]\displaystyle{ \alpha }[/math]-finite and play a similar role to the finite numbers in classical recursion theory.
- Members of [math]\displaystyle{ L_{\alpha+1} }[/math] are called [math]\displaystyle{ \alpha }[/math]-arithmetic. [2]
There are also some similar definitions for functions mapping [math]\displaystyle{ \alpha }[/math] to [math]\displaystyle{ \alpha }[/math]:[3]
- A partial function from [math]\displaystyle{ \alpha }[/math] to [math]\displaystyle{ \alpha }[/math] is [math]\displaystyle{ \alpha }[/math]-recursively-enumerable, or [math]\displaystyle{ \alpha }[/math]-partial recursive,[4] iff its graph is [math]\displaystyle{ \Sigma_1 }[/math]-definable on [math]\displaystyle{ (L_\alpha,\in) }[/math].
- A partial function from [math]\displaystyle{ \alpha }[/math] to [math]\displaystyle{ \alpha }[/math] is [math]\displaystyle{ \alpha }[/math]-recursive iff its graph is [math]\displaystyle{ \Delta_1 }[/math]-definable on [math]\displaystyle{ (L_\alpha,\in) }[/math]. Like in the case of classical recursion theory, any total [math]\displaystyle{ \alpha }[/math]-recursively-enumerable function [math]\displaystyle{ f:\alpha\rightarrow\alpha }[/math] is [math]\displaystyle{ \alpha }[/math]-recursive.
- Additionally, a partial function from [math]\displaystyle{ \alpha }[/math] to [math]\displaystyle{ \alpha }[/math] is [math]\displaystyle{ \alpha }[/math]-arithmetical iff there exists some [math]\displaystyle{ n\in\omega }[/math] such that the function's graph is [math]\displaystyle{ \Sigma_n }[/math]-definable on [math]\displaystyle{ (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]\displaystyle{ \Delta_0 }[/math]-definable in [math]\displaystyle{ (L_\alpha,\in) }[/math] play a role similar to those of the primitive recursive functions.[3]
We say R is a reduction procedure if it is [math]\displaystyle{ \alpha }[/math] recursively enumerable and every member of R is of the form [math]\displaystyle{ \langle H,J,K \rangle }[/math] where H, J, K are all α-finite.
A is said to be α-recursive in B if there exist [math]\displaystyle{ R_0,R_1 }[/math] reduction procedures such that:
- [math]\displaystyle{ K \subseteq A \leftrightarrow \exists H: \exists J:[\langle H,J,K \rangle \in R_0 \wedge H \subseteq B \wedge J \subseteq \alpha / B ], }[/math]
- [math]\displaystyle{ K \subseteq \alpha / A \leftrightarrow \exists H: \exists J:[\langle H,J,K \rangle \in R_1 \wedge H \subseteq B \wedge J \subseteq \alpha / B ]. }[/math]
If A is recursive in B this is written [math]\displaystyle{ \scriptstyle A \le_\alpha B }[/math]. By this definition A is recursive in [math]\displaystyle{ \scriptstyle\varnothing }[/math] (the empty set) if and only if A is recursive. However A being recursive in B is not equivalent to A being [math]\displaystyle{ \Sigma_1(L_\alpha[B]) }[/math].
We say A is regular if [math]\displaystyle{ \forall \beta \in \alpha: A \cap \beta \in L_\alpha }[/math] or in other words if every initial portion of A is α-finite.
Work in α recursion
Shore's splitting theorem: Let A be [math]\displaystyle{ \alpha }[/math] recursively enumerable and regular. There exist [math]\displaystyle{ \alpha }[/math] recursively enumerable [math]\displaystyle{ B_0,B_1 }[/math] such that [math]\displaystyle{ A=B_0 \cup B_1 \wedge B_0 \cap B_1 = \varnothing \wedge A \not\le_\alpha B_i (i\lt 2). }[/math]
Shore's density theorem: Let A, C be α-regular recursively enumerable sets such that [math]\displaystyle{ \scriptstyle A \lt _\alpha C }[/math] then there exists a regular α-recursively enumerable set B such that [math]\displaystyle{ \scriptstyle A \lt _\alpha B \lt _\alpha C }[/math].
Barwise has proved that the sets [math]\displaystyle{ \Sigma_1 }[/math]-definable on [math]\displaystyle{ L_{\alpha^+} }[/math] are exactly the sets [math]\displaystyle{ \Pi_1^1 }[/math]-definable on [math]\displaystyle{ L_\alpha }[/math], where [math]\displaystyle{ \alpha^+ }[/math] denotes the next admissible ordinal above [math]\displaystyle{ \alpha }[/math], and [math]\displaystyle{ \Sigma }[/math] is from the Levy hierarchy.[5]
There is a generalization of limit computability to partial [math]\displaystyle{ \alpha\to\alpha }[/math] functions.[6]
A computational interpretation of [math]\displaystyle{ \alpha }[/math]-recursion exists, using "[math]\displaystyle{ \alpha }[/math]-Turing machines" with a two-symbol tape of length [math]\displaystyle{ \alpha }[/math], that at limit computation steps take the limit inferior of cell contents, state, and head position. For admissible [math]\displaystyle{ \alpha }[/math], a set [math]\displaystyle{ A\subseteq\alpha }[/math] is [math]\displaystyle{ \alpha }[/math]-recursive iff it is computable by an [math]\displaystyle{ \alpha }[/math]-Turing machine, and [math]\displaystyle{ A }[/math] is [math]\displaystyle{ \alpha }[/math]-recursively-enumerable iff [math]\displaystyle{ A }[/math] is the range of a function computable by an [math]\displaystyle{ \alpha }[/math]-Turing machine. [7]
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]\displaystyle{ \alpha }[/math], the automorphisms of the [math]\displaystyle{ \alpha }[/math]-enumeration degrees embed into the automorphisms of the [math]\displaystyle{ \alpha }[/math]-enumeration degrees.[8]
Relationship to analysis
Some results in [math]\displaystyle{ \alpha }[/math]-recursion can be translated into similar results about second-order arithmetic. This is because of the relationship [math]\displaystyle{ L }[/math] has with the ramified analytic hierarchy, an analog of [math]\displaystyle{ L }[/math] for the language of second-order arithmetic, that consists of sets of integers.[9]
In fact, when dealing with first-order logic only, the correspondence can be close enough that for some results on [math]\displaystyle{ 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]\displaystyle{ \Sigma_1^0 }[/math] formula iff it's [math]\displaystyle{ \Sigma_1 }[/math]-definable on [math]\displaystyle{ L_\omega }[/math], where [math]\displaystyle{ \Sigma_1 }[/math] is a level of the Levy hierarchy.[10] More generally, definability of a subset of ω over HF with a [math]\displaystyle{ \Sigma_n }[/math] formula coincides with its arithmetical definability using a [math]\displaystyle{ \Sigma_n^0 }[/math] formula.[11]
References
- 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, 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
- ↑ P. Koepke, B. Seyfferth, Ordinal machines and admissible recursion theory (preprint) (2009, p.315). Accessed October 12, 2021
- ↑ R. Gostanian, The Next Admissible Ordinal, Annals of Mathematical Logic 17 (1979). Accessed 1 January 2023.
- ↑ 3.0 3.1 Srebrny, Marian, Relatively constructible transitive models (1975, p.165). Accessed 21 October 2021.
- ↑ W. Richter, P. Aczel, "Inductive Definitions and Reflecting Properties of Admissible Ordinals" (1974), p.30. Accessed 7 February 2023.
- ↑ T. Arai, Proof theory for theories of ordinals - I: recursively Mahlo ordinals (1998). p.2
- ↑ 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.
- ↑ P. Koepke, B. Seyfferth, "Ordinal machines and admissible recursion theory". Annals of Pure and Applied Logic vol. 160 (2009), pp.310--318.
- ↑ D. Natingga, Embedding Theorem for the automorphism group of the α-enumeration degrees (p.155), PhD thesis, 2019.
- ↑ P. D. Welch, The Ramified Analytical Hierarchy using Extended Logics (2018, p.4). Accessed 8 August 2021.
- ↑ G. E. Sacks, Higher Recursion Theory (p.152). "Perspectives in Logic", Association for Symbolic Logic.
- ↑ P. Odifreddi, Classical Recursion Theory (1989), theorem IV.3.22.
 |  |
