📂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, and this is shown through the fact that no ‘one-to-one correspondence’ exists between the set of real numbers and any countable set. This can be obtained by showing that no one-to-one correspondence exists between the set of natural numbers and the open interval $(0,1)$, and then as its corollary.

Cantor proved this in an astonishing way, and this method remained as Cantor’s achievement together with the name ‘diagonal argument’. Regardless of the result, it is a proof whose beauty can be appreciated in itself, so even if you do not understand it after reading it a few times, keep reading until you do.

Proof

Assume that a one-to-one correspondence $f : \mathbb{N} \to (0,1)$ exists. Writing ${ a } _{ ij }$ as the $j$th digit after the decimal point, it can be represented as follows. $$ f(i)=0. { a } _{ i1 } { a } _{ i2 } { a } _{ i3 } { a } _{ i4 } \cdots $$ Then for a natural number $i \in \mathbb{N}$, it can be represented as an array 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 us 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 that of the numbers located on the diagonal of the above array, namely $a_{11} , a_{22} , \cdots$. Let us look only at whether the $i$th digit after the decimal point of $z$ and $f(i)$ is odd or even. Since ${ z }_{ i }$ being even means ${ a } _{ ii }$ is odd, and $\ { z } _{ i }$ being odd means ${ a } _{ ii }$ is even, we have $$ z\neq f(1) \\ z\neq f(2) \\ z\neq f(3) \\ \vdots \\ z\neq f(k) \\ \vdots $$ Since $z \neq f(i)$ for every natural number $i$, we have $z \notin f(\mathbb{N}) $; but since $f$ is a one-to-one correspondence, $f(\mathbb{N})=(0,1)$, and since $z \in (0,1)$, it must be that $z\in f(\mathbb{N})$. This contradicts the assumption, so no one-to-one correspondence $f : \mathbb{N} \to (0,1)$ exists.

■