# Injection from a Well-Ordered Set to $\mathbb{Q}$

Call a set $W \subset \mathbb{R}$ well-ordered if every non-empty $A \subset W$ has a minimum element. Prove that if $W \subset \mathbb{R}$ is well-ordered, then there is an injection from $W$ to $\mathbb{Q}$.

This problem was presented in my Topology class independent of the textbook we are using which is Principles of Topology by Fred H. Croom.

I understand that a function is injective, or one-to-one, if $f(x_1) = f(x_2) \Rightarrow x_1=x_2$. How does this along with the definition of well-ordered tie into a proof of the above problem? Any assistance will be greatly appreciated, thanks in advance.

• As there is a bijection between $\Bbb Q$ and $\Bbb N$ you might as well find an injection into $\Bbb N$. This means that you are being asked to prove that every well ordered subset of $\Bbb R$ is countable. – Ross Millikan Feb 11 '15 at 5:19
• For what it's worth, there is a reason to prefer $\mathbb{Q}$ over $\mathbb{N}$: In fact, there is an order preserving injection from $W$ to $\mathbb{Q}$ (but generally there won't be one into $\mathbb{N}$. (Of course, as stated, the question isn't asking for "order preserving", so Ross's point, and Brian's answer are spot on.) – Jason DeVito Feb 11 '15 at 6:09

HINT: If $A\subseteq\Bbb R$, and there is not injection from $A$ into $\Bbb Q$, then $A$ must be an uncountable set. Thus, you need only show that if $A\subseteq\Bbb R$ is uncountable, then $A$ is not well-ordered. One way to do this is to show that $A$ contains an infinite strictly decreasing sequence.
Suppose not; then in particular no point of $A$ is the limit of a decreasing sequence in $A$, so for each $a\in A$ there is an $\epsilon_a>0$ such that $[a,a+\epsilon_a)\cap A=\{a\}$. (Why?)
• Show that the intervals $[a,a+\epsilon_a)$ for $a\in A$ are pairwise disjoint.
• Thank you for the suggestion. I have a few questions regarding the hints. Would $[a, a+ \epsilon_a) \cap A = \{a\}$ because it is decreasing and therefore eventually the left and right endpoints would equal? How does one show that the interval $[a, a+ \epsilon_a)$ is disjoint? – Jamil_V Feb 11 '15 at 16:41
• @Jamil_V: If every interval of the form $(a,a+\epsilon)$ with $\epsilon>0$ contained a point of $A$, you could construct a strictly decreasing sequence in $A$ converging to $a$. We’re assuming that no such sequence exists, so there must be a positive $\epsilon_a$ such that $(a,a+\epsilon_a)\cap A=\varnothing$ and hence $[a,a+\epsilon_a)\cap A=\{a\}$. \\ Suppose that $a,b\in A$, $a<b$, and $[a,a+\epsilon_a)\cap[b,b+\epsilon_b)\ne\varnothing$. Show that $b\in(a,\epsilon_a)\cap A$, contradicting the choice of $\epsilon_a$. – Brian M. Scott Feb 11 '15 at 18:12