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)

apologies for the laziness


2 Answers 2


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 \} $$

  • $\begingroup$ Thanks, your answer is much more readable then the original solution! And your alternative solution is very neat. Regarding the first solution, I was wondering about the importance of being so careful around $0$. If we naively put all the elements of $S$ "behind" the elements of $\Bbb{N}\setminus S$, then we would have no way to discriminate between the set and its complement, right? But even if that is the case, we would have still established an injection..? $\endgroup$
    – davideleo
    May 16, 2019 at 21:45
  • 1
    $\begingroup$ @Davide: The motivation for that seems mostly to avoid special cases. With your proposal, most $S$ would give different orders, but you'd get the usual ordering of $\mathbb N$ whenever $\mathbb N\setminus S$ happens to be an initial segment of $\mathbb N$. Since there are only countably many of these exceptional cases, they could be handwaved away in some other way, but apparently the author found it simpler to reserve $0$ as an explicit separator. $\endgroup$ May 16, 2019 at 21:50
  • $\begingroup$ Ooh I see, now the point of the construction is clearer. Thanks for the help! $\endgroup$
    – davideleo
    May 16, 2019 at 21:58
  • $\begingroup$ @Davide: On the other hand you could take first $\mathbb N\setminus S$ in ascending order, followed by $S$ in descending order. This works, but proving that it is injective takes a bit of ingenuity (a simple way is to reconstruct $S$ as being all the numbers that have only finitely many successors in the new order). $\endgroup$ May 16, 2019 at 22:06

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.


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.