Alpha recursion theory

Short description: Extension of recursion theory to admissible ordinals beyond the natural numbers

In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals α. An admissible set is closed under Σ1(Lα) functions, where Lξ denotes a rank of Godel's constructible hierarchy. α is an admissible ordinal if Lα is a model of Kripke–Platek set theory. In what follows α is considered to be fixed.

## Contents

* 1 Definitions
* 2 Work in α recursion
* 3 Relationship to analysis
* 4 References
* 5 Inline references

## Definitions

The objects of study in α recursion theory are subsets of α. These sets are said to have some properties:

* A set A⊆α is said to be α-recursively-enumerable if it is Σ1 definable over Lα, possibly with parameters from Lα in the definition.[1]
* A is α-recursive if both A and α∖A (its relative complement in α) are α-recursively-enumerable. It's of note that α-recursive sets are members of Lα+1 by definition of L.
* Members of Lα are called α-finite and play a similar role to the finite numbers in classical recursion theory.
* Members of Lα+1 are called α-arithmetic. [2]

There are also some similar definitions for functions mapping α to α:[3]

* A partial function from α to α is α-recursively-enumerable, or α-partial recursive,[4] if and only if its graph is Σ1-definable on (Lα,∈).
* A partial function from α to α is α-recursive if and only if its graph is Δ1-definable on (Lα,∈). Like in the case of classical recursion theory, any total α-recursively-enumerable function f:α->α is α-recursive.
* Additionally, a partial function from α to α is α-arithmetical if and only if there exists some n∈ω such that the function's graph is Σn-definable on (Lα,∈).

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 Δ0-definable in (Lα,∈) play a role similar to those of the primitive recursive functions.[3]

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

A is said to be α-recursive in B if there exist R0,R1 reduction procedures such that:

K⊆A↔∃H:∃J:[⟨H,J,K⟩∈R0∧H⊆B∧J⊆α/B],

K⊆α/A↔∃H:∃J:[⟨H,J,K⟩∈R1∧H⊆B∧J⊆α/B].

If A is recursive in B this is written A≤αB. By this definition A is recursive in ∅ (the empty set) if and only if A is recursive. However A being recursive in B is not equivalent to A being Σ1(Lα[B]).

We say A is regular if ∀β∈α:A∩β∈Lα or in other words if every initial portion of A is α-finite.

## Work in α recursion

Shore's splitting theorem: Let A be α recursively enumerable and regular. There exist α recursively enumerable B0,B1 such that A=B0∪B1∧B0∩B1=∅∧A≤αBi(i<2).

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

Barwise has proved that the sets Σ1-definable on Lα+ are exactly the sets Π11-definable on Lα, where α+ denotes the next admissible ordinal above α, and Σ is from the Lévy hierarchy.[5]

There is a generalization of limit computability to partial α->α functions.[6]

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

## Relationship to analysis

Some results in α-recursion theory 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ω, the arithmetical and Lévy hierarchies can become interchangeable. For example, a set of natural numbers is definable by a Σ10 formula if and only if it's Σ1-definable on Lω, where Σ1 is a level of the Lévy hierarchy.[10] More generally, definability of a subset of ω over Lω with a Σn formula coincides with its arithmetical definability using a Σn0 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. ↑ 3.0 3.1 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.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Alpha recursion theory. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Alpha_recursion_theory&oldid=4297138"