A basic question about the definition of $\Sigma_n$ completeness

Question

Suppose I want to show that $A$ is $\Sigma_8$-complete. By definition, this requires to prove, in particular, that $A$ is itself a $\Sigma_8$ set. But I don't really understand if I need to prove as well that $\Sigma_8$ is the "best" one could get? (I.e., that $A$ is not $\Sigma_i$ or $\Pi_i$ for $i=1,2,3,4,5,6,7$.) Some $\Sigma_8$ sets may be as well $\Sigma_1$, but they still qualify for being $\Sigma_8$...

Answer 1

There are three different notions here:

• Being $\Sigma_8$.

• Being properly $\Sigma_8$, which is to say being $\Sigma_8$ but not $\Sigma_n$ for any $n<8$ (or $\Pi_k$ either for that matter for any $k\le 8$).

• Being $\Sigma_8$-complete.

If we want to show that something is $\Sigma_8$-complete, it is - as you say - not enough to simply show that it is $\Sigma_8$. But it is also not enough to show that it is properly $\Sigma_8$! $\Sigma_8$-completeness is a very strong property: we have to show that any other $\Sigma_8$ set is many-one reducible to the given set, and that doesn't follow from proper-$\Sigma_8$-ness alone. In order to prove that a set $A$ is $\Sigma_8$ complete, we have to prove two things:

• $A$ is $\Sigma_8$.

• Every $\Sigma_8$ set $B$ can be many-one reduced to $A$.

That's it - we never need to refer to proper-$\Sigma_8$-ness, and we don't get any benefit from doing so either.

(That said, as a matter of practice basically every naturally-occurring properly-$\Sigma_n$ set is $\Sigma_n$-complete. So you can always take a proof of proper-$\Sigma_n$-ness as really good evidence for $\Sigma_n$-completeness. But this isn't a theorem or anything, it's just a fact about the sorts of sets we run into in mathematical practice ... at least, so far.)

---

Note, incidentally, that it is not immediately obvious that $\Sigma_8$-completeness implies properly-$\Sigma_8$-ness! To get that you need to use the fact that the arithmetical hierarchy doesn't collapse, which takes a proof. Of course that's not hard, but it is worth noting - and it's worth keeping in mind that there are hierarchies out there which do, or may as far as we know, collapse.