Proving a set is at a certain level of the arithmetical hierarchy

Question

I'm interested in methods for proving a set is at some level $\Sigma^0_n$ (or $\Pi^0_n$) in the arithmetical hierarchy, and in particular, proving it is at the level with the smallest $n$ possible.

I know that a set is in $\Sigma_n^0$ if it can be expressed as a sequence of $n$ quantifiers (starting with $\exists$ and then switching between $\exists$ and $\forall$) on variables, followed by a decidable formula on those variables. I also know membership in $\Pi_n^0$ can be proved in a similar way, just starting with $\forall$ instead of $\exists$.

These slides use that approach to place several sets at different places in the arithmetic heirarchy (on slides 26,31,33, and 35, for example).

Here's where things start to get tricky for me. If a language is in $\Sigma^0_n$, it seems like it's also trivially in $\Sigma^0_{n+1}$, $\Sigma^0_{n+2}$, and so on -- because you can take the formula you used to show that the language was in $\Sigma^0_n$, and tack on "dummy" quantifiers that don't actually do anything.

So, let's say I want to proving that a language is in $\Sigma^0_n$, but not $\Sigma^0_{n-1}$, i.e. I want to put the language in its lowest spot on the arithmetical heirarchy. Now, it seems like just showing that the language corresponds to a a $\exists,\forall,...$ sequence followed by a decidable formula won't cut it, because there's a chance that I was adding useless quantifiers to artificially inflate my language's difficulty. What techniques exist to get around this issue -- How do I prove that my quantifiers are "essential", so to speak?

I'm definitely interested in being as formal as possible with such a proof, so any links to textbooks or papers would be much appreciated.

Answer 1

In order to show that a language is in (say) $\Sigma_n^0$ but not in $\Sigma_{n-1}^0$ or $\Pi_{n-1}^0$, we show that the language is complete for $\Sigma_n^0$. Since the arithmetical hierarchy is strict (by a generalization of the proof of the uncomputability of the halting problem by diagonalization, which you can find in many different sources), a $\Sigma_n^0$-complete language cannot be in any lower level of the hierarchy.

How do we show that a language is complete for a level of the hierarchy? Either by a direct proof or by reduction. Let me illustrate both techniques using variants of the halting problem.

We will consider two variants of the halting problem:

• $H_1$ consists of all pairs $(\langle M \rangle, x)$ such that $M$ is a Turing machine halting on $x$.
• $H_2$ consists of all singletons $\langle M \rangle$ such that $M$ is a Turing machine halting on an empty tape.

Let us show that $H_1$ is $\Sigma_1^0$-complete by a direct proof. In order to show that it is in $\Sigma_1^0$, we notice that $(\langle M \rangle,x)$ iff there exists $t$ such that $M$ halts on $x$ within $t$ steps; the latter predicate is computable.

In order to show that $H_1$ is $\Sigma_1^0$-hard, consider any language $L \in \Sigma_1^0$. By definition, there exists a computable predicate $P$ such that $$ x \in L \Longleftrightarrow \exists y \, P(x,y). $$ Let $M$ be a Turing machine that on input $x$, enumerates all strings $y$ (say first by length, then lexicographically), for each one computes $P(x,y)$, and halts if $P(x,y)$ holds for any $y$. Then $x \in L$ iff $(\langle M \rangle, x) \in H_1$. The mapping $x \mapsto (\langle M \rangle, x)$ is clearly computable, and so this reduces $L$ to $H_1$.

We now show that $H_2$ is $\Sigma_1^0$-complete by reduction from $H_1$. Given an instance $(\langle M \rangle, x)$, we construct (in a computable way) a new machine $M_x$ that first initializes the tape $x$, and then transfers control to $M$. Clearly $(\langle M \rangle, x) \in H_1$ iff $\langle M_x \rangle \in H_2$. Since the reduction is computable and $H_1$ is $\Sigma_1^0$-hard, this shows that $H_2$ is also $\Sigma_1^0$-hard. Also, $H_2 \in \Sigma_1^0$, using the same proof as above. So $H_2$ is $\Sigma_1^0$-complete.