Định lý Cantor: tập số thực không đếm được

Giả sử, để phản chứng, rằng $[0,1]$ đếm được: mọi số thực trong đó xuất hiện đúng một lần trong một cách liệt kê $x_1, x_2, x_3, \ldots$ nào đó. Viết mỗi số dưới dạng thập phân $x_n = 0.d_{n1}d_{n2}d_{n3}\ldots$, chọn cách biểu diễn không kết thúc bằng dãy vô hạn chữ số 9 khi một số có hai cách biểu diễn.

Bây giờ xây dựng một số mới $y$ từng chữ số một, bằng cách nhìn xuống đường chéo của danh sách này: $y = 0.e_1e_2e_3\ldots$, trong đó chữ số thứ $n$ được xác định bởi $e_n=\begin{cases}5 & d_{nn}\neq5\\6 & d_{nn}=5\end{cases}$. Việc giới hạn lựa chọn trong $\{5,6\}$ đảm bảo $y$ không bao giờ kết thúc toàn chữ số 0 hoặc toàn chữ số 9, nên biểu diễn thập phân của nó là duy nhất và không mập mờ.

Với mọi chỉ số $n$, số $y$ khác $x_n$ tại chữ số thập phân thứ $n$ theo cách xây dựng ($e_n\neq d_{nn}$), nên $y\neq x_n\ \forall n$. Vì mọi chữ số của $y$ đều là $5$ hoặc $6$, ta có $y\in[0,1]$.

Nhưng khi đó $y$ là một số thực thuộc $[0,1]$ mà không bằng bất kỳ $x_n$ nào trong danh sách được giả định là đầy đủ — mâu thuẫn, vì danh sách được giả sử chứa mọi phần tử của $[0,1]$. Vậy không thể tồn tại cách liệt kê nào của $[0,1]$, và $[0,1]$ (do đó tập lớn hơn $\mathbb{R}$) là không đếm được.