Return to Answer

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 non-zero degree $\mathbf{d}$, 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.

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.

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.

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 non-zero degree $\mathbf{d}$, 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.

The Turing degrees are probably the most intricate poset ever studied (by humans at least).

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.