0
$\begingroup$

In a Combinatorics text, I find this:

Not all infinite sets have the same cardinality. Consider the set of all integers and the set of all reals. Assume that the set of reals can be put in one-to-one-onto correspondence with the integers. Then consider the real number whose ith digit after the decimal is the ith digit of the ith real plus 5 mod 10. This real number cannot be in correspondence with any integer, since it differs from every real that has been mapped to an integer. From this we conclude that the reals cannot be placed in one-to-one correspondence with the integers.

What the bolded text is really saying to prove that one real number has been missed from mapping? Can you please explain the bolded sentence? I want to know how exactly has that real number missed the mapping.

$\endgroup$
1
  • 4
    $\begingroup$ Yes, and that happens whatever the mapping was. So the mapping cannot be a bijection. $\endgroup$ – Marc van Leeuwen Feb 7 '14 at 14:11
0
$\begingroup$

Indeed. This is called Cantor's diagonal argument. For ANY mapping from $\mathbb N$ to $\mathbb R$ you can think of, using this argument, you can find a real number the mapping missed.

The ANY part is really important, because you cannot say that ok, if I missed $x$, I'll just add $x$ and now I covered all the examples. The problem with this is that after you do this, you have created a new mapping from $\mathbb N$ to $\mathbb R$, to which, again, you can apply the argument.

Okay, look at it this way. You come rusing to my office, shouting you just discovered the mapping from $\mathbb N$ to $(0,1)$. I ask you to show it to me, and you display it to me. It looks like this:

a1 = 0.15333524632394823876423498029343...
a2 = 0.18736120389038483789102374u32908...
a3 = 0.28193719283789900000000000000000...
a4 = 0.12372937890483092848237496324908...

I can easily look at your sequence and use the argument in your question to produce a number. It starts with $0.$, then on the first decimal place, i will put $1+5=6$ because the first digit of $a_1$ is $1$. On the second place, I put $8+5\mod 10=3$ because the second digit of $a_2$ is $8$. I have thus produced a number that is not on your list:

0.6362...

The real magic here is that there is no way you can escape my argument. In a way, imagine the set of ALL mappings from $\mathbb N$ to $(0,1)$. The proof above shows that EVERY element in this set has SOME real number it misses.

$\endgroup$
1
  • $\begingroup$ Can you please elaborate it how exactly this argument is smart? $\endgroup$ – user33786 Feb 7 '14 at 14:18
0
$\begingroup$

$\begin{array}{cccccc} 9 & 7 & 8 & 2 & 1 & \cdots\\ - & - & - & - & - & \cdots\\ 4 & 6 & 0 & 3 & 2 & \cdots\\ 5 & 2 & 5 & 6 & 6 & \cdots\\ 6 & 7 & 3 & 5 & 1 & \cdots\\ 0 & 1 & 5 & 7 & 9 & \cdots\\ 2 & 8 & 3 & 5 & 6 & \cdots\\ \vdots & \vdots & \vdots & \vdots & \vdots\end{array}$

The upper number will not be one of the numbers below, since $9\neq 4$ (so it cannot be the first number), $7\neq 2$ (so it cannot be the second number) et cetera.

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