# Cantor's theorem

The theorem cardinality of set of real numbers is strictly larger than cardinality of set of natural numbers uses diagonal method in its proof.

Why can't we use the same argument for creating a natural number just like we do real number? i.e. take 1st digit of the first element, 2nd digit of the second element... and change the digits so that the new natural number differs from the rest in the set of natural numbers.

-
I'm not sure what your idea is. Suppose we start with the list $1$, $2$, $3$, $\dots$. How would you hope to add a natural number not in the list? – Andrea Mori Jul 29 '12 at 8:59
1 an be written as ...0001 and so on. Then we can follow this rule: take pn (the nth digit in nth element of the set), construct a new number s=pn...p32p1, change the digits at every place and get a new number r. But as pointed out by @Dan, this argument is flawed since it does not guarantee that there will be a "infinite string of zeros (reading right-to-left)". – Sagar Patel Jul 30 '12 at 6:46
but, I mean, if the original list already includes all the natural numbers, do you really need an extra-argument to show that your idea is flawed? – Andrea Mori Jul 30 '12 at 8:02
@Andrea, well, yes, because we are looking for a proof by contradiction analogous to Cantor's proof, which initially assumes a countable list of all the real numbers. Consider that for p-adics the construction works to show that p-adics are uncountable. – Dan Brumleve Aug 1 '12 at 5:13

## 1 Answer

Because, in order to be an integer, the constructed digit-string must end in an infinite string of zeros (reading right-to-left), and there is no way to guarantee this with a diagonal argument. However, the diagonal argument can be used to prove that there are an uncountable number of p-adic numbers.

-
So a natural number must have infinite zeros like 000...p1p2p3...pn? – Sagar Patel Jul 29 '12 at 5:48
Yes, although there is no "first zero", so it is probably better to think about it as "...000p1p2p3...pn". – Dan Brumleve Jul 29 '12 at 6:00