1
$\begingroup$

Let $W_0, W_1, W_2,\dotsc$ be an effective numbering of r.e. sets.

Consider sets $\text{Emp}=\{x\mid W_x=\emptyset\}$, $\text{Tot}=\{x\mid W_x=\mathbb{N}\}$ and $S_n=\{x\mid W_x=W_n\}$ (for some fixed $n$).

It is easy to show that $\text{Emp}$ is many-one reducible to $\text{Tot}$, but $\text{Tot}$ is not many-one reducible to $\text{Emp}$. Moreover, for all $n$, $S_n$ is many-one reducible to $\text{Tot}$.

I was able to show that if $W_n$ is infinite, then $S_n$ and $\text{Tot}$ are many-one equivalent, i.e. have the same m-degree.

But what if $W_n$ is nonempty but finite? I have shown that the m-degree of $S_n$ is in such a case strictly greater than the m-degree of $\text{Emp}$. But is it strictly smaller then the m-degree of $\text{Tot}$, or maybe they are equal?

$\endgroup$

1 Answer 1

1
$\begingroup$

In fact if $W_n$ is finite then $S_n$ is weaker than $\mathsf{Tot}$. This is because, in this case, $S_n$ is $\Sigma^0_1\wedge\Pi^0_1$-definable (or equivalently, is the intersection of a c.e. set and a co-c.e. set), while $\mathsf{Tot}$ is $\Pi^0_2$-complete.

Specifically, fix $n$ such that $W_n$ is finite, let $A=\{m: W_m\supseteq W_n\}$ and let $B=\{m: W_m\subseteq W_n\}$. Since $W_n$ is finite we have that $A$ is c.e. (if $W_n$ were infinite then $A$ would be merely $\Pi^0_2$) and $B$ is co-c.e. (Note that without an assumption on $W_n$, the most we could say is that $A$ and $B$ are each $\Pi^0_2$.) We clearly have $S_n=A\cap B$.

With this question we've stepped into the difference (Ershov) hierarchy; see the first section of Stephan/Yang/Yu for a good survey of its basic properties. Note that every set in the difference hierarchy is Turing-reducible to the Halting Problem, while $\mathsf{Tot}$ is strictly above the Halting Problem even with respect to Turing reducibility.

$\endgroup$
1
  • $\begingroup$ Dear Noah, thank you for your answer and the reference! Now I understand why my efforts (using only the machinery of Rogers classical book up to chapter 7) were unfruitful (but still I learned a lot). $\endgroup$
    – ijon
    Oct 28, 2023 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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