Proof that $ \mathbb{R} $ is uncountable

Question

Im sure this question has been asked here a lot, but I'd like to hear if the way I understood Cantor's diagonal proof is correct.

We know that $ \left(0,1\right)\sim\mathbb{R} $. So its enough to prove that $ (0,1) $ is uncountable.

Now, assume by contradiction that $ (0,1) $ is countable. It implies that exists injection $ f:\left(0,1\right)\to\mathbb{N} $, and by Cantor-Berenstein theorem it follows that exists a bijection

$ g:\mathbb{N}\to(0,1) $.

(Now we need to make and assumption that I do not fully understand, so explanations would be appreaciated. ) We assume that if $2$ real numbers has the same representaion as a decimal expansion that ends with $999999\dots$ and decimal expansion that ends with $00000\dots$ we'll take the expansion that ends with $0000\dots$

Now, from the last arguments we can count the interval $ (0,1) $ and write their decimal expansion:

$ g\left(0\right)=0.x_{0,0}x_{0,1}x_{0,2}.... $

$ g\left(1\right)=0.x_{1,0}x_{1,1}x_{1,2....} $

$ \vdots $

We'll show that $ f $ is not surjective. We'll define a sequence of numbers that would be the numbers in the decimal expansion of real number $ d $ such that $ d\notin Im(f) $.

define

$ y_{i}=\begin{cases} 2 & x_{i,i}=1\\ 1 & x_{i,i}\neq1 \end{cases} $

and define $ d=0.y_{0}y_{1}y_{2}\dots $.

Now assume by contradiction that exists $ i\in \mathbb{N} $ such that $ f(i)=d $. So the $ i_{th} $ digit in the decimal expansions of $ d $ and $ g(i) $ should be equal, but that's a contradiction.

Thus, $ g $ is not surjective.

I think this proof works, but Im not sure why would we need the assumption that we are taking the decimal expansion that ends with 00000 rather than the one that ends with 999999.

Thanks in advance.

Answer 1

For this step:

Now assume by contradiction that exists i∈N such that f(i)=d. So the ith digit in the decimal expansions of d and f(i) should be equal, but that's a contradiction

If it is possible that the same number may have two different representations, then it is not the case that f(i)=d implies that the digits of f(i) and d are the same. In order to make this step work, you need to have a unique representation for each number. Either 0000... or 9999... will do.

Answer 2

It depends on how you want to count them, but there are at least three mistakes in how many people understand Cantor's Diagonal Argument, or CDA. Most questions raised about CDA are directly related to at least one them.

1. The proposition he was trying to demonstrate with CDA was "There is an infinite set which cannot be put into a bijection with the natural numbers." All he needed was an example, and he specifically chose to not use the real numbers. The set he actually used was the set of all infinite-length binary strings. I call then Cantor Strings.

2. He used the two characters 'm' and 'w', but it might be easier to understand with the characters '0' and '1'. Because then the strings can be interpreted as the binary representations of the set you did use. With one problem: the Cantor Strings "100000..." and "011111..." both represent the real number one-half. This raises the issue you asked about.

3. It is not a proof by contradiction; at least, not how it as taught as one. And in fact, it is logically invalid as taught. When you assume NOT(P) in order to derive a contradiction and so deduce that P is true, you must use all parts of what you assume in that derivation. The assumption that you have a surjection is never used in the derivation. CDA proves, directly, that you don't.

I'm not familiar with math formatting, so I'm just going to outline it.

1. Call the set of all Cantor Strings T.
2. Assume there is a subset of T, called S, that has a surjection s(n) from the natural numbers N.
3. Construct a new Cantor String s0 where the nth character is the opposite of the nth character of s(n).
4. For every n in N, s0 is a different Cantor String than s(n).
5. So s0 is not in S, but it is in T.
6. Any function s(n) is not a surjection from N to T. (This really should be enough, but Cantor justified it in a final step. That's where it can be called a proof-by-contradition, and I'm going to use as close to Cantor's actual words as possible.)
7. From this proposition it follows immediately that T cannot be put into a surjection from N, otherwise we would have the contradiction, that a string s0 would be both an element of T, but also not an element of T.

Using real numbers instead of Cantor Strings requires two additional steps, that are unnecessary. You have to show that you can use [0,1] instead of all real numbers, and you have to prove (in step #5) that s0 does not have an alternative binary (or decimal) representation. For that, you have to never allow infinite trailing 1's (or 9's).