|

The uncountability of $(0, 1)$ is an important result that demonstrates that $\mathbb{R}$, the set of real numbers, has a greater cardinality, i.e. “bigger size” than that of $\mathbb{N}$, the natural numbers. In other words, the result shows to us that $\mathbb{N}$ is countable while $\mathbb{R}$ is uncountable.

Georg Cantor was the first to have proven this result, and consequently showing to us that there are different “degrees” of infinity. This result is consequently known to us as Cantor’s Diagonalization, or Cantor’s Diagonal Argument.

Constructive Proof

Suppose the function $f : \mathbb{N} \to (0, 1)$ is bijective. Then, we have

where we are really only allowing the images of the natural numbers to be anything but repeating 9’s or the image of any other natural number (for f is bijective). Then, let

where $a_i$ is the diagonal digit starting from the first decimal place of the image of 0. Then, let

where we define

Clearly so, this $b \in (0, 1)$. But if b has a pre-image, then there must be some $m \in \mathbb{N}$ such that $f(m) = b$. But this would mean

i.e. this would mean $a_m = b_m$, which is impossible by our construction of b.

Graphically, we observe that

i.e. the diagonal cut that we used to define a will cross every image, and the image that complements every digit in a must end up having one digit that cannot be a complement of one of the digits of a due to the bijection.

As constructive as this seems, there are some subtleties involved in the proof that should be clarified:

• The images are sometimes given as if it is carefully and/or deliberately constructed, instead of being completely random (while abiding to uniqueness due to the bijection), which it is not. To show this randomness, I decided to write the images in the most careless way possible.
• The construction of $b$ seems deliberate during presentation unless explicitly stated; we can really let the digits in $b$ completely be the complements of the digits of $a$, by simply making sure that $a_n \neq b_n$.

Set-theoretic Proof

In set theory, Cantor’s Diagonalization is presented in a way that strongly resembles the infamous Russel’s Paradox (or should I say that the resemblance is the other way around).

The statement is as follows:

where $A$ is any set, $\mathcal{P}(A)$ is the power set of $A$, and $\abs{A}$ is the cardinality of $A$. This is a more general proof than what we had above.

It is clear by the injective function $x \mapsto {x}$ that $\abs{A} \leq \abs{\mathcal{P}(A)}$. Suppose a bijection $f: A → \mathcal{P}(A)$ exists. Let

which is a set by the Axiom of Specification. Note that this set is non-empty, for if it is, then for each $x \in A$, we have $x \in f(x)$, which means that there is no preimage for, say, $\{ x_1, x_2 \} \subset I$.

Now notice that $B \in \mathcal{P}(A)$ by construction. Since f is bijective, $\exists y \in A$ such that $f(y) = B$. However,

both of which are contradictions. Thus f cannot be a bijection, and in particular, it cannot be a surjection. Notationally, we have that $\mid A \mid \lt \abs{\mathcal{P}(A)}$.

Russell’s Paradox

As aforementioned, Russell’s Paradox resembles the set B constructed in Cantor’s argument; let R be the set of all sets that are not members of themselves, i.e.

Then

both of which are contradictions. Cantor’s argument tells us that the notion of a set of all sets is incoherent: if $R$ is a set of all sets, then in particular, $\mathcal{P}(R)$ would be an element of $R$, and in the language of sets, a subset of R, leading up to $\abs{R} = \abs{\mathcal{P}(R)}$.