Định lý bất toàn của Gödel nói rằng một hệ tiên đề nhất quán, đủ mạnh để diễn đạt số học thông thường, luôn có những mệnh đề mà hệ ấy không chứng minh được, cũng không bác bỏ được. Định lý thứ hai thêm rằng hệ ấy không thể tự chứng minh mình không mâu thuẫn.
Chào bạn, đây là Nhà Học Thuật. Ít định lý nào bị trích dẫn sai nhiều như định lý này, từ thần học tới quản trị doanh nghiệp. Tập này mình kể nó ra đời trong hoàn cảnh nào, ý tưởng chứng minh đẹp ra sao, và nó thật sự chỉ nói gì.
Giấc mơ của Hilbert
Đầu thế kỷ hai mươi, toán học vừa trải qua những cú sốc về nền tảng. Nhà toán học Đức David Hilbert đề ra một chương trình đầy tham vọng: đặt toàn bộ toán học lên một hệ tiên đề hình thức, rồi chứng minh bằng những phương pháp hữu hạn, chắc chắn, rằng hệ ấy không bao giờ dẫn tới mâu thuẫn.
Nếu thành công, toán học sẽ có một nền móng tuyệt đối. Mọi câu hỏi toán học, về nguyên tắc, đều có thể được giải quyết bằng cách suy ra từ tiên đề.
Hilbert có một câu nói nổi tiếng, đại ý chúng ta phải biết và chúng ta sẽ biết. Điều trớ trêu của lịch sử là cũng vào dịp ấy, ở cùng thành phố Königsberg, một chàng trai hai mươi bốn tuổi người Áo tên Kurt Gödel lần đầu công bố kết quả sẽ khiến giấc mơ đó không thể thành hiện thực theo dạng ban đầu.
Bài báo chính thức của Gödel ra đời năm một nghìn chín trăm ba mươi mốt.
Ý tưởng chứng minh: một câu tự nói về mình
Mấu chốt đầu tiên là mã hoá. Gödel gán cho mỗi ký hiệu, mỗi công thức, mỗi chuỗi chứng minh một con số tự nhiên riêng. Nhờ vậy, những câu về chứng minh trở thành những câu về số. Số học bỗng tự nói được về chính nó.
Mấu chốt thứ hai là tự quy chiếu. Ông dựng được một mệnh đề số học, mà dịch nôm ra lời có nghĩa là: mệnh đề này không chứng minh được trong hệ. Nó gợi nhớ tới nghịch lý người nói dối, nhưng không phải nghịch lý, vì nó nói về tính chứng minh được chứ không nói về đúng sai.
Giờ hãy suy. Nếu hệ chứng minh được mệnh đề ấy, thì hệ chứng minh được một điều sai, tức hệ không đáng tin. Vậy nếu hệ nhất quán, nó không chứng minh được mệnh đề ấy. Nhưng đó chính là điều mệnh đề nói. Vậy mệnh đề ấy đúng, mà không chứng minh được trong hệ.
Điểm tinh tế là cái đúng ở đây được nhìn từ bên ngoài hệ. Và nếu ta thêm mệnh đề đó vào làm tiên đề mới, hệ mới lại sinh ra một mệnh đề không chứng minh được mới. Không có cách vá cho trọn.
Định lý thứ hai đánh vào đâu?
Định lý thứ hai đi xa hơn: một hệ như vậy, nếu nhất quán, không thể chứng minh chính sự nhất quán của mình. Đây là đòn trực diện vào chương trình Hilbert, vốn muốn hệ toán học tự bảo đảm cho mình bằng phương tiện bên trong.
Điều này không có nghĩa toán học có mâu thuẫn. Nó có nghĩa muốn bảo đảm một hệ không mâu thuẫn, ta phải dùng những giả định mạnh hơn chính hệ đó, và câu hỏi về độ tin cậy được dời lên một tầng cao hơn.
Vài năm sau, nhà toán học Gerhard Gentzen chứng minh được tính nhất quán của số học thông thường, nhưng phải dùng một nguyên lý quy nạp vượt ra ngoài số học ấy. Đúng như Gödel dự báo.
Ngày nay giới toán học sống thoải mái với tình trạng này. Phần lớn tin chắc các hệ tiên đề chuẩn là nhất quán, dựa trên kinh nghiệm hàng thế kỷ và nhiều bằng chứng gián tiếp, dù không có chứng minh tuyệt đối.
Những cách hiểu sai thường gặp
Sai lầm phổ biến nhất là nói Gödel chứng minh mọi thứ đều tương đối, hay không có chân lý. Thực ra định lý chỉ nói về các hệ hình thức đủ mạnh, và chính chứng minh của nó dựa vào khái niệm chân lý khá chặt chẽ.
Sai lầm thứ hai là áp nó cho mọi hệ thống, từ luật pháp tới tôn giáo. Định lý đòi những điều kiện rất cụ thể: hệ phải hình thức, có quy tắc suy luận máy móc, và đủ mạnh để làm số học. Hình học phẳng cơ bản, chẳng hạn, có những hệ tiên đề hoàn chỉnh không bị định lý này chạm tới.
Sai lầm thứ ba gây tranh cãi hơn: lập luận cho rằng Gödel chứng minh trí óc con người vượt trội máy tính, vì ta thấy được mệnh đề kia đúng còn máy thì không. Lập luận này từng được nhà triết học John Lucas và nhà vật lý Roger Penrose bảo vệ, nhưng phần đông các nhà logic học cho rằng nó có lỗ hổng, chủ yếu vì ta cũng không chắc chắn về sự nhất quán của chính mình.
Nói ngắn, định lý bất toàn là một kết quả kỹ thuật chính xác về giới hạn của chứng minh hình thức, không phải một câu triết lý chung chung.
Sau Gödel, toán học đi tiếp thế nào?
Lúc đầu, có người lo rằng những mệnh đề không quyết định được chỉ là đồ chơi tự quy chiếu, không dính dáng gì tới toán học thật. Về sau, người ta tìm ra những mệnh đề tự nhiên, phát biểu như toán học bình thường, cũng không chứng minh được trong số học chuẩn.
Nổi tiếng hơn cả là giả thuyết continuum về kích cỡ các tập vô hạn, được chứng minh là độc lập với hệ tiên đề chuẩn của lý thuyết tập hợp, nhờ công trình của chính Gödel và về sau của Paul Cohen.
Cũng từ những ý tưởng của Gödel, Alan Turing đi tới khái niệm máy tính trừu tượng và chứng minh có những bài toán không máy nào giải được. Định lý về giới hạn hoá ra lại sinh ra cả một ngành khoa học máy tính.
Có lẽ đó là bài học đẹp nhất: biết rõ giới hạn của một công cụ nhiều khi mở ra những thứ mới, thay vì khép lại.
Câu hỏi thường gặp
Gödel có phải là người buồn bã vì phát hiện của mình không?
Gödel tin vào sự tồn tại khách quan của chân lý toán học, nên ông không xem định lý của mình là bi quan. Với ông, nó cho thấy chân lý toán học rộng hơn mọi hệ hình thức có thể nắm được.
Hệ tiên đề nhất quán nghĩa là gì?
Nghĩa là từ các tiên đề ấy không bao giờ suy ra được cả một mệnh đề lẫn phủ định của nó. Một hệ có mâu thuẫn thì chứng minh được mọi thứ, nên trở nên vô dụng.
Định lý bất toàn có ảnh hưởng tới toán học thường ngày không?
Rất ít. Phần lớn các nhà toán học làm việc với những câu hỏi mà hệ tiên đề chuẩn giải quyết được. Định lý chủ yếu quan trọng ở tầng nền tảng và logic.
Định lý bất toàn và bài toán dừng của Turing liên quan thế nào?
Cả hai đều dùng ý tưởng tự quy chiếu để chỉ ra giới hạn. Từ việc không có thuật toán nào quyết định được mọi chương trình có dừng hay không, có thể suy ra một dạng của định lý bất toàn.
Có cuốn sách nào giải thích Gödel cho người không chuyên?
Cuốn sách mỏng Chứng minh của Gödel của Ernest Nagel và James Newman là một lựa chọn kinh điển. Cuốn Gödel, Escher, Bach của Douglas Hofstadter dài và vui hơn, đi sâu vào ý tưởng tự quy chiếu.
