# Why does Cantor's Proof (that R is uncountable) fail for Q?

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

Matt

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

## 1 Answer

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

• 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. – Matt Brenneman Sep 20 '13 at 13:45
• 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. – littleO Sep 20 '13 at 13:47
• So just to be clear. My idea is to now apply this same method with the rationals in [0,1]. – Matt Brenneman Sep 20 '13 at 13:48
• 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 – Thomas Andrews Sep 20 '13 at 13:48
• OK, I see it now! Sorry. – Matt Brenneman Sep 20 '13 at 13:50