2
$\begingroup$

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.

$\endgroup$
6
  • 3
    $\begingroup$ Do you mean the set of linear orders on $\mathbb{N}$, or the set of isomorphism types of linear orders on $\mathbb{N}$? The answer to the first question is affirmative and not too hard; the answer to the second question is negative and rather tricky if I remember correctly. $\endgroup$ Commented Apr 12, 2023 at 19:36
  • $\begingroup$ I once asked a relevant question years ago. $\endgroup$
    – Hanul Jeon
    Commented Apr 12, 2023 at 19:37
  • $\begingroup$ I meant the first question, but that second question is also an interesting one @NoahSchweber $\endgroup$
    – FD_bfa
    Commented Apr 12, 2023 at 19:38
  • $\begingroup$ Don't forget: Some linear orders on $\Bbb N$ are dense. Choose your favorite enumeration $f: \Bbb N \to \Bbb Q$ and then define $a \lt^* b \iff f(a) \lt f(b)$. $\endgroup$ Commented Apr 12, 2023 at 19:42
  • 1
    $\begingroup$ @NoahSchweber The suggestion in the original post seems to assume the ordering has a least element. $\endgroup$ Commented Apr 12, 2023 at 21:43

1 Answer 1

3
$\begingroup$

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.)

$\endgroup$
1
  • $\begingroup$ Thanks for your answer. Did you manage to find out about whether or not the final remark was true? $\endgroup$
    – FD_bfa
    Commented Apr 16, 2023 at 0:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .