Chung qui chỉ tại Cantor (3)

Tôi thấy, nhưng tôi không tin.

[Trích một bức thư Cantor gửi Dedekind năm 1878]

Trở lại với hành trình lịch sử của ta: trong các thập niên cuối cùng cùng của thế kỷ 19, nhà toán học vĩ đại Georg Cantor ( Georg Ferdinand Ludwig Philipp Cantor, 1845-1918) đề ra một trong những tư tưởng táo bạo nhất trong lịch sử toán học, khuấy đảo toàn bộ thế giới toán học lúc bấy giờ, làm cho các nhà toán học xuất sắc nhất thế giới thời kỳ đó như Henri Poincaré (1854-1912) và David Hilbert (1862-1943) phải nhảy vào "tham chiến". Cá nhân tôi có cảm tình đặc biệt với Cantor, và cho rằng ông là nhà toán học có tư tưởng độc đáo nhất mọi thời đại. Chữ độc đáo không đủ để diễn tả điều tôi muốn nói về Cantor. Tiếng Anh họ dùng chữ original, mang nghĩa là nguyên gốc, độc đáo, đầu tiên, …

Lý thuyết tập hợp của Cantor không chỉ làm lung lay nền tảng toán học, đặt ra các vấn đề mấu chốt của triết học và logic, là tiền thân của lý thuyết tập hợp hiện đại, mà còn mang một trong những tư tưởng tiên phong của lý thuyết tính toán hiện đại. Sinh viên học máy tính nên biết và đọc về lý thuyết Cantor.

Lý thuyết tập hợp Cantor có hai đối tượng chính: các tập hợp, và lực lượng (cardinality) của các tập hợp. Tập {a,b,c} có lực lượng là 3. Ta dùng |S| để chỉ lực lượng của tập S. Có tất cả 2³=8 tập con của tập {a,b,c}. Nói chung, nếu S là tập hữu hạn thì có tất cả 2^|S| tập con của tập S. Ta dùng 2 ^S để chỉ tập tất cả các tập con của S. Nếu S hữu hạn, thì rõ ràng |2^S| = 2^|S| > |S|.

Dĩ nhiên những điều này người ta đã biết từ lâu. Cantor bắt đầu lý thuyết của ông bằng một câu hỏi cực kỳ khó chịu: thế nếu S là tập vô hạn thì thế nào? Quan hệ |S| < |2^S| có còn đúng nữa không? Thế nào là lực lượng của tập vô hạn?

Hai tập {a,b,c} và {x,y,z} có lực lượng bằng nhau. Điều này có thể hiểu theo hai cách: (1) đếm các phần tử trong từng tập, và cho kết quả là 3. Thế là chúng bằng nhau. Nhưng đối với Cantor, lý do chúng bằng nhau sâu sắc hơn nhiều. Chúng có lực lượng bằng nhau là vì ta có thể ghép cặp một-một giữa chúng: (a,y), (b,x), (c,z). Dĩ nhiên có nhiều song ánh ( bijection - hoặc ánh xạ một-một) giữa hai tập này (3! = 6), nhưng miễn có một song ánh là chúng bằng nhau. Theo dòng lý luận này, nếu có một đơn ánh (injection) từ tập A vào tập B thì |A|≤|B|. Ví dụ: từ {a,b} vào {x,y,z} thì có đơn ánh {(a,z),(b,x)}, cho nên |{a,b|}≤|{x,y,z}|. Nếu có đơn ánh từ A vào B, nhưng không có song ánh từ A vào B, thì |A|<|B|.

Để làm ví dụ, ta thử xét các tập hợp sau: N là tập các số tự nhiên, E là tập các số tự nhiên chẵn, và R là tập các số thực. Dễ thấy |E|≤|N|≤|R|. Về mặt trực quan, ta có thể nghĩ rằng tập E bằng khoảng một nửa tập N, nhưng thực ra |N|=|E| vì ta có song ánh f: N --> E định nghĩa bởi f(x) = 2x. Ví dụ này minh họa sự tinh tế khi ta xét các tập vô hạn.

Với căn bản như trên, ta có thể chứng minh |S|< |2^S | bằng một lý luận đơn giản nhưng có uy lực cực kỳ gọi là lý luận đường chéo (diagonal argument). Lý luận này cũng là nền tảng của các kết quả nổi tiếng của Gödel và Turing mà ta sẽ đề cập sau. Đại khái, để chứng minh |S|< |2^S| (dù S là vô hạn) ta có thể làm như sau:

• Dễ thấy |S|≤|2^S| (bạn nên tự tìm vài đơn ánh chứng minh điều này).
• Giả sử |S|=|2^S|, nghĩa là có một song ánh f: S --> 2^S. Gọi T là tập tất cả các phần tử x thuộc S sao cho x không thuộc f(x). Gọi b là phần tử của S mà f(b) = T. Bây giờ ta thử hỏi: b có nằm trong T hay không? Nếu b thuộc T thì, theo định nghĩa của T, b không thuộc f(b=T), vô lý. Nếu b không thuộc T, thì cũng theo định nghĩa của T, b thuộc f(b)=T.
• Tóm lại, |S|< |2^S|.

Nhà toán học nổi tiếng Paul Erdos thường ví von rằng một chứng minh tuyệt đẹp như vậy phải là một chứng minh trong quyển sách của thượng đế (xem "Proofs from the book"). Không biết các bạn thế nào chứ lần đầu tiên tôi thấy chứng minh này, tôi cảm thấy ná thở vì cái đẹp! Sau này tôi mới khám phá ra rằng lúc đó, dù hiểu về mặt kỹ thuật và cảm nhận được một ít cái đẹp của ý tưởng này, tôi thật sự chưa hiểu vấn đề!

Bài tập 1 : chứng minh rằng |N|<|R|.

Ta sẽ còn gặp lại lý luận đường chéo vài lần trên hành trình xuôi dòng lịch sử này.