Cardinality of the set of all total orders on $\Bbb{N}$

Question

I need to compute the cardinality of the set of all total orders on $\Bbb{N}$.

Now, by definition there is an inclusion of this set into $\mathcal{P}(\Bbb{N}\times\Bbb{N})$, and so has cardinality $\le 2^{\aleph_0}$.

Now, finding an injection from $\mathcal{P}(\Bbb{N})$ to the set in question is much harder. I have the solution below, which I don't really understand and don't intuitively see. It feels like the usual $\le$ with some priority to elements of the set injected, but not quite.

Can anyone extrapolate some meaning from this, or provide a nicer solution?

(apologies for the laziness of not rewriting the solution)

Answer 1

What the definition says, somewhat convolutedly, is:

Let $S$ be some subset of $\mathbb N_0$. Use $S$ to split $\mathbb N_+$ into two subsets $A$ and $B$, such that each number $n$ ends up in either $A$ or $B$ depending on whether or not $n-1$ is in $S$. It is possible that either $A$ or $B$ ends up being empty; that is fine.

Now consider the following total order on $\mathbb N$:

• First come all elements of $B$, with the usual ordering between them.
• Then comes $0$.
• Finally come all elements of $A$, in their usual order.

This gives a different order for different $S$, because if we have some $n$ such that $n\in S_1$ but $n\notin S_2$, then we have $0\le_{S_1}n+1$ but $n+1\le_{S_2}0$. So $\le_{S_1}$ and $\le_{S_2}$ are different orderings. More generally, we can reconstruct $S$ just by knowing the ordering $\le_S$, simply by using it to compare $0$ to each nonzero number.

---

A different construction that would be simpler to explain would be

Given $S\subseteq\mathbb N$ take the usual order on $\mathbb N$, and then interchange the elements $2n$ and $2n+1$ for each $n\in S$.

or, in symbols, as a set of ordered pairs: $$ \bigl({\leq} \setminus \{ \langle 2n,2n+1\rangle \mid n\in S \}\bigr) \cup \{\langle 2n+1,n\rangle \mid n \in S \} $$

Answer 2

It seems that the author tried quite hard to find an explicit injection from $\mathcal P(\Bbb N)$.

This however is not necessary; we only need an injection from any set of cardinality $2^{\aleph_0}$.

For example, consider the set $\{ S: 0 \notin S\} \subseteq \mathcal P(\Bbb N)$ and assign to each element $S$ of it the total order intuitively described as:

$$S \le' {(\Bbb N \setminus S)}$$

However, as you see this requires assuming that $0 \notin S$ so as to preserve injectivity (otherwise we just get the usual order on $\Bbb N$).

My guess is that the author wanted to avoid this.