Định lý bất toàn, Bài 3: Đánh số Gödel – Bí mật biến mọi công thức toán học thành những con số

Trong bài viết trước, chúng ta đã tìm hiểu về hệ tiên đề, các quy tắc suy luận và hai khái niệm quan trọng là tính nhất quán và tính đầy đủ. Đó là những nền tảng cần thiết để hiểu Định lý Bất toàn của Kurt Gödel.

Trong bài này, chúng ta sẽ tiếp cận một ý tưởng đặc biệt thông minh, có thể xem là chiếc chìa khóa mở ra toàn bộ chứng minh của Gödel:

Liệu chúng ta có thể biến mọi công thức toán học, mọi phát biểu logic và thậm chí cả những chứng minh toán học thành các con số tự nhiên hay không?

Câu trả lời là có.

Gödel đã tìm ra một phương pháp để thực hiện điều đó. Phương pháp này được gọi là đánh số Gödel (Gödel numbering).

Thoạt nhìn, việc gán số cho các ký hiệu toán học có vẻ chẳng có gì đặc biệt. Nhưng khi kết hợp với một kỹ thuật mã hóa thích hợp, chúng ta có thể biến những câu nói về công thức toán học thành những câu nói về số tự nhiên.

Và nhờ đó, toán học có thể bắt đầu nói về chính nó.

1. Ý tưởng: Mỗi ký hiệu toán học có một mã số riêng

Hãy xét một biểu thức toán học rất quen thuộc:

x + 2 = 5

Biểu thức này được tạo thành từ những ký hiệu:

• x: biến số.

• +: phép cộng.

• 2 và 5: các chữ số.

• =: dấu bằng.

Bây giờ, hãy tưởng tượng chúng ta quy định mỗi ký hiệu có một mã số riêng:

Ký hiệu	Mã số
x	1
+	2
=	3
0	4
1	5
2	6
3	7
4	8
5	9

Theo quy ước này, biểu thức:

x + 2 = 5

được chuyển thành dãy số:

1, 2, 6, 3, 9

Như vậy, một biểu thức toán học đã được chuyển thành một dãy số tự nhiên.

Tuy nhiên, chúng ta mới chỉ giải quyết được một nửa vấn đề.

Một dãy số vẫn chưa phải là một số duy nhất. Gödel cần một cách để biến cả dãy số đó thành một số tự nhiên duy nhất.

Đây là lúc một tính chất đặc biệt của số nguyên tố được sử dụng.

2. Số nguyên tố và khả năng mã hóa

Chúng ta đều biết số nguyên tố là những số tự nhiên lớn hơn 1 chỉ có hai ước dương là 1 và chính nó.

Ví dụ:

2, 3, 5, 7, 11, 13, 17, 19, 23,...

Một tính chất cực kỳ quan trọng của số nguyên tố là:

Mọi số nguyên dương lớn hơn 1 đều có một cách phân tích duy nhất thành tích các thừa số nguyên tố, nếu không xét thứ tự các thừa số.

Ví dụ:

60 = 2² × 3 × 5

Hay:

360 = 2³ × 3² × 5

Tính chất này được gọi là định lý cơ bản của số học.

Gödel đã tận dụng tính chất đó để mã hóa một dãy số thành một số tự nhiên duy nhất.

Ý tưởng như sau.

Giả sử chúng ta có một dãy số:

a₁, a₂, a₃, ..., aₙ

Ta lấy n số nguyên tố đầu tiên:

2, 3, 5, 7, 11, ...

Sau đó, xây dựng số:

N = 2^a₁ × 3^a₂ × 5^a₃ × 7^a₄ × ...

Nói cách khác, mỗi số nguyên tố được dùng để mã hóa một vị trí trong dãy, còn số mũ của nó chính là giá trị tại vị trí đó.

Đây là một cách mã hóa rất thông minh.

Vì phân tích một số thành thừa số nguyên tố là duy nhất, chúng ta có thể khôi phục lại toàn bộ dãy ban đầu từ số N.

3. Thử thực hiện một ví dụ cụ thể

Giả sử chúng ta muốn mã hóa dãy số:

1, 2, 3

Ta thực hiện theo công thức:

N = 2¹ × 3² × 5³

Tính toán:

N = 2 × 9 × 125

N = 2250

Như vậy, dãy số:

1, 2, 3

được mã hóa thành số:

2250

Bây giờ, giả sử chỉ biết số 2250, liệu chúng ta có thể khôi phục dãy ban đầu không?

Có.

