Chương 21: Vô hạn có nhiều cỡ

Câu hỏi mở đầu

Song ánh cho ta cách so sánh cỡ của hai tập mà không cần đếm. Áp dụng cho tập vô hạn thì sao? Mọi tập vô hạn có "to bằng nhau" không?

Khách sạn không bao giờ hết phòng

Hãy tưởng tượng một khách sạn có vô hạn phòng, đánh số 1, 2, 3, ..., và tối nay phòng nào cũng có khách. Một người khách mới đến. Ở một khách sạn thường, câu trả lời là "hết phòng". Ở đây, người quản lý nhờ mỗi vị khách chuyển sang phòng kế bên: khách ở phòng \(n\) sang phòng \(n + 1\). Không ai phải ra đường, không ai phải ở chung, và phòng 1 trống cho người mới.

Rồi một chiếc xe chở vô hạn khách mới đến, khách trên xe đánh số 1, 2, 3, .... Người quản lý nhờ khách ở phòng \(n\) chuyển sang phòng \(2n\). Mọi phòng lẻ trống ra, và khách thứ \(k\) trên xe vào phòng \(2k - 1\). Tình huống này thường được gọi là khách sạn Hilbert (Hilbert's hotel).

Trên: khách ở phòng \(n\) dời sang phòng \(n + 1\), phòng 1 trống. Dưới: khách ở phòng \(n\) dời sang phòng \(2n\), mọi phòng lẻ trống.

Không có gì ma thuật ở đây. Mỗi cách dời phòng là một đơn ánh từ tập các phòng vào chính nó mà không phải toàn ánh: \(n \mapsto n + 1\) bỏ sót phòng 1, \(n \mapsto 2n\) bỏ sót mọi phòng lẻ. Bài C4 của Chương 20 đã chứng minh điều này không thể xảy ra với một tập hữu hạn. Với tập vô hạn, nó xảy ra ngay ở tập đơn giản nhất.

Trực giác "toàn thể lớn hơn bộ phận" có từ rất lâu; trong bộ Cơ sở của Euclid, nó là một trong những điều được thừa nhận không cần chứng minh. Chương 4 đã thấy nó hỏng: các số chẵn chỉ là một phần của \(\mathbb{N}\), vậy mà ghép cặp một-một được với cả \(\mathbb{N}\). Không ai cố ý tạo ra những điều lạ này. Chúng buộc phải xảy ra ngay khi ta giữ hai lựa chọn đã làm: đo cỡ bằng ghép cặp (Chương 20, Mệnh đề 6) và coi một tập vô hạn là một đối tượng (Chương 19).

Vậy câu hỏi thật sự là: mọi tập vô hạn có to bằng nhau không? Trực giác nói có, vì vô hạn thì là vô hạn. Chương này cho thấy trực giác ấy sai, và sai triệt để: có vô số cỡ vô hạn khác nhau.

Xếp được thành hàng

Cỡ vô hạn quen thuộc nhất là cỡ của \(\mathbb{N}\). Một tập có cỡ ấy là một tập mà ta xếp được mọi phần tử thành một hàng \(a_0, a_1, a_2, \dots\), không lặp, sao cho mỗi phần tử đứng ở một vị trí hữu hạn nào đó. Xếp hàng như thế chính là một song ánh \(n \mapsto a_n\) từ \(\mathbb{N}\) lên tập ấy. Nếu cứ đọc tên lần lượt theo hàng, mỗi phần tử rồi sẽ được đọc tới sau hữu hạn bước.

Chữ "mỗi phần tử" là chỗ mấu chốt. Hàng "mọi số chẵn, rồi mọi số lẻ" không phải một cách xếp \(\mathbb{N}\): đọc mãi các số chẵn, ta không bao giờ tới số 1. Một hàng hợp lệ phải đi tới mọi phần tử sau hữu hạn bước. Phần lớn chương này là tìm những đường đi như thế, hoặc chứng minh rằng không có đường nào.

Hai điều giúp việc xếp hàng dễ hơn. Thứ nhất, hàng được phép lặp: nếu một hàng có lặp đi qua mọi phần tử, bỏ những lần lặp đi, ta được một hàng không lặp (Mệnh đề 2). Thứ hai, tập hữu hạn cũng tính là xếp được, bằng một hàng có điểm dừng.

Ký hiệu

Với hai tập bất kỳ, kể cả vô hạn, viết \(|A| = |B|\) khi có một song ánh từ \(A\) tới \(B\), tức khi \(A\) và \(B\) cùng số lượng. Với tập vô hạn, ký hiệu này không gán cho \(|A|\) một số tự nhiên nào; nó chỉ ghi lại quan hệ "ghép cặp được". Viết \(|A| \leq |B|\) khi có một đơn ánh từ \(A\) tới \(B\), và \(|A| < |B|\) khi có đơn ánh nhưng không có song ánh.

Một tập là đếm được (countable) nếu nó hữu hạn hoặc cùng số lượng với \(\mathbb{N}\); trong trường hợp sau, ta nói nó là vô hạn đếm được (countably infinite). Tập nào không như vậy gọi là không đếm được (uncountable).

Một tập con thực sự (proper subset) của \(B\) là một tập con của \(B\) khác chính \(B\). Như ở Chương 4, \(\mathbb{N}^* = \{1; 2; 3; \dots\}\) là tập các số tự nhiên khác 0, một tập con thực sự của \(\mathbb{N}\).

Làm bằng tay

Ví dụ 1 (\(\mathbb{Z}\) đếm được). \(\mathbb{Z}\) trông như "gấp đôi" \(\mathbb{N}\), vì có thêm các số âm. Nhưng hàng \(0, -1, 1, -2, 2, -3, 3, \dots\) đi qua mọi số nguyên. Viết thành công thức, đó là hàm \(f: \mathbb{N} \to \mathbb{Z}\) với

\[ f(n) = \begin{cases} \dfrac{n}{2} & \text{nếu } n \text{ chẵn}, \\[6pt] -\dfrac{n + 1}{2} & \text{nếu } n \text{ lẻ}. \end{cases} \]

Chẳng hạn \(f(10) = 5\) và \(f(11) = -6\). Hàm \(g: \mathbb{Z} \to \mathbb{N}\) với \(g(m) = 2m\) khi \(m \geq 0\) và \(g(m) = -2m - 1\) khi \(m < 0\) tháo ngược nó: \(g(5) = 10\), \(g(-6) = 11\). Theo Định lý 5 của Chương 20, có hàm ngược nghĩa là \(f\) là song ánh, nên \(|\mathbb{Z}| = |\mathbb{N}|\).

Ví dụ 2 (\(\mathbb{Q}\) đếm được). Các số hữu tỉ nằm dày đặc: giữa hai số hữu tỉ bất kỳ có vô số số hữu tỉ khác (Chương 10). Không có số hữu tỉ dương nào đứng "ngay sau" 0 để mở đầu hàng. Vậy mà vẫn xếp hàng được, miễn là đừng xếp theo thứ tự lớn nhỏ.

Đặt mọi phân số dương \(\frac{p}{q}\) vào một bảng vô hạn: hàng thứ \(p\) gồm các phân số có tử số \(p\), cột thứ \(q\) gồm các phân số có mẫu số \(q\). Đi dọc một hàng thì không bao giờ xuống được hàng sau. Nhưng các đường chéo \(p + q = 2\), \(p + q = 3\), \(p + q = 4\), ... đều ngắn: đường chéo \(p + q = s\) chỉ có \(s - 1\) ô. Đi lần lượt qua từng đường chéo, đổi chiều ở mỗi đường như một đường zigzag, ta tới mọi ô sau hữu hạn bước. Bỏ qua các phân số chưa tối giản (chúng lặp lại một số đã gặp), ta được hàng

\[ \frac11, \frac12, \frac21, \frac31, \frac13, \frac14, \frac23, \frac32, \frac41, \frac51, \frac15, \frac16, \frac25, \frac34, \dots \]

Số \(\frac34\) đứng thứ 14.

Đường zigzag đi qua từng đường chéo. Ô xám là phân số chưa tối giản, bị bỏ qua vì lặp lại một số đã gặp; số nhỏ ở góc ô là thứ tự trong hàng. Số \(\frac34\) đứng thứ 14.

Muốn có cả \(\mathbb{Q}\), xen các số âm vào như với \(\mathbb{Z}\): \(0, \frac11, -\frac11, \frac12, -\frac12, \frac21, -\frac21, \dots\).

Ví dụ 3 (một khoảng nhỏ và cả trục số). Hàm \(x \mapsto 2x\) là song ánh từ \((0; 1)\) lên \((0; 2)\), với hàm ngược \(y \mapsto \frac{y}{2}\): khoảng dài gấp đôi có cùng số điểm. Hơn thế, hàm

\[ f(x) = \frac{x}{1 - |x|} \]

là song ánh từ khoảng \((-1; 1)\) lên cả \(\mathbb{R}\). Hàm ngược của nó là \(g(y) = \frac{y}{1 + |y|}\), luôn cho giá trị trong \((-1; 1)\) vì \(|y| < 1 + |y|\). Thật vậy, với \(x \in (-1; 1)\) thì \(1 + |f(x)| = 1 + \frac{|x|}{1 - |x|} = \frac{1}{1 - |x|}\), nên \(g(f(x)) = \frac{x}{1 - |x|} \cdot (1 - |x|) = x\); chiều \(f(g(y)) = y\) kiểm tương tự (bài B8). Chẳng hạn \(f(0{,}5) = 1\), \(f(0{,}75) = 3\), \(f(0{,}9) = 9\): càng gần đầu mút, điểm càng bị kéo ra xa. Ghép thêm \(x \mapsto 2x - 1\) từ \((0; 1)\) lên \((-1; 1)\), ta thấy khoảng \((0; 1)\) có cùng số lượng với cả trục số.

Hàm \(x \mapsto \frac{x}{1 - |x|}\) kéo khoảng \((-1; 1)\) ra thành cả trục số: mỗi điểm của khoảng ứng với đúng một số thực, và ngược lại.

Ví dụ 4 (dựng số đường chéo). Giả sử có người đưa ra một danh sách các số trong \((0; 1)\) và khẳng định nó chứa mọi số. Sáu số đầu là

\[ x_1 = 0{,}1234567\ldots, \quad x_2 = 0{,}5555555\ldots, \quad x_3 = 0{,}3333333\ldots, \]

\[ x_4 = 0{,}2718281\ldots, \quad x_5 = 0{,}5000000\ldots, \quad x_6 = 0{,}4545454\ldots \]

Dựng một số \(y = 0{,}y_1 y_2 y_3 \ldots\) theo quy tắc: chữ số \(y_n\) là 4 nếu chữ số thứ \(n\) của \(x_n\) là 5, và là 5 trong mọi trường hợp khác. Các chữ số trên đường chéo là 1, 5, 3, 8, 0, 5, nên \(y = 0{,}545554\ldots\) Số \(y\) khác \(x_1\) ở chữ số thứ nhất, khác \(x_2\) ở chữ số thứ hai, và cứ thế, khác mọi số trong danh sách. Danh sách, dù dài vô tận, không thể đầy đủ. Cách dựng này là lập luận đường chéo (diagonal argument) của Georg Cantor.

Các chữ số trên đường chéo (ô xanh) quyết định các chữ số của \(y\) (ô cam): 4 nếu chữ số trên đường chéo là 5, còn lại là 5. Số \(y\) khác \(x_n\) ở chữ số thứ \(n\).

Ví dụ 5 (các câu hữu hạn đếm được). Với bảng chữ cái chỉ gồm hai chữ \(a\) và \(b\), xếp mọi dãy chữ hữu hạn theo độ dài, cùng độ dài thì theo thứ tự từ điển: dãy rỗng, \(a\), \(b\), \(aa\), \(ab\), \(ba\), \(bb\), \(aaa\), .... Mỗi độ dài \(k\) chỉ có \(2^k\) dãy, nên mọi dãy đều được tới sau hữu hạn bước: \(bb\) đứng thứ 7, và có \(1 + 2 + 4 + 8 = 15\) dãy dài không quá 3 chữ. Cách xếp này dùng được cho mọi bảng chữ cái hữu hạn, kể cả các chữ cái tiếng Việt có dấu cùng dấu cách và dấu câu. Vậy tập mọi câu tiếng Việt, dài bao nhiêu cũng được miễn là hữu hạn, là đếm được.

Ranh giới

Toàn thể không nhất thiết lớn hơn bộ phận. Với tập hữu hạn, một tập con thực sự luôn có ít phần tử hơn (Chương 4, bài C2). Với tập vô hạn thì không: \(\mathbb{N}\) cùng số lượng với tập con thực sự \(\mathbb{N}^*\) của nó (khách sạn), và với tập các số chẵn. Điều vẫn đúng là một tập con không bao giờ nhiều hơn tập chứa nó: đưa mỗi phần tử về chính nó là một đơn ánh, nên \(A \subseteq B\) kéo theo \(|A| \leq |B|\).

Dày đặc không có nghĩa là nhiều hơn. \(\mathbb{Q}\) dày đặc trên trục số mà vẫn cùng số lượng với \(\mathbb{N}\), một tập mà giữa hai phần tử liên tiếp không có gì. Dày đặc là chuyện của thứ tự; cỡ là chuyện của ghép cặp, và hàng zigzag của Ví dụ 2 nhảy qua lại trên trục số, không hề tôn trọng thứ tự lớn nhỏ.

Lập luận đường chéo không chứng minh được \(\mathbb{Q}\) không đếm được. Áp dụng cách dựng của Ví dụ 4 cho một danh sách mọi số hữu tỉ trong \((0; 1)\), ta vẫn được một số \(y\) không có trong danh sách. Không có mâu thuẫn nào: \(y\) đơn giản là một số vô tỉ. Lập luận chỉ phá được một danh sách khi số \(y\) buộc phải thuộc tập đang được liệt kê, và điều ấy đúng với \((0; 1)\) chứ không đúng với \(\mathbb{Q}\) (bài C2).

Vì sao chỉ dùng chữ số 4 và 5. Một số có thể có hai cách viết thập phân: \(0{,}4999\ldots = 0{,}5000\ldots\), như \(0{,}999\ldots = 1\) ở Chương 11. Giả sử quy tắc là "cộng 1 vào chữ số trên đường chéo, 9 thành 0", danh sách mở đầu bằng \(x_1 = 0{,}4999\ldots\), và mọi \(x_n\) sau đó có chữ số thứ \(n\) là 9. Khi đó \(y = 0{,}5000\ldots\), khác \(x_1\) ở mọi chữ số mà vẫn bằng \(x_1\). Chỉ dùng chữ số 4 và 5 thì chuyện này không xảy ra, như chứng minh của Định lý 4 cho thấy.

"Mô tả được" phải hiểu cẩn thận. Mệnh đề 8 dưới đây nói hầu hết số thực không được câu nào chỉ ra riêng. Nhưng chữ "mô tả" phải gắn với một ngôn ngữ cố định có luật đọc chính xác. Nếu dùng nó tùy tiện, ta gặp lại kiểu nghịch lý của Chương 14 và Chương 19: cụm "số tự nhiên nhỏ nhất không thể mô tả bằng một câu dưới hai mươi chữ" chỉ có mười sáu chữ, vậy mà mô tả đúng số ấy.

Một câu hỏi mà tiên đề không trả lời. Có tập nào có cỡ nằm giữa \(\mathbb{N}\) và \(\mathbb{R}\) không? Cantor đoán là không; điều phỏng đoán ấy gọi là giả thuyết continuum (continuum hypothesis). Kurt Gödel (1940) và Paul Cohen (1963) chứng minh rằng, nếu hệ tiên đề Zermelo-Fraenkel (Chương 19) không mâu thuẫn, thì từ nó không thể chứng minh, cũng không thể bác bỏ, giả thuyết này. Một câu hỏi phát biểu rõ ràng vẫn có thể nằm ngoài tầm với của những tiên đề ta đã chọn.

Phát biểu chặt chẽ

Định nghĩa 1. Cho hai tập \(A\), \(B\). Viết \(|A| = |B|\) nếu có một song ánh từ \(A\) tới \(B\); \(|A| \leq |B|\) nếu có một đơn ánh từ \(A\) tới \(B\); \(|A| < |B|\) nếu \(|A| \leq |B|\) nhưng không có \(|A| = |B|\). Tập \(A\) là đếm được nếu nó hữu hạn hoặc \(|A| = |\mathbb{N}|\), và không đếm được trong trường hợp ngược lại.

Mệnh đề 2 (hàng có lặp). Cho \(A\) khác rỗng. Nếu có một toàn ánh \(h: \mathbb{N} \to A\) thì \(A\) đếm được.

Chứng minh. Nếu \(A\) hữu hạn thì xong. Giả sử \(A\) vô hạn. Đi dọc hàng \(h(0), h(1), h(2), \dots\) và chỉ giữ lại mỗi giá trị ở lần xuất hiện đầu tiên của nó. Mọi phần tử của \(A\) đều xuất hiện, nên đều được giữ lại đúng một lần; vì \(A\) vô hạn, số giá trị được giữ lại là vô hạn. Gọi chúng theo thứ tự giữ lại là \(a_0, a_1, a_2, \dots\). Mỗi \(a \in A\) xuất hiện lần đầu ở một vị trí hữu hạn \(m\) nào đó, nên \(a = a_k\) với một \(k \leq m\); hai chỉ số khác nhau cho hai giá trị khác nhau. Vậy \(k \mapsto a_k\) là một song ánh từ \(\mathbb{N}\) lên \(A\). \(\square\)

Định lý 3. \(\mathbb{Z}\) và \(\mathbb{Q}\) đếm được.

Chứng minh. Với \(\mathbb{Z}\), hàm \(f\) của Ví dụ 1 có hàm ngược \(g\), nên là song ánh (Định lý 5 của Chương 20). Với \(\mathbb{Q}\), đi qua các cặp \((p; q) \in \mathbb{N}^* \times \mathbb{N}^*\) theo từng đường chéo \(p + q = 2, 3, 4, \dots\). Đường chéo \(p + q = s\) có \(s - 1\) ô, nên ô \((p; q)\) được tới sau không quá \(1 + 2 + \dots + (p + q - 1)\) bước, một số hữu hạn. Từ các ô theo thứ tự ấy, lập hàng \(0, \frac{p_1}{q_1}, -\frac{p_1}{q_1}, \frac{p_2}{q_2}, -\frac{p_2}{q_2}, \dots\). Mỗi số hữu tỉ là 0 hoặc có dạng \(\pm \frac{p}{q}\) với \(p, q \in \mathbb{N}^*\), nên xuất hiện trong hàng. Theo Mệnh đề 2, \(\mathbb{Q}\) đếm được. \(\square\)

Định lý 4 (Cantor). Khoảng \((0; 1)\) không đếm được.

Chứng minh. Khoảng \((0; 1)\) vô hạn, nên ta chỉ cần chứng minh rằng không có hàng \(x_1, x_2, x_3, \dots\) nào chứa mọi số của nó. Giả sử có. Mỗi \(x_n\) có ít nhất một cách viết thập phân (Chương 11); chọn một cách, và gọi chữ số thứ \(n\) của nó là \(d_n\). Đặt \(y = 0{,}y_1 y_2 y_3 \ldots\) với \(y_n = 4\) nếu \(d_n = 5\) và \(y_n = 5\) nếu \(d_n \neq 5\). Vì \(0{,}444\ldots \leq y \leq 0{,}555\ldots\), tức \(\frac49 \leq y \leq \frac59\), số \(y\) thuộc \((0; 1)\).

Cố định \(n\). Cách viết của \(y\) và của \(x_n\) khác nhau ở vị trí \(n\); gọi \(k \leq n\) là vị trí đầu tiên chúng khác nhau. Viết

\[ y = P + 10^{-k}(c + t), \qquad x_n = P + 10^{-k}(c' + t'), \]

trong đó \(P\) là giá trị của \(k - 1\) chữ số chung, \(c \neq c'\) là hai chữ số thứ \(k\), còn \(t\), \(t'\) là giá trị của hai phần đuôi sau vị trí \(k\), đọc như những số \(0{,}\ldots\). Mọi phần đuôi nằm trong \([0; 1]\), vì \(0{,}999\ldots = 1\); riêng đuôi của \(y\) chỉ gồm chữ số 4 và 5, nên \(\frac49 \leq t \leq \frac59\). Do đó \(|t - t'| \leq \frac59 < 1 \leq |c - c'|\), và

\[ y - x_n = 10^{-k}\big((c - c') + (t - t')\big) \neq 0. \]

Vậy \(y\) khác mọi \(x_n\), trái với giả thiết rằng hàng chứa mọi số của \((0; 1)\). \(\square\)

Hệ quả 5. \(\mathbb{R}\) không đếm được.

Chứng minh. Theo Ví dụ 3, \(\varphi(x) = f(2x - 1)\) là một song ánh từ \((0; 1)\) lên \(\mathbb{R}\) (hợp của hai song ánh là song ánh, bài C1 của Chương 20). Nếu có song ánh \(h: \mathbb{N} \to \mathbb{R}\), thì \(n \mapsto \varphi^{-1}(h(n))\) là một song ánh từ \(\mathbb{N}\) lên \((0; 1)\), trái với Định lý 4. \(\square\)

Định lý 6 (Cantor). Với mọi tập \(A\), không có toàn ánh nào từ \(A\) lên tập lũy thừa \(\mathcal{P}(A)\). Vì \(a \mapsto \{a\}\) là một đơn ánh, ta có \(|A| < |\mathcal{P}(A)|\).

Chứng minh. Cho một hàm \(F: A \to \mathcal{P}(A)\). Đặt

\[ D = \{a \in A \mid a \notin F(a)\}. \]

Giả sử \(D = F(d)\) với một \(d \in A\). Theo định nghĩa của \(D\), \(d \in D \Leftrightarrow d \notin F(d)\), tức \(d \in D \Leftrightarrow d \notin D\): mâu thuẫn. Vậy \(D\) không phải giá trị của \(F\) tại phần tử nào, và \(F\) không là toàn ánh. \(\square\)

Đây chính là lập luận Russell ở Chương 19, và cũng là một đường chéo: coi \(F\) như một bảng mà hàng \(a\) ghi, với mỗi \(b\), \(b\) có thuộc \(F(a)\) hay không; tập \(D\) được dựng bằng cách đảo từng ô trên đường chéo.

Hệ quả 7. Không có cỡ vô hạn lớn nhất: \(|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|\), \(|\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))|\), và cứ thế mãi.

