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.

This was asked by blogegog on a YouTube comment (gasp!):

[Regarding Cantor's diagonal argument:]

Couldn't I just make the same statement about rational numbers and say, 'take the largest number [sic he probably meant the one with the most digits] on the chart and append to the end of it a 1 if I'm hungry, or a 2 if I'm not' to show that his list of rational numbers doesn't contain them all?

share|improve this question
    
I suggest you have a look at previous questions on this site - this has surely come up before. –  Gerry Myerson Aug 9 '12 at 7:03
2  
"Largest on the chart", "the one with the most digits in the chart" are both nonsenses of the same caliber and mean nothing mathematically (I'm assuming that by chart you meant the list of numbers between zero and one usually used in the diagonal proof of Cantor's theorem) and, of course, "appending" stuff to "the end" of a number with a probably infinite decimal expansion is a nonsense two levels higher than the above ones. –  DonAntonio Aug 9 '12 at 7:04
    
possible duplicate of Proof that the irrational numbers are uncountable –  J. M. Aug 9 '12 at 7:11
    
Related: A very thorough discussion of Cantor's diagonal argument was given by Arturo in an answer to How does Cantor's diagonal argument work? –  t.b. Aug 9 '12 at 7:15
    
add comment

4 Answers 4

Another way of looking at this is via continued fractions. Note the following facts:

  1. Every rational number finite continued fraction representation of the form $[a;b_1,b_2,\ldots,b_n]$ -- although every rational number has two such representations. Also, every such finite continued fraction represents a rational number.
  2. Every irrational number has a unique infinite continued fraction representation of the form $[a;b_1,b_2,\ldots]$, and every such infinite continued fraction represents an irrational number in this interval.

If we restrict our attention to the interval $[0,1)$, we may assume that $a=0$ in all of these representations.

It follows easily that the family of rational numbers in $[0,1)$ has cardinality not greater than the family of all finite sequences of positive integers. Similarly, the family of all irrational numbers in $[0,1)$ has cardinality exactly equal to the family of all infinite sequences of positive integers. We have thus reduced our problem to comparing the families of finite and infinite sequences of positive integers.

It is not too difficult to show that the family of all finite sequences of positive integers is equinumerous to the family of all positive integers itself. From this and the above observation we have that $\mathbb{Q} \cap [0,1)$ is countable.

Exactly using Cantor's diagonalisation technique one can show that the family of infinite sequences of positive integers is uncountable, and therefore $[0,1) \setminus \mathbb{Q}$ is also uncountable.

share|improve this answer
add comment

Well. The real numbers are uncountable. But, the real numbers are the union of the rationals and the irrationals. The rational numbers are countable. If the irrationals were also countable, then so would be the real numbers (why?). Hence, the set of irrational numbers is uncountable.

Note that countable means that there exists a bijection between the natural numbers and the set in question.

share|improve this answer
    
I believe it's more common to use the word "countable" to mean that there is a surjection from the natural numbers to the set in question. In other words, finite sets are considered to be countable too. –  user22805 Aug 9 '12 at 8:23
    
Yeah, you're right. People do use countable to mean that. I suppose that I should have said denumerable. I didn't want to go into the details of ordering cardinals, because the person posting the question would likly not know what that means. But, in the context of my paragraph, 'countable' is unambiguious. –  Chris Dugale Aug 9 '12 at 16:55
    
In the main paragraph of your answer, the word "countable" is fine. It's only the extra sentence at the end that I have an issue with. –  user22805 Aug 9 '12 at 20:49
add comment

Rationals are Countably Infinite (Proof : http://theoremoftheweek.wordpress.com/2010/02/24/theorem-18-the-rational-numbers-are-countable/) , while Irrationals ($\Bbb R-\Bbb Q$) are uncountably Infinite as Real Numbers are uncountably infinite (Proof: http://germain.its.maine.edu/~farlow/sec25.pdf)

share|improve this answer
add comment

A sequence of all possible rational numbers though infinite (regardless of their magnitude) has a definite unbreakable order. Between two rational numbers in such sequence, you can't squeeze in more rational numbers. But that is not the case with irrational numbers. In any given sequence of irrational numbers, you can squeeze in infinite irrational numbers between any two irrational numbers. So irrational numbers are uncountable and thus have greater cardinality beyond the countable rational numbers.

share|improve this answer
    
What do you mean by 'definite unbreakable order'? If you mean that the usual ordering by size of the rationals has 'adjacent' numbers then you're wrong; for every pair of rationals $a/b$ and $c/d$ there's a rational number between them ($(a+c)/(b+d)$ will work, with some caveats). –  Steven Stadnicki Sep 25 '12 at 16:59
    
Contrariwise, if you just mean sequence in the sense of there being a list, then it's not (necessarily) so that 'in any given sequence of irrational numbers, you can squeeze in infinitely many more', depending on your notion of sequence - most mathematicians believe that the irrationals (more broadly, the reals) have a so-called well-ordering, which means that you can 'sort' them such that after every irrational there's a well-defined 'next irrational'. You need to be very careful and precise about your language when you're dancing around infinity. –  Steven Stadnicki Sep 25 '12 at 17:00
    
@StevenStadnicki I didn't mean the ordering of rational numbers by size, I meant the ordering by the position of numerator and denominator (regardless of the magnitude of the rational number). You are right, I need to very careful and precise about my langauge when translating the thoughts into words. I guess in maths, language poses a great challenge to convey the ideas. –  Saurabh Sep 26 '12 at 5:07
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.