Assuming the axiom of choice, every set can be linearly (indeed, well-) ordered. However, without choice this can fail, as witnessed most drastically by the consistency of amorphous sets. More reasonable failures of choice - e.g. via determinacy - tend to yield more reasonable behavior, but can still exclude certain structures from occurring.

I'm interested in what the situation with the Turing degrees can be, if we assume AD. That is:

In ZF+DC+AD (plus whatever else is needed to get a good answer), can the set $\mathcal{D}$ of Turing degrees be linearly ordered?

(Note that of course there is no demand that this ordering behave nicely with respect to $\le_T$, in any sense.)

I strongly suspect the answer is "no," but I don't immediately see how to prove it.

In fact, as far as I can tell very few sets of Turing degrees admit "definable" linear orderings - specifically, every example I can find is the image of some injective partial function $f$: $\subseteq2^\omega\rightarrow\mathcal{D}$. For example, the standard construction of a continuum-sized antichain of Turing degrees consists of building a continuous function $g:2^\omega\rightarrow 2^\omega$ such that $x\not=y\implies deg(g(x))\not=deg(g(y))$; we then push the lexicographic order on $2^\omega$ through the map $f=deg\circ g$. This raises the following question, especially assuming a negative answer to (1):

Is there a reasonable extension of ZF which proves that every orderable set of Turing degrees is the image of some injective function from a subset of $2^\omega$?

As usual, we get closely related questions if we work in ZFC instead and restrict attention to (say) Borel sets and orders. I would also be interested in answers to these questions.

  • $\begingroup$ Can you try mimicking the ordering of the surreal numbers? Or does that require too much choice? Gerhard "Seems Bizarre To A Degree" Paseman, 2018.01.24. $\endgroup$ Jan 25, 2018 at 5:36
  • $\begingroup$ I thought it was well-established that there are exactly $2^\omega$ Turing degrees; does that argument use Choice? $\endgroup$ Jan 25, 2018 at 6:17
  • $\begingroup$ @StevenStadnicki In ZF there is of course a surjection from $2^\omega$ onto $\mathcal{D}$, but I don't know about an injection the other way - I don't think that exists without choice. $\endgroup$ Jan 25, 2018 at 12:01
  • $\begingroup$ @GerhardPaseman I'm not sure what you mean. $\endgroup$ Jan 25, 2018 at 12:01
  • 2
    $\begingroup$ @Noah As Paul mentioned, the key is that you can embed $\mathbb R/E_0$ into $\mathcal D $. (In my paper with Ketchersid, we explain that in natural determinacy models, for instance, a set is not linearly orderable if and only if there is such an injection.) $\endgroup$ Jan 25, 2018 at 14:04

1 Answer 1


You can't linearly order the Vitali ($\mathcal{P}(\omega)/\mathrm{Fin}$) degrees if every set of reals has the property of Baire, since you can't even choose between complementary degrees. The set of $x$ which are chosen can't be meager or somewhere comeager, since below any initial segment you can find a pair of complements which are both in any given comeager set.

There's a continuous, Vitali-invariant map $c$ that sends mod-finite different subsets of $\omega$ to mutually Cohen-generic reals over $L$ (assuming $\mathcal{P}(\omega)^{L}$ is countable; this is overkill in any case), giving you an embedding of the Vitali degrees into the Turing degrees. Such a map can be induced by a pair of functions $f, g \colon \omega \to \mathrm{Fin}$ so that for all $x \subseteq \omega$, $c(x) = \bigcup\{ f(n) : n \in x\} \cup \bigcup \{ g(n) : n \not\in x\}$. This should answer the first question.

  • 1
    $\begingroup$ Very nice! Of course, it's important that the map you mention also sends two mod-finite-equivalent things to Turing-equivalent reals, but that's easily done. $\endgroup$ Jan 25, 2018 at 13:42
  • 3
    $\begingroup$ Can you explain the first sentence a bit more fully? $\endgroup$ Jan 25, 2018 at 13:43
  • 5
    $\begingroup$ @Joel You asked the same a while ago. Here is a sketch. $\endgroup$ Jan 25, 2018 at 14:07
  • $\begingroup$ Combined with Andres' comment below my question, I think this basically answers what I was asking. $\endgroup$ Jan 29, 2018 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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