Alpha recursion theory explained

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.^[1]

• 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\_$ are called

\alpha -arithmetic. ^[2]

There are also some similar definitions for functions mapping

\alpha to \alpha :^[3]

• A partial function from

\alpha to \alpha is \alpha -recursively-enumerable, or \alpha -partial recursive,^[4] 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 → \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.^[5]

There is a generalization of limit computability to partial

\alpha\to\alpha functions.^[6]

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. ^[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

\alpha , the automorphisms of the \alpha -enumeration degrees embed into the automorphisms of the \alpha -enumeration degrees.^[8]

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.^[9]

In fact, when dealing with first-order logic only, the correspondence can be close enough that for some results on

L _{\omega=rm{HF}} , the arithmetical and Levy hierarchies can become interchangeable. For example, a set of natural numbers is definable by a \Sigma ^{0} _{1} formula iff it's \Sigma _{1} -definable on L _{\omega} , where \Sigma _{1} is a level of the Levy hierarchy.^[10] More generally, definability of a subset of ω over HF with a \Sigma _{n} formula coincides with its arithmetical definability using a \Sigma ^{0} _{n} 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.