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.

Solution 1:

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

Solution 2:

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.

Solution 3:

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.