Extensions of Recursion Theory

Hyperarithmetical Theory

Hyperarithmetic theory is obtained via iterating the Turing Jump operator along the recursive ordinals ($\alpha <{\omega }_1^{CK}$), which contains the hyperarithmetic hierarchy, an extension of the arithmetic hierarchy with levels ${\Sigma }_{\alpha }^0$ and ${\Pi }_{\alpha }^0$. The limit of the hierarchy is the stage ${\Sigma }_{{\omega }_1^{CK}}^0={\Pi }_{{\omega }_1^{CK}}^0={\Delta }_1^1$ in the analytical hierarchy, which is the stage of the set of all hyperarithmetic sets, ${}^{\prime }HY{P}^{\prime }$. A subset if $\mathbb{N}$ is hyperarithmetical if it is a member of $L_{{\omega }_1^{CK}}$

Meta-recursion theory is the case in $\alpha$-recursion theory where $\alpha ={\omega }_1^{CK}$ (i.e., ${\omega }_1^{CK}$-recursion theory). A set if meta-arithmetic if it is a member of $L_{{\omega }_1^{CK}+1}$ and meta-finite if it is a member of $L_{{\omega }_1^{CK}}$ (the notion of a set being hyperarithmetical is the same as being meta-arithmetic).

The Hyperjump operator can be defined as follows: Consider a set $X\subseteq \mathbb{N}$, the set of natural numbers that are ordinal numbers relative to $X$ is denoted ${\mathcal{O}}^X$ (note the supremum of all ordinal that can be represented in ${\mathcal{O}}^X$ is denoted ${\omega }_1^X$). Then the hyperjump of $X$ is the function $f:X\to {\mathcal{O}}^X$.

The hyperjump of $X$ is ${\mathcal{O}}^X$. This means that ${\mathcal{O}}^X$ is ${\Pi }_1^1$ in $X$, and every set ${\Pi }_1^1$ in $X$ is many-one reducible to ${\mathcal{O}}^X$.

• If $X$ is hyperarithmetic hierarchy, then $X$ is ${\Delta }_1^1$
• The predicate, "$X\in HYP$" is ${\Pi }_1^1$

Proposition: $A{\le }_{h}B⟷{\mathcal{O}}^A{\le }_m{\mathcal{O}}^B$ That is, $A$ is hyper-reducible to $B$ if and only if the hyperjump of $A$ is $m$-reducible (many-one reducible) to the hyperjump pf $B$. $⟹$ The hyperjump operation is well-defined for hyperdegrees.

Proposition: If $X,Y\in {\Pi }_1^1$ and $Y\notin HYP$, then $X{\le }_{h}Y$ (i.e., $X$ is hyper-reducible to $Y$)

A Turing reduction procedure $P$ consists of a recursively enumerable sequence of finite computations. A set $B$ is reduced by applying to $B$ those elements of $P$ that ‘fit’ $B$, those computations based on membership statements true of $B$. $\to$ A hyperarithmetic reduction procedure $Q$ fails to resemble a ${\Pi }_1^1$ sequence of hyperarithmetic computations. If $Q$ (procedure) is applied to a non-hyperarithmetic $B$, then the resulting computations are hyperarithmetic in $B$ rather than hyperarithmetic.

• Suppose that a meta-recursively enumerable set is defined to be a ${\Pi }_1^1$ set of hyperarithmetic sets of numbers. Then a meta-recursive set is a meta-recursively enumerable set whose complement w/ respect to the domain of hyperarithmetic sets $HYP$ is also meta-recursively enumerable. $\to$ A meta-finite set is a hyperarithmetic collection of hyperarithmetic sets.

Notes:

• Meta-recursively enumerable means ${\Pi }_1^1$ on $HYP$
• Meta-recursive means ${\Delta }_1^1$ on $HYP$
• Meta-finite is the same as being hyperarithmetic

Meta-recursive: Let $Q$ be a ${\Pi }_1^1$ set of unique notations of recursive ordinals. Let $n:{\omega }_1^{CK}\to Q$ take each recursive ordinal to its unique notation. Thus, $|n(\beta )|=\beta$.

The natural enumeration of a ${\Pi }_1^1$ set in ${\omega }_1^{CK}$ steps yields a hyperarithmetic set at each step (analogous to how the enumeration of recursively enumerable set yields a finite set as each step).

Note: Non-hyperarithmetic ${\Pi }_1^1$-sets have the same hyperdegree as Kleene’s $\mathcal{O}$.

Meta-computable function: Let $\Phi \subseteq {\omega }_1^{CK}\times {\omega }_1^{CK}$ be a partial function. $\Phi$ is meta-computable if there exists a finite set $E$ of equations w/ principal function letter $f$ such that for all $\alpha ,\beta <{\omega }_1^{CK}:$ $\varphi (\alpha )=\beta \leftrightarrow (f(\alpha )=\beta )\in C(E)$

Analytical Hierarchy

The analytical hierarchy is an extension of the arithmetic hierarchy which includes formulas of second-order arithmetic and which quantify over sets of natural numbers $S\subseteq \mathbb{N}$ and equivalently, over functions $f:\mathbb{N}\to \mathbb{N}$. We have stages ${\Pi }_{\alpha }^1$ and ${\Sigma }_{\alpha }^1$ for $\alpha <{\omega }_1^{CK}$, as well as the stages from the hyperarithmetical hierarchy.

