# Formal proof for A subset of the real numbers, well ordered with the normal order of $\mathbb R$, is at most $\aleph_0$

I tried to write a formal proof for the theorem: $A$ subset of $\mathbb R$ well ordered by the normal order $\implies A$ is at most of cardinality $\aleph_0$.

Any suggestions?

Thanks.

-
Every element has a successor, so you can associate to every element an interval above it, which contains...? – Qiaochu Yuan Jun 10 '11 at 14:19

Now that your question has been answered, let me point out that it may be interesting to observe furthermore that all the countable well-orderings are in fact represented by suborders of $\langle\mathbb{R},\lt\rangle$, and even of $\langle\mathbb{Q},\lt\rangle$. Let me give two proofs.

The first proof is an elementary exercise in transfinite induction. One shows that every countable ordinal $\alpha$ embeds into $\mathbb{Q}$. Note that $0$ embeds trivially. If an ordinal $\alpha$ embeds, then by composing with an isomorphism of $\mathbb{Q}$ with an interval in $\mathbb{Q}$, we may suppose the embedding is bounded above, and thereby extend it to an embedding of $\alpha+1$. If $\lambda$ is a countable limit ordinal, with $\lambda=\text{sup}_n\alpha_n$, then by induction we may map $\alpha_n$ into $\mathbb{Q}\cap (n,n+1)$, and this is an embedding of an ordinal at least as large as $\lambda$. QED

The second proof is simply to argue that $\langle\mathbb{Q},\lt\rangle$ is universal for countable linear orders: every countable linear order embeds into $\mathbb{Q}$. This is proved by using just the "forth" part of Cantor's famous back-and-forth argument, namely, given a linear order $L=\langle\{p_n\mid n\in\mathbb{N}\},\lt_L\rangle$, then map $p_n$ to a rational $q_n$ so that one has a order-preserving map at each finite stage. The next element $p_{n+1}$ relates to the previous elements either by being above them all, between two of them, or below them all, and we may choose a corresponding $q_{n+1}$ of the same type. So we get an order-preserving map $L\to \mathbb{Q}$. Thus, in particular, every countable well-ordering embeds into $\mathbb{Q}$. QED

-
There's something confusing me about your first proof. How do we know that the mapping of all the $\alpha_n$ is consistent with the ordering of $\lambda$? That is, you seem to have enumerated the $\alpha_n$ by natural numbers, but you can't do that for any countable ordinal and keep the ordering consistent. For example, if $\lambda = 2\omega$, where would $\omega + 1$ get mapped to? I may be misunderstanding something, I have quite limited experience with transfinite proofs. – MartianInvader Jun 10 '11 at 17:57
I just meant that $\lambda$ is the supremum of the $\alpha_n$, that is, that the $\alpha_n$ are cofinal in $\lambda$, because the embedding I build has ordertype $\Sigma_n\alpha_n$, which would then be at least as large as $\text{sup}_n\alpha_n$, which is $\lambda$. It isn't necessary that the $\alpha_n$ enumerate all the ordinals less than $\lambda$ or even that the $\alpha_n$ are increasing. In your remark, I think you mean $\omega\cdot 2$ rather than $2\omega$, since $2\omega=\omega$ in the usual ordinal arithemtic; but for $\omega\cdot 2$, you could take $\alpha_n=\omega+n$ if you like. – JDH Jun 10 '11 at 18:22
Ah, I understand. And yes, I did mean $\omega \cdot 2$. Thanks for the explanation. – MartianInvader Jun 10 '11 at 18:24

Suppose $A\subseteq\mathbb R$ can be well-ordered by the usual $<$, and fix an enumeration of the rationals, i.e. $\mathbb Q = \langle q_n\mid n\in\omega\rangle$.

For $a\in A$ denote $S(a)$ the successor of $a$ in $A$, if $b\in A$ is a maximal element of $A$ then $S(b) = b+1$.

