How to understand this informal description of the levels of the arithmetical hierarchy?

Question

In my class notes I do not understand why the following statement is true, nor what it means:

Informally, the lowest level in the Arithmetical Hierarchy in which $n$-ary relation $R$ is definable determines how often we have to go through the natural numbers in their totality in order that we are guaranteed to have an answer to the questions: is $n$-tuple $n_0,\cdots,n_k$, in the relation $R$?

I would be most grateful if someone could explain what is meant here.

Answer 1

The "obvious" way to check whether a formula of the form $(\forall x)\,\phi(n,x)$ is true in the natural numbers, for specified $n$, is to check all the possible values of $x$, one after the other, and see whether they make $\phi(n,x)$ true. Similarly for $(\exists x)\,\phi(n,x)$. [I'm intentionally ignoring the simplification that, when checking $(\forall x)\,\phi(n,x)$, you can quit as soon as one value of $x$ makes $\phi(n,x)$ false, and when checking $(\exists x)\,\phi(n,x)$, you can quit as soon as one value of $x$ makes $\phi(n,x)$ true.]

If you wanted to check a formula of the form $(\forall x)(\exists y)\,\phi(n,x,y)$, this approach would involve running through all values of $x$ and, for each of those values, running through all values of $y$. So you'd actually be running through the $y$-values infinitely often, once for each $x$-value. Similarly, if your formula begins with $k$ quantifiers, you'd do a $k$-deep nesting of infinite searches. As far as I can see, it is this depth of nesting that is, in your notes, called "how often we have to go through the natural numbers".

If two consecutive quantifiers are of the same sort, i.e., both universal or both existential, then a simplification becomes possible. For example, in checking $(\forall x)(\forall y)\,\phi(n,x,y)$, instead of nesting the searches as above, you could do a single search, going through all pairs of natural numbers as values for $(x,y)$. Because of this simplification, the nesting depth is given not by the total number of quantifiers but by the number of blocks of same-sort quantifiers. That number is the rank of your formula in the arithmetical hierarchy.

Answer 2

Recall the definition of the hierarchy.

$\Sigma_0^0$ are those relations which are defined by bounded formulas. Given an assignment, we only need to verify the bounded quantifiers to check the truth value of a bounded formula. So there is no need to go over all the natural numbers.

Then come $\Sigma^0_1$ and $\Pi^0_1$, which are defined by one unbounded quantifier. To check that $\exists x\varphi(x)$ holds we need to look for a witness, and potentially we need to go over all the natural numbers; similarly for $\forall x\varphi(x)$ we need to check for all the natural numbers.

Now we proceed by induction, $\Sigma^0_{n+1}$ and $\Pi^0_{n+1}$ are defined as additional quantifier over a lower-level formula. So we need to go over the natural numbers to verify that, and then by induction $n$ more times to verify the inner formula.