Mệnh đề 8 (câu hữu hạn). Với một bảng chữ cái hữu hạn, tập mọi dãy chữ hữu hạn là đếm được. Do đó, trong một ngôn ngữ cố định, các số thực được một câu nào đó chỉ ra riêng tạo thành một tập đếm được, còn các số thực còn lại tạo thành một tập không đếm được.

Chứng minh. Nếu bảng chữ cái có \(m\) chữ, mỗi độ dài \(k\) có \(m^k\) dãy, một số hữu hạn; xếp theo độ dài như Ví dụ 5, mỗi dãy được tới sau hữu hạn bước. Đi dọc hàng các câu ấy và ghi lại số thực mà câu chỉ ra, nếu có; hàng thu được đi qua mọi số được chỉ ra, nên tập các số ấy đếm được (Mệnh đề 2, hoặc hữu hạn). Nếu các số còn lại cũng tạo thành một tập đếm được, thì \(\mathbb{R}\) là hợp của hai tập đếm được, nên đếm được (bài C1), trái với Hệ quả 5. \(\square\)

Sợi chỉ

• S5. Rời rạc và liên tục. Ở tầng sâu nhất, rời rạc và liên tục khác nhau về cỡ. \(\mathbb{N}\), \(\mathbb{Z}\) và cả \(\mathbb{Q}\), dù dày đặc, đều đếm được; \(\mathbb{R}\), tập đã lấp các lỗ hổng ở Chương 11, thì không. Những lỗ mà \(\mathbb{Q}\) để trống nhiều hơn hẳn những điểm nó có.
• S2. Thông tin và khả nghịch. Song ánh, không mất và không sót, là thước đo cỡ duy nhất. Lập luận đường chéo và định lý Cantor nói rằng mọi hàm từ \(\mathbb{N}\) vào \((0; 1)\), từ \(A\) vào \(\mathcal{P}(A)\), đều bỏ sót. Mọi câu hữu hạn gộp lại cũng chỉ chỉ ra được một phần đếm được của \(\mathbb{R}\).
• S6. Biểu diễn khác nhau của cùng một cấu trúc. Cùng một tập có nhiều cách xếp hàng, và chỉ một số cách đi tới được mọi phần tử: \(\mathbb{Q}\) theo từng hàng ngang thì không, theo zigzag thì có. Định lý Cantor và lập luận Russell là một lập luận; một tập con của \(\mathbb{N}\) là một dãy vô hạn chữ số 0 và 1.

Tóm tắt

• Hai tập, kể cả vô hạn, cùng cỡ khi có song ánh giữa chúng; với tập vô hạn, một tập con thực sự có thể cùng cỡ với toàn thể (khách sạn Hilbert, số chẵn và \(\mathbb{N}\)).
• Đếm được nghĩa là xếp được mọi phần tử thành một hàng mà mỗi phần tử đứng ở một vị trí hữu hạn; hàng được phép lặp.
• \(\mathbb{Z}\) và \(\mathbb{Q}\) đếm được; với \(\mathbb{Q}\), đi theo các đường chéo zigzag của bảng phân số; \(\mathbb{Q}\) dày đặc nhưng không nhiều hơn \(\mathbb{N}\).
• Khoảng \((0; 1)\) cùng cỡ với cả \(\mathbb{R}\), và không đếm được: lập luận đường chéo dựng từ mọi danh sách một số không có trong danh sách.
• Định lý Cantor: không có toàn ánh từ \(A\) lên \(\mathcal{P}(A)\), nên không có cỡ vô hạn lớn nhất; đó cũng là lập luận Russell.
• Các câu hữu hạn trong một ngôn ngữ chỉ đếm được, nên hầu hết số thực không được câu nào chỉ ra riêng; chữ "mô tả" phải được hiểu chính xác.
• Có hay không một cỡ nằm giữa \(\mathbb{N}\) và \(\mathbb{R}\) là câu hỏi mà hệ tiên đề Zermelo-Fraenkel không quyết định được.

Bài tập

A. Tư duy

A1. Khách sạn Hilbert đang đầy. Vô hạn chiếc xe đến, mỗi xe chở vô hạn khách. Có xếp được mọi người vào phòng không? Mô tả một cách làm.

Lời giải

Được. Trước hết dời khách cũ từ phòng \(n\) sang phòng \(2n\), mọi phòng lẻ trống ra. Khách mới được gọi tên bằng một cặp \((i; j)\): khách thứ \(j\) trên xe thứ \(i\). Xếp mọi cặp thành một hàng theo đường zigzag như bảng phân số ở Ví dụ 2 (không bỏ ô nào), rồi cho cặp thứ \(k\) trong hàng vào phòng lẻ thứ \(k\), tức phòng \(2k - 1\). Mỗi khách mới có đúng một phòng, vì mỗi cặp đứng ở đúng một vị trí hữu hạn trong hàng; không ai phải chờ vô hạn.

A2. Một người lập luận: "Giữa hai số hữu tỉ luôn có vô số số hữu tỉ, còn giữa hai số tự nhiên liên tiếp thì không có gì. Vậy \(\mathbb{Q}\) phải nhiều hơn \(\mathbb{N}\)." Lập luận này sai ở đâu?

Lời giải

Nó lẫn thứ tự với cỡ. "Dày đặc" nói về cách các số xếp trên trục số, tức về quan hệ thứ tự \(<\); cỡ thì chỉ đo bằng ghép cặp, và một song ánh không cần tôn trọng thứ tự. Hàng zigzag của Ví dụ 2 ghép \(\mathbb{Q}\) với \(\mathbb{N}\) bằng cách nhảy qua lại trên trục số. Trực giác "nhiều chỗ chen hơn thì nhiều số hơn" là trực giác của tập hữu hạn, như trực giác "toàn thể lớn hơn bộ phận".

