Sets which are strictly $\Sigma_n$ but not $\Sigma_n$-complete

63 Views Asked by At

This question is about classifying the complexity of subsets $A \subseteq \mathbb{N}$ in the arithmetical hierarchy. Empirically, it seems that whenever you can show $A$ is, say, $\Sigma_n$, then $A$ turns out to be $\Sigma_n$-complete (i.e. for any other $\Sigma_n$ set $B$, there is a many-one reduction $h\colon A \leq_m B$). Or at least, when you give a reasonable definition of $A$.

This is the case for many index sets, e.g. $\mathrm{TOT} = \{ e: \varphi_e$ total$\}$, $\mathrm{INF} = \{ e: W_e$ infinite$\}$, etc. Here, $\varphi_e$ list the partial computable functions, and $W_e$ the c.e. sets. Unpacking the definition shows that $\mathrm{TOT}$ and $\mathrm{INF}$ are both $\Pi_2$, and they both turn out to be $\Pi_2$-complete.

It seems there must be sets that are strictly $\Sigma_n$ but not $\Sigma_n$-complete, and I'm sure some sort of forcing argument could be used to construct one. What I'm more interested in is if there are natural examples of such things. That is, sets that one could conceivably care about for reasons other than they are strictly $\Sigma_n$ but not $\Sigma_n$-complete. E.g. index sets such as $\mathrm{TOT}$ or $\mathrm{INF}$.

(of course, examples for $\Pi_n$ or $\Delta_n$ are equally fine)