8
$\begingroup$

Since the reals are uncountable, rationals countable and rationals + irrationals = reals, it follows that the irrational numbers are uncountable. I think I've found a "disproof" of this fact, and I can't see the error.

Since $Q$ is countable, list $q_1, q_2, \dots$ such that $q_i < q_{i+1}$. I want to show that between $q_i$ and $q_{i+1}$ there is exactly one irrational number; this will give us a bijection and prove the irrationals countable.

Since the irrationals are dense, it follows that there is at least one irrational number in $\left(q_i,q_{i+1}\right)$. Suppose there was more than one in this range, e.g. $x$ and $y$. Since $(x,y)$ is an open subset of $R$ and the rationals are dense, there must be some rational $q_c$ in this interval. But that means $q_i<q_c<q_{i+1}$, which contradicts our ordering. So there must be exactly one irrational in this range. QED.

Where is the problem? The only thing I can think of is that the rationals can be put into a sequence, but cannot be put into an increasing sequence, which seems odd.

$\endgroup$
7
  • 7
    $\begingroup$ If the rationals could be put into an increasing sequence, with the usual ordering, would they be dense? $\endgroup$
    – David Mitra
    Aug 20, 2012 at 15:50
  • 1
    $\begingroup$ Uhmm, right at the beginning is a problem. How do introduce a total order on the rationals (which respects the usual order)? $\endgroup$
    – user20266
    Aug 20, 2012 at 15:51
  • 3
    $\begingroup$ Note that if such ordering existed, there wouldn't be even one irrational number between $q_i$ and $q_{i+1}$. One can just repeat your argument. In fact, assume there is an irrational number $x$ such that $q_i\lt x\lt q_{i+1}$. Since $(q_i,x)$ is open and rationals are dense in $\mathbb{R}$, there must be some rational $q_c$ in this interval, that is $q_i\lt q_c\lt q_{i+1}$. Again, it contradicts our ordering. $\endgroup$
    – Kuba Helsztyński
    Aug 20, 2012 at 18:03
  • 3
    $\begingroup$ Here's a similarly odd property of the natural numbers: You can list them in increasing order, but you can't list them in decreasing order. $\endgroup$
    – MJD
    Aug 20, 2012 at 18:50
  • 4
    $\begingroup$ Something else to consider that may be enlightening: For each positive integer, there is a unique Roman numeral. For example, $100\mapsto C, 49\mapsto XLIX, 9876\mapsto MMMMMMMMMDCCCLXXVI$. Consider the set of positive integers ordered by alphabetical order of their roman numerals. This ordering begins with 100, 200, 300, 301… ($C, CC, CCC, CCCI\ldots$) and ends with 38 ($XXXVIII$). But it is infinite in the middle. $\endgroup$
    – MJD
    Aug 20, 2012 at 18:53

2 Answers 2

Reset to default
11
$\begingroup$

Your final statement is correct: the rationals can be listed, but not using the usual order. To convince yourself, just remember that between any two distinct rationals there are an infinite number of rationals (and irrationals).

$\endgroup$
3
  • $\begingroup$ Is there a description of "attainable" orderings? I think my difficulty is that all infinite sequences are in some sense "impossible" to write, yet some are "more impossible" than others. $\endgroup$
    – Xodarap
    Aug 20, 2012 at 16:52
  • 1
    $\begingroup$ @Xodarap you might want to look into ordinal numbers then. $\mathbb{Q}$ is countable, just like $\mathbb{N}$, but they have different order types. $\endgroup$
    – Robert Mastragostino
    Aug 20, 2012 at 17:00
  • 1
    $\begingroup$ @Xodarap Just because it's impossible to write the entire sequence doesn't mean it's impossible to define what a given entry will be, given the index of that entry. $\endgroup$
    – MartianInvader
    Aug 20, 2012 at 20:33
6
$\begingroup$

The assumption that you can list $\mathbb Q$ such that $q_1 < q_2 < \ldots$ is not true. You can prove that it is impossible to have this ordering with the argument you made.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .