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 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}$, there is a degree $\mathbf{c} < \mathbf{d}$ such that $\mathbf{c}'=\mathbf{d}$. (here $\mathbf{c}'$ denotes the jump of $\mathbf{c}$)
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.