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.

  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Feb 11 '15 at 5:19
  • $\begingroup$ 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.) $\endgroup$ – 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.
  • Show that each of these intervals contains a rational number.
  • Conclude that there can be only countably many of these intervals.
  • $\begingroup$ 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? $\endgroup$ – Jamil_V Feb 11 '15 at 16:41
  • $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Feb 11 '15 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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