0
$\begingroup$

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

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

Let $d_n$ 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 $d_n(f(n))$, and not $0$ or $9$.

Now, suppose $f(m) = r$. Then, the $m$-th digit of $r$ must be $d_m(r) = d_m(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$
0

2 Answers 2

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$ Commented Apr 21, 2012 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 $d_m(r) = d_m(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 $d_m(r) = d_m(f(m))$, or one of $d_m(f(m))$ and $d_m(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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .