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?

Solution 1:

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.

Solution 2:

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)}$.

1: http://en.wikipedia.org/wiki/Post%27s_theorem