Ta phân tích:

2250 = 2 × 3² × 5³

Đọc các số mũ theo thứ tự các số nguyên tố 2, 3, 5, ta thu được:

1, 2, 3

Dãy số ban đầu đã được khôi phục hoàn toàn.

Một ví dụ khác:

Dãy số 2, 1, 4 được mã hóa thành:

N = 2² × 3¹ × 5⁴

= 4 × 3 × 625

= 7500

Ta có thể kiểm tra ngược:

7500 = 2² × 3 × 5⁴

Suy ra dãy ban đầu là:

2, 1, 4.

Điều đáng chú ý là hai dãy số khác nhau sẽ tạo ra hai số mã hóa khác nhau.

Chẳng hạn:

• Dãy 1, 2, 3 tạo ra số 2250.

• Dãy 2, 1, 4 tạo ra số 7500.

Không có sự nhầm lẫn giữa hai dãy.

Đây chính là nguyên tắc cốt lõi của phương pháp mã hóa Gödel.

4. Mã hóa một công thức toán học hoàn chỉnh

Bây giờ, chúng ta quay lại biểu thức:

x + 2 = 5

Theo bảng mã ở phần 1, biểu thức này tương ứng với dãy số:

1, 2, 6, 3, 9

Áp dụng phương pháp mã hóa bằng số nguyên tố:

N = 2¹ × 3² × 5⁶ × 7³ × 11⁹

Đây là một số tự nhiên rất lớn.

Chúng ta không cần tính giá trị chính xác của nó. Điều quan trọng là:

Công thức x + 2 = 5 đã được đại diện bởi một số tự nhiên duy nhất.

Nếu biết số mã hóa, chúng ta có thể phân tích nó thành thừa số nguyên tố và khôi phục lại dãy ký hiệu ban đầu.

Như vậy, một công thức toán học vốn được viết bằng các ký hiệu x, +, = đã được chuyển thành một con số.

Đây là một bước chuyển đổi rất quan trọng.

5. Không chỉ công thức, cả chứng minh toán học cũng có thể được mã hóa

Đến đây, chúng ta mới mã hóa được các công thức.

Nhưng mục tiêu của Gödel còn lớn hơn thế.

Ông muốn mã hóa cả những chứng minh toán học.

Hãy nhớ rằng một chứng minh toán học là một chuỗi hữu hạn các công thức, trong đó mỗi công thức phải được tạo ra từ tiên đề hoặc suy ra hợp lệ từ những công thức trước đó.

Ví dụ, giả sử một chứng minh gồm ba dòng:

1. A → B

2. A

3. B

Dòng thứ ba được suy ra từ hai dòng đầu bằng quy tắc Modus Ponens.

Nếu mỗi công thức đã có một số Gödel riêng, chúng ta có thể xem toàn bộ chứng minh là một dãy số.

Sau đó, tiếp tục sử dụng phương pháp mã hóa bằng số nguyên tố để biến cả dãy số ấy thành một số tự nhiên duy nhất.

Như vậy:

• Một ký hiệu được mã hóa thành một số.

• Một công thức được mã hóa thành một số.

• Một chuỗi công thức được mã hóa thành một số.

• Một chứng minh hoàn chỉnh cũng được mã hóa thành một số.

Đây là một kết quả vô cùng quan trọng.

Bởi vì từ đây, chúng ta có thể nghiên cứu các chứng minh toán học bằng cách nghiên cứu những tính chất của số tự nhiên.

6. Một bước tiến lớn: Biến câu hỏi logic thành câu hỏi số học

Hãy tưởng tượng chúng ta đặt câu hỏi:

"Có tồn tại một chứng minh cho công thức A hay không?"

Thông thường, đây là một câu hỏi thuộc về logic.

Nhưng nếu mỗi chứng minh đều có một mã số, câu hỏi trên có thể được chuyển thành:

"Có tồn tại một số tự nhiên n sao cho n mã hóa một chứng minh hợp lệ của A hay không?"

Đây đã là một câu hỏi về số tự nhiên.

Tương tự, chúng ta có thể đặt câu hỏi:

• Một số n có phải là mã của một công thức hợp lệ không?

• Một số n có phải là mã của một chứng minh không?

• Một chứng minh có kết luận là công thức A hay không?

• Có tồn tại một chứng minh của công thức A không?

Những câu hỏi này có thể được diễn đạt bằng các quan hệ số học.

Đó chính là bước chuyển quan trọng mà Gödel đã thực hiện.

