4 Cantor's Diagonal Argument

In 1891, Cantor published a proof of extraordinary simplicity: no list, however infinite, can enumerate all real numbers.

Suppose, for contradiction, that the reals in [0,1] are countable:

r1=0.d11 d12 d13 d14 ⋯r_1 = 0.d_{11}\,d_{12}\,d_{13}\,d_{14}\,\cdots
r2=0.d21 d22 d23 d24 ⋯r_2 = 0.d_{21}\,d_{22}\,d_{23}\,d_{24}\,\cdots
r3=0.d31 d32 d33 d34 ⋯r_3 = 0.d_{31}\,d_{32}\,d_{33}\,d_{34}\,\cdots

Construct a new real number s by choosing each digit to differ from the diagonal:

s=0.s1 s2 s3 ⋯wheresn≠dnn  for all  ns = 0.s_1\,s_2\,s_3\,\cdots \quad\text{where}\quad s_n \neq d_{nn} \;\text{for all}\; n

Then s differs from every listed number at some decimal place:

s≠rnfor every n∈Ns \neq r_n \quad \text{for every } n \in \mathbb{N}

But s is in [0,1], contradicting completeness of the list.

↯
  ∣R∣>∣N∣  \boxed{\;|\mathbb{R}| > |\mathbb{N}|\;}

The continuum is strictly larger than the integers. This was the first proof that distinct sizes of infinity exist.