Do all sets with total order have an injective mapping to the reals?

76 Views Asked by At

If a set is equipped with total order (reflexive, transitive, antisymmetric, strongly connected), does this necessarily mean there exists an injective mapping from that set to the reals? Alternatively, if a set has larger cardinality than the reals can it not be well-ordered?

I'm struggling to think of a counter example. Most of the canonical examples of sets with larger cardinality than the reals (all functions, power set of reals) cannot be equipped with total order.

1

There are 1 best solutions below

2
On

If we assume the axiom of choice then - contra your claim "Most of the canonical examples of sets with larger cardinality than the reals (all functions, power set of reals) cannot be equipped with total order" - every set can be linearly (indeed well-) ordered.

Even in the absence of choice, though, we can prove that the answer to your question is negative via Hartogs' theorem, which says that there is an ordinal $\alpha$ with no injection to $\mathbb{R}$. (More generally, for any set $X$ there is an ordinal not injecting into $X$.) The proof is quite simple: let $\mathcal{A}$ be the set of well-orderings of subsets of $\mathbb{R}$, up to order-isomorphism, and note that $\mathcal{A}$ itself is well-ordered by $[R]\le[S]$ iff $R$ is isomorphic to an initial segment of that corresponding to $S$. The unique ordinal $\mathcal{A}$, well-ordered this way, is isomorphic to will not embed into $\mathbb{R}$. Note that this proof does use Powerset and Separation, but does not use Choice.

(And if we replace "well-order" with "pre-well-order" in our definition of $\mathcal{A}$ we get an even stronger result: there is an ordinal onto which $\mathbb{R}$ does not surject! In the absence of choice this is not the same as simply lacking an injection into $\mathbb{R}$, and indeed the two ordinals so produced can be wildly different: if the axiom of determinacy holds, for instance, then $\omega_1$ does not inject into $\mathbb{R}$ but the smallest ordinal $\mathbb{R}$ doesn't surject onto - called "$\Theta$" - is much bigger than $\omega_1$.)