| | |
Proof:
We will argue indirectly. Suppose $f: \mathbb{N} \rightarrow [0,1]$ is a one-to-one correspondence between these two sets. We intend to argue this to a contradiction that $f$ cannot be "onto" and hence cannot be a one-to-one correspondence -- forcing us to conclude that no such function exists.
Consider the value of $f(1)$. This is some real number between 0 and 1, so we can express it in decimal notation in the following way:
$$f(1) = .x_1^{(1)} x_2^{(1)} x_3^{(1)} \cdots$$
Here, each $x_j^{(i)}$ is just a single digit (0-9) of the decimal form for $f(1)$.
Listing the outputs of $f$ corresponding to the first several natural numbers, we have:
$$\begin{align*}
f(1) &= .x_1^{(1)} x_2^{(1)} x_3^{(1)} x_4^{(1)} x_5^{(1)} \cdots\\
f(2) &= .x_1^{(2)} x_2^{(2)} x_3^{(2)} x_4^{(2)} x_5^{(2)} \cdots\\
f(3) &= .x_1^{(3)} x_2^{(3)} x_3^{(3)} x_4^{(3)} x_5^{(3)} \cdots\\
f(4) &= .x_1^{(4)} x_2^{(4)} x_3^{(4)} x_4^{(4)} x_5^{(4)} \cdots\\
f(5) &= .x_1^{(5)} x_2^{(5)} x_3^{(5)} x_4^{(5)} x_5^{(5)} \cdots\\
&\vdots
\end{align*}$$
Now consider the real number $y$ between 0 and 1 with decimal form, $y = .y_1 y_2 y_3 y_4 y_5 \cdots$ where each $y_j$ is chosen to disagree with $x_j^{(j)}$. In particular, if $x_j^{(j)}=5$, we take $y_j = 2$, while if $x_j^{(j)} \not= 5$, we take $y_j = 5$. Thus, $y$ disagrees with the $n^{\textrm{th}}$ element in our list above in the $n^{\textrm{th}}$ decimal place. As such, $y$ never appears in this list, no matter how far down we extend it.
We have reached our contradiction. We have found a real number $y$ in the set $[0,1]$ that never appears as an output of our ("onto") one-to-one correspondence. We consequently reject our original assumption and thus, no such function $f$ could have existed in the first place. As such, there can never be a one-to-one correspondence between the naturals and the infinite set $[0,1]$. Consequently, the set of real numbers in the interval $[0,1]$ must be uncountable.
QED.