Ông đã đưa những khái niệm tưởng như thuộc về thế giới logic trừu tượng vào thế giới của các số tự nhiên.

7. Vì sao phát hiện này lại dẫn đến Định lý Bất toàn?

Đến đây, chúng ta đã có một công cụ rất đặc biệt.

Giả sử có một hệ thống toán học đủ mạnh để nghiên cứu số tự nhiên.

Hệ thống đó có thể:

• Mã hóa các công thức thành số.

• Mã hóa các chứng minh thành số.

• Diễn đạt những quan hệ giữa các mã số.

• Diễn đạt câu hỏi liệu một công thức có thể được chứng minh hay không.

Điều này tạo ra một khả năng rất kỳ lạ.

Chúng ta có thể xây dựng một mệnh đề toán học mà nội dung của nó nói về chính khả năng chứng minh của nó.

Hãy tưởng tượng có một câu như sau:

"Tôi không thể được chứng minh."

Nếu câu này đúng, thì nó không thể được chứng minh.

Nếu nó có thể được chứng minh, thì nội dung của nó lại nói rằng nó không thể được chứng minh.

Nghe giống một nghịch lý logic nổi tiếng:

"Câu này là sai."

Tuy nhiên, mệnh đề Gödel không đơn giản là một trò chơi ngôn ngữ như vậy. Nó được xây dựng bằng những công thức số học chính xác, dựa trên kỹ thuật mã hóa mà chúng ta vừa tìm hiểu.

Đây là điểm khác biệt căn bản giữa một nghịch lý ngôn ngữ thông thường và lập luận toán học của Gödel.

8. Điều cần nhớ sau bài viết này

Chúng ta đã đi qua một trong những ý tưởng quan trọng nhất của chứng minh Gödel.

Hãy tóm tắt lại:

Thứ nhất: Mỗi ký hiệu toán học được gán một số tự nhiên.

Thứ hai: Mỗi công thức toán học trở thành một dãy số.

Thứ ba: Dãy số có thể được mã hóa thành một số tự nhiên duy nhất bằng cách sử dụng các số nguyên tố.

Thứ tư: Một chứng minh toán học, vốn là một chuỗi công thức, cũng có thể được mã hóa thành một số tự nhiên.

Thứ năm: Những câu hỏi về công thức và chứng minh có thể được chuyển thành những câu hỏi về số học.

Đây chính là nền móng để Gödel xây dựng lập luận bất toàn.

Tuy nhiên, có một câu hỏi vẫn còn bỏ ngỏ:

Làm thế nào để một công thức toán học có thể nói về chính số Gödel của nó?

Làm thế nào để xây dựng một mệnh đề có nội dung:

"Mệnh đề mang số Gödel này không thể được chứng minh trong hệ thống đang xét"?

Đây chính là vấn đề mà chúng ta sẽ giải quyết trong bài tiếp theo.

Và có lẽ, đó cũng là phần hấp dẫn nhất của toàn bộ câu chuyện.

Định lý bất toàn, Bài 2: Hệ tiên đề là gì? Nền móng để hiểu Định lý Bất toàn của Gödel

Trong bài viết trước, chúng ta đã biết rằng năm 1931, nhà toán học Kurt Gödel đã chứng minh một kết quả gây chấn động: Trong một hệ thống toán học đủ mạnh và nhất quán, luôn tồn tại những mệnh đề mà hệ thống đó không thể chứng minh hoặc bác bỏ.

Nhưng có một câu hỏi cần được làm rõ trước khi chúng ta tìm hiểu chứng minh của Gödel:

Một hệ thống toán học thực chất là gì?

Chúng ta thường nghĩ toán học là một tập hợp những công thức, định lý và phép tính. Tuy nhiên, ở góc độ logic, toán học có thể được nhìn nhận như một hệ thống được xây dựng từ một số nguyên tắc ban đầu, sau đó sử dụng các quy tắc suy luận để tạo ra những kết quả mới.

Hệ thống ấy được gọi là hệ tiên đề.

Để hiểu được Định lý Bất toàn, trước tiên chúng ta cần hiểu thật rõ khái niệm này.

1. Tiên đề là gì?

Trong toán học, tiên đề là một mệnh đề được chấp nhận làm điểm xuất phát mà không cần chứng minh trong hệ thống đang xét.

Ví dụ, trong hình học Euclid, chúng ta có một tiên đề nổi tiếng:

"Qua một điểm nằm ngoài một đường thẳng, chỉ có duy nhất một đường thẳng song song với đường thẳng đã cho."

