<p>In fact if <span class="math-container">$W_n$</span> is finite then <span class="math-container">$S_n$</span> is weaker than <span class="math-container">$\mathsf{Tot}$</span>. This is because, in this case, <span class="math-container">$S_n$</span> is <span class="math-container">$\Sigma^0_1\wedge\Pi^0_1$</span>-definable (or equivalently, is the intersection of a c.e. set and a co-c.e. set), while <span class="math-container">$\mathsf{Tot}$</span> is <span class="math-container">$\Pi^0_2$</span>-complete.</p>
<p>Specifically, fix <span class="math-container">$n$</span> such that <span class="math-container">$W_n$</span> is finite, let <span class="math-container">$A=\{m: W_m\supseteq W_n\}$</span> and let <span class="math-container">$B=\{m: W_m\subseteq W_n\}$</span>. Since <span class="math-container">$W_n$</span> is finite we have that <span class="math-container">$A$</span> is c.e. (if <span class="math-container">$W_n$</span> were infinite then <span class="math-container">$A$</span> would be merely <span class="math-container">$\Pi^0_2$</span>) and <span class="math-container">$B$</span> is co-c.e. (Note that without an assumption on <span class="math-container">$W_n$</span>, the most we could say is that <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are each <span class="math-container">$\Pi^0_2$</span>.) We clearly have <span class="math-container">$S_n=A\cap B$</span>.</p>
<p>With this question we've stepped into the <strong>difference (Ershov) hierarchy</strong>; see the first section of <a href="http://maths.nju.edu.cn/%7Eyuliang/ssyy.pdf" rel="nofollow noreferrer">Stephan/Yang/Yu</a> for a good survey of its basic properties. Note that every set in the difference hierarchy is Turing-reducible to the Halting Problem, while <span class="math-container">$\mathsf{Tot}$</span> is strictly above the Halting Problem even with respect to Turing reducibility.</p>

CC BY-SA 4.0
2023-10-28T22:41:18.850Z
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).
ijon
CC BY-SA 4.0
2023-10-28T22:25:39.557Z
2023-10-28T22:25:39.557Z
Noah Schweber
<p>Let <span class="math-container">$W_0, W_1, W_2,\dotsc$</span> be an effective numbering of r.e. sets.</p>
<p>Consider sets <span class="math-container">$\text{Emp}=\{x\mid W_x=\emptyset\}$</span>, <span class="math-container">$\text{Tot}=\{x\mid W_x=\mathbb{N}\}$</span> and <span class="math-container">$S_n=\{x\mid W_x=W_n\}$</span> (for some fixed <span class="math-container">$n$</span>).</p>
<p>It is easy to show that <span class="math-container">$\text{Emp}$</span> is many-one reducible to <span class="math-container">$\text{Tot}$</span>, but  <span class="math-container">$\text{Tot}$</span> is not many-one reducible to <span class="math-container">$\text{Emp}$</span>. Moreover, for all <span class="math-container">$n$</span>, <span class="math-container">$S_n$</span> is many-one reducible to <span class="math-container">$\text{Tot}$</span>.</p>
<p>I was able to show that if <span class="math-container">$W_n$</span> is infinite, then <span class="math-container">$S_n$</span> and <span class="math-container">$\text{Tot}$</span> are many-one equivalent, i.e. have the same m-degree.</p>
<p>But what if <span class="math-container">$W_n$</span> is nonempty but finite? I have shown that the m-degree of <span class="math-container">$S_n$</span> is in such a case strictly greater than the m-degree of <span class="math-container">$\text{Emp}$</span>. But is it strictly smaller then the m-degree of <span class="math-container">$\text{Tot}$</span>, or maybe they are equal?</p>

<computability>
Many-one degrees of some particular sets
ijon
# Many-one degrees of some particular sets

(Asked by: username_0 on 2023-10-28)

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?

**Tags:** computability


---

## 1 answers

### Answer by username_1 on 2023-10-28. Score: 1 | Accepted answer

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](http://maths.nju.edu.cn/%7Eyuliang/ssyy.pdf) 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.

> **Comments:**
> **username_0**: 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).  

---

