In studying the issue of linear orders and well ordering in the context of ZF Set Theory (without the Axiom of Choice), I have recently been thinking about the following question:
Is the set of all linear orders of $\mathbb{N}$ linearly orderable?
It feels as though there may be some way to construct a linear order on this set, perhaps by considering the number generated by the ordering (e.g $1 – 2 – 3 . . .$ would be smaller than $2 – 1 – 3 . . . $ ) but I am struggling to formalise this idea. Also, this feels like an idea that may rely upon the Axiom of Choice (although, again, I am unsure about this).
My other idea, is that this is a result that depends upon well ordering (in which case, due to the absence of the Axiom of Choice, would make the answer no).
I would be grateful for any clarity here.
Best Answer
The answer to the question as stated and clarified in the comments is yes, but there is an important subtlety.
Given a binary relation $R\subseteq\mathbb{N}^2$ - such as a linear order of the natural numbers - let $$x_R=\{\langle i,j\rangle: iRj\}$$ where $\langle\cdot,\cdot\rangle$ is a fixed bijection $\mathbb{N}^2\rightarrow\mathbb{N}$ (say, the Cantor pairing function). The corresponding map $$\mathcal{P}(\mathbb{N}^2)\rightarrow\mathcal{P}(\mathbb{N}):R\mapsto x_R$$ is clearly injective, and there is a natural linear order on $\mathcal{P}(\mathbb{N})$, namely by $x\le y$ iff $x=y$ or $m\in y\setminus x$ where $m=\min(x\triangle y)$ is the smallest natural number that $x$ and $y$ disagree about. We can also think of this as the left-to-right ordering on the set of paths through the full binary tree. This lets us linearly order the set of linear orders on $\mathbb{N}$ as follows: if $R,S$ are linear orders on $\mathbb{N}$, set $R\le S\iff x_R\le x_S$.
Note that there is nothing special about linear orders here: for any kind of finite-language structure (linear orders, groups, rings, ...) the set of such structures with domain $\mathbb{N}$ is $\mathsf{ZF}$-provably linearly orderable. This trick of representing structures by (essentially) reals gets used all the time in descriptive set theory and computable structure theory, incidentally.
The subtlety
Note, however, that the above idea is not isomorphism-invariant. What if we want to order, not the literal set of linear orders on $\mathbb{N}$, but the set of isomorphism types of same?
This is in fact impossible; precisely, it's consistent with $\mathsf{ZF}$ that the set of isomorphism types of countable linear orders is not linearly orderable. Unfortunately consistency proofs are necessarily quite involved, but the basic idea is that we can whip up (following the above idea, actually) a method $\mathfrak{M}$ of explicitly constructing linear orders from binary sequences such that two binary sequences are eventually equal iff their corresponding sequences are isomorphic; if we let $G_i$ ($i\in\omega$) be mutually Cohen generic over a ground model $M$, then in an appropriate symmetric submodel the set of ordertypes of the $\mathfrak{M}(G_i)$s won't be linearly orderable.
(Incidentally, I think that the discussion at/sources cited in an old question of Hanul Jeon mentioned in the comments gives a stronger result: the theory $\mathsf{ZF+DC+AD}$ proves that the set of countable isomorphism types of linear orders can't be linearly ordered. But this isn't actually mentioned there explicitly as far as I can tell, so I'm doing some inferring; I'll double-check this later today to see if it's actually true.)