Chúng ta không chứng minh tiên đề này từ những kết quả khác trong hình học Euclid. Thay vào đó, chúng ta chấp nhận nó và sử dụng nó để xây dựng các định lý tiếp theo.

Một ví dụ khác là các tiên đề Peano về số tự nhiên. Chúng mô tả những tính chất cơ bản của các số:

• Có số 0.

• Mỗi số tự nhiên có một số kế tiếp.

• Hai số khác nhau không thể có cùng số kế tiếp.

• Số 0 không phải là số kế tiếp của bất kỳ số tự nhiên nào.

• Nếu một tính chất đúng với 0 và khi đúng với một số thì cũng đúng với số kế tiếp của nó, thì tính chất đó đúng với mọi số tự nhiên.

Tiên đề cuối cùng chính là nguyên lý quy nạp toán học quen thuộc mà học sinh phổ thông thường sử dụng.

Như vậy, rất nhiều kiến thức toán học mà chúng ta học ở trường thực chất được xây dựng trên những nguyên tắc nền tảng như thế.

2. Từ tiên đề đến định lý: Một cỗ máy suy luận

Có tiên đề rồi, chúng ta cần một cách để suy ra những kết quả mới.

Công cụ đó là các quy tắc suy luận.

Hãy xét một ví dụ đơn giản:

• Nếu trời mưa thì đường ướt.

• Trời đang mưa.

Từ hai điều trên, chúng ta kết luận:

• Đường đang ướt.

Đây là một quy tắc suy luận rất cơ bản trong logic, được gọi là Modus Ponens.

Có thể viết dưới dạng:

Nếu A suy ra B, và A đúng, thì B đúng.

Trong ký hiệu logic:

A → B

A

Suy ra B.

Trong toán học, chúng ta cũng làm việc tương tự. Bắt đầu từ những tiên đề, áp dụng các quy tắc suy luận, chúng ta tạo ra những mệnh đề mới. Những mệnh đề được suy ra bằng một chuỗi lập luận hợp lệ được gọi là các định lý.

Do đó, một hệ thống toán học có thể được mô tả bằng ba thành phần:

1. Ngôn ngữ: Những ký hiệu và cách viết được phép sử dụng.

2. Tiên đề: Những mệnh đề được chấp nhận làm điểm xuất phát.

3. Quy tắc suy luận: Những quy định cho phép chúng ta suy ra mệnh đề mới từ những mệnh đề đã có.

Đây chính là hình ảnh đơn giản nhất của một hệ tiên đề hình thức.

3. Chứng minh toán học có phải là một phép tính?

Hãy thử tưởng tượng chúng ta cần chứng minh:

Nếu A đúng và A kéo theo B, thì B đúng.

Một người có thể hiểu ngay điều này bằng trực giác. Nhưng trong logic hình thức, chúng ta cần quy định chính xác từng bước được phép thực hiện.

Một chứng minh toán học có thể được xem như một danh sách hữu hạn các dòng. Mỗi dòng phải thỏa mãn ít nhất một trong những điều kiện:

• Là một tiên đề.

• Là một giả thiết đã được chấp nhận.

• Được suy ra từ những dòng trước đó bằng một quy tắc suy luận hợp lệ.

Nếu một chứng minh tuân thủ đầy đủ các quy tắc, chúng ta gọi nó là chứng minh hợp lệ.

Điều thú vị là việc kiểm tra một chứng minh có hợp lệ hay không về nguyên tắc có thể được thực hiện bằng những thao tác cơ học.

Một máy tính có thể kiểm tra từng dòng, xác định xem dòng đó có phải là tiên đề hay có được suy ra hợp lệ từ các dòng trước hay không.

Đây là một trong những ý tưởng nền tảng của khoa học máy tính và các hệ thống chứng minh tự động ngày nay.

Và cũng chính điều này sẽ đóng vai trò rất quan trọng trong chứng minh của Gödel.

4. Hai tính chất quan trọng: Nhất quán và đầy đủ

Bây giờ chúng ta đến với hai khái niệm cốt lõi.

Tính nhất quán (Consistency)

Một hệ tiên đề được gọi là nhất quán nếu nó không thể chứng minh đồng thời một mệnh đề và phủ định của mệnh đề đó.

Ví dụ, nếu hệ thống chứng minh được cả hai kết luận:

A đúng.

A không đúng.

Thì hệ thống đó chứa mâu thuẫn và được gọi là không nhất quán.

Tại sao tính chất này quan trọng?

