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:
Ngôn ngữ: Những ký hiệu và cách viết được phép sử dụng.
Tiên đề: Những mệnh đề được chấp nhận làm điểm xuất phát.
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:
Một hệ tiên đề gồm ngôn ngữ, tiên đề và quy tắc suy luận.
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ó.
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.
Không có nhận xét nào:
Đăng nhận xét