Alpha recursion theory

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.

Definitions

The objects of study in $\alpha$ recursion 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, iff its graph is ${\Sigma }_1$-definable on $(L_{\alpha },\in )$.
• A partial function from $\alpha$ to $\alpha$ is $\alpha$-recursive iff 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 \to \alpha$ is $\alpha$-recursive.
• Additionally, a partial function from $\alpha$ to $\alpha$ is $\alpha$-arithmetical iff 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 $⟨H,J,K⟩$ 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 \mathrm{\exists }H:\mathrm{\exists }J:[⟨H,J,K⟩\in R_0\wedge H\subseteq B\wedge J\subseteq \alpha /B],$

$K\subseteq \alpha /A\leftrightarrow \mathrm{\exists }H:\mathrm{\exists }J:[⟨H,J,K⟩\in R_1\wedge H\subseteq B\wedge J\subseteq \alpha /B].$

If A is recursive in B this is written $A{\le }_{\alpha }B$. By this definition A is recursive in $\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 $\mathrm{\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{\le }_{\alpha }{B}_i(i<2).$

Shore's density theorem: Let A, C be α-regular recursively enumerable sets such that $A{<}_{\alpha }C$ then there exists a regular α-recursively enumerable set B such that $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.

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 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.

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 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 }=\text{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. 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.

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