Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
add comment

1 Answer

up vote 9 down vote accepted

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.

share|improve this answer
    
So, there are $2^{\aleph_1}$ different chains, up to isomorphism, right? –  Vladimir Reshetnikov Jul 24 '12 at 20:03
    
Doesn't this start to get tricky when 'fixed representations of $\alpha$' themselves are ill-defined? I know this works in concept, but thought there were serious issues once you hit roughly $\alpha=\omega^1_{\mathrm{CK}}$... –  Steven Stadnicki Jul 24 '12 at 20:11
    
The issue at $\omega_1^{ck}$ has to do with the uniqueness of the jump iteration, but I am only proving existence here. There are indeed many ways to carry out the limit step. For existence, the lemma to prove is that every countable set of Turing degrees is bounded above, and this can be done as I said just by fixing representatives and an enumeration of them, and then gluing them as columns of a subset of the plane, which is then thought of as a subset of $\mathbb{N}$. Use the lemma then to get above what you've got so far at every limit stage. At successors, take the jump. –  JDH Jul 24 '12 at 20:22
    
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. –  JDH Jul 24 '12 at 20:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.