Cardinality of Orderings of $\mathbb{R}$

418 Views Asked by At

For a finite set $S$ there are $\vert S\vert!$ orderings of its elements.

What is the cardinality of all orderings of $\mathbb{N}$? What would $$\vert \mathbb{N}\vert!$$ mean? Is it $\prod_{n\in\mathbb{N}} \aleph_0=\aleph_0^{\aleph_0}=\aleph_1$?

Wikipedia says the "equivalence classes of well-orderings of the natural numbers" has cardinality $\aleph_1$. But I can't put together in my mind the connection between well-orderings of $\mathbb{N}$ and all orderings of $\mathbb{N}$. (Are there non well-ordered orderings of $\mathbb{N}$?)

This leads to wondering what the cardinality of all orderings of $\mathbb{R}$ is. (Actually my thought process went in the other direction, from $\mathbb{R}$ to $\mathbb{N}$.) I think knowing the answer to the above question will teach how to determine what $$\vert \mathbb{R}\vert !$$ means, if anything.

I will be happy if you assume the continuum hypothesis to be true for the purposes of this question, but any level of completeness is welcome.

1

There are 1 best solutions below

0
On

First thing first, you don't need the continuum hypothesis if you are willing to use the provable cardinality of $\Bbb R$ being $2^{\aleph_0}$, also denoted by $\frak c$ often.

Now. One can easily prove that $\Bbb N$ has $\aleph_0^{\aleph_0}=2^{\aleph_0}=\frak c$ permutations. Given any permutation $f\colon\Bbb N\to\Bbb N$, we can define an order $<_f$ on $\Bbb N$ by taking $f(n)<_f f(m)\iff n<m$. Since any two distinct permutations induce two different orders, this means that there are at least $2^{\aleph_0}$ ways to linearly order $\Bbb N$ which. And there can't be any more than that too, because there are only $2^{\aleph_0}$ relations on $\Bbb N$ to begin with.

Similarly with $\Bbb R$. We can quite easily prove that there are $2^{2^{\aleph_0}}$ permutations of $\Bbb R$, each inducing a different ordering, so there are $2^{2^{\aleph_0}}$ ways to linearly order the real numbers.


As a side remark, $\aleph_1$ is defined to be the cardinality of all countable ordinals, which is exactly the different isomorphism types of countable well-orders. But even then, there are $2^{\aleph_0}$ ways to order a countable set in a given order type.