Alpha recursion theory

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

Definitions

edit

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

  • A set   is said to be  -recursively-enumerable if it is   definable over  , possibly with parameters from   in the definition.[1]
  • A is  -recursive if both A and   (its relative complement in  ) are  -recursively-enumerable. It's of note that  -recursive sets are members of   by definition of  .
  • Members of   are called  -finite and play a similar role to the finite numbers in classical recursion theory.
  • Members of   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] iff its graph is  -definable on  .
  • A partial function from   to   is  -recursive iff its graph is  -definable on  . Like in the case of classical recursion theory, any total  -recursively-enumerable function   is  -recursive.
  • Additionally, a partial function from   to   is  -arithmetical iff there exists some   such that the function's graph is  -definable on  .

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  -definable in   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   where H, J, K are all α-finite.

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

 
 

If A is recursive in B this is written  . 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  .

We say A is regular if   or in other words if every initial portion of A is α-finite.

Work in α recursion

edit

Shore's splitting theorem: Let A be   recursively enumerable and regular. There exist   recursively enumerable   such that  

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

Barwise has proved that the sets  -definable on   are exactly the sets  -definable on  , where   denotes the next admissible ordinal above  , and   is from the Levy 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   is  -recursive iff it is computable by an  -Turing machine, and   is  -recursively-enumerable iff   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

edit

Some results in  -recursion can be translated into similar results about second-order arithmetic. This is because of the relationship   has with the ramified analytic hierarchy, an analog of   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  , the arithmetical and Levy hierarchies can become interchangeable. For example, a set of natural numbers is definable by a   formula iff it's  -definable on  , where   is a level of the Levy hierarchy.[10] More generally, definability of a subset of ω over HF with a   formula coincides with its arithmetical definability using a   formula.[11]

References

edit

Inline references

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