0
$\begingroup$

In the following version of Cantor's diagonal argument, where is the assumption that the nth digit of r must be different from 0 or 9 used? Thanks

Suppose f is a 1-1 mapping between the positive integers and the reals.

Let dn be the function that returns the n-th digit of a real number.

Now, let's construct a real number, r. For the n-th digit of r, select something different from dn(f(n)), and not 0 or 9.

Now, suppose f(m) = r. Then, the m-th digit of r must be dm(r) = dm(f(m)), but by construction that cannot be the m-th digit of r.

Therefore, no such f exists.

Thus, there is no 1-1 mapping between the positive integers and the reals.

The important thing to note is when I construct r, it really is a real number.

(by n-th digit, I mean to the right of the decimal point)


2 Answers 2

3

If r has digits 0 or 9, then it is possible that f(m)=r but they have different digits, for example 1 = 0.999...

  • 0
    It is in fact enough to avoid _one of_ the digits 0 and 9 in the construction.2012-04-21
0

Here is where you need the assumption: it says

Now, suppose f(m) = r. Then, the m-th digit of r must be dm(r) = dm(f(m)), but by construction that cannot be the m-th digit of r.

This should be:

Now, suppose f(m) = r. Then, either m-th digit of r must be dm(r) = dm(f(m)), or one of dm(f(m)) and dm(r) is 0 while the other is 9, but the former is not possible by construction, and the latter is not possible because r has no 0 or 9 in the decimal expansion.

The case when $d_m(r)=0$ and $d_m(f(m))=9$ or vice versa is possible because rational numbers of the form $\frac{n}{10^m}$ have two decimal expansions: for example, $1=1.000\ldots=0.999\ldots$ etc.