Return to Revisions

The Turing degrees are an immensely intricate poset $\mathcal{D}$. Here are some of their remarkable properites:

1. Every countable poset is embeddable in $\mathcal{D}$.
2. $\mathcal{D}$ contains minimal degrees. (a non-zero degree $\mathbf{m}$ with no degree between $\mathbf{0}$ and $\mathbf{m}$)
3. For every non-zero degree $\mathbf{d}$, there is a degree that is incomparible with $\mathbf{d}$.
4. $\mathcal{D}$ contains an antichain of size $2^{\aleph_0}$.
5. No infinite strictly increasing chain in $\mathcal{D}$ has a least upper bound.
6. For every degree $\mathbf{d} \geq \mathbf{0}' $, there is a degree $\mathbf{c} < \mathbf{d}$ such that $\mathbf{c}'=\mathbf{d}$. (Here $\mathbf{c}'$ denotes the set of indices of oracle Turing machines that halt when using $\mathbf{c}$ as an oracle. Note that one must check that this is well-defined on degrees.)
7. For any two recursively enumerable degrees, there is a recursively enumerable degree strictly between them.
8. Any finite distributive lattice can be embedded in the recursively enumerable degrees.