Recursion Theory

Arithmetic Hierarchy

Arithmetic Hierarchy: The arithmetic hierarchy classifies formulae of Peano Arithmetic by their complexity

• Limit stages are ${\Sigma }_{\omega }={\Pi }_{\omega }={\Delta }_{\omega }$ (= ${\Sigma }_0^1={\Delta }_0^1={\Pi }_0^1$)
• Note that for all $n<\omega$, ${\Delta }_{n+1}={\Sigma }_n\cap {\Pi }_n$
• ${\Sigma }_0={\Delta }_0={\Pi }_0$, if a formula $\varphi$ is logically equivalent to some $\psi$ with bounded quantifiers (i.e., $\exists n<t$), then $\varphi \in {\Delta }_0$.
• ${\Delta }_1$ is the set of all recursive sets.
• ${\Sigma }_1$ is the set of all recursively-enumerable sets, and ${\Pi }_1$ is the set of all co-recursively-enumerable sets

[Arithmetical hierarchy](Arithmetical hierarchy - Wikipedia)

• If a formula $\varphi$ is logically equivalent to another formula of the form $\exists m_1\exists m_2\dots \exists m_k\psi$ where $\psi$ is a ${\Pi }_n^0$-formula, then $\varphi$ is said to be ${\Sigma }_{n+1}^0$-formula (i.e., $\varphi \in {\Sigma }_{n+1}^0$)
• If a formula $\varphi$ is logically equivalent to another formula of the form $\forall m_1\forall m_2\dots \forall m_k\psi$ where $\psi$ is a ${\Sigma }_n^0$-formula, then $\varphi$ is said to be a ${\Pi }_{n+1}^0$-formula (i.e., $\varphi \in {\Pi }_{n+1}^0$)

That is, a ${\Pi }_n^0$-formula is equivalent to a formula that begins w/ a ‘block’ of universal quantifiers $\forall$ (i.e., $\forall m_1\dots \forall m_k$) and alternates $n-1$ times between series of $\exists$ and $\forall$ quantifiers. A ${\Sigma }_n^0$ is equivalent to a formula that begins w/ a block of existential quantifiers $\exists$ and alternates $n-1$ times between a series of $\exists$ and $\forall$ quantifiers.

From the above, a formula $\varphi$ is a ${\Delta }_{n+1}^0$-formula if it is both ${\Sigma }_n^0$ and ${\Pi }_n^0$.

or each $n\in \mathbb{N}$: -${\Pi }_n^0\subset {\Sigma }_{n+1}^0$ -${\Pi }_n^0\subset {\Pi }_{n+1}^0$ -${\Sigma }_n^0\subset {\Sigma }_{n+1}^0$ -${\Sigma }_n^0\subset {\Pi }_{n+1}^0$ And so, ${\Delta }_n^0\subset {\Pi }_n^0$ and ${\Delta }_n^0\subset {\Sigma }_n^0$.

Note: Because redundant quantifiers can be added once a formula is assigned the classification ${\Sigma }_n^0$ or ${\Pi }_n^0$ (or ${\Delta }_{n+1}^0$ if it is both), it will also be assigned the classification ${\Sigma }_m^0$ or ${\Pi }_m^0$ (or ${\Delta }_{m+1}^0$) for all $m>n$.

Notation: For e.g., ${\Sigma }_n^0$, the $n$ denotes the number of alternations between series of $\exists$ and $\forall$ quantifiers and the '$0$' denotes the type of the objects being quantified over. Type $0$ objects are natural numbers, and objects of type $1$ are function intaking natural numbers and outputting natural numbers. A type $i+1$ object are functions that map the set of objects of type $i$ to the natural numbers. This is related to higher-order objects, an arithmetic hierarchy for second-order arithmetic called the analytical hierarchy can be considered for object of type $1$ (see Extensions of Recursion Theory). ${\Sigma }_n^0$ is the same as ${\Sigma }_n\dots$,etc. it is only in extensions of the arithmetic hierarchy (i.e., the analytical hierarchy) that we use the notation ${\Sigma }_n^0$.

---

Recursive: A language $\mathcal{L}$ is called recursive (or equivalently, decidable) if there is some algorithm (or program) is able to ‘decide’ if a sequence (or string) of symbol in $\mathcal{L}$ is a $\mathcal{L}$-formula. ‘Decide’ meaning the algorithm will return true or false (either way this algorithm will ‘halt’). In terms of computable functions: A language $A\subseteq {\Sigma }^{\ast }$ is called recursively enumerable if, $A=\varnothing$ or if there exist a total computable function $f:\mathbb{N}\to {\Sigma }^{\ast }$ with $A=\{f(0),f(1),\dots \}:=f(\mathbb{N})$. Then $f$ enumerate $A$.

We say that a theory $T$ is recursive if there is an algorithm that when given an $\mathcal{L}$-sentence $\varphi$ as an input, decides whether $\varphi \in T$.

Recursively-enumerable: A language is called recursively-enumerable (or equivalently, semi-decidable) if there is some program which when given a string in the language as an input, returns true, and if given a string not in the language, returns false or loops forever. Trivially, it can be shown that every language that is recursive is also recursively-enumerable.

We say that a theory $T$ is recursively-enumerable if there is an algorithm that will halt if $T⊢\varphi$ and not halt for $T/⊢\varphi$

Proposition: If $\mathcal{L}$ is a recursive language and $T$ is a recursive $\mathcal{L}$-theory, then $\{\varphi |T⊢\varphi \}$ is recursively-enumerable.

We say that a theory $T$ is decidable if there is an algorithm that when given an $\mathcal{L}$-sentence $\varphi$ as an input decides whether $T\models \varphi$ Lemma: Let $T$ be a recursive complete satisfiable theory in a recursive language $\mathcal{L}$. Then $T$ is decidable

References

Turing Machines & Computability Theory Extensions of Recursion Theory Higher Recursion Theory.pdf [Arithmetic Hierarchy](Arithmetical hierarchy - Wikipedia) Analytical Hierarchy