📂Set Theory

Cantor's Diagonal Argument

Theorem ¹

The open interval $(0,1)$ is an uncountable set.

Proof

The set of real numbers $\mathbb{R}$ is not a countable set, which is shown by the absence of a ‘one-to-one correspondence’ between the set of real numbers and any countable set. This demonstrates that there is no one-to-one correspondence between the set of natural numbers and the open interval $(0,1)$, which can be obtained as a corollary.

Cantor proved this in an astonishing method, which remained as an achievement named ‘diagonal argument’. Regardless of the result, it’s a proof that can be appreciated for its beauty alone, so even if it doesn’t make sense after reading it a few times, keep reading until it does.

Proof

Assuming that a one-to-one correspondence $f : \mathbb{N} \to (0,1)$ exists, ${ a } _{ ij }$ can be represented with $j$th digit after the decimal point as follows: $$f(i)=0. { a } _{ i1 } { a } _{ i2 } { a } _{ i3 } { a } _{ i4 } \cdots$$ Then, for natural numbers $i \in \mathbb{N}$, it could be represented in an arrangement like: $$f(1)=0. { a } _{ 11 } { a } _{ 12 } { a } _{ 13 } { a } _{ 14 } \cdots \\ f(2)=0. { a } _{ 21 } { a } _{ 22 } { a } _{ 23 } { a } _{ 24 } \cdots \\ f(3)=0. { a } _{ 31 } { a } _{ 32 } { a } _{ 33 } { a } _{ 34 } \cdots \\ \vdots \\ f(k)=0. { a } _{ k1 } { a } _{ k2 } { a } _{ k3 } { a } _{ k4 } \cdots \\ \vdots$$ Here, let’s define $z \in (0,1)$ as follows: $$z=0. { z } _{ 1 } { z } _{ 2 } { z } _{ 3 } { z } _{ 4 } \cdots, \left( { z } _{ j } = \begin{cases} 2 & { a } _{ jj } \text{가 홀수일 때} \\ 1 & { a } _{ jj } \text{가 짝수일 때} \end{cases} \right)$$ This picks numbers whose parity is opposite to the numbers $a_{11} , a_{22} , \cdots$ located on the diagonal in the above arrangement. Let’s just look at whether the $i$th digit after the decimal point of $z$ and $f(i)$ is odd or even. If ${ z }_{ i }$ is even, then ${ a } _{ ii }$ is odd, and if $\ { z } _{ i }$ is odd, then ${ a } _{ ii }$ is even, hence $$z\neq f(1) \\ z\neq f(2) \\ z\neq f(3) \\ \vdots \\ z\neq f(k) \\ \vdots$$ is true. Since $z \neq f(i)$ for all natural numbers $i$, and $z \notin f(\mathbb{N})$ while $f$ is a one-to-one correspondence, then $f(\mathbb{N})=(0,1)$ and since $z \in (0,1)$, $z\in f(\mathbb{N})$ must be true. This contradicts the assumption, so the one-to-one correspondence $f : \mathbb{N} \to (0,1)$ does not exist.

■