Alpha recursion theory

The objects of study in \alpha recursion theory 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. • 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_{\alpha+1} are called \alpha-arithmetic. There are also some similar definitions for functions mapping \alpha to \alpha: • A partial function from \alpha to \alpha is \alpha-recursively-enumerable, or \alpha-partial recursive, if and only if its graph is \Sigma_1-definable on (L_\alpha,\in). • A partial function from \alpha to \alpha is \alpha-recursive if and only if 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\rightarrow\alpha is \alpha-recursive. • Additionally, a partial function from \alpha to \alpha is \alpha-arithmetical if and only if 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 Shore's density theorem: Let A, C be α-regular recursively enumerable sets such that \scriptstyle A then there exists a regular α-recursively enumerable set B such that \scriptstyle A . 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 Lévy hierarchy. There is a generalization of limit computability to partial \alpha\to\alpha functions. 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 if and only if it is computable by an \alpha-Turing machine, and A is \alpha-recursively-enumerable if and only if A is the range of a function computable by an \alpha-Turing machine. 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. ==Relationship to analysis==

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