Bởi vì trong logic cổ điển, nếu một hệ thống chứa mâu thuẫn, chúng ta có thể suy ra bất kỳ mệnh đề nào từ hệ thống đó.

Nói cách khác, một hệ thống không nhất quán sẽ mất đi khả năng phân biệt giữa những kết quả có cơ sở và những kết quả tùy ý.

Tính đầy đủ (Completeness)

Một hệ thống được gọi là đầy đủ đối với một lớp mệnh đề nếu với mọi mệnh đề trong lớp đó, hệ thống có thể chứng minh mệnh đề ấy hoặc chứng minh phủ định của nó.

Ví dụ, xét mệnh đề A.

Nếu hệ thống có thể chứng minh A, hoặc có thể chứng minh không A, thì hệ thống quyết định được mệnh đề đó.

Nếu có một mệnh đề mà hệ thống không thể chứng minh cả A lẫn không A, thì mệnh đề đó là bất khả quyết định trong hệ thống.

Đây chính là hiện tượng mà Định lý Bất toàn của Gödel sẽ chỉ ra.

Tuy nhiên, cần phân biệt hai khái niệm:

• Tính đầy đủ về mặt logic: mọi hệ quả logic của các tiên đề đều có thể chứng minh được.

• Tính đầy đủ về mặt quyết định mệnh đề: với mỗi mệnh đề đang xét, hệ thống chứng minh được nó hoặc phủ định của nó.

Hai khái niệm này không hoàn toàn giống nhau. Định lý Bất toàn nói đến giới hạn thứ hai, trong khi một hệ thống hình thức vẫn có thể đầy đủ theo nghĩa logic thứ nhất.

5. Một ví dụ nhỏ: Hệ tiên đề có thể không trả lời được mọi câu hỏi

Hãy tưởng tượng chúng ta xây dựng một hệ thống toán học chỉ có một số tiên đề rất hạn chế.

Chẳng hạn, hệ thống chỉ nghiên cứu các tính chất của một số tự nhiên nhất định và không có đủ quy tắc để xử lý tất cả các vấn đề liên quan.

Khi đặt một câu hỏi mới, có thể xảy ra ba trường hợp:

Trường hợp 1: Hệ thống chứng minh được mệnh đề A.

Trường hợp 2: Hệ thống chứng minh được mệnh đề phủ định của A.

Trường hợp 3: Hệ thống không chứng minh được cả A lẫn phủ định của A.

Trường hợp thứ ba cho thấy hệ thống không đủ sức quyết định câu hỏi đang xét.

Điều này không nhất thiết có nghĩa là mệnh đề A không có giá trị đúng hoặc sai. Nó chỉ có nghĩa rằng những tiên đề và quy tắc hiện tại chưa đủ để đưa ra kết luận.

Trong toán học, hiện tượng này không phải là điều xa lạ.

Một ví dụ nổi tiếng là giả thuyết continuum trong lý thuyết tập hợp. Với những tiên đề thông dụng của lý thuyết tập hợp ZFC, nếu ZFC nhất quán, cả giả thuyết continuum lẫn phủ định của nó đều không thể được chứng minh từ các tiên đề ấy.

Đây là một ví dụ thực tế cho thấy có những câu hỏi toán học nằm ngoài khả năng quyết định của một hệ tiên đề cụ thể.

6. Vì sao chúng ta cần một hệ tiên đề đủ mạnh?

Đến đây, có thể bạn sẽ đặt câu hỏi:

Nếu một hệ thống nhỏ không thể trả lời mọi câu hỏi, tại sao chúng ta không xây dựng một hệ thống lớn hơn, với thật nhiều tiên đề hơn?

Đó cũng chính là một trong những ý tưởng mà các nhà toán học đã theo đuổi.

Nhưng Gödel đã phát hiện ra rằng vấn đề không đơn giản như vậy.

Ông không nghiên cứu những hệ thống quá yếu, chỉ có thể thực hiện vài phép tính đơn giản. Ông nghiên cứu những hệ thống đủ mạnh để biểu diễn số học cơ bản.

Nói cách khác, hệ thống phải có khả năng nói về các số tự nhiên, phép cộng, phép nhân và những tính chất cơ bản của chúng.

Và nếu hệ thống ấy thỏa mãn những điều kiện nhất định, đặc biệt là có thể mô tả các phép chứng minh một cách hình thức, thì định lý Bất toàn sẽ xuất hiện.

