26 Oct 2018  0

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

00.123456789...10.234567890...20.345678901...30.456789012...\begin{aligned} 0 &\to 0.123456789... \\ 1 &\to 0.234567890... \\ 2 &\to 0.345678901... \\ 3 &\to 0.456789012... \\ &\vdots \end{aligned}

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

a=0.a1a2a3...a = 0.a_1a_2a_3...

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

b=0.b1b2b3...b = 0.b_1b_2b_3...

where we define

bn={3an37an=3b_n = \begin{cases} 3 & a_n \neq 3 \\ 7 & a_n = 3 \end{cases}

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

m0.b1b2b3...bm...m \to 0.b_1b_2b_3...b_m...

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

Graphically, we observe that

00.123456789...10.234567890...20.345678901...30.456789012...m0.b1b2b3b4...bm...\begin{aligned} 0 &\to 0.123456789... \\ 1 &\to 0.234567890... \\ 2 &\to 0.345678901... \\ 3 &\to 0.456789012... \\ &\vdots \\ m &\to 0.b_1b_2b_3b_4...b_m... \end{aligned}

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:

\absA<\absP(A)\abs{A} < \abs{\mathcal{P}(A)}

where $A$ is any set, $\mathcal{P}(A)$ is the power set of $A$, and \absA\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

B:={xAxf(x)}A,B := \{ x \in A \mid x \notin f(x) \} \subset A,

which is a set by the Axiom of Specification. Note that this set is non-empty, for if it is, then for each xAx \in A, we have xf(x)x \in f(x), which means that there is no preimage for, say, {x1,x2}I\{ 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,

yB=f(y)    yB=f(y) and yB=f(y)    yB=f(y),y \in B = f(y) \implies y \notin B = f(y) \text{ and } y \notin B = f(y) \implies y \in B = f(y),

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.

R={xxx}R = \{ x \mid x \notin x \}

Then

RR    RR and RR    RR,R \notin R \implies R \in R \text{ and } R \in R \implies R \notin R,

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)}$.

- Japorized -

Comments

There are currently no comments.
Comments have been disabled across the site.