Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
9  
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
    
add comment

4 Answers

up vote 11 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
1  
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
1  
@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
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.