Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)


share|improve this question

2 Answers 2

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

share|improve this answer
    
It is in fact enough to avoid one of the digits 0 and 9 in the construction. –  Henning Makholm Apr 21 '12 at 9:14

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.

share|improve this answer

Your Answer

 
discard

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.