A3. Người ta nói: "Hầu hết số thực không thể mô tả được." Câu này đúng theo nghĩa nào? Có thể đưa ra một ví dụ cụ thể về một số như thế không?

Lời giải

Đúng theo nghĩa của Mệnh đề 8: cố định một ngôn ngữ với bảng chữ cái hữu hạn và luật đọc chính xác, thì các câu chỉ đếm được, mỗi câu chỉ ra nhiều nhất một số, nên các số được chỉ ra tạo thành một tập đếm được; phần còn lại của \(\mathbb{R}\) không đếm được. Nhưng không thể đưa ra một ví dụ cụ thể: nêu được một số như thế bằng một câu trong ngôn ngữ ấy tức là đã mô tả nó. Ta biết những số ấy tồn tại, và nhiều hơn hẳn phần còn lại, mà không chỉ ra được số nào. Đó là một chứng minh không xây dựng theo nghĩa của Chương 17.

B. Tính toán

B1. Với song ánh \(f: \mathbb{N} \to \mathbb{Z}\) của Ví dụ 1, tính \(f(0)\) tới \(f(7)\), \(f(100)\) và \(f(101)\). Tìm \(n\) để \(f(n) = -50\), và \(n\) để \(f(n) = 50\).

Lời giải

\(f(0), \dots, f(7)\) là \(0, -1, 1, -2, 2, -3, 3, -4\). \(f(100) = 50\) và \(f(101) = -\frac{102}{2} = -51\). Dùng hàm ngược \(g\): \(f(n) = -50\) khi \(n = g(-50) = 99\); \(f(n) = 50\) khi \(n = g(50) = 100\).

