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. If $L_{\alpha }$ is a model of Kripke–Platek set theory then $\alpha$ is an admissible ordinal. In what follows $\alpha$ is considered to be fixed.

The objects of study in $\alpha$ recursion are subsets of $\alpha$. A is said to be $\alpha$-recursively-enumerable if it is $\Sigma _{1}$ definable over $L_{\alpha }$. A is $\alpha$-recursive if both A and $\alpha \setminus A$ (its relative complement in $\alpha$) are $\alpha$-recursively-enumerable.

Members of $L_{\alpha }$ are called $\alpha$ finite and play a similar role to the finite numbers in classical recursion theory.

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.

Results in $\alpha$ 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 \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.

Relation 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 results on $L_{\omega }={\textrm {HF}}$, the arithmetic and Levy hierarchies can become interchangeable. For example, a set is recursive iff it's $\Sigma _{1}$-definable on $L_{\omega }$, where $\Sigma$ is part of the Levy hierarchy.

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