Alpha recursion theory

In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals ${\displaystyle \alpha }$. An admissible set is closed under ${\displaystyle \Sigma _{1}(L_{\alpha })}$ functions, where ${\displaystyle L_{\xi }}$ denotes a rank of Godel's constructible hierarchy. ${\displaystyle \alpha }$ is an admissible ordinal if ${\displaystyle L_{\alpha }}$ is a model of Kripke–Platek set theory. In what follows ${\displaystyle \alpha }$ is considered to be fixed.

Definitions

The objects of study in ${\displaystyle \alpha }$ recursion are subsets of ${\displaystyle \alpha }$. These sets are said to have some properties:

• A set ${\displaystyle A\subseteq \alpha }$ is said to be ${\displaystyle \alpha }$-recursively-enumerable if it is ${\displaystyle \Sigma _{1}}$ definable over ${\displaystyle L_{\alpha }}$, possibly with parameters from ${\displaystyle L_{\alpha }}$ in the definition.^[1]
• A is ${\displaystyle \alpha }$-recursive if both A and ${\displaystyle \alpha \setminus A}$ (its relative complement in ${\displaystyle \alpha }$) are ${\displaystyle \alpha }$-recursively-enumerable. It's of note that ${\displaystyle \alpha }$-recursive sets are members of ${\displaystyle L_{\alpha +1}}$ by definition of ${\displaystyle L}$.
• Members of ${\displaystyle L_{\alpha }}$ are called ${\displaystyle \alpha }$-finite and play a similar role to the finite numbers in classical recursion theory.
• Members of ${\displaystyle L_{\alpha +1}}$ are called ${\displaystyle \alpha }$-arithmetic. ^[2]

There are also some similar definitions for functions mapping ${\displaystyle \alpha }$ to ${\displaystyle \alpha }$:^[3]

• A partial function from ${\displaystyle \alpha }$ to ${\displaystyle \alpha }$ is ${\displaystyle \alpha }$-recursively-enumerable, or ${\displaystyle \alpha }$-partial recursive,^[4] iff its graph is ${\displaystyle \Sigma _{1}}$-definable on ${\displaystyle (L_{\alpha },\in )}$.
• A partial function from ${\displaystyle \alpha }$ to ${\displaystyle \alpha }$ is ${\displaystyle \alpha }$-recursive iff its graph is ${\displaystyle \Delta _{1}}$-definable on ${\displaystyle (L_{\alpha },\in )}$. Like in the case of classical recursion theory, any total ${\displaystyle \alpha }$-recursively-enumerable function ${\displaystyle f:\alpha \rightarrow \alpha }$ is ${\displaystyle \alpha }$-recursive.
• Additionally, a partial function from ${\displaystyle \alpha }$ to ${\displaystyle \alpha }$ is ${\displaystyle \alpha }$-arithmetical iff there exists some ${\displaystyle n\in \omega }$ such that the function's graph is ${\displaystyle \Sigma _{n}}$-definable on ${\displaystyle (L_{\alpha },\in )}$.

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 ${\displaystyle \Delta _{0}}$-definable in ${\displaystyle (L_{\alpha },\in )}$ play a role similar to those of the primitive recursive functions.^[3]

We say R is a reduction procedure if it is ${\displaystyle \alpha }$ recursively enumerable and every member of R is of the form ${\displaystyle \langle H,J,K\rangle }$ where H, J, K are all α-finite.

A is said to be α-recursive in B if there exist ${\displaystyle R_{0},R_{1}}$ reduction procedures such that:

${\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],}$

${\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].}$

If A is recursive in B this is written ${\displaystyle \scriptstyle A\leq _{\alpha }B}$. By this definition A is recursive in ${\displaystyle \scriptstyle \varnothing }$ (the empty set) if and only if A is recursive. However A being recursive in B is not equivalent to A being ${\displaystyle \Sigma _{1}(L_{\alpha }[B])}$.

We say A is regular if ${\displaystyle \forall \beta \in \alpha :A\cap \beta \in L_{\alpha }}$ or in other words if every initial portion of A is α-finite.

Work in α recursion

