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)


$\endgroup$
3
$\begingroup$

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...

$\endgroup$
1
  • $\begingroup$ It is in fact enough to avoid one of the digits 0 and 9 in the construction. $\endgroup$ – hmakholm left over Monica Apr 21 '12 at 9:14
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.