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

The objects of study in recursion theory 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.
  • A is -recursive if both A and 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 L_ are called -arithmetic.
There are also some similar definitions for functions mapping to :
  • A partial function from to is -recursively-enumerable, or -partial recursive, if and only if its graph is -definable on.
  • A partial function from to is -recursive if and only if 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 if and only if 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:
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 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

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 Lévy hierarchy.
There is a generalization of limit computability to partial functions.
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 if and only if it is computable by an -Turing machine, and is -recursively-enumerable if and only if is the range of a function computable by an -Turing machine.
A problem in α-recursion theory which is open 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.

Relationship to analysis

Some results in -recursion theory 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.
In fact, when dealing with first-order logic only, the correspondence can be close enough that for some results on, the arithmetical and Lévy hierarchies can become interchangeable. For example, a set of natural numbers is definable by a formula if and only if it's -definable on, where is a level of the Lévy hierarchy. More generally, definability of a subset of ω over with a formula coincides with its arithmetical definability using a formula.