Arithmetical hierarchy: Why is $\Delta_0^0\ne \Delta_1^0$?

412 Views Asked by At

The definitions are different from one textbook to the other, but if we take the following definitions:

$\Delta_0^0$ = all the first-order arithmetic formulas with bounded quantifiers only.

$\Delta_1^0$ = conjunction of $\Sigma_1^0$ and $\Pi_1^0$.

Then it turns out $\Delta_0^0$ is strictly included in $\Delta_1^0$.

How does one proves they are different?

1

There are 1 best solutions below

9
On BEST ANSWER

There are no $\Delta^0_1$ formulas, but there are $\Delta^0_1$ sets of integers, defined as the ones that are both definable by a $\Pi^0_1$ formula and definable by a $\Sigma^0_1$ formula.

The $\Delta^0_1$ sets are exactly the decidable sets (if there is a TM that always either halts-and-reject or halts-and-accepts, then "there is a computation that accepts" is the same as "every computation doesn't reject"; conversely a$\Delta^0_1$ set can be decided simply by looking in parallel for an example of the $\Sigma^0_1$ formula or a counterexample to the $\Pi^0_1$ formula).

On the other hand, not all decidable sets are $\Delta^0_0$. One argument for this is that any fixed $\Delta^0_0$ formula can be evaluated in time polynomial in the values of its free variables, and there are decidable sets that are not decidable within such a time bound, due to the time hierarchy theorem.

Edit: As a different approach, we can construct a concrete decidable set that is not $\Delta^0_0$ by direct diagonalization: Let $\varphi_0, \varphi_1, \varphi_2, \ldots$ be an effective enumeration of all $\Delta^0_0$ formulas. Then it is decidable whether $\varphi_n(m)$ is true or not, given $n$ and $m$. Now let $$ A = \{n\in\mathbb N\mid \neg\varphi_n(n)\} $$ $A$ is obviously decidable, but it cannot be the extension of $\varphi_i$ for any $i$, because such an $i$ would be in $A$ if and only it isn't.