For every $a\in A$ set $q_a$ the least rational $q_n$ in the enumeration, such that $a< q_n< S(a)$. Since $a\neq S(a)$ we have that $\mathbb Q\cap (a,S(a))$ is non-empty, therefore such minimal element exists.

We prove that this is indeed one to one, suppose not then for some $a, b\in A$ such that $a\le b$ we have $q_a=q_b$. By the choice of $q_a$ we have that $a<q_a=q_b<S(a)$, therefore $a\le b<q_b=q_a<S(a)$. Since the $S(a)$ is the least element of $A$ such that $a<S(a)$, we have that $b\le a$ therefore $a=b$.

We found an injective function of $A$ into a countable set, therefore it is countable.

-
I would say "the first rational", not "the least rational". There is no such least rational! – TonyK Jun 10 '11 at 16:34
@TonyK: There's also no "first rational", there is "least rational in the enumeration such that ..." however (which is the same as your suggestion). :-) – Asaf Karagila Jun 10 '11 at 16:47
(+1) Nice proof! Just a nitpick: "$a\le b\in A$" should be "$a,b\in A$, with $a\le b$,". Also, Tony K is right: "least" applies to orderings, not enumerations; "first" applies to enumerations. – John Bentin Jun 11 '11 at 12:44
@John: Thanks. I tried to shorten with $a<b$, but I should have written in full. As for "least" and "first", both apply to linear orderings, be them dense; well or any other kind. – Asaf Karagila Jun 11 '11 at 13:20
How do least and first apply to any linear ordering? There's no least or first integer. And regardless, when you say "least rational" it makes me think the usual order, I don't automatically assume you mean the rational with the least index. Ignoring correctness, from a communications/pedagogical stance "first" is better in this case, I feel like. – Ryan Apr 28 at 16:06

The following idea uses some set-theoretic machinery, has the advantage of coming from a simple geometric visualization.

Suppose to the contrary that there is an uncountable set $A$ of reals which is well-ordered under the natural order.

Then $A$ is order isomorphic to an uncountable ordinal. It follows that some subset $B$ of $A$ is order isomorphic to the least uncountable ordinal $\omega_1$.

The set $B$ has a least element. By shifting if necessary, we can make that least element $0$. Either $B$ is bounded above or it isn't. If it is bounded above, let $m$ be the least upper bound. Note that since $B$ is order-isomorphic to $\omega_1$, $m$ cannot be in $B$. Then the map that takes $x$ to $x/(m-x)$ is order preserving, and "stretches" $B$ so that for every integer $n$, there is $b\in B$ such that $b>n$. (We have kept the name $B$ for the stretched set.)

So we can assume that $B$ has smallest element $0$, and that for every integer $n$, there is an element of $B$ which is $>n$.

Let $B_n$ be the intersection of $B$ with the interval $[0, n]$. Then $B_n$ is order isomorphic to an initial segment of $\omega_1$. Since $\omega_1$ is the least uncountable ordinal, it follows that $B_n$ is countable.

Since $$B =\bigcup_{n \in N} B_n$$ we have expressed $B$ as a countable union of countable sets, or equivalently $\omega_1$ as a countable union of countable ordinals. This is impossible.

-

A sketch proof...

Consider $\mathbb{R}$ as the set of equivalence classes of Cauchy sequences of rationals. We define "the normal" partial order on $\mathbb{R}$ by $x \leq y$ iff $(x = y)$ OR $(\forall \langle x_{i} \rangle)(\forall \langle y_{i} \rangle)(\langle x_{i} \rangle \in x$ AND $\langle y_{i} \rangle \in y \rightarrow (\exists n)(n \in \mathbb{N} \rightarrow (\forall m)(m > n \rightarrow x_{m} < y_{m}))))$. For $A$ to be well-ordered under this partial order there can only be at most $\aleph_{0}$ distinct $n$ in the last part of the definition as they are drawn from $\mathbb{N}$.

-