Cantor đã sai ! [Vitalik Buterin]

Bài viết gốc mang tựa đề: Cantor was wrong: debunking the infinite set hierarchy

Bài viết này yêu cầu bạn đọc có sẵn một số kiến thức về lực lượng của tập hợp, biểu diễn số trên hệ nhị phân, hệ thập phân.

Chứng minh của Cantor

Định lý: Tập hợp các số thực trong khoảng \((0,1)\) là không đếm được.

Chứng minh (phản chứng)

Giả sử các số thực trong khoảng \((0,1)\) là đếm được, nghĩa là tất cả các số thực này có thể được liệt kê như một tập hợp có thứ tự \(S= \{x^{(1)}, x^{(2)}, \dots,\}\). Mỗi số này có thể được biểu diễn dưới dạng nhị phân như sau:

$$x^{(k)}=0. x_1^{(k)} x_2^{(k)}\dots \text{ where } x_j^{(k)} \in \{0,1\}$$

Ta có thể lập bảng các số này như sau:

$$\begin{align*} x^{(1)} &= x_1^{(1)} \quad x_2^{(1)} \quad x_3^{(1)} \quad x_4^{(1)} \quad \dots \\ x^{(2)} &= x_1^{(2)} \quad x_2^{(2)} \quad x_3^{(2)} \quad x_4^{(2)} \quad \dots \\ x^{(3)} &= x_1^{(3)} \quad x_2^{(3)} \quad x_3^{(3)} \quad x_4^{(3)} \quad \dots \\ x^{(4)} &= x_1^{(4)} \quad x_2^{(4)} \quad x_3^{(4)} \quad x_4^{(4)} \quad \dots \\ \dots \end{align*}$$

Bây giờ, ta tạo ra một số \(y=0.y_1y_2y_3\dots\) sao cho \(y_1 \ne x_1^{(1)}, y_2 \ne x_2^{(2)}, \dots\) Số \(y\) này không nằm trong tập hợp \(S=\{x^{(1)}, x^{(2)}, \dots,\}\) ban đầu vì \(y\) có ít nhất một con số khác với từng giá trị của \(x^{(j)}\). Rõ ràng ta có \(y \in \mathbb R, y \not \in S\) (vô lý) Từ đó suy ra tập số thực là không đếm được.

Phản biện 1

Thực sự là vậy! Ví dụ: \(\displaystyle \pi = 4 - \frac 4 3 + \frac 4 5 - \dots\) có thể tính xấp xỉ bằng một vòng lặp trong một chương trình máy tính. Điều này nghĩa là mọi số thực đều có một ánh xạ \(1-1\) tới một chương trình, vậy lực lượng số thực bằng lực lượng số nguyên.

Phản biện 2

Một ví dụ phản biện:

$$\begin{align*} x^{(1)} &= 0.000000\dots \\ x^{(2)} &= 0.010000\dots \\ x^{(3)} &= 0.001111\dots \\ x^{(4)} &= 0.000111\dots \\ \dots \end{align*}$$

Để dựng số \(y\) như cách của Cantor, ta lấy các phần tử đường chéo sẽ được \(0.0111\dots11\dots\), tiếp theo ở mỗi vị trí ta hoán đổi \(0\) và \(1\) sẽ có \(0.100\dots\)

Vấn đề: trong hệ thập phân thì \(0.9999\dots \) bằng \(1\). Vấn đề tương tự xảy ra trong hệ nhị phân: \(0.0111\dots\) bằng \(0.1000\dots\) và từ đó có thể thấy rằng kể cả khi \(y\) có biểu diễn khác với các số trong tập \(S\) thì \(y\) vẫn có giá trị nằm trong \(S\).

Lời kết

Vitalik kết bài với một câu bỏ ngỏ:

Bài viết này được đăng đúng vào ngày Cá Tháng Tư năm 2019.

Mặc dù bài viết này vẫn còn lỗ hổng về mặt logic (ví dụ như anh ta đã cố tình đưa ra một dãy không có thứ tự một cách chủ định), mình vẫn thấy nó quá sức thú vị và đáng để chia sẻ cho mọi người cùng suy nghĩ.