0

I know that there are exactly $2^{\aleph_0}$ Turing degrees, but I am trying to realize the reason: I am convinced there can't be more than $2^{\aleph_0}$ of them, but why can't there be less? I know it should be trivial...

Asaf Karagila
  • 393,674
any_one
  • 387

1 Answers1

2

For each real $X$, the set of things Turing below $X$ is countable. In set theoretic notation $|\{Y : Y \leq_t X\}| = \aleph_0$. This is because there are only countably many Turing machines. Consequently, for each $X$ its (Turing) degree $\text{deg}(X) = \{ Y : Y\leq_t X \ \& \ X\leq_T Y\}$ is at most countable.

Turing equivalence $\equiv_T$ partitions the set of reals into countable equivalence classes, and you can show that if $|\bigcup_{i\in I} C_i| = 2^{\aleph_0}$ when each $C_i$ is countable, then $I$ has size at least continuum.

I don't think any 1-degree is equal to any m-degree is equal to any $t$-degree, but I could be mistaken. There are, however, continuum many 1 degrees and m-degrees too.

James
  • 5,443
  • Thank you. It thought it was more complicated. But why are there anyway countably many 1- and m-degrees? I mean, I can imagine it...but why exactly? – any_one Oct 15 '16 at 22:24
  • 1
    The collection of m and 1 degrees are both size continuum, not countable. The argument is the same as for the Turing degrees: there are only countably many $Y$ which are either $m $ or 1 equivalent to a given $X $. – James Oct 15 '16 at 22:33