Computability: why any m-degree a is denumerable?

322 Views Asked by At

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?

1

There are 1 best solutions below

3
On BEST ANSWER

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