Shore's splitting theorem: Let A be ${\displaystyle \alpha }$ recursively enumerable and regular. There exist ${\displaystyle \alpha }$ recursively enumerable ${\displaystyle B_{0},B_{1}}$ such that ${\displaystyle A=B_{0}\cup B_{1}\wedge B_{0}\cap B_{1}=\varnothing \wedge A\not \leq _{\alpha }B_{i}(i<2).}$

Shore's density theorem: Let A, C be α-regular recursively enumerable sets such that ${\displaystyle \scriptstyle A<_{\alpha }C}$ then there exists a regular α-recursively enumerable set B such that ${\displaystyle \scriptstyle A<_{\alpha }B<_{\alpha }C}$.

Barwise has proved that the sets ${\displaystyle \Sigma _{1}}$-definable on ${\displaystyle L_{\alpha ^{+}}}$ are exactly the sets ${\displaystyle \Pi _{1}^{1}}$-definable on ${\displaystyle L_{\alpha }}$, where ${\displaystyle \alpha ^{+}}$ denotes the next admissible ordinal above ${\displaystyle \alpha }$, and ${\displaystyle \Sigma }$ is from the Levy hierarchy.^[5]

There is a generalization of limit computability to partial ${\displaystyle \alpha \to \alpha }$ functions.^[6]

A computational interpretation of ${\displaystyle \alpha }$-recursion exists, using "${\displaystyle \alpha }$-Turing machines" with a two-symbol tape of length ${\displaystyle \alpha }$, that at limit computation steps take the limit inferior of cell contents, state, and head position. For admissible ${\displaystyle \alpha }$, a set ${\displaystyle A\subseteq \alpha }$ is ${\displaystyle \alpha }$-recursive iff it is computable by an ${\displaystyle \alpha }$-Turing machine, and ${\displaystyle A}$ is ${\displaystyle \alpha }$-recursively-enumerable iff ${\displaystyle A}$ is the range of a function computable by an ${\displaystyle \alpha }$-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 ${\displaystyle \alpha }$, the automorphisms of the ${\displaystyle \alpha }$-enumeration degrees embed into the automorphisms of the ${\displaystyle \alpha }$-enumeration degrees.^[8]

Relationship to analysis

Some results in ${\displaystyle \alpha }$-recursion can be translated into similar results about second-order arithmetic. This is because of the relationship ${\displaystyle L}$ has with the ramified analytic hierarchy, an analog of ${\displaystyle L}$ 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 ${\displaystyle L_{\omega }={\textrm {HF}}}$, the arithmetical and Levy hierarchies can become interchangeable. For example, a set of natural numbers is definable by a ${\displaystyle \Sigma _{1}^{0}}$ formula iff it's ${\displaystyle \Sigma _{1}}$-definable on ${\displaystyle L_{\omega }}$, where ${\displaystyle \Sigma _{1}}$ is a level of the Levy hierarchy.^[10] More generally, definability of a subset of ω over HF with a ${\displaystyle \Sigma _{n}}$ formula coincides with its arithmetical definability using a ${\displaystyle \Sigma _{n}^{0}}$ 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

1. P. Koepke, B. Seyfferth, Ordinal machines and admissible recursion theory (preprint) (2009, p.315). Accessed October 12, 2021
2. R. Gostanian, The Next Admissible Ordinal, Annals of Mathematical Logic 17 (1979). Accessed 1 January 2023.
3. Srebrny, Marian, Relatively constructible transitive models (1975, p.165). Accessed 21 October 2021.
4. W. Richter, P. Aczel, "Inductive Definitions and Reflecting Properties of Admissible Ordinals" (1974), p.30. Accessed 7 February 2023.
5. T. Arai, Proof theory for theories of ordinals - I: recursively Mahlo ordinals (1998). p.2
6. 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.
7. P. Koepke, B. Seyfferth, "Ordinal machines and admissible recursion theory". Annals of Pure and Applied Logic vol. 160 (2009), pp.310--318.
8. D. Natingga, Embedding Theorem for the automorphism group of the α-enumeration degrees (p.155), PhD thesis, 2019.
9. P. D. Welch, The Ramified Analytical Hierarchy using Extended Logics (2018, p.4). Accessed 8 August 2021.
10. G. E. Sacks, Higher Recursion Theory (p.152). "Perspectives in Logic", Association for Symbolic Logic.
11. P. Odifreddi, Classical Recursion Theory (1989), theorem IV.3.22.