Dù chúng ta bổ sung thêm những tiên đề mới, một giới hạn tương tự vẫn có thể xuất hiện ở hệ thống mở rộng, miễn là hệ thống mới tiếp tục đáp ứng những điều kiện thích hợp.

Đây chính là điều làm cho kết quả của Gödel trở nên sâu sắc.

7. Chuẩn bị cho ý tưởng quan trọng nhất của Gödel

Trong bài tiếp theo, chúng ta sẽ bắt đầu tiếp cận một ý tưởng có vẻ kỳ lạ nhưng cực kỳ quan trọng:

Mỗi công thức toán học có thể được gán một số tự nhiên duy nhất.

Ví dụ, chúng ta có thể quy định:

• Ký hiệu cộng được gán một số.

• Ký hiệu nhân được gán một số.

• Dấu bằng được gán một số.

• Các biến x, y, z được gán những số khác nhau.

• Mỗi công thức được biểu diễn bằng một dãy ký hiệu, từ đó có thể mã hóa thành một số tự nhiên.

Kỹ thuật này được gọi là đánh số Gödel (Gödel numbering).

Nhờ đó, những phát biểu về công thức toán học và chứng minh toán học có thể được chuyển thành những phát biểu về số tự nhiên.

Đây là bước ngoặt quan trọng nhất trong chứng minh của Gödel.

Bởi nếu toán học có thể mã hóa chính những chứng minh của mình thành các con số, thì chúng ta có thể xây dựng một mệnh đề toán học nói về khả năng chứng minh của chính nó.

Và từ đó, cánh cửa dẫn đến Định lý Bất toàn thực sự mở ra.

Hãy nhớ ba điều quan trọng của bài viết này:

1. Một hệ tiên đề gồm ngôn ngữ, tiên đề và quy tắc suy luận.

2. Tính nhất quán có nghĩa là hệ thống không chứng minh được đồng thời một mệnh đề và phủ định của nó.

3. Tính đầy đủ theo nghĩa quyết định mệnh đề có nghĩa là hệ thống có thể chứng minh một mệnh đề hoặc phủ định của nó.

Để hiểu Gödel, chúng ta cần nắm chắc ba khái niệm này trước khi đi sâu vào những kỹ thuật toán học phức tạp hơn.

Định lý Bất toàn, Bài 1: Khi toán học gặp giới hạn của chính mình

Có một câu hỏi nghe tưởng như rất đơn giản: Liệu chúng ta có thể xây dựng một hệ thống toán học đủ mạnh để chứng minh mọi mệnh đề toán học đúng hay không?

Trong một thời gian dài, nhiều nhà toán học tin rằng câu trả lời có thể là “có”. Nếu toán học được xây dựng từ những tiên đề rõ ràng và những quy tắc suy luận chặt chẽ, biết đâu chúng ta có thể tạo ra một cỗ máy lý luận hoàn hảo: mọi mệnh đề đều có thể được quyết định là đúng hoặc sai, miễn là chúng ta đủ thông minh và kiên trì.

Nhưng năm 1931, một nhà toán học người Áo tên là Kurt Gödel đã chứng minh rằng giấc mơ ấy có một giới hạn rất sâu sắc.

Ông công bố hai kết quả nổi tiếng ngày nay được gọi là Định lý Bất toàn của Gödel.

Điều thú vị là Gödel không chứng minh rằng toán học “sai”. Ngược lại, ông cho thấy một điều tinh tế hơn nhiều: bất kỳ hệ tiên đề đủ mạnh nào cũng sẽ có những giới hạn mà bản thân hệ thống đó không thể vượt qua.

1. Trước Gödel, người ta muốn xây dựng một “nền móng hoàn hảo”

Đầu thế kỷ XX, toán học đang trải qua một cuộc khủng hoảng về nền tảng.

Các nhà toán học muốn biết chính xác: toán học dựa trên cái gì? Một chứng minh toán học hợp lệ là gì? Có thể biến toàn bộ toán học thành một hệ thống các quy tắc cơ học, rõ ràng đến mức một cỗ máy cũng có thể kiểm tra được hay không?

Nhà toán học David Hilbert là một trong những người thúc đẩy mạnh mẽ chương trình này. Một trong những mục tiêu quan trọng là xây dựng một hệ thống toán học vừa nhất quán — không thể chứng minh đồng thời một mệnh đề và phủ định của nó — vừa đủ mạnh để xử lý những phần toán học quan trọng, đồng thời có thể xác định một cách có hệ thống mệnh đề nào là đúng.

Nói nôm na, người ta muốn tạo ra một “bộ luật giao thông” hoàn chỉnh cho thế giới toán học.

