Proper-$\Sigma_n$-ness of $\Sigma_n$-complete sets

180 Views Asked by At

This is a follow-up to this answer.

How does the fact that the arithmetic hierarchy doesn't collapse imply that if $A$ is $\Sigma_n$ complete, then $A$ is properly-$\Sigma_n$?

Some thoughts (but nothing serious). Assume that $A$ is not properly-$\Sigma_n$. Then it's either $\Sigma_i$ for $0\leq i\leq n-1$ or $\Pi_i$ for $0\leq i\leq n$. Suppose the former first. We know that any $\Sigma_n$ set is $m$-reducible to $A$. Should I consider a proper-$\Sigma_n$ set and show somehow that it's not possible to $m$-reduce it to $A$ (if this is even true)? I don't really see how the properness or inclusions in the hierarchy would be used.


Update: here are the definitions.

A set $B$ is $\Sigma_0$ ($\Pi_0$, $\Delta_0$) if $B$ is computable.

For $n\ge 1$, a set $B$ is $\Sigma_n$ if there is a computable relation $R(x,y_1,\dots,y_n)$ such that $$x\in B\iff (\exists y_1)(\forall y_2)\dots (Q y_n) R(x,y_1,\dots, y_n)$$ where $Q$ is $\exists$ for $n$ odd and $\forall$ for $n$ even.

The definition of $\Pi_n$ sets for $n\ge 1$ is similar (just switch the quantifiers).

A set $B$ is $\Delta_n$ if it's both $\Sigma_n$ and $\Pi_n$

A set $B$ is $\Sigma_n$-complete if $B$ is $\Sigma_n$ and for any $\Sigma_n$ set $A$, one has $A\leq_m B$.

1

There are 1 best solutions below

11
On BEST ANSWER

The key fact here is that if a set $A$ qualifies for some level of the hierarchy, then so does any set m-reducible to $A.$ Thus if $A$ is $\Sigma_n$ complete, and also qualifies for some lower level, then any $\Sigma_n$ set also qualifies for that lower level and the hierarchy collapses.

To prove the key fact based on your definition for the levels of the hierarchy, just observe that if $f$ is a total computable function and $R(n,y_1,\ldots, y_n)$ is a computable relation, then the relation $R'$ defined by $$R'(n,y_1,\ldots,y_n)\iff R(f(n),y_1,\ldots,y_n) $$ is computable. Thus if $B$ is m-reducible to $A,$ then there is a total computable $f$ such that $n\in B$ iff $f(n)\in A,$ and we can see from the definition this means that $B$ qualifies for any level that $A$ qualifies for.