Note: ${\Sigma }_0^1={\Pi }_0^1={\Delta }_0^1$

Limit stages: ${\Pi }_{{\omega }_1^{CK}}^1$ and ${\Sigma }_{{\omega }_1^{CK}}^1$

As in the arithmetic hierarchy, for each $\alpha$: -${\Pi }_{\alpha }^1\subset {\Sigma }_{\alpha +1}^1$ -${\Pi }_{\alpha }^1\subset {\Pi }_{\alpha +1}^1$ -${\Sigma }_{\alpha }^1\subset {\Sigma }_{\alpha +1}^1$ -${\Sigma }_{\alpha }^1\subset {\Pi }_{\alpha +1}^1$ And so, ${\Delta }_{\alpha }^1\subset {\Pi }_{\alpha }^1$ and ${\Delta }_{\alpha }^1\subset {\Sigma }_{\alpha }^1$.

• A formula $\varphi$ in the language of second-order arithmetic is said to be ${\Sigma }_{\alpha +1}^1$ if it is logically equivalent to a formula of the form $\exists X_1\dots \exists X_k\psi$ where $\psi$ is a ${\Pi }_{\alpha }^1$formula.
• A formula $\varphi$ in the language of second-order arithmetic is said to be ${\Pi }_{\alpha +1}^1$ if it is logically equivalent to a formula of the form $\forall X_1\dots \forall X_k\psi$ where $\psi$ is a ${\Sigma }_{\alpha }^1$formula.
• ${\Delta }_{\alpha +1}^1={\Sigma }_{\alpha +1}^1\cup {\Pi }_{\alpha +1}^1$, and so a formula $\varphi$ is ${\Delta }_{\alpha +1}^1$ if it is logically equivalent to both a ${\Sigma }_{\alpha +1}^1$-formula and a ${\Pi }_{\alpha +1}^1$-formula. Recall: '$X$' denotes a second-order variable.

E.g., For a relation $\prec$ on ${\mathbb{N}}^2$, the statement ”$\prec$ is a well-order on $\mathbb{N}$” is ${\Pi }_1^1$.

We can further extend the analytical hierarchy to stages ${\Sigma }_{\alpha }^i$ and ${\Pi }_{\alpha }^i$ for $\alpha$ is recursive ordinal, and $i>1$ (for $i+1^{th}$ arithmetic). i.e., a hierarchy of third-order arithmetic formulas would have stages ${\Sigma }_{\alpha }^2$ and ${\Pi }_{\alpha }^2$. There have been papers talking about ${\Delta }_1^2$ well-orderings of the reals.

Alpha-Recursion Theory

$\alpha$-recursion theory is an extension of recursion theory to subsets of admissible ordinals $\alpha$. What is usually considered as recursion theory is recursion on $\mathbb{N}$ or $\omega$.

Admissible Ordinals:

• An ordinal $\alpha$ is admissible if $L_{\alpha }\models KP$ (Kripke-Platek set theory).
• All admissible ordinals are limit ordinals and are countable, the first admissible ordinal is the Church-Kleene ordinal ${\omega }_1^{CK}$ (the supremum of all recursive ordinals).

A set $A\subseteq \alpha$ is said to be $\alpha$-recursively enumerable if it is ${\Sigma }_1$ definable over $L_{\alpha }$ (this may include parameter from $L_{\alpha }$ in the definition).

$A$ is $\alpha$-recursive if both $A$ and $\alpha$ \ $A$ are $\alpha$-recursively-enumerable (or alternatively, ${\Delta }_1$ definable over $L_{\alpha }$).

• $\alpha$-recursive sets are members of $L_{\alpha +1}$
• Members of $L_{\alpha }$ are called $\alpha$-finite
• Members of $L_{\alpha +1}$ are called $\alpha$-arithmetic

$\alpha$-recursion theory also has its own analogue of $\alpha$-jumps and $\alpha$-reducibility.

Partial functions

---

There are even further extensions of recursion theory beyond $\alpha$-recursion theory

Applications

• $\alpha$-recursion theory can be used to extend Gödel encoding (Gödel’s Incompleteness Theorems), where instead of logical symbols being assigned to a natural number (an element of $\omega$), it is instead assigned to an element of $\alpha$ for $\alpha$ is an admissible ordinal. $\to$ This has further application in defining provability and truth predicates. In a Tarski hierarchy (see Tarski’s theory of truth) we can effectively allow for an $\alpha$-many meta-levels and still be able to differentiate between truth predicates at each level. As mentioned though that even while employing $\alpha$-recursion theory, we would still only be able to differentiate between countably-many meta-levels (recall that all admissible ordinals are countable).

References

Turing Machines & Computability Theory Recursion Theory Gödel’s Incompleteness Theorems Tarski’s theory of truth Higher Recursion Theory.pdf [Math.stackexchange post](set theory - Is there any generalization of the hyperarithmetical hierarchy using the analytical hierarchy to formulas belonging to third-order logic and above? - Mathematics Stack Exchange)