This question already has an answer here:

If we can say that any positive rational number is countable or listable by showing that every positive rational number is the quotient of p/q of two positive integers, and then listing those in an array like this:

1/1 2/1 3/1 4/1 ...
1/2 2/2 3/2 4/2 ...
1/3 2/3 3/3 4/3 ...

We know that each row can go on for infinity, so instead we can draw a diagonal lines through the array to ensure that every fraction is counted, right?

But if we take all real numbers and try and list or count them, allegedly we can't, but why?

For example, if we wanted to list or make countable all numbers between 0 and 1, why can't we say that all possible permutations of decimal number combinations could be listed or counted the same way that all fractions are countable or listable for positive rational numbers?

If we're unable to list or count all possible combinations of decimal numbers between 0 and 1, why are we not saying that all the infinite combinations of fractions used to make up all positive rational numbers isn't countable as well?

I realize that a very erudite and technical explanation of the Cantor Diagonalization Argument was provided in this post, however I'm not specifically asking for an explanation of this argument and moreover the very thorough explanation provided by Arturo Magidin for the OP in the post is slightly beyond my understanding as I'm very new to set theory and discrete mathematics.


marked as duplicate by mrf, quid, Asaf Karagila, user296602, Rob Arthan Feb 11 '16 at 0:13

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ You need to look up Cantor's diagonal argument. $\endgroup$ – Gregory Grant Feb 10 '16 at 22:25
  • 2
    $\begingroup$ In part, it's because all rationals can be described in a finite number of symbols (ex. 13/19) but some reals need an infinite number of symbols (ex. 2.816452…). But look at Cantor's argument for an actual proof. $\endgroup$ – Akiva Weinberger Feb 10 '16 at 22:40
  • 1
    $\begingroup$ @Malvin9000 What does "there is actually a finite number of fractions for each rational" mean? For the rational $0.5$, there are infinitely many fractions ($\frac12$, $\frac24$, $\frac36$, etc.), for example. But there are finitely many symbols per each fraction, and so we only need finitely many symbols to uniquely name a rational. $\endgroup$ – Akiva Weinberger Feb 10 '16 at 23:30
  • 1
    $\begingroup$ @Malvin9000 If the reals were countable, we would be able to make a list of them, and name each real by where it appears in our list. We could call them "the first one in our list," "the second one in our list," etc. But that contradicts the idea (that I haven't actually proven) that some reals would need infinitely many symbols to name. $\endgroup$ – Akiva Weinberger Feb 10 '16 at 23:32
  • 1
    $\begingroup$ @AkivaWeinberger Sorry to tax your patience buddy, if I understood Cantor's argument I wouldn't have asked this layman's question in the first place, right? $\endgroup$ – AdjunctProfessorFalcon Feb 11 '16 at 0:44