Hình 1. Ví dụ về Hydra (cây có gốc). Gốc cây là phần thân. Lá cây là các đầu.
Hercules sẽ chặt từng chiếc đầu của con Hydra. Mỗi khi một đầu bị chặt con Hydra sẽ mọc thêm nhiều đầu mới theo quy tắc như sau:
- Nếu đầu bị chặt nối trực tiếp với thân, không mọc thêm đầu mới.
- Nếu không, gọi $H$ là đầu bị chặt, gọi $P$ là đỉnh cha của $H$ và gọi $G$ là đỉnh cha của $P$ ($P$ không phải gốc cây). Đánh dấu đỉnh $P$ và toàn bộ con cháu của nó (trừ đỉnh $H$ đã bị chặt), và mọc từ đỉnh $G$ thêm một số bản sao (bao nhiêu cũng được) của phần vừa đánh dấu. Người đọc có thể xem Hình 3 về ví dụ sau 3 lần chặt.
Hình 2. Chặt đầu H. Hydra mọc thêm từ G 3 bản sao của phần được đánh dấu màu xanh.
Hình 3. Hydra sau 3 lần chặt.
Câu hỏi: Có cách nào để Hercules tiêu diệt con Hydra hay không?
Trả lời: Hercules luôn có cách để thắng.
Tuy nhiên câu trả lời trên chưa thực sự ấn tượng. Ta có câu trả lời tiếp theo, đó chính là nội dung của định lý Goodstein [1]. Tất nhiên phát biểu định lý hơi rắc rối một chút, nhưng có thể mô tả trực quan như trên.
Định lý Goodstein. Hercules không thể thua. Cho dù có chặt theo cách nào thì sau một số hữu hạn lần, Hydra sẽ bị tiêu diệt.
Để chứng minh định lý này, ta cần sử dụng khái niệm số thứ tự [2] và các phép toán (cộng, nhân, lũy thừa) trên số thứ tự [3]. Người đọc có thể tham khảo chứng minh ở [4]. Nói thêm về điều này. Lý thuyết tập hợp (set theory) do nhà toán học Cantor sáng lập cho phép mô tả các đối tượng vô hạn. Có nhiều vấn đề về vô hạn rất phản trực giác, chẳng hạn, khách sạn vô hạn của Hilbert (xem [5]). Sự thật là các mức độ vô hạn có thể so sánh được với nhau, chẳng hạn: Số các số tự nhiên, số các số nguyên và số các số hữu tỉ đều bằng nhau, nhưng số các số thực thì nhiều hơn số các số tự nhiên (xem thêm: suy luận đường chéo của Cantor [6]). Để đo sự vô hạn lại có hai khái niệm: Số thứ tự (ordinal number) và số đếm (cardinal number). Số thứ tự hữu hạn và số đếm hữu hạn đều giống nhau, đó là các số tự nhiên quen thuộc. Nhưng số thứ tự vô hạn và số đếm vô hạn rất khác nhau. Các phép toán trên số thứ tự vô hạn khó hơn nhiều. Chẳng hạn, nếu $\omega$ là số thứ tự vô hạn nhỏ nhất thì $1 + \omega = \omega$, nhưng $\omega + 1 > \omega$. Ngược lại, nếu $a, b$ là hai số đếm và một trong hai là vô hạn thì ta luôn có $a+b = ab = \text{max}\{a,b\}$.
Quay lại với định lý Goodstein. Đây là một định lý có thể phát biểu bằng số học sơ cấp (số học sơ cấp, theo ý người viết, là hệ tiên đề Peano, xem [7]). Ta có
Định lý Kirby-Paris. Lý thuyết nào đủ mạnh để chứng minh định lý Goodstein thì cũng đủ mạnh để chứng minh rằng số học sơ cấp là phi mâu thuẫn (consistent).
Chứng minh của định lý này khó hơn nhiều [8]. Định lý Gödel (Gödel's second incompleteness theorem) nói rằng, nếu số học sơ cấp có thể chứng minh rằng bản thân nó là phi mâu thuẫn, thì thực ra nó là mâu thuẫn [9]. Như vậy, định lý Goodstein không thể chứng minh được bằng số học sơ cấp (trừ khi bản thân số học sơ cấp là mâu thuẫn, chú ý rằng một lý thuyết mâu thuẫn có thể chứng minh mọi thứ, nghĩa là nó không phân biệt được đúng sai). Có rất nhiều chứng minh rằng số học sơ cấp là phi mâu thuẫn. Chẳng hạn, Gentzen, một nhà toán học, logic học nổi tiếng, đã đưa ra không dưới 4 chứng minh. Tất nhiên, các chứng minh này phải dùng lý thuyết bên ngoài số học sơ cấp. Nếu muốn chứng minh lý thuyết này là phi mâu thuẫn thì lại phải tiếp tục mở rộng nó. Không có bữa trưa miễn phí trong logic bậc nhất.
Người đọc có thể thử sức với trò chơi tiêu diệt Hydra ở [11].
Tham khảo:
[1] https://en.wikipedia.org/wiki/Goodstein%27s_theorem
[2] https://en.wikipedia.org/wiki/Ordinal_number
[3] https://en.wikipedia.org/wiki/Ordinal_arithmetic
[6] https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
[7] https://en.wikipedia.org/wiki/Peano_axioms
[8] L. Kirby, J. Paris, Accessible Independence Results for Peano Arithmetic. https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/blms/14.4.285
[9] https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems
[10] http://home.uchicago.edu/~wwtx/Gentzen.original.pdf
[11] https://github.com/andrejbauer/hydra
Bài viết đã được chỉnh sửa nội dung bởi nmlinh16: 21-09-2020 - 20:20
