en.wikipedia.org

Alpha recursion theory - Wikipedia

From Wikipedia, the free encyclopedia

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.

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

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

Additional connections between recursion theory and α recursion theory can be drawn, although explicit definitions may not have yet been written to formalize them:

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\leq _{\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

[edit]

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 \leq _{\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

[edit]

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 }={\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.^[10] 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.^[11]

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

^ 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.
^ ^a ^b 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.