2. Georg Cantor (1845–1918)
"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 thập niên cuối 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 (GS. Ngô Quang Hưng) có cảm tình đặc biệt với Cantor, và cho rằng ông là một trong vài 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 khoa học máy tính nên biết và tìm đọ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 \left \{ a,b,c \right \} 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^3 = 8 tập con của tập \left \{ a,b,c \right \}. 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 \left \{ a,b,c \right \} và \left \{ x,y,z \right \} có lực lượng bằng nhau. Điều này có thể hiểu theo hai cách:
- Đế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 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 song ánh), 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ừ \left\{a,b\right\} vào \left \{ x,y,z \right \} thì có đơn ánh \left\{(a, z), (b, x)\right \}, cho nên \left |\left \{a,b \right \} \right| \leq \left |\left \{x,y,z \right \} \right|. 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| \leq |N| \leq |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ập 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 Godel 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| = |2S|, 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 sách của Thượng đế (xem “Proofs from the book” [3]). Không biết các bạn thế nào chứ lần đầu tiên thấy chứng minh này, tôi cảm thấy ná thở vì vẻ đẹp của nó! 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 đề! Ta sẽ còn gặp lại lập luận đường chéo vài lần trên hành trình xuôi dòng lịch sử.
Bài tập 1. Chứng minh rằng |N| < |R|.
Ta đã chứng minh |S| < |2^S| với mọi tập S bằng lập luận đường chéo. Cantor không dừng lại ở đó, ông xét một chuỗi vô hạn các lực lượng của các tập vô hạn được tạo ra theo cách này: |N|,|2^N|,|2^{2^N}|,… và ông dùng \aleph_0, \aleph_1, \aleph_2 … (đọc là Aleph không, Aleph một, Aleph hai…) để chỉ lực lượng của các tập này. Như vậy, \aleph_0 là lực lượng của N, câu hỏi tự nhiên là: thế lực lượng của R nằm đâu trong chuỗi này? Cantor tin rằng |R| = \aleph_1 nhưng ông không chứng minh được điều này. Đây là một trong những bài toán nổi tiếng nhất của thế kỷ 20, thường được gọi là giả thuyết công-ti-num, hay giả thuyết liên tục (continuum hypothesis).
Giả thuyết liên tục, các va chạm với Leopod Kronecker (1823 – 1891) (người không chấp nhận lý thuyết tập hợp này), cùng với vài nghịch lý đau đầu trong lý thuyết của mình (xem dưới đây) làm Cantor bị suy nhược thần kinh liên tục trong hơn hai mươi năm cuối đời. Ông mất trong viện an dưỡng sau một cơn đau tim.
Ta thử xem xét một nghịch lý nảy sinh từ lý thuyết Cantor, gọi là nghịch lý Russell. Bertrand Russell (1872-1970) xét tập hợp sau đây: S = {X | X không phải là phần tử của X}.
Ví dụ, nếu X là tập hợp các khái niệm hiểu được, thì X là phần tử của chính nó, vì rõ ràng khái niệm này có thể hiểu được. Nhưng nếu X là tập hợp các quán nhậu ở Sài Gòn, thì X không phải là phần tử của chính nó. Russell đặt câu hỏi: “thế S có phải là phần tử của chính nó không?” Dễ thấy đây là nghịch lý. Rất oái oăm là nghịch lý này có ý tưởng tương tự như lập luận đường chéo của Cantor. Trước đó, người ta cũng đã biết các nghịch lý khác có tư tưởng tương tự, nhưng vì không phát biểu bằng ngôn ngữ hình thức của toán học nên chúng bị bỏ qua, bị cho là sản phẩm của tính mù mờ trong văn nói, văn viết. Ví dụ, nghịch lý kẻ nói dối có thể mô tả như sau: anh A nói “Tôi đang nói điều dối trá”. Nghịch lý thợ cắt tóc: “Ở một làng nọ, có một thợ cắt tóc, cắt tóc cho tất cả những ai trong làng không tự cắt tóc.” (nghịch lý là, thế anh ta có tự cắt cho mình không?). Vấn đề của các nghịch lý này là lối tự tham chiếu (self-reference) mà sau này Godel cũng dùng để chứng minh định lý không toàn vẹn (incompleteness theorem) lừng danh của ông. Ta sẽ nói rõ hơn về định lý này sau.
Các nghịch lý kiểu như trên khuấy động một cuộc tranh luận lớn có một không hai trong lịch sử về nền tảng của toán học. Bạn thử tưởng tượng, nếu có một nghịch lý không giải quyết được trong bất kỳ ngành học nào, thì nền tảng logic của ngành đó có nguy cơ sụp đổ hoàn toàn! Các nhà toán học hoặc ủng hộ Cantor, hoặc chống đối hoàn toàn lý thuyết tập hợp này. David Hilbert nói: “Không ai có thể đuổi chúng ta ra khỏi thiên đàng mà Cantor đã tạo cho chúng ta”. Henri Poincaré bảo: “Các thế hệ sau sẽ xem lý thuyết tập hợp như một căn bệnh“.
Các nhà toán học và logic học thời đó đề cử vài phương pháp để giải quyết các nghịch lý này:
- Trường phái logic (logicism) đề nghị dùng logic hình thức (formal logic) để làm toán, với hy vọng là logic hình thức sẽ xóa bỏ được sự mù mờ của ngôn ngữ phổ thông. Bộ sách Principia Mathematica của Alfred North Whitehead và Bertrand Russell [38] là một trong những công trình đại diện cho trường phái này. Các tác giả phải dùng đến hai quyển để có thể chứng minh “1 + 1 = 2”.
- Trường phái trực quan (intuitionism) được khởi xướng khoảng năm 1908 bởi nhà toán học Hà Lan Luitzen Egbertus Jan Brouwer (1881-1966). Trường phái này là cả một hệ thống triết học. Một trong những luận điểm cơ bản nhất của trường phái trực quan về toán học là: ta phải làm toán mang tính xây dựng (constructive mathematics). Các khái niệm như các số tự nhiên 1,2,3 có thể “xây dựng” được từ trực quan của con người. Khi định nghĩa một khái niệm mới, nó phải được xây dựng được bằng một số hữu hạn các bước. Như vậy, các chứng minh bằng phản chứng không thể chấp nhận được trong trường phái này, và vì thế các nghịch lý trên không mang ý nghĩa gì cả (xem [12,32,33,36]). Kể cũng thú vị là một định lý cực kỳ nổi tiếng của Brouwer trong hình học tô-pô (fixed point theorem) lại được chứng minh bằng phản chứng!
- Trường phái hình thức (formalism) do Hilbert khởi xướng. Về căn bản, Hilbert tin rằng các nhánh của toán học có thể được mô tả bằng một hệ thống tiên đề và một ngôn ngữ hình thức bậc nhất (first order language) với cú pháp cụ thể. Ngôn ngữ này có thể được nghiên cứu như một đối tượng toán học, và nhờ đó ta có thể trả lời chắc chắn các câu hỏi kiểu như: “có thể nào nhánh toán học này có nghịch lý không?” (Dĩ nhiên nghịch lý đó phải được phát biểu bằng ngôn ngữ hình thức ấy.) Hilbert đề nghị là hình thức hóa tất cả các nhánh của toán học, sau đó chứng minh rằng tất cả các nhánh này đều không có nghịch lý. Đây là nội dung chính của chương trình Hilbert (Hilbert’s program) (xem [32]).
Hiện nay, chúng ta nói chung đều theo trường phái hình thức của Hilbert. Các ngành như hình học Euclid, lý thuyết số, đại số… đều được tiên đề hóa và hình thức hóa khá cụ thể. Các sách giáo khoa đều dạy học sinh theo kiểu này.
Ảnh hưởng của Hilbert vào sự phát triển của toán học hơn 100 năm qua là vô cùng to lớn. Khoa học máy tính cũng không ngoại lệ.
[/membersonly]
