Is every non-recursive set in $\Sigma_1$ complete in $\Sigma_1$ (relatively to many-to-one reductions)?

Question

Most well known sets in $\Sigma_1 \setminus\Delta_0$, such as the Halting problem, are complete in $\Sigma_1$, relatively to the many-to-one reduction. In fact I don't know any example of a (non recursive) set in $\Sigma_1$ that is not complete.

Is every set in $\Sigma_1\setminus\Delta$ complete in $\Sigma_1$?

• If so, why the trouble of proving completeness for such problems?

• If not (is there some Ladner-type Theorem?), can anyone give natural examples of $\Sigma_1\setminus\Delta_0$ sets that are not complete?

  Of course the question generalizes for other levels of the arithmetic hierarchy.

  I apologize if this question was already answered here, or if the answer is well known.

Answer 1

Not every set in $\Sigma_1\setminus\Delta_1$ is $\Sigma_1$-complete.

For Turing reductions it was known as Post's Problem and resolved by Friedberg and Muchnik around 1957. Interestingly there is still no known natural solution to Post's problem. Perhaps the closest is as follows: let $W_{e,s}$ be the $e$th $\Sigma_1$ set in some standard enumeration, as it looks at stage $s$; let $K(j)[s]$ be the prefix free Kolmogorov complexity of $j$ as approximated at stage $s$; and let $A=\bigcup_sA_s$ where the finite sets $A_s$ are uniformly $\Delta_1$ and $$ A=\{\langle e,n\rangle : \exists s(W_{e,s}\cap A_s=\varnothing\wedge \langle e,n\rangle\in W_{e,s}\wedge \sum_{\langle e,n\rangle\le j\le s}2^{-K(j)[s]}<2^{-(e+2)})\} $$ Then $A$ is $K$-trivial (which implies it is not $\Sigma_1$-complete) and not $\Delta_1$ (Downey, Hirschfeldt, Nies, Stephan).

For $m$-reductions the problem was already resolved by Post. He constructed a set $A\in \Sigma_1\setminus\Delta_1$ whose complement $B$ contains no infinite $\Delta_1$ set, and showed that such a set $A$ would have to be $m$-incomplete. In standard terminology $A$ is simple and $B$ is immune.

Answer 2

Let $\Omega$ be the halting probability, and let $X$ be the set of rational numbers less than $\Omega$. I think I can reasonably claim that $X$ is a natural set.

Since $\Omega$ is left-c.e., $X$ is $\Sigma^0_1$. Also, $X$ is non-computable since it's Turing equivalent to $\Omega$. However, $X$ cannot be many-one complete for $\Sigma^0_1$ sets. Indeed, no convex set of rationals (or finite union of convex sets of rationals) can be many-one complete for $\Sigma^0_1$ sets.

Suppose $X$ were complete. Note that $\emptyset'$ is uniformly many-one complete: from a $\Sigma^0_1$ index for a set, we can compute an index for its reduction to $\emptyset'$. Since $X$ is complete, there is a reduction from $\emptyset'$ to $X$, and so by composing these we see that $X$ is uniformly many-one complete (this argument works for any complete set).

Now, we'll make a $\Sigma^0_1$ set $V$, and by a standard argument with the recursion theorem we can assume we already know an $n$ with $V = W_n$. Using the uniformity, this means we know the index of a computable reduction $f$ from $V$ to $X$.

Begin by computing $f(0), f(1)$ and $f(2)$. These are rational numbers, and so are arranged in some order. Without loss of generality, let's assume that $f(0) \le_\mathbb{Q} f(1) \le_\mathbb{Q} f(2)$. Then enumerate $0$ and $2$ into $V$, but leave $1$ out. By assumption, this means that $f(0)$ and $f(2)$ are in $X$, but $f(1)$ is not. But this contradicts the convexity of $X$.