2

So I know there are precisely $2^{\aleph_0} $ Turing degrees, but is there a proof of this somewhere?

Christopher Rose
  • 925

1 Answers1

3

There are at most $2^{\aleph_0}$ degrees, since each degree corresponds to the Turing degree of some subset of $\mathbb{N}$.

Given a set $B \subseteq \mathbb{N}$, there are only countably many "oracle programs" that can be written which use $B$ as an oracle. So there are at most countably many sets which can be computed from $B$. That means that each degree has at most countably many sets in them. Since every set from $\mathcal{P}(\mathbb{N})$ has to be in some degree, there must be exactly $2^{\aleph_0}$ of them.

Athar Abdul-Quader
  • 1,017
  • So I understand that there are $2^{\aleph_0}$ subsets of $N$. However, doesn't each degree contain more than one subset? For example, all finite subsets of $N$ are in the same Degree. Hence the total number of degrees appears to be $< 2^{\aleph_0}$. What am I getting wrong? – Christopher Rose Mar 18 '16 at 19:12
  • 1
    Each degree contains at most countably many subsets, so there have to be $2^{\mathbb{N}}$ degrees. – Athar Abdul-Quader Mar 18 '16 at 20:07
  • Remember, a countable union of countable sets is countable. Analogously, a union of $\kappa$ many countable sets has cardinality $\kappa$. So if we take the set of degrees, each degree gives us a countable collection of subsets of $\mathbb{N}$, and the union of all those should give us the power set of $\mathbb{N}$. So the cardinality of the set of degrees has to be equal to the cardinality of $2^{\mathbb{N}}$. – Athar Abdul-Quader Mar 18 '16 at 21:17