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.

surjectionfrom $2^\omega$ onto $\mathcal{D}$, but I don't know about aninjectionthe other way - I don't think that exists without choice. $\endgroup$ – Noah Schweber Jan 25 '18 at 12:01