Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
So a natural number must have infinite zeros like – 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 "". – Dan Brumleve Jul 29 '12 at 6:00

Your Answer


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.