How many Turing degrees are there?

772 Views Asked by At

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

1

There are 1 best solutions below

3
On BEST ANSWER

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.