Chung qui chỉ tại Cantor (6)

 

"Tôi đã khám phá ra một khả năng logic và hợp pháp mà hợp chủng quốc Hoa Kỳ có thể biến thành một nước độc tài."

[Trích lời Gödel nói với Oskar Morgenstern năm 1952]

Đầu thế kỷ 20, Hilbert dành rất nhiều thời gian phát triển "chương trình Hilbert" như đã đề cập. Tại đại hội các nhà toán học thế giới năm 1928 ở Bologna, Hilbert tuyên bố là Wilhelm Ackermann (1896-1962) và John von Neumann (1903-1957) đã chứng minh được tính nhất quán (consistent – nghĩa là không dẫn đến các mệnh đề mâu thuẫn nhau) của lý thuyết số. Dĩ nhiên nếu tuyên bố này là đúng, thì chương trình Hilbert đã tiến được một bước dài. Hilbert còn tuyên bố là Ackermann gần kết thúc được cả chứng minh rằng số học của các số thực cũng nhất quán. Ông liệt kê bốn bài toán để hoàn tất chứng minh này của Ackermann. Đến năm 1931 thì cả bốn vấn đề này cùng với bài toán số 2 của Hilbert đều được giải quyết thỏa đáng. Kurt Gödel phủ định tất cả! Và nói chung là ông phá tan tành chương trình Hilbert. Năm ấy Gödel mới có 25 tuổi.

Bài tập 2 : chúng ta đều biết là các dữ liệu trong máy tính đều được lưu trữ theo dạng nhị phân. Mã ASCII gán 8 bits nhị phân (0 hoặc 1) cho mỗi chữ cái và chỉ cần cách này ta có thể mã hóa các văn tự tiếng Anh. Thế có thể nào mã hóa các văn tự tiếng Anh với chỉ một ký tự 1 thôi hay không? (Thay vì có cả 0 lẫn 1.)

Gödel có ba định lý rất nổi tiếng: (1) định lý toàn vẹn ( completeness theorem), (2) định lý không toàn vẹn thứ nhất ( first incompleteness theorem), và (3) định lý không toàn vẹn thứ hai.(second incompleness theorem ).

Để giới thiệu về định lý toàn vẹn, hãy xét một bộ tiên đề của một trường (field) số, như trường số thực, trường số hữu tỉ, trường số phức, vân vân. Với một bộ tiên đề như vậy, có nhiều cấu trúc toán học thỏa mãn bộ này (các cấu trúc thực, phức, hữu tỉ, vectors, …). Nếu có một mệnh đề nào đó có thể suy ra được từ hệ tiên đề này (ví dụ "nếu a+a=a, thì a=0"), thì mệnh đề này đúng cho tất cả các cấu trúc toán trên hệ tiên đề này. Tính chất này gọi là tính hợp lý (soundness) của hệ thống. Ngược lại, nếu một mệnh đề nào đó đúng cho tất cả các cấu trúc toán học trên hệ tiên đề, thì có chắc rằng ta sẽ chứng minh được mệnh đề đó không? Câu trả lời là có, và đó chính là nội dung của định lý toàn vẹn Gödel. Theo một nghĩa nào đó, định lý này ủng hộ chương trình Hilbert.

Định lý không toàn vẹn thứ nhất đại khái nói rằng: nếu ta lấy hệ tiên đề cho số học các số tự nhiên (bao gồm cộng trừ nhân chia), thì sẽ có một phát biểu (bằng ngôn ngữ logic) không thể chứng minh được là đúng hay sai. Điều cực kỳ thú vị là Gödel dùng "nghịch lý kẻ nói dối" để xây dựng một phát biểu trong hệ logic này. Phát biểu đó nói rằng: "mệnh đề này không chứng minh được", sau đó dùng lập luận đường chéo của Cantor để hoàn tất chứng minh.

Ta thử nghĩ thêm một chút về ý nghĩa to lớn của định lý này. Thứ nhất, nó hủy tan chương trình Hilbert. Không cần biết hệ tiên đề tốt đến đâu (kể cả khi có một số vô hạn – nhưng đếm được – các tiên đề), luôn luôn có các mệnh đề "độc lập" với hệ thống. Ta có thể lấy mệnh đề mới này làm một tiên đề và mở rộng hệ thống. Như vậy, toán học là tuyệt đối vô hạn! Bạn có thể tưởng tượng một cái "cây tri thức", bắt đầu bằng một số tiên đề và phân nhánh ra nhờ suy luận logic. Các tiên đề có thể là các nguyên tắc sống (không giết người, cướp của) chẳng hạn, và ta sống theo luật logic cùng các nguyên tắc của mình, ai cũng hy vọng là có thể làm thế được. Không may là, sẽ luôn có các tình huống trong cuộc sống nằm ngoài hệ thống giá trị của bản thân ta. Như vậy, định lý này của Gödel theo nghĩa nào đó đã dạy cho chúng ta phải sống với một tâm hồn mở, không thể theo một nguyên tắc bất di bất dịch nào đó. Ít nhất là nếu ta sống có logic.

Định lý không toàn vẹn thứ hai của Gödel phá hủy hoàn toàn những gì còn lại của chương trình Hilbert. Định lý này nói rằng không thể chứng minh rằng số học có tính nhất quán. Chỉ số học đã "phức tạp" đến thế, ta không có hy vọng gì vào chương trình chứng minh tính nhất quán của toàn bộ toán học.

Sự độc lập (independence) của một mệnh đề trong hệ thống (như mệnh đề Gödel dựng nên để chứng minh định lý không toàn vẹn thứ nhất) là một ý tưởng rất quan trọng trong lịch sử toán học. Tiên đề số 5 của Euclid là một ví dụ kinh điển. Bỏ nó vào thì ta có hình học Euclid, thay đổi nó một chút theo vài kiểu khác nhau là ta có vài loại hình học phi Euclid với các công trình của Carl Friedrich Gauss, Nikolai Ivanovich Lobachevsky, János Bolyai, và Bernhard Riemann. Giả thuyết liên tục (bài toán số 1 của Hilbert) được Paul Cohen chứng minh tính độc lập năm 1963. Câu hỏi P chọi NP của chúng ta cũng có khả năng là nó độc lập với hệ thống suy luận hiện hành, ta sẽ quay lại khả năng này sau.

Các nghiên cứu về các hệ thống chứnh minh và các tiên đề có giá trị to lớn trong khoa học máy tính. Nhiều nhà khoa học máy tính nổi tiếng (như Edsger Wybe Dijkstra) đã bỏ nhiều năm nghiên cứu để làm thế nào "chứng minh" được là một chương trình máy tính chạy đúng với dự định thiết kế (specification), mà trong ngữ cảnh của chúng ta là các tiên đề! Một công trình khác của Gödel về "độ dài" của các chứng minh đã nuôi mầm cho các định lý "tăng tốc" của lý thuyết tính toán hiện đại.

John von Neumann từng nói là Kurt Gödel là nhà logic học lỗi lạc nhất thế giới sau Aristotle. Ta không thể không đồng ý với Neumann. (Bản thân Neumann cũng là một thiên tài tuyệt đỉnh có ảnh hưởng cực lớn đến khoa học máy tính mà ta sẽ "gặp" ông vào dịp khác.)