Having trouble understanding Cantors proof that real numbers are uncountable

Question

I found this video very easy to follow and understood the proof. https://www.youtube.com/watch?v=mEEM_dLWY0g

However, I am still having trouble understanding the proof presented to me in my csmath course. Here is a picture of the proof presented to me in class.

The part that really confuses me is when it says d_i = {1 if d_ii = 0, 0 otherwise, I also don't understand what the last two statements, and how they lead to a contradiction. Why is dk,n = dn ? I am very confused, thanks for your help.

Answer 1

Since you understood the video, let me just explain how the proof from class is really the same thing. In the video, the infinite decimals in the list are $$.a_1a_2a_3\ldots\\.b_1b_2b_3\ldots\\.c_1c_2c_3\ldots\\ \text{etc}$$ In the class proof, they are written as $$.d_{00}d_{01}d_{02}\ldots\\.d_{10}d_{11}d_{12}\ldots\\.d_{20}d_{21}d_{22}\ldots\\ \text{etc}$$ So $a_1=d_{00}$, $a_2=d_{01}$, etc.; $b_1=d_{10}$, $b_2=d_{11}$, etc.; and so on for the rest of the list.

The video proof writes $.x_1x_2x_3\ldots$ for the decimal constructed by the diagonal process, the one not on the list. The class proof writes this as $.d_0d_1d_2\ldots$. So $x_1=d_0$, $x_2=d_1$, etc.

In the video, the key point is that $x_1\neq a_1$, $x_2\neq b_2$, $x_3\neq a_3$, etc. The class proof expresses the same thing as $d_0\neq d_{00}$, $d_1\neq d_{11}$, $d_2\neq d_{22}$, etc.

The video simply says that $.x_1x_2x_3\ldots$ differs from $.a_1a_2a_3\dots$ in the first place, differs from $.b_1b_2b_3\dots$ in the second place, etc. The class version expresses this more generally and symbolically. The $k$-th decimal in the list is $$.d_{k0}d_{k1}d_{k2}\ldots$$ Now if $.d_0d_1d_2\ldots$ appeared on the list, it would have to be the $k$-th decimal for some $k$. In other words, we would have to have $d_n=d_{kn}$ for all $n$ (and this value of $k$). But $.d_0d_1d_2\ldots$ differs from $.d_{k0}d_{k1}d_{k2}\ldots$ in the $k$-th place by construction: in other words, $d_k\neq d_{kk}$ by the definition of $.d_0d_1d_2\ldots$.

There are advantages to both notation choices. You found the video easier to understand, so that says something. On the other hand, you could be persnickety and ask the video guy what comes after the 26th decimal on the list, $.z_1z_2z_3\ldots$. This is an over-fussy objection, since it's clear what he means, but it explains why some people prefer to use two subscripts instead.

More significantly, the diagonal sequence in the video proof is written $.a_1b_2c_3\ldots$; in the class proof, it's written $.d_{00}d_{11}d_{22}\ldots$. With the latter notation, we have an easy way to write the $n$-th element of the diagonal sequence: $d_{nn}$.

Answer 2

The idea is to create a real number that doesn't have a mapping to any natural number. We do so by creating a real number represented by his decimal representation which his i-th decimal digit after the floating point is different than the i-th natural mapping. This number is obviously doesn't have a mapping since it's different from all the mapped real numbers which is a contradiction to the assumption that $Im(f)=R$

Answer 3

The purpose of the confusing part is to construct a real number which is different from every other real number which is already in the list. That is the linchpin of the entire argument.

The way it is presented with 1 and 0 is related to the fact that Cantor's proof can be carried out using binary (base two) numbers instead of decimal.

Say we have a square of four binary numbers, like say:

1001
1101
1011
1110

Now, how can we find a binary number which is different from these four? One algorithm is to look at the diagonal digits:

 1 001
1 1 01
10 1 1
111 0

If we complement these digits 1110 (turn 1 into 0 and 0 into 1), then we get a number which is different from any the four, namely 0001. That is because it differs in the first bit from the first number, differs in the second bit from the second number, differs in the third bit from the third number, and differs in the fourth bit in the fourth number.

For any given existing number, there is a bit position for which the new number differs from that number; and so it differs from all the numbers.

Now this can be carried over into decimal digite, where the "complement" operation replaces every zero with a 1, and every nonzero with 0. This still works because it satisifies the goal of producing a new number which differs from every other number in at least one digit.

The contradiction in Cantor's proof is of the assumption of completeness, because the diagonal argument shows that there are real numbers which have been missed. The function $f$ has failed to match all real numbers in the range with the integers, because by the diagonal algorithm, we can construct new numbers which are not on the list and not accounted for.