Chứng Minh định Lý Bất Toàn (incompleteness Theorem) - Kurt Gödel

Đây là post thứ 2 của blog, ở post này mình sẽ giới thiệu với các bạn 1 định lý mà có thể nói chính nó đã làm thay đổi quan niệm của mình về khoa học nói chung. Định lý này có thể rất lạ đối với nhiều người. Đó là “ định lý bất toàn” của nhà toán học Kurt Gödel. Tên tiếng anh là “Incompleteness Theorem “.

Trước khi đi sâu vào bài viết này thì các bạn cần biết tổng quan về một học thuyết khoa học là gì ? Nếu ai chưa biết có thể tham khảo qua bài học thuyết khoa học là gì ?

Đầu tiên, mình sẽ nói về nội dung của định lý, sau đó sẽ đi vào phần chứng minh.

Mục lục

• Nội dung và ý nghĩa
  • Định lý
  • Ý nghĩa
• Chứng minh
  • Các tiên đề của lý thuyết N
  • Số Gödel
  • Định nghĩa \(  P\left( X \right) \)
  • Tính nhất quán trong N
  • Tự quy chiếu
  • Chứng minh các mệnh đề cần thiết
  • Nhận xét
    • 1, Tồn tại 1 mệnh đề A trong N, sao cho ⊬A và ⊬\( \neg A \)
    • 2, Luôn tồn tại 1 mệnh đề đúng trong N nhưng không thể chứng minh nó trong N.
    • 3, ⊬ \( \neg P(0=1) \)
• Kết luận

Nội dung và ý nghĩa

Định lý

Định lý này nói rằng : “Bất kỳ một lý thuyết nào được tạo ra một cách hiệu quả đủ khả năng biểu diễn số học sơ cấp đều không thể vừa nhất quán vừa đầy đủ. Đặc biệt, bất kì một lý thuyết hình thức nào nhất quán, được tạo ra một cách hiệu quả cho phép chứng minh một số chân lý số học căn bản, sẽ tồn tại một mệnh đề số học đúng nhưng không thể chứng minh trong lý thuyết ấy.”

Theo ngôn ngữ của toán học thì là như thế, nhưng bạn có thể hiểu như sau: “Bất cứ điều gì mà bạn có thể vẽ một vòng tròn bao quanh nó sẽ không thể tự giải thích về bản thân nó mà không tham chiếu đến một cái gì đó ở bên ngoài vòng tròn – một cái gì đó mà bạn phải thừa nhận là đúng nhưng không thể chứng minh”

Ý nghĩa

Đó là ngôn ngữ của khoa học, còn ý nghĩa của nó thì như thế nào ? -) Theo cuốn “Gödel, A Life of Logic”  : Các phương pháp suy diễn logic thực ra vẫn quá yếu để chúng ta có thể chứng minh tất cả những chân lý đó. Nói cách khác, là thế giới chân lý lớn hơn thế giới chứng minh. Có nghĩa là toán học – lĩnh vực nhận thức mà ta tưởng là “ông vua của các khoa học” – thực ra cũng rất “yếu”: Bằng trực giác, con người có thể cảm nghiệm được những chân lý toán học mà chính toán học không thể chứng minh! -) Trích dẫn  Wittgenstein, “logic là cần chứ không đủ để mô tả bất kỳ một thực tế khách quan nào”, và rằng “ngôn ngữ không thể bắt kịp với tất cả những gì tồn tại trên thế giới”, đã được Gödel trình bầy dưới dạng toán học … Về căn bản, cái mà Godel chỉ ra là không có một dạng toán học nào có thể đủ thông minh để biểu hiện đầy đủ khái niệm chân lý thường ngày. -) Máy tính,” trí thông minh nhân tạo” sẽ không bao giờ có thể thông minh hơn con người,vì nó được trang bị “Bộ não nhân tạo”, dù thông minh đến đâu, thì cũng chỉ có thể “suy nghĩ” dựa trên một tập hợp hữu hạn các tiên đề (chương trình). Trong khi đó não con người có thể có nhưng phát kiến bất chợt : Những cảm nhận Trực giác xuất thần không dựa theo bất kỳ một hệ thống lý thuyết nào.

Chứng minh

Nội dung và ý nghĩa của định lý bất toàn là như thế nhưng chứng minh nó thì như thế nào ?

Khi mới bắt đầu biết đến định lý này thì mình cũng bắt đầu nghi ngờ, vì trước đó mình vẫn nghĩ là toán học nói riêng và khoa học nói chung thì đều có tính logic rất mạnh mẽ, có nghĩa là trong toán học thì cái gì cũng phải rõ ràng, đúng hoặc sai, và mình tin rằng con người sẽ hiểu hết được vũ trụ. Để giải đáp nghi ngờ của bản thân mình bắt đầu tìm cách để chứng minh định lý này. Mình đã tham khảo rất nhiều cách chứng minh, nhưng cách nào cũng tương đối phức tạp đòi hỏi phải có lượng kiến thức nhất định về logic học. Dưới đây là cách mà mình cảm thấy dễ hiểu nhất. Phần chứng minh dưới đây chỉ là chứng minh định lý trong phạm vi hẹp hơn so với định lý gốc nhưng cũng tương đối phức tạp đòi hỏi các bạn cần có kiến thức tương đối về môn đại số phần logic học.

Ta sẽ chứng minh định lý này trong lý thuyết logic số học : N , với các tiên đề hiển nhiên đúng cho trước ( các tiên đề này có thể chứng minh bằng bảng chân lý logic )

Ký hiệu:

\( \vdash X : X \) là một định lý trong N \( \neg \) : là kí hiệu phủ định “not” vd: \( \overline {A} \)

Các tiên đề của lý thuyết N

(1) Phủ định đôi : \( \vdash \neg\neg X\leftrightarrow X \) (2) Mâu thuẫn : \( \vdash X\rightarrow \left( \neg X\rightarrow Y\right) \) (3) Phân phối hàm ý : \( \vdash \left( X\rightarrow \left( Y\rightarrow Z\right) \right) \rightarrow \left( \left( X\rightarrow Y\right) \rightarrow \left( X\rightarrow Z\right) \right) \) (4) Chấm dứt : \( if \vdash X\rightarrow \neg Y, then \vdash Y\rightarrow \neg X \) (5) Modus Ponens : \( if \vdash X and \vdash X \rightarrow Y, then \vdash Y \) (6) Giả thuyết Syllogism : \( if \vdash X \rightarrow Y and \vdash Y \rightarrow Z, then \vdash X \rightarrow Z \)

Số Gödel

\(  g\left( \sigma \right) \) là số  Gödel của \( \sigma \) với \( \sigma \) là một ký hiệu, một công thức, một bằng chứng… \( \sigma \in \left\{ \top ,\bot ,\neg,\wedge ,\vee ,\rightarrow ,\leftrightarrow ,P_{1},x_{1},R_{1}\ldots \right\} \)

\(  g\left( \sigma \right) = n : \sigma \) như là vị trí thứ \( n \) trong danh sách trên \( g\left( \sigma _{1}*\sigma _{2}… *\sigma _{m}\right) = 2^{g\left( \sigma _{1}\right) } * 3^{g\left( \sigma _{2}\right) } …* P_{m}^{g\left( \sigma _{m}\right) } \) \( P_{m} \) : số nguyên tố thứ m \( g\left( X_{1}* X_{2}… *X_{m}\right) = 2^{g\left( X_{1}\right) } * 3^{g\left( X_{2}\right) } …* P_{m}^{g\left( X_{m}\right) } \) \( X_{i}:\) là một công thức, một mệnh đề …

Tính chất : do \( g \) phân tích được thành số nguyên tố *) \( g \) là một hàm tính được *) \(  g\left( u*v\right) \) tính được thông qua \(  g\left( u \right) \) và \(  g\left( v\right) \) *) cho \( n\in \mathbb{N} \), nếu \( n= g\left( X \right) \), thì \( X \) có thể được tính thông qua n.

Tóm lại : số Gödel, ứng với mỗi một mệnh đề, công thức, ký hiệu ( gọi chung là X) tồn tại trong N sẽ tương ứng với một số tự nhiên n. Nếu chứng minh được X tương đương với 1 số tự nhiên n trong N thì X tồn tại trong N.

Định nghĩa \(  P\left( X \right) \)

+) \( proof \left( x,y\right) \) : là một vị từ. ( x là số Gödel của 1 bằng chứng của công thức X có số Gödel là y ( \( y = g \left( X\right) \) ) +) Đặt \( Pr\left( X\right) = \exists x , proof\left( x, y\right) \) : tồn tại 1 số tự nhiên x là số Gödel của một bằng chứng của công thức X, công thức X có số Gödel là y (\( y = g\left( X\right)\)) Nếu mệnh đề trên là đúng thì nghĩa là X chứng minh được trong N. +) Đặt \( P\left( X\right) = Pr\left( y\right) =Pr\left( g\left( X\right)\right) \) \( P\left( X\right) = 1 \) : nghĩa là X chứng minh được trong N. \( P\left( X\right) = 0 \) : nghĩa là X không chứng minh được trong N. (1, 0 ở đây là giá trị chân lý )

Tính chất của \(  P\left( X \right) \) ( Những tính chất này được suy ra từ định nghĩa )

(7) \( if \vdash X, then \vdash P\left( X\right) \) (8) \( \vdash P\left( X \rightarrow Y\right) \rightarrow \left( P\left( X\right) \rightarrow P\left( Y\right) \right) \) (9) \( \vdash P(X) \rightarrow P(P(X)) \)

Tính nhất quán trong N

\( 0 \ne 1 \) trong N, \( P(0=1) \) biểu hiện sự không nhất quán của N. Vì vậy, tính nhất quán của N có thể được xây dựng bởi khẳng định rằng \( P(0=1) \) không là một định lý của N. kí hiệu: (10) ⊬ \(  P(0=1) \)

Tự quy chiếu

Cho \( B_{1}(n), B_{2}(n)…\) là các công thức trong N có đúng một biến tự do. Xét công thức \( \neg P(B_{n}(n)) \) là 1 công thức có 1 biến tự do \( \Rightarrow \neg P(B_{n}(n)) \) thuộc danh sách trên, đặt nó bằng \( B_{k}(n) \) \( \Rightarrow \vdash B_{k}(n) \leftrightarrow \neg P(B_{n}(n)) \) Do n là biến tự do, thay n = k ta có: \( \vdash B_{k}(k) \leftrightarrow \neg P(B_{n}(k)) \) Đặt \( A= B_{k}(k) \), ta được: (11) \( \vdash A \leftrightarrow \neg P(A) \)

Chứng minh các mệnh đề cần thiết

(12) \( \vdash P(A) \rightarrow P(\neg A) \) (13) \( \vdash P(A) \rightarrow P(0=1) \)

Chứng minh (12): Ta có (11) \( \vdash A \leftrightarrow \neg P(A) \), áp dụng (4) \(\Rightarrow \vdash P(A) \rightarrow \neg A \), áp dụng (7) \( \Rightarrow \vdash P(P(A) \rightarrow \neg A) \) Ta có (8) : \( \vdash P(P(A) \rightarrow \neg A) \rightarrow [P(P(A)) \rightarrow P(\neg A)] \) Áp dụng (5) ta được : \( \vdash P(P(A)) \rightarrow P(\neg A) \) Ta có (9): \( \vdash P(A) \rightarrow P(P(A)) \) Áp dụng (6) cho 2 ý trên ta được: \( \vdash P(A) \rightarrow P(\neg A) \)

Chứng minh (13): Ta có (2): \( \vdash A\rightarrow (\neg A\rightarrow (0=1)) \), áp dụng (7) \( \vdash P(A\rightarrow (\neg A\rightarrow (0=1))) \) Ta có (8): \( \vdash P(A\rightarrow (\neg A\rightarrow (0=1)))\rightarrow [P(A)\rightarrow P(\neg A\rightarrow (0=1))] \) Áp dụng (5) cho 2 ý trên ta được: \( \vdash P(A)\rightarrow P(\neg A\rightarrow (0=1)) \) Ta có (8): \( \vdash P(\neg A\rightarrow (0=1)) \rightarrow [P(\neg A) \rightarrow P(0=1)] \) Áp dụng (6) cho 2 ý trên ta được: \( \vdash P(A) \rightarrow [P(\neg A) \rightarrow P(0=1)] \) Ta có (3): \( \vdash [P(A) \rightarrow (P(\neg A) \rightarrow P(0=1))] \rightarrow [(P(A) \rightarrow P(\neg A)) \rightarrow (P(A) \rightarrow P(0=1))] \) Áp dụng (5) cho 2 ý trên: \( \vdash [(P(A) \rightarrow P(\neg A)) \rightarrow (P(A) \rightarrow P(0=1))] \) Áp dụng (5) và (12) ta được: \( \vdash P(A)\rightarrow P(0=1) \)

Nhận xét

1, Tồn tại 1 mệnh đề A trong N, sao cho ⊬A và ⊬\( \neg A \)

Chứng minh:( sử dụng A ở trong (11)) +) Giả sử \( \vdash A \) , từ (7) \( \Rightarrow \vdash P(A) \), nhưng từ (11) và (5) ta có \( \vdash \neg P(A) \Rightarrow \) mâu thuẫn nhau. \( \Rightarrow \) ⊬A +) Giả sử \( \vdash \neg A \), từ (11) \( \Rightarrow \vdash \neg P(A) \rightarrow A \) từ (4) \( \Rightarrow \vdash \neg A \rightarrow P(A) \) từ (5) \( \Rightarrow \vdash P(A) \), áp dụng (13) ta có: \( \vdash P(0=1) \) mâu thuẫn với (10) \( \Rightarrow ⊬ \neg A \)

Ví dụ : mệnh đề “Ta là kể nói dối” Giả sử mệnh đề này đúng thì người nói là người nói dối, nên câu nói ấy là nói dối \( \Rightarrow  \) người đó là người nói thật. (Mâu thuẫn) Giả sử mệnh đề này sai thì người nói là người nói thật, nên câu nói ấy là nói thật  \( \Rightarrow  \) người đó là người nói dối. (Mâu thuẫn)

\( \Rightarrow \) số học là phủ định không đầy đủ.

2, Luôn tồn tại 1 mệnh đề đúng trong N nhưng không thể chứng minh nó trong N.

Chứng minh:( sử dụng A trong (11) mệnh đề tự quy chiếu) +) Giả sử A đúng, sử dụng (11) \(\rightarrow \neg P(A) \) đúng. Nghĩa là: A đúng và không thể chứng minh. +) Giả sử A sai, sử dụng (11) \(\rightarrow \neg P(A) \) sai \(\rightarrow P(A) \) đúng. \( \Rightarrow \) A chứng minh được, \( \Rightarrow \) A đúng. (mâu thuẫn với giả thiết )

tóm lại: bắt buộc A phải đúng và A không thể chứng minh được trong N.

Ví dụ : “Mệnh đề này không có bất cứ chứng minh nào” ( Mệnh đề tự quy chiếu) Chú ý rằng đó là một mệnh đề nói về chính nó. Nếu mệnh đề trên sai, suy ra phủ định của nó đúng, tức là nó có thể chứng minh được, nhưng kết luận này trái với nội dung của chính nó. Vậy buộc nó phải đúng, tức là không thể chứng minh được.

Nhận xét 2 đã giải nghĩa cho nhận xét 1: A ở đây là đúng, nhưng nó không phải là định lý trong N vì ta không thể chứng minh nó.

\( \Rightarrow \) Không thể có hệ tiên đề nào đầy đủ cả.

3, ⊬ \( \neg P(0=1) \)

Chứng minh: Giả sử \( \vdash \neg P(0=1) \) , ta có (13): \( \vdash P(A) \rightarrow P(0=1) \) áp dụng (4) ta được: \( \vdash \neg P(0=1) \rightarrow \neg P(A) \) áp dụng (5) ta được: \( \vdash \neg P(A) \) Từ (11) \( \Rightarrow \neg P(A) \rightarrow A \), áp dụng (5): \( \Rightarrow \vdash A \), từ (7) \( \Rightarrow \vdash P(A) \), áp dụng (13) \( \Rightarrow \vdash P(0=1) \) mâu thuẫn với (10)

\( \Rightarrow  \)⊬ \( \neg P(0=1) \)

Tính nhất quán của số học không thể được chứng minh bằng cách sử dụng cơ chế chứng minh số học.

Kết luận

Nếu các bạn có theo dõi hết phần chứng minh của mình thì phần nào trong tư tưởng của bạn về toán học, khoa học nói chung cũng đã bị ảnh hưởng rồi đúng không.Các bạn sẽ thấy rằng con người sẽ không bao giờ hiểu hết được vũ trụ này, và khoa học cũng sẽ không thể nào giải thích được mọi hiện tượng của tự nhiên. Chúng ta đứng trong vũ trụ này thì sẽ không thể nào giải thích được mọi thứ bến trong, muốn giải thích được thì phải đi ra ngoài vũ trụ này(Nhưng điều này hiện tại là không thể ). Sẽ luôn tồn tại những thứ mà vượt ngoài hiểu biết của khoa học, chẳng hạn như “niềm tin”,  bạn không thể nào biết được “mặt trời sẽ mọc vào sáng mai” bạn không thể chứng minh điều đó, nhưng bạn tin vào điều đó :)) Bài viết của mình không thể nói hết được nội dung và ý nghĩa của định lý này, bài viết này chỉ nhằm mục đích nói tóm tắt một phần ý nghĩa cũng như một cách chứng minh nó, để đọc về định lý này nhiều hơn bạn có thể tìm kiếm những bài viết tương tự trên mạng, có thể ở bài viết nào đó bạn có thể thể tìm được sự tồn tại của “CHÚA TRỜI”, “ĐẤNG TẠO HÓA”

:)) cảm ơn bạn đã theo dõi bài viết.