alpha recursion theory

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

Definitions

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

A set $A\subseteq\alpha$ is said to be $\alpha$ -recursively-enumerable if it is $\Sigma_1$ definable over $L_\alpha$ , possibly with parameters from $L_\alpha$ in the definition.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
A is $\alpha$ -recursive if both A and $\alpha \setminus A$ (its relative complement in $\alpha$ ) are $\alpha$ -recursively-enumerable. It's of note that $\alpha$ -recursive sets are members of $L_{\alpha+1}$ by definition of $L$ .
Members of $L_\alpha$ are called $\alpha$ -finite and play a similar role to the finite numbers in classical recursion theory.
Members of $L_{\alpha+1}$ are called $\alpha$ -arithmetic. R. Gostanian, [https://www.sciencedirect.com/science/article/pii/0003484379900251 The Next Admissible Ordinal], Annals of Mathematical Logic 17 (1979). Accessed 1 January 2023.

There are also some similar definitions for functions mapping $\alpha$ to $\alpha$ :Srebrny, Marian, [http://matwbn.icm.edu.pl/ksiazki/fm/fm96/fm96114.pdf Relatively constructible transitive models] (1975, p.165). Accessed 21 October 2021.

A partial function from $\alpha$ to $\alpha$ is $\alpha$ -recursively-enumerable, or $\alpha$ -partial recursive,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. iff its graph is $\Sigma_1$ -definable on $(L_\alpha,\in)$ .
A partial function from $\alpha$ to $\alpha$ is $\alpha$ -recursive iff its graph is $\Delta_1$ -definable on $(L_\alpha,\in)$ . Like in the case of classical recursion theory, any total $\alpha$ -recursively-enumerable function $f:\alpha\rightarrow\alpha$ is $\alpha$ -recursive.
Additionally, a partial function from $\alpha$ to $\alpha$ is $\alpha$ -arithmetical iff there exists some $n\in\omega$ such that the function's graph is $\Sigma_n$ -definable on $(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 $\Delta_0$ -definable in $(L_\alpha,\in)$ play a role similar to those of the primitive recursive functions.

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

A is said to be α-recursive in B if there exist $R_0,R_1$ reduction procedures such that:

: $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 ],$

: $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 $\scriptstyle A \le_\alpha B$ . By this definition A is recursive in $\scriptstyle\varnothing$ (the empty set) if and only if A is recursive. However A being recursive in B is not equivalent to A being $\Sigma_1(L_\alpha[B])$ .

We say A is regular if $\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 $\alpha$ recursively enumerable and regular. There exist $\alpha$ recursively enumerable $B_0,B_1$ such that $A=B_0 \cup B_1 \wedge B_0 \cap B_1 = \varnothing \wedge A \not\le_\alpha B_i (i<2).$

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

Barwise has proved that the sets $\Sigma_1$ -definable on $L_{\alpha^+}$ are exactly the sets $\Pi_1^1$ -definable on $L_\alpha$ , where $\alpha^+$ denotes the next admissible ordinal above $\alpha$ , and $\Sigma$ is from the Levy hierarchy.T. Arai, [https://www.sciencedirect.com/science/article/pii/S0168007203000204 Proof theory for theories of ordinals - I: recursively Mahlo ordinals] (1998). p.2

There is a generalization of limit computability to partial $\alpha\to\alpha$ functions.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.

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

A problem in α-recursion theory which is open (as of 2019) is the embedding conjecture for admissible ordinals, which is whether for all admissible $\alpha$ , the automorphisms of the $\alpha$ -enumeration degrees embed into the automorphisms of the $\alpha$ -enumeration degrees.D. Natingga, Embedding Theorem for the automorphism group of the α-enumeration degrees (p.155), PhD thesis, 2019.

Relationship to analysis

Some results in $\alpha$ -recursion can be translated into similar results about second-order arithmetic. This is because of the relationship $L$ has with the ramified analytic hierarchy, an analog of $L$ for the language of second-order arithmetic, that consists of sets of integers.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.

In fact, when dealing with first-order logic only, the correspondence can be close enough that for some results on $L_\omega=\textrm{HF}$ , the arithmetical and Levy hierarchies can become interchangeable. For example, a set of natural numbers is definable by a $\Sigma_1^0$ formula iff it's $\Sigma_1$ -definable on $L_\omega$ , where $\Sigma_1$ is a level of the Levy hierarchy.G. E. Sacks, Higher Recursion Theory (p.152). "Perspectives in Logic", Association for Symbolic Logic. More generally, definability of a subset of ω over HF with a $\Sigma_n$ formula coincides with its arithmetical definability using a $\Sigma_n^0$ formula.P. Odifreddi, Classical Recursion Theory (1989), theorem IV.3.22.

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, [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

Category:Computability theory