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.


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.

| cite | improve this answer | |
  • 1
    $\begingroup$ There are even conjectures and results to the effect that there cannot be a natural solution: for example, there is no $e\in\omega$ and computable total $f$ such that (1) for all sets $X$, $X<_TW_e^X<_TX'$, (2) if $X\equiv_TY$ via $\Phi_d$ then $W_e^X\equiv_TW_e^Y$ via $\Phi_{f(d)}$. I believe even more is known, but I can't recall. $\endgroup$ – Noah Schweber Mar 21 '14 at 23:53
  • 1
    $\begingroup$ Does your remark on the lack of natural complete sets apply to many-one completeness (mentioned in the OP) as well as Turing completeness? $\endgroup$ – Joel David Hamkins Mar 22 '14 at 3:08

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$.

| cite | improve this answer | |
  • $\begingroup$ Nice although I suppose the $ m $-degree of this set depends on the version of $\Omega $ used? Also instead of $\Omega $ we could use $0'$ which is even more natural? $\endgroup$ – Bjørn Kjos-Hanssen Mar 22 '14 at 20:43
  • 1
    $\begingroup$ Yeah, I'm pretty sure I've got a construction of m-incomparable versions. If you mean the real $0.\emptyset'$, that should also work, but again different numberings will give different $m$-degrees. Also, I'm stumped on whether these are tt-complete. $\endgroup$ – Dan Turetsky Mar 22 '14 at 20:57
  • 1
    $\begingroup$ Because $\Omega$ itself is not a canonical number, but is only a arbitrarily chosen member of an infinite class of $\Omega$-numbers, sets defined using $\Omega$ will not be natural. $\endgroup$ – Carl Mummert Mar 24 '14 at 11:12
  • $\begingroup$ Well, even Hilbert ' 10th problem has to be encoded to get a subset of $\omega $... which can be done in many ways $\endgroup$ – Bjørn Kjos-Hanssen Mar 24 '14 at 12:11
  • 3
    $\begingroup$ Often, naturalness makes sense only modulo some notion of equivalence. In the context of $m$-equivalence, there is only one reasonable encoding of Hilbert's 10th problem, and it is natural. Not so for (left cuts of) $\Omega$. $\endgroup$ – Denis Hirschfeldt Mar 24 '14 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.