Định lý bất toàn, bài 5: Tự quy chiếu – Làm thế nào một mệnh đề toán học có thể nói về chính nó?
Trong bài 3 và bài 4, chúng ta đã tìm hiểu hai ý tưởng quan trọng trong công trình của Kurt Gödel:
Mỗi công thức toán học có thể được mã hóa thành một số tự nhiên.
Mỗi chứng minh toán học cũng có thể được mã hóa thành một số tự nhiên.
Nhờ đó, những phát biểu về công thức và chứng minh có thể được chuyển thành những phát biểu về số tự nhiên.
Nhưng vẫn còn một câu hỏi rất kỳ lạ:
Liệu chúng ta có thể tạo ra một mệnh đề toán học nói về chính nó hay không?
Chẳng hạn, hãy tưởng tượng có một mệnh đề mang nội dung:
"Tôi không thể được chứng minh."
Nếu mệnh đề này đúng, thì nó không thể được chứng minh. Nhưng nếu nó có thể được chứng minh, nội dung của nó lại nói rằng nó không thể được chứng minh.
Đây chính là ý tưởng trung tâm trong chứng minh Định lý Bất toàn thứ nhất của Gödel.
Tuy nhiên, Gödel không sử dụng một trò chơi ngôn ngữ đơn giản. Ông đã tìm ra một phương pháp toán học chính xác để xây dựng những mệnh đề có khả năng tự nói về chính mình.
Trong bài viết này, chúng ta sẽ từng bước tìm hiểu ý tưởng đó.
1. Tự quy chiếu là gì?
Tự quy chiếu là hiện tượng một câu nói, một phát biểu hoặc một đối tượng có nội dung đề cập đến chính nó.
Hãy xét ba ví dụ.
Ví dụ 1:
"Câu này có năm từ."
Đây là một câu tự quy chiếu vì nội dung của nó đề cập đến chính câu đang được đọc.
Ví dụ 2:
"Câu này được viết bằng tiếng Việt."
Câu nói này cũng đề cập đến chính nó.
Ví dụ 3:
"Câu này không thể được chứng minh."
Đây là ví dụ đặc biệt quan trọng. Nó không chỉ nói về chính mình mà còn đề cập đến khả năng chứng minh của bản thân.
Tự quy chiếu xuất hiện trong nhiều lĩnh vực như ngôn ngữ học, triết học, logic và toán học.
Tuy nhiên, cần phân biệt tự quy chiếu với nghịch lý.
Không phải câu tự quy chiếu nào cũng tạo ra mâu thuẫn.
Chẳng hạn, câu "Câu này có năm từ" có thể đúng hoặc sai tùy theo số lượng từ thực tế, nhưng không nhất thiết tạo ra nghịch lý.
Điều đặc biệt nằm ở việc một mệnh đề có thể nói về tính đúng sai hoặc khả năng chứng minh của chính nó.
2. Nghịch lý kẻ nói dối
Một trong những ví dụ nổi tiếng nhất về tự quy chiếu là nghịch lý kẻ nói dối.
Hãy xét câu:
"Câu này là sai."
Chúng ta thử phân tích:
Nếu câu này đúng thì nội dung của nó khẳng định rằng nó sai.
Nếu câu này sai thì nội dung của nó lại không đúng, tức là nó không sai theo cách diễn giải thông thường.
Chúng ta rơi vào một vòng lặp logic.
Đây là một nghịch lý nổi tiếng đã được nghiên cứu từ thời cổ đại.
Nhưng tại sao chúng ta lại nhắc đến nghịch lý này khi tìm hiểu Định lý Bất toàn?
Bởi vì Gödel đã sử dụng một ý tưởng có vẻ tương tự, nhưng thay vì tạo ra câu nói:
"Câu này là sai."
Ông xây dựng một mệnh đề có nội dung:
"Mệnh đề này không thể được chứng minh trong hệ thống đang xét."
Hai câu nói có vẻ giống nhau nhưng có sự khác biệt rất quan trọng.
Nghịch lý kẻ nói dối liên quan đến khái niệm đúng và sai.
Trong khi đó, mệnh đề Gödel liên quan đến khả năng chứng minh từ một hệ tiên đề cụ thể.
Chúng ta không được đồng nhất hai vấn đề này.
3. Làm thế nào toán học có thể nói về chính nó?
Đây là phần quan trọng nhất.
Hãy nhớ lại kỹ thuật đánh số Gödel trong bài 3.
Giả sử chúng ta có một hệ thống toán học. Mỗi ký hiệu, mỗi công thức đều được gán một số tự nhiên.
Chẳng hạn, một công thức A có mã số:
G(A) = 125.
Trong đó G(A) được gọi là số Gödel của công thức A.
Một công thức khác B có thể có mã số:
G(B) = 240.
Như vậy, thay vì nói về công thức A, chúng ta có thể nói về số 125.
Thay vì nói về công thức B, chúng ta có thể nói về số 240.
Đây là bước chuyển đổi rất quan trọng.
Bởi vì khi các công thức được mã hóa thành số, chúng ta có thể xây dựng những phát biểu số học nói về các công thức ấy.
Ví dụ, ở bài 4, chúng ta đã giới thiệu quan hệ:
Proof(x, y).
Nó có nghĩa là:
"x là mã số của một chứng minh hợp lệ cho công thức có mã số y."
Do đó, biểu thức:
∃x Proof(x, y)
có nghĩa là:
"Tồn tại một chứng minh cho công thức có mã số y."
Ngược lại:
¬∃x Proof(x, y)
có nghĩa là:
"Không tồn tại chứng minh nào cho công thức có mã số y."
Chúng ta đã có thể diễn đạt khái niệm "không thể chứng minh" bằng ngôn ngữ số học.
Nhưng vẫn còn một bước khó hơn:
Làm sao để y chính là số Gödel của công thức đang được xét?
Đây chính là vấn đề tự quy chiếu.
4. Ý tưởng quan trọng: Một công thức có thể nhận chính mã số của nó làm đầu vào
Hãy tưởng tượng chúng ta có một công thức chứa một biến số x.
Khi thay x bằng một số tự nhiên cụ thể, chúng ta nhận được một công thức mới.
Ví dụ đơn giản:
P(x): "x là số chẵn."
Nếu thay x bằng 6, ta được:
P(6): "6 là số chẵn."
Nếu thay x bằng 7, ta được:
P(7): "7 là số chẵn."
Đây là thao tác rất quen thuộc trong toán học: thay một biến bằng một giá trị cụ thể.
Bây giờ, hãy tưởng tượng thay vì sử dụng một số bất kỳ, chúng ta thay x bằng số Gödel của chính công thức đó.
Giả sử công thức P có số Gödel là n.
Khi thay x bằng n, ta có:
P(n).
Công thức P(n) đang nói về một số chính là mã số của công thức P.
Đây là bước đầu tiên giúp chúng ta tiến đến ý tưởng tự quy chiếu.
Tuy nhiên, cần chú ý:
P(n) chưa chắc đã nói về chính nó. Nó chỉ nói về số Gödel của P.
Muốn tạo ra một công thức thực sự nói về chính mã số của nó, chúng ta cần một kỹ thuật tinh vi hơn.
Kỹ thuật đó được gọi là bổ đề đường chéo.
5. Bổ đề đường chéo – Chìa khóa tạo ra mệnh đề tự quy chiếu
Trong logic toán học, có một kết quả rất quan trọng gọi là Bổ đề đường chéo (Diagonal Lemma).
Đây là công cụ cho phép chúng ta xây dựng một câu có nội dung nói về chính mã Gödel của nó.
Có thể phát biểu ý tưởng của bổ đề như sau:
Cho một công thức toán học có một biến tự do x, chúng ta có thể xây dựng một câu G sao cho G tương đương về mặt chứng minh với công thức ban đầu khi biến x được thay bằng số Gödel của chính G.
Viết dưới dạng ký hiệu:
G ↔ φ(⌜G⌝)
Trong đó:
φ(x) là một công thức có biến x.
G là câu được xây dựng từ φ.
⌜G⌝ là ký hiệu biểu thị số Gödel của G.
↔ có nghĩa là tương đương logic.
Nói đơn giản hơn:
G được xây dựng sao cho nội dung của nó tương ứng với việc áp dụng một công thức nào đó lên chính số Gödel của G.
Đây là một kết quả rất sâu sắc.
Nó cho thấy tự quy chiếu không chỉ là một trò chơi ngôn ngữ. Chúng ta có thể xây dựng nó bằng những phép toán và quy tắc hình thức.
Một ví dụ trực quan
Giả sử chúng ta muốn xây dựng một mệnh đề có nội dung:
"Không tồn tại chứng minh cho mệnh đề mang số Gödel n."
Ta bắt đầu với công thức:
φ(x) = ¬∃y Proof(y, x).
Công thức này có nghĩa:
"Không tồn tại số y mã hóa một chứng minh cho công thức có mã số x."
Áp dụng bổ đề đường chéo, chúng ta có thể xây dựng một câu G thỏa mãn:
G ↔ ¬∃y Proof(y, ⌜G⌝).
Đọc bằng tiếng Việt:
Mệnh đề G đúng khi và chỉ khi không tồn tại chứng minh nào cho chính G trong hệ thống đang xét.
Đây chính là hình thức toán học của ý tưởng:
"Mệnh đề này không thể được chứng minh."
Chúng ta đã tiến rất gần đến mệnh đề Gödel.
6. Bổ đề đường chéo hoạt động như thế nào?
Để hiểu sâu hơn, hãy xem ý tưởng xây dựng của bổ đề đường chéo.
Chúng ta sẽ không đi ngay vào toàn bộ chứng minh hình thức, mà sử dụng một mô hình đơn giản để hình dung.
Giả sử có một công thức:
φ(x).
Công thức này có thể nhận một số tự nhiên làm đầu vào.
Bây giờ, ta xây dựng một công thức mới bằng cách đưa mã Gödel của một công thức vào chính công thức đó.
Về mặt hình thức, chúng ta cần có một phép thay thế:
Sub(u, v).
Trong đó Sub(u, v) biểu thị số Gödel của công thức thu được khi thay một biến tự do trong công thức có mã u bằng số v.
Vì thao tác thay thế ký hiệu là một thao tác hữu hạn và có thể kiểm tra được, nó có thể được biểu diễn bằng các quan hệ số học thích hợp.
Tiếp theo, ta sử dụng phép thay thế này để tạo ra một công thức mới có khả năng nhận mã số của chính nó.
Bằng cách lựa chọn công thức và thực hiện phép thay thế một cách thích hợp, ta thu được câu G có nội dung tương đương với:
φ(⌜G⌝).
Đây chính là ý tưởng của bổ đề đường chéo.
Điểm quan trọng là:
Chúng ta không cần viết trực tiếp câu "Tôi đang nói về chính tôi".
Thay vào đó, chúng ta sử dụng các phép toán trên mã Gödel để tạo ra một công thức có tính chất tự quy chiếu.
Trong chứng minh chính thức, bổ đề đường chéo đảm bảo rằng quá trình xây dựng này có thể được thực hiện trong những hệ thống số học đủ mạnh.
7. Tại sao mệnh đề tự quy chiếu lại quan trọng đối với Gödel?
Bây giờ, hãy kết hợp những gì chúng ta đã học.
Ở bài 4, chúng ta đã biết:
∃x Proof(x, y)
có nghĩa là tồn tại một chứng minh cho công thức mang mã số y.
Phủ định của nó:
¬∃x Proof(x, y)
có nghĩa là không tồn tại chứng minh cho công thức mang mã số y.
Bây giờ, nhờ bổ đề đường chéo, Gödel có thể xây dựng một câu G thỏa mãn:
G ↔ ¬∃x Proof(x, ⌜G⌝).
Đọc bằng ngôn ngữ thông thường:
G khẳng định rằng không có chứng minh nào chứng minh được chính G.
Đây chính là mệnh đề Gödel.
Nó không phải một câu văn thông thường, mà là một công thức toán học được xây dựng bằng ngôn ngữ hình thức.
Và từ đây, chúng ta có thể bắt đầu chứng minh Định lý Bất toàn thứ nhất.
8. Một câu hỏi quan trọng: Nếu G không thể chứng minh thì G có đúng không?
Đây là câu hỏi rất thú vị.
Giả sử hệ thống toán học đang xét là nhất quán.
Ta có:
G ↔ ¬∃x Proof(x, ⌜G⌝).
Giả sử hệ thống chứng minh được G.
Khi đó, tồn tại một chứng minh cho G.
Nhưng G lại khẳng định rằng không tồn tại chứng minh cho chính nó.
Điều này tạo ra mâu thuẫn với tính nhất quán của hệ thống.
Do đó, trong những điều kiện thích hợp, G không thể được chứng minh trong hệ thống.
Nhưng nếu G không thể chứng minh, liệu điều đó có đủ để kết luận rằng G đúng?
Để trả lời đầy đủ, chúng ta cần phân biệt:
Không chứng minh được G.
Không chứng minh được phủ định của G.
G đúng trong mô hình số tự nhiên chuẩn.
Đây là những vấn đề không hoàn toàn giống nhau.
Trong phiên bản ban đầu của Gödel năm 1931, việc chứng minh tính bất khả quyết định sử dụng một điều kiện mạnh hơn tính nhất quán đơn thuần, thường được gọi là ω-nhất quán.
Sau này, Rosser đã cải tiến lập luận để chỉ cần giả thiết nhất quán theo cách diễn đạt thích hợp.
Chúng ta sẽ tìm hiểu kỹ vấn đề này trong bài 7.
9. Những điều cần ghi nhớ
Sau bài viết này, chúng ta đã tiếp cận được một trong những ý tưởng sâu sắc nhất của logic toán học.
Hãy nhớ năm điểm sau:
Tự quy chiếu là hiện tượng một phát biểu nói về chính nó.
Nghịch lý kẻ nói dối là ví dụ nổi tiếng về tự quy chiếu, nhưng không đồng nhất với lập luận của Gödel.
Đánh số Gödel cho phép biến công thức và chứng minh toán học thành các số tự nhiên.
Bổ đề đường chéo cho phép xây dựng một công thức có nội dung tương đương với một phát biểu về chính số Gödel của nó.
Nhờ đó, có thể xây dựng mệnh đề G khẳng định rằng chính nó không có chứng minh trong hệ thống đang xét.
Đây chính là chiếc cầu nối giữa kỹ thuật mã hóa ở các bài trước và chứng minh Định lý Bất toàn.
10. Kết luận: Toán học đã tìm ra cách nói về chính mình
Điều làm cho công trình của Gödel trở nên đặc biệt không chỉ là kết luận rằng toán học có những giới hạn.
Điều đáng kinh ngạc hơn là cách ông đạt được kết luận đó.
Ông không sử dụng một nghịch lý ngôn ngữ đơn giản, cũng không dựa vào những lập luận triết học mơ hồ.
Ông sử dụng số học để mã hóa ngôn ngữ toán học, sử dụng logic để mô tả các chứng minh, và sử dụng bổ đề đường chéo để tạo ra một mệnh đề có khả năng tự quy chiếu.
Từ đó, một công thức toán học có thể khẳng định:
"Tôi không thể được chứng minh trong hệ thống này."
Đây là một trong những ý tưởng đẹp và sâu sắc nhất của toán học hiện đại.
Nhưng chúng ta vẫn chưa hoàn thành chứng minh.
Ở bài tiếp theo, chúng ta sẽ bắt đầu xây dựng mệnh đề Gödel một cách cụ thể hơn, sau đó sử dụng nó để chứng minh định lý Bất toàn thứ nhất.
Chúng ta sẽ trả lời câu hỏi:
Nếu một hệ thống toán học đủ mạnh và nhất quán, tại sao nó nhất thiết phải tồn tại một mệnh đề mà chính hệ thống đó không thể chứng minh?
Đó chính là bước cuối cùng để biến ý tưởng tự quy chiếu thành một định lý toán học thực sự.
Tham gia cuộc trò chuyện