2

The problem printed in Cutland 9-2.9-6 is wrong, it should be countable, not denumerable

m-degree is an equivalence class of the relation $\equiv_m$(many-one equivalent).

Question:

Why any m-degree a is denumerable?

My thoughts:

Denote m-degree of A as $d_m(A)=\{B:A\equiv_mB\}$.

Clearly, $d_m(\mathbb{N}) = \{\mathbb{N}\}$ is denumerable. And $d_m(\emptyset)=\{\emptyset\}$ is denumerable is a vacuous truth.

Denote $0_m$ as the recursive m-degree that consists of all recursive sets except $\emptyset$ and $\mathbb{N}$.

Any recursive enumerable set is the range of a computable function. But if we enumberate computable functions by their Gödel numbers, there is repeatition. Thus not a bijection from $0_m$ to $\mathbb{N}$. So how to prove $0_m$ or even other m-degrees are denumerable?

Eric Xu
  • 179
  • @CarlMummert Could you provide some idea on how to prove $0_m$ is denumerable? – Eric Xu May 09 '14 at 12:19
  • 1
    If you have a map from $\mathbb N$ onto an infinite set $A$, then there is also a bijection from $\mathbb N$ to $A$ --- just skip the repetitions. – Andreas Blass May 09 '14 at 13:44

1 Answers1

1

So first, according to your definition, $d_m(A)$ is a set of subset of $\mathbb{N}$. So I think it is confusing to write $d_m(\emptyset)=\emptyset$. Instead you should write $d_m(\emptyset)=\{\emptyset\}$. (And $d_m(\mathbb{N})=\{\mathbb{N}\}$).

Now, for any $X$, the set $\{Y\ :\ X \geq_m Y\}$ is countable, essentially because the set of computable functions is countable. Indeed, by definition $X \geq_m Y$ if there exists a total computable function $f$ so that $n \in Y \leftrightarrow f(n) \in X$. Another way to say this is $f^{-1}(X)=Y$.

So if $X \geq_m Y_1$ and $X \geq_m Y_2$ for $Y_1 \neq Y_2$, you have to use two distinct computable functions in the many-one reductions, as if $f^{-1}(X)=Y_1$ then $f^{-1}(X) \neq Y_2$.

As there are only countably many total computable functions $f$, then there are only countably many $Y$ so that $X \geq_m Y$. It follows that there are only countably many $Y$ so that $X \equiv_m Y$.

Archimondain
  • 918
  • @Archinondain Thanks for your answer. But in this problem, I think denumerable means countably infinite, which is different from countable. – Eric Xu May 10 '14 at 04:22
  • Not very different. Countably infinite means both countable and infinite. I gave a proof that each m-degree is countable. The fact that each m-degree is infinite (except for $d_m(\emptyset)$ and $d_m(\mathbb{N})$) is obvious, because adding or removing finitely many integer of a set does not change its m-degree. – Archimondain May 11 '14 at 02:55
  • Thanks! I found the problem is wrong. It should be countable in my title not denumerable. – Eric Xu May 11 '14 at 14:28