Why doesn't the "diagonalization argument" used by Cantor to show that the reals in the intervals [0,1] are uncountable, also work to show that the rationals in [0,1] are uncountable?

To avoid confusion, here is the specific argument.

Cantor considers the reals in the interval [0,1] and using proof by contradiction, supposes they are countable. Since this set is infinite, there must be a one to one correspondence with the naturals, which implies the reals in [0,1] admit of an enumeration which we can write in the form x$_j$ = 0.a$_{j1}$ a$_{j2}$ a$_{j3}$... (for j $\in$ $\mathbb{N}$).
Now Cantor constructs a number x* where the jth digit of x* is (a$_{jj}$+2) mod 10 (I know there are other schemes; this is the one my professor used). The observation that x* $\neq$ x$_j$ $\forall$ j $\in$ $\mathbb{N}$, leads us to the conclusion that x* is not in this list, and hence the reals in [0,1] cannot be enumerated, and so [0,1] is not countable (which implies that the real numbers are not countable).
I asked my professor and she was unable to tell me why this same argument couldn't be used to prove that the rationals in [0,1] are also uncountable. It seems the argument would have to somehow show that the number you constructed using Cantor's method must be either a terminatingor repeating decimal, but I can't see how to prove this


  • 7
    $\begingroup$ $x^*$ might not be rational. $\endgroup$ – littleO Sep 20 '13 at 13:44
  • $\begingroup$ The elements in the list are rationals now. $\endgroup$ – Matt Brenneman Sep 20 '13 at 13:47
  • 6
    $\begingroup$ Yes, the elements in the list are rationals, but $x^*$ is not. $\endgroup$ – littleO Sep 20 '13 at 13:50
  • $\begingroup$ @littleO Is there a counter example? $\endgroup$ – Andes Lam Jan 17 at 7:49

Why should the decimal expansion constructed from the diagonal of the list yield a rational number? (I.e., why would that decimal expansion be repeating?)

  • $\begingroup$ My logic is that since the rationals in [0,1] are countable, this argument cannot show they are uncountable. Hence this construction could not lead to a contradiction similar to what Cantor gets for the reals. Therefore, this number must be "in the list", and being a rational number, must therefore have either a terminating or repeating decimal expansion. $\endgroup$ – Matt Brenneman Sep 20 '13 at 13:45
  • 5
    $\begingroup$ Why do you think that number must be in the list? You can list the rationals, you can construct $x^*$, and $x^*$ isn't in the list. There's no contradiction. $\endgroup$ – littleO Sep 20 '13 at 13:47
  • $\begingroup$ So just to be clear. My idea is to now apply this same method with the rationals in [0,1]. $\endgroup$ – Matt Brenneman Sep 20 '13 at 13:48
  • 3
    $\begingroup$ Why must it be in the list, and not just "not a rational number." It's certainly a real number, but there are lots of real numbers not in the list. @MattBrenneman $\endgroup$ – Thomas Andrews Sep 20 '13 at 13:48
  • 1
    $\begingroup$ OK, I see it now! Sorry. $\endgroup$ – Matt Brenneman Sep 20 '13 at 13:50

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.