1
$\begingroup$

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.

  • 0
    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?2012-07-29
  • 0
    **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)".2012-07-30
  • 0
    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?2012-07-30
  • 0
    @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.2012-08-01

1 Answers 1

2

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.

  • 0
    So a natural number must have infinite zeros like **000...p1p2p3...pn**?2012-07-29
  • 1
    Yes, although there is no "first zero", so it is probably better to think about it as "...000p1p2p3...pn".2012-07-29