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.

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.

share|improve this question
6  
If the rationals could be put into an increasing sequence, with the usual ordering, would they be dense? –  David Mitra Aug 20 '12 at 15:50
1  
Uhmm, right at the beginning is a problem. How do introduce a total order on the rationals (which respects the usual order)? –  user20266 Aug 20 '12 at 15:51
2  
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. –  Kuba Helsztyński Aug 20 '12 at 18:03
2  
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. –  MJD Aug 20 '12 at 18:50
4  
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. –  MJD Aug 20 '12 at 18:53
show 2 more comments

2 Answers

up vote 10 down vote accepted

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).

share|improve this answer
    
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. –  Xodarap Aug 20 '12 at 16:52
1  
@Xodarap you might want to look into ordinal numbers then. $\mathbb{Q}$ is countable, just like $\mathbb{N}$, but they have different order types. –  Robert Mastragostino Aug 20 '12 at 17:00
1  
@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. –  MartianInvader Aug 20 '12 at 20:33
add comment

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.

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.