4
$\begingroup$

Recall that Turing degrees are equivalence classes of subsets of $\mathbb{N}$ under Turing equivalence (mutual Turing reducibility). They are partially ordered by Turing reducibility and form a join-semilattice of cardinality $2^{\aleph_0}$, which is also known to contain antichains of cardinality $2^{\aleph_0}$. Countable chains can be easily constructed by iterated Turing jump.

Question: Does it contain chains of cardinality $>\aleph_0$?

1 Answers 1

9

Yes, there are $\omega_1$-like chains, which can be obtained by iterating the Turing jump into the transfinite. These are uncountable linearly ordered chains of order type $\omega_1$, uncountable chains with all proper initial segments being countable.

Let $0$ be the computable degree; if $0^{(\alpha)}$ is defined, then let $0^{(\alpha+1)}$ be the jump of $0^{(\alpha)}$, and at limit ordinals simply find any degree above, such as $\oplus_{\beta<\alpha} 0^{(\beta)}$, using fixed representatives of $0^{(\beta)}$ and a fixed representation of $\alpha$.

Indeed, by filling out this chain into a dense order, one can embed a copy of the long rational line into the Turing degrees.

Every chain must have all countable initial segments, however, since the cone below any degree is countable, as there are only countable many Turing machine programs.

  • 0
    Vladimir, you probably want to count the maximal chains, since otherwise you get that many just as subsets of a given chain. But for $2^{\omega_1}$ many maximal chains, just realize that there are antichains between successive degrees in the chain I built, and so a chain can make independent selections in each of $\omega_1$ many of these intervals, creating $2^{\omega_1}$ many distinct and incompatible chains, which can be extended to that many maximal chains.2012-07-24