# Why are $\Delta_1$ sentences of arithmetic called recursive?

The arithmetic hierarchy defines the $\Pi_1$ formulae of arithmetic to be formulae that are provably equivalent to a formula in prenex normal form that only has universal quantifiers, and $\Sigma_1$ if it is provably equivalent to a prenex normal form with only existential quantifiers.

A formula is $\Delta_1$ if it is both $\Pi_1$ and $\Sigma_1.$ These formulae are often called recursive: why?

If a formula $\phi(x_1, ... x_n)$ is in both $\Sigma_1, \Pi_1$, then one can define a Turing machine to determine whether it is true or false. Namely, in parallel, search for a collection of parameters that makes true the existential formula, and search for a collection of formulas that makes false the universal formula. If the first happens, return true; if the second happens, return false. One of these must exist, so the Turing machine always halts.

(The set of $x_1,...x_n$ such that $\phi(x_1, ... , x_n)$ is valid if $\phi$ belongs to $\Sigma_1$ is, by contrast, is only recursively enumerable.)

By contrast, since the action of any Turing machine is simulable by existential formulas in first-order logic (i.e. there exists a number $k$ such that $M$ halts in $k$ steps), any language which is recursively enumerable can be expressed by existential formulas. Any language whose complement is recursively enumerable can similarly be expressed by universal formulas (by the analog of deMorgan's laws). So any recursive language (i.e., one which is both recursively enumerable and whose complement is r.e.), can be expressed in both ways.

• I'm accepting this, because it's a complete and correct answer, but I think from a didactic point of view, I think this is hard going: what is the reader to make of "Any formula in $\Sigma_1$, by contrast, is only recursively enumerable"? Any such formula is just one formula, isn't it? – Charles Stewart Jul 22 '10 at 9:05
• Charles, I meant that the corresponding set of values making the formula true is only recursively enumerable. Indeed, if the formula is $\exists y_1 \exists y_2... \exists y_m \psi(x_1...x_n y_1...y_m)$ where $\psi$ is quantifer free, we search over all $x_1, ... x_n, y_1....y_m$ and add $x_1, ... x_n$ to the list whenever a match is found. I have edited the post to fix it; it was unclear. – Akhil Mathew Jul 22 '10 at 11:35

The general theorem giving the relationship between the arithmetical hierarchy and computability is known as Post's theorem [1].

In part, Post's theorem states that a set of natural numbers is $\Sigma^0_1$ if and only if it is recursively enumerable. If the set is also $\Pi^0_1$ then its complement is recursively enumerable too. So a $\Delta^0_1$ set of natural numbers must be computable.

A more general consequence of Post's theorem is that a set of natural numbers is $\Delta^0_{n+1}$ if and only if the set is computable from the $n$th Turing jump of the empty set, $\emptyset^{(n)}$.

The term recursive in computability theory is the same as the term computable, which may or may not give a better intuition of the concept of $\Delta_1^0$.

Anyway, you can understand a set $A$ (or relation $\Theta$) to be computable if there is an algorithmic process such that for any $n$, in finite time will return the answer of whether $n \in A$ or $n \notin A$.

A relation $\Theta$ is $\Sigma_1^0$ if it is of the form $(\exists k)\varphi(x,k)$ where $\varphi$ is something known to be computable. So if $\Theta(n)$ holds, then by searching, one will find a witness $k$ in finite amount of time. However, in finite time you can not ascertain if $\neg\Theta(x)$ holds since it requires checking that every $k$ is not a witness.

A relation is $\Pi_1^0$ if its complement is $\Sigma_1^0$.

Now so understand why $\Delta_1^0$ relations are consider recursive or computable. So $\Theta$ being $\Delta_1^0$ means that it an its complement is $\Sigma_1^0$. Suppose that $\Theta(x) = (\exists k)(\varphi(x))$ and $\neg\Theta(x) = (\exists k)(\psi(x))$ where both $\varphi$ and $\psi$ are computable. The claim is that determining $\Theta$ is computable. To do this just search through all $k$ such and ask if $\varphi(x,k)$ or $\psi(x,k)$. If the first is found then $\Theta(x)$ if the second is found then $\neg\Theta(x)$. Such a $k$ will definitely be found for one or the other since for all $x$, either $\Theta(x)$ or $\neg\Theta(x)$. So $\Delta_1^0$ relations satisfies the intuition that computable relations are those which one can determine satisfiability or nonsatisfiability in finite amount of time.