B2. Viết một song ánh, kèm hàm ngược: (a) từ \(\mathbb{N}\) lên \(\mathbb{N}^*\); (b) từ \(\mathbb{N}\) lên tập các bội tự nhiên của 3; (c) từ \((0; 1)\) lên \((3; 5)\); (d) từ tập các số tự nhiên chẵn lên tập các số tự nhiên lẻ.

Lời giải

(a) \(n \mapsto n + 1\), ngược \(m \mapsto m - 1\). (b) \(n \mapsto 3n\), ngược \(m \mapsto \frac{m}{3}\). (c) \(x \mapsto 3 + 2x\), ngược \(y \mapsto \frac{y - 3}{2}\). (d) \(m \mapsto m + 1\), ngược \(k \mapsto k - 1\). Mỗi trường hợp, kiểm tra hai hàm tháo ngược nhau là đủ (Định lý 5 của Chương 20).

B3. Viết tiếp hàng các số hữu tỉ dương ở Ví dụ 2 từ vị trí 15 tới vị trí 21. Các số \(\frac52\) và \(\frac17\) đứng thứ mấy?

Lời giải

Đường chéo \(p + q = 7\) đi theo chiều tử số tăng: sau \(\frac16\), \(\frac25\), \(\frac34\) (thứ 12, 13, 14) là \(\frac43\), \(\frac52\), \(\frac61\) (thứ 15, 16, 17). Đường chéo \(p + q = 8\) đi theo chiều tử số giảm, bỏ \(\frac62\), \(\frac44\), \(\frac26\): \(\frac71\), \(\frac53\), \(\frac35\), \(\frac17\) (thứ 18, 19, 20, 21). Vậy \(\frac52\) đứng thứ 16 và \(\frac17\) đứng thứ 21.

B4. Đánh số các ô \((p; q)\) của \(\mathbb{N} \times \mathbb{N}\) bắt đầu từ 0, đi theo từng đường chéo \(p + q = 0, 1, 2, \dots\), trên mỗi đường chéo theo chiều \(q\) tăng. Giải thích vì sao ô \((p; q)\) mang số \(\frac{(p + q)(p + q + 1)}{2} + q\). Ô \((2; 3)\) mang số mấy? Ô nào mang số 20?

Lời giải

Trước đường chéo \(p + q = s\) có các đường chéo \(0, 1, \dots, s - 1\), với \(1 + 2 + \dots + s = \frac{s(s + 1)}{2}\) ô (Chương 18). Trên đường chéo \(s\), ô \((p; q)\) đứng sau \(q\) ô có \(q\) nhỏ hơn. Vậy số của nó là \(\frac{s(s + 1)}{2} + q\) với \(s = p + q\).

Ô \((2; 3)\): \(s = 5\), số là \(15 + 3 = 18\). Số 20: vì \(15 \leq 20 < 21\), ô nằm trên đường chéo \(s = 5\) với \(q = 20 - 15 = 5\), nên là ô \((0; 5)\).

B5. Một danh sách các số trong \((0; 1)\) mở đầu bằng \(x_1 = 0{,}5000000\ldots\), \(x_2 = 0{,}6543210\ldots\), \(x_3 = 0{,}1111111\ldots\), \(x_4 = 0{,}1415926\ldots\), \(x_5 = 0{,}9876543\ldots\), \(x_6 = 0{,}3030303\ldots\). Dựng sáu chữ số đầu của số \(y\) theo quy tắc ở Ví dụ 4.

Lời giải

Các chữ số trên đường chéo: chữ số thứ nhất của \(x_1\) là 5, thứ hai của \(x_2\) là 5, thứ ba của \(x_3\) là 1, thứ tư của \(x_4\) là 5, thứ năm của \(x_5\) là 5, thứ sáu của \(x_6\) là 0. Quy tắc cho \(y = 0{,}445445\ldots\)

B6. Với các dãy chữ trên bảng chữ cái \(\{a; b\}\) xếp như Ví dụ 5 (dãy rỗng đứng thứ 1): (a) dãy \(abb\) đứng thứ mấy? (b) Có bao nhiêu dãy dài không quá 5 chữ? (c) Dãy nào đứng thứ 20?

Lời giải

(a) Trước các dãy dài 3 có \(1 + 2 + 4 = 7\) dãy. Trong các dãy dài 3 theo thứ tự từ điển, \(aaa\), \(aab\), \(aba\), \(abb\), dãy \(abb\) đứng thứ tư. Vậy nó đứng thứ 11. (b) \(1 + 2 + 4 + 8 + 16 + 32 = 63 = 2^6 - 1\). (c) Có 15 dãy dài không quá 3, nên dãy thứ 20 là dãy dài 4 đứng thứ năm: \(aaaa\), \(aaab\), \(aaba\), \(aabb\), \(abaa\). Đó là \(abaa\).

B7. Cho \(A = \{1; 2; 3\}\) và \(F: A \to \mathcal{P}(A)\) với \(F(1) = \{1; 2\}\), \(F(2) = \varnothing\), \(F(3) = \{1; 3\}\). Tìm tập \(D\) trong chứng minh Định lý 6 và kiểm tra rằng \(D\) không phải giá trị của \(F\).

Lời giải

\(1 \in F(1)\) nên \(1 \notin D\); \(2 \notin F(2) = \varnothing\) nên \(2 \in D\); \(3 \in F(3)\) nên \(3 \notin D\). Vậy \(D = \{2\}\), khác cả ba tập \(\{1; 2\}\), \(\varnothing\), \(\{1; 3\}\). Ở đây còn thấy ngay bằng cách đếm: \(\mathcal{P}(A)\) có \(2^3 = 8\) phần tử, mà \(F\) chỉ đạt được nhiều nhất 3.

B8. Với \(f(x) = \frac{x}{1 - |x|}\) trên \((-1; 1)\) và \(g(y) = \frac{y}{1 + |y|}\) ở Ví dụ 3: (a) tính \(f(0{,}5)\), \(f(-0{,}8)\), \(f(0{,}99)\); (b) tìm \(x\) để \(f(x) = 4\) và \(x\) để \(f(x) = -\frac13\); (c) kiểm tra \(f(g(y)) = y\).

Lời giải

(a) \(f(0{,}5) = \frac{0{,}5}{0{,}5} = 1\); \(f(-0{,}8) = \frac{-0{,}8}{0{,}2} = -4\); \(f(0{,}99) = \frac{0{,}99}{0{,}01} = 99\).

(b) \(x = g(4) = \frac45 = 0{,}8\); \(x = g(-\frac13) = \frac{-1/3}{4/3} = -\frac14\).

(c) Với \(y \in \mathbb{R}\), \(|g(y)| = \frac{|y|}{1 + |y|}\), nên \(1 - |g(y)| = \frac{1}{1 + |y|}\) và \(f(g(y)) = \frac{y}{1 + |y|} \cdot (1 + |y|) = y\).

B9. Khách sạn Hilbert đang đầy thì có hai xe, mỗi xe vô hạn khách. Người quản lý dời khách cũ từ phòng \(n\) sang phòng \(3n\), cho khách thứ \(k\) của xe thứ nhất vào phòng \(3k - 2\), khách thứ \(k\) của xe thứ hai vào phòng \(3k - 1\). Khách cũ ở phòng 5, khách thứ 5 của mỗi xe vào phòng nào? Vì sao không phòng nào có hai khách?

Lời giải

Phòng 15, 13 và 14. Khách cũ vào các phòng chia hết cho 3, xe thứ nhất vào các phòng chia cho 3 dư 1, xe thứ hai vào các phòng chia cho 3 dư 2. Ba nhóm phòng rời nhau và phủ kín mọi phòng (chia có dư, Chương 6), và trong mỗi nhóm, người khác nhau vào phòng khác nhau.

C. Phản ví dụ và chứng minh

C1. Chứng minh rằng hợp của hai tập đếm được là đếm được. Suy ra tập các số vô tỉ không đếm được.

Lời giải

Cho \(A\), \(B\) đếm được; nếu một trong hai rỗng thì xong. Nếu không, mỗi tập có một hàng (có thể lặp) đi qua mọi phần tử của nó: với tập hữu hạn, cứ lặp lại phần tử cuối mãi. Gọi hai hàng là \(a_0, a_1, \dots\) và \(b_0, b_1, \dots\). Hàng xen kẽ \(a_0, b_0, a_1, b_1, a_2, b_2, \dots\) đi qua mọi phần tử của \(A \cup B\), nên theo Mệnh đề 2, \(A \cup B\) đếm được. \(\square\)

Nếu tập các số vô tỉ đếm được, thì \(\mathbb{R}\), hợp của nó với \(\mathbb{Q}\), cũng đếm được, trái với Hệ quả 5. Vậy số vô tỉ "nhiều hơn hẳn" số hữu tỉ, dù ta quen gặp số hữu tỉ hơn.

C2. Một bạn lập luận: "Liệt kê mọi số hữu tỉ trong \((0; 1)\) thành \(x_1, x_2, \dots\), rồi dựng \(y\) bằng đường chéo như Ví dụ 4. Số \(y\) không có trong danh sách, vậy các số hữu tỉ trong \((0; 1)\) không đếm được." Chỉ ra chỗ sai. Lập luận ấy thật ra cho biết gì?

Lời giải

Mâu thuẫn chỉ xuất hiện nếu \(y\) buộc phải có trong danh sách, tức nếu \(y\) là số hữu tỉ. Không có gì bảo đảm điều ấy: \(y\) thuộc \((0; 1)\), nhưng có thể vô tỉ. Theo Định lý 3, các số hữu tỉ trong \((0; 1)\) xếp hàng được, nên với một danh sách đầy đủ của chúng, \(y\) khác mọi số hữu tỉ trong \((0; 1)\) mà vẫn nằm trong \((0; 1)\): \(y\) phải là số vô tỉ. Lập luận đường chéo, áp vào một danh sách mọi số hữu tỉ, là một cách dựng số vô tỉ.

C3. Chứng minh rằng mọi tập con vô hạn \(S\) của \(\mathbb{N}\) đều đếm được.

Lời giải

Dùng nguyên lý sắp thứ tự tốt (Chương 18). Đặt \(s_0\) là số nhỏ nhất của \(S\), và \(s_{k+1}\) là số nhỏ nhất của \(S \setminus \{s_0; \dots; s_k\}\); tập này khác rỗng vì \(S\) vô hạn. Dãy \(s_0 < s_1 < s_2 < \dots\) tăng hẳn, các số khác nhau. Cho \(m \in S\). Không thể mọi \(s_k\) đều nhỏ hơn \(m\), vì chỉ có hữu hạn số tự nhiên nhỏ hơn \(m\). Gọi \(k\) là chỉ số nhỏ nhất mà \(s_k \geq m\). Các số \(s_0, \dots, s_{k-1}\) đều nhỏ hơn \(m\), nên \(m\) thuộc \(S \setminus \{s_0; \dots; s_{k-1}\}\), và vì \(s_k\) là số nhỏ nhất của tập ấy, \(s_k \leq m\). Vậy \(s_k = m\). Do đó \(k \mapsto s_k\) là song ánh từ \(\mathbb{N}\) lên \(S\). \(\square\)

C4. Chứng minh bằng đường chéo rằng tập mọi dãy vô hạn \(e_0 e_1 e_2 \ldots\) gồm các chữ số 0 và 1 không đếm được. Giải thích vì sao tập ấy cùng số lượng với \(\mathcal{P}(\mathbb{N})\).

Lời giải

Giả sử các dãy được xếp thành hàng \(e^{(0)}, e^{(1)}, e^{(2)}, \dots\). Dựng dãy \(u\) với \(u_n = 1 - e^{(n)}_n\): nó khác dãy thứ \(n\) ở vị trí \(n\), nên không có trong hàng. Ở đây không có vấn đề hai cách viết như với số thập phân, vì hai dãy khác nhau ở một vị trí là hai đối tượng khác nhau. \(\square\)

Ghép mỗi tập con \(S \subseteq \mathbb{N}\) với dãy có \(e_n = 1\) khi \(n \in S\) và \(e_n = 0\) khi \(n \notin S\): đây là một song ánh, như ghép tập con với dãy câu trả lời có hoặc không ở Chương 19. Vậy \(|\mathcal{P}(\mathbb{N})|\) bằng cỡ của tập các dãy 0 và 1, và lập luận trên chính là Định lý 6 với \(A = \mathbb{N}\).

Câu hỏi để ngỏ

Trong nghĩa tập hợp, một hàm là một bảng khổng lồ các cặp. Nhưng trong đời sống, ta gặp hàm như một quy luật biến đổi: nhiệt độ theo giờ, tiền lãi theo năm, quãng đường theo thời gian. Nhìn hàm như một quy luật, một cỗ máy, thì thấy thêm được gì?