Nếu có một mệnh đề, chúng ta chỉ cần áp dụng đúng các quy tắc, cuối cùng sẽ biết nó đúng hay sai.

Ý tưởng rất đẹp.

Nhưng rồi Gödel xuất hiện.

2. Bí quyết kỳ lạ: Cho toán học “nói về chính nó”

Điều đáng kinh ngạc trong công trình của Gödel là ông tìm ra cách để một hệ thống toán học có thể mã hóa những phát biểu về chính hệ thống đó.

Hãy tưởng tượng một thư viện khổng lồ chứa toàn bộ các quy tắc và chứng minh toán học. Mỗi quy tắc, mỗi công thức, mỗi chứng minh đều được gán một con số.

Khi đó, thay vì nói:

“Đây là một chứng minh hợp lệ.”

chúng ta có thể biến câu nói đó thành một phát biểu về những con số.

Gödel đã phát triển ý tưởng này thành thứ ngày nay thường được gọi là đánh số Gödel.

Nhờ vậy, những câu tưởng như thuộc về “ngôn ngữ” có thể được chuyển thành những câu nói về số tự nhiên.

Và đây chính là chiếc chìa khóa.

Bởi khi một hệ thống toán học đủ mạnh có thể nói về chính các công thức và chứng minh của nó, chúng ta có thể tạo ra một mệnh đề có nội dung đại khái như:

“Mệnh đề này không thể được chứng minh trong hệ thống này.”

Nghe hơi giống một câu đố mẹo.

Nhưng nó không phải trò chơi chữ. Gödel đã biến ý tưởng này thành một lập luận toán học chính xác.

3. Định lý Bất toàn thứ nhất nói gì?

Một cách diễn đạt đơn giản của Định lý Bất toàn thứ nhất là:

Trong mọi hệ tiên đề nhất quán, đủ mạnh để mô tả số học cơ bản, tồn tại những mệnh đề mà hệ thống đó không thể chứng minh cũng không thể bác bỏ.

Điều này có nghĩa là nếu chúng ta xây dựng một hệ thống toán học đủ mạnh và hệ thống đó không chứa mâu thuẫn, thì sẽ luôn tồn tại những câu hỏi mà các quy tắc bên trong hệ thống không đủ để trả lời.

Đây là một phát hiện gây chấn động.

Hãy hình dung một trò chơi có một bộ luật rất hoàn chỉnh. Bạn có thể chơi hàng triệu ván và áp dụng luật chính xác tuyệt đối. Nhưng nếu bộ luật đủ phức tạp, sẽ có những câu hỏi về trò chơi mà chính bộ luật ấy không thể quyết định.

Điều đó không có nghĩa là câu hỏi vô nghĩa.

Nó chỉ có nghĩa là bộ luật hiện tại không đủ để trả lời.

Trong toán học cũng vậy.

Một mệnh đề có thể đúng, nhưng không thể chứng minh được từ những tiên đề mà chúng ta đang sử dụng.

4. “Đúng” và “có thể chứng minh” không phải lúc nào cũng giống nhau

Đây có lẽ là phần sâu sắc nhất của định lý.

Trong suy nghĩ thông thường, chúng ta dễ đồng nhất hai khái niệm:

Đúng = chứng minh được.

Gödel cho thấy sự đồng nhất này không thể duy trì trong mọi hệ thống toán học đủ mạnh.

Có những mệnh đề mà từ góc nhìn bên ngoài, chúng ta có thể xác định chúng là đúng, nhưng hệ thống ban đầu không thể chứng minh chúng.

Để chứng minh thêm những mệnh đề ấy, chúng ta có thể đưa thêm tiên đề mới vào hệ thống.

Nhưng khi hệ thống đã mạnh hơn, một lần nữa có thể xuất hiện những mệnh đề mới mà hệ thống mới cũng không thể quyết định.

Nói cách khác:

Thêm tiên đề có thể mở rộng biên giới của toán học, nhưng không thể tạo ra một hệ thống đủ mạnh mà không còn bất kỳ giới hạn nào.

Đây là lý do định lý của Gödel thường được xem là một trong những kết quả sâu sắc nhất của logic toán học hiện đại.

5. Định lý Bất toàn thứ hai còn mạnh hơn

Nếu định lý thứ nhất đã gây kinh ngạc thì định lý thứ hai còn đáng chú ý hơn.

Một cách diễn đạt phổ thông là:

Một hệ thống toán học đủ mạnh và nhất quán không thể tự chứng minh rằng chính nó là nhất quán.

Hãy tưởng tượng bạn có một chiếc máy kiểm tra toán học. Nó được thiết kế để xác nhận rằng tất cả các quy tắc của nó không bao giờ dẫn đến mâu thuẫn.

Gödel cho thấy nếu chiếc máy ấy đủ mạnh và thực sự nhất quán, thì nó không thể dùng chính các quy tắc của mình để hoàn toàn chứng minh sự nhất quán của bản thân.

Muốn chứng minh điều đó, về cơ bản chúng ta phải đứng ở một hệ thống mạnh hơn — hoặc sử dụng những giả định bổ sung.

Và hệ thống mạnh hơn ấy lại có những giới hạn riêng.

Có cảm giác như chúng ta đang leo một chiếc cầu thang không có bậc cuối cùng.

6. Có phải Gödel chứng minh rằng toán học không đáng tin?

Không.

Đây là một hiểu lầm khá phổ biến.

Định lý Bất toàn không nói rằng mọi thứ trong toán học đều mơ hồ, tương đối hay không thể biết được.

Phần lớn toán học vẫn hoạt động hoàn toàn bình thường. Chúng ta vẫn có thể chứng minh vô số định lý, tính toán, xây dựng lý thuyết và ứng dụng toán học vào vật lý, kỹ thuật, máy tính…

Điều Gödel chỉ ra là một giới hạn về nguyên tắc:

Không có một hệ thống tiên đề duy nhất, đủ mạnh và nhất quán, có thể quyết định tất cả mọi mệnh đề toán học.

Đây không phải thất bại của toán học.

Thực ra, nó cho chúng ta hiểu rõ hơn bản chất của toán học.

7. Vì sao một định lý trừu tượng lại quan trọng?

Ảnh hưởng của Gödel vượt xa logic toán học.

Những ý tưởng liên quan đến định lý Bất toàn đã trở thành một phần quan trọng trong triết học toán học, khoa học máy tính và lý thuyết tính toán.

Nó giúp chúng ta hiểu rằng có những giới hạn không phải do máy tính quá chậm, con người chưa đủ thông minh hay dữ liệu chưa đủ nhiều.

Có những vấn đề không thể giải quyết bằng một hệ thống quy tắc nhất định, dù chúng ta có kiên nhẫn đến đâu.

Đó là một ý tưởng rất quan trọng trong thời đại máy tính và trí tuệ nhân tạo.

Nhưng cũng cần thận trọng: định lý Bất toàn không đơn giản có nghĩa là “máy tính không thể làm được mọi thứ”, cũng không phải bằng chứng trực tiếp rằng trí tuệ con người vượt trội máy móc. Những kết luận như vậy cần thêm nhiều lập luận khác.

8. Một cánh cửa mở ra vô tận

Trước Gödel, người ta có thể mơ về một cuốn sách toán học tối hậu: viết ra những tiên đề hoàn hảo, sau đó dùng các quy tắc logic để giải quyết mọi câu hỏi.

Gödel cho thấy cuốn sách ấy, nếu đủ mạnh, sẽ luôn có những trang mà chính nó không thể viết tiếp.

Nhưng có lẽ đó không phải là một tin xấu.

Bởi chính giới hạn ấy cũng mở ra một chân trời mới.

Khi gặp một mệnh đề không thể chứng minh từ hệ tiên đề hiện tại, chúng ta có thể đặt câu hỏi:

Nếu thêm mệnh đề này làm tiên đề thì sao?

Và từ đó, một hệ thống toán học mới ra đời.

Rồi hệ thống mới lại có những câu hỏi mới.

Toán học vì thế không giống một thành phố có bức tường cuối cùng. Nó giống một cuộc thám hiểm: mỗi khi chúng ta đi đến rìa của bản đồ, chúng ta không nhất thiết phải quay về.

Chúng ta có thể vẽ thêm bản đồ.

Đó có lẽ là điều đẹp nhất mà Định lý Bất toàn để lại.

Gödel không chứng minh rằng con người sẽ không bao giờ hiểu hết toán học.

Ông chỉ cho chúng ta thấy rằng trong một hệ thống đủ mạnh, luôn tồn tại những điều nằm ngoài khả năng chứng minh của chính hệ thống đó.

Và đôi khi, trong toán học, phát hiện ra một giới hạn không phải là đóng một cánh cửa.

Nó là phát hiện ra rằng phía bên kia cánh cửa còn có cả một thế giới mới.