Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh
- - - - -

Hercules và Hydra


  • Please log in to reply
Chủ đề này có 2 trả lời

#1 nmlinh16

nmlinh16

    Binh nhất

  • Thành viên mới
  • 27 Bài viết
  • Giới tính:Nam
  • Đến từ:Hạ Long
  • Sở thích:Algebraic invariant theory, Algebraic topology, Analytic number theory

Đã gửi 21-09-2020 - 19:06

Giả sử Hercules phải tiêu diệt một con Hydra. Nó được mô tả như ở Hình 1. Nếu ai đã biết đến lý thuyết đồ thị: Một con Hydra đơn giản là một cây có gốc (rooted tree). Gốc cây (màu đỏ) là thân của Hydra và lá cây (màu xanh lá) là các đầu của nó.
Trong một cây có gốc, nếu hai đỉnh (node) được nối với nhau thì đỉnh gần gốc hơn sẽ được gọi là đỉnh cha (parent node) và đỉnh xa gốc hơn được gọi là đỉnh con (child node). Trong Hình 1, mỗi mũi tên đều trỏ từ một đỉnh vào một đỉnh con của nó. Lá cây là các đỉnh không có đỉnh con.
 

hinh1.png

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.

hinh2.png

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.

 

hinh3.jpg

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

[4]

[5]

[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

$$x - \sum_{\substack{0 < \operatorname{Re} \rho < 1 \\ \zeta(\rho) = 0}} \frac{x^\rho}{\rho} - \log 2\pi - \frac{1}{2}\log(1-x^{-2}) = \frac{\psi(x+0) + \psi(x - 0)}{2}, \qquad \psi(x) = \sum_{\substack{p^n \le x \\  n \ge 1}} \log p.$$

 

"Wir müssen wissen, wir werden wissen." - David Hilbert


#2 Funimation

Funimation

    Hạ sĩ

  • Thành viên
  • 92 Bài viết
  • Giới tính:Nam
  • Đến từ:フニマチオン
  • Sở thích:アニメ

Đã gửi 23-09-2020 - 22:58

Giả sử con hydra có dạng như hình 1 

Thì có ít nhất bao nhiêu lần Hercules phải chặt đầu Hydra để Hydra chết ? ( Với những chi tiết từ bài viết trên )

「突き通せてもいて防げてもいるなんて現象があるわけないだろう」という方にオススメのパラドックスが、『シュレディンガーの猫』です。


#3 hung4299

hung4299

    Binh nhất

  • Thành viên mới
  • 39 Bài viết
  • Giới tính:Nam
  • Đến từ:THCS - THPT Nguyễn Tất Thành
  • Sở thích:Khoa Học Tự Nhiên, Toán Học, Công Nghệ Thông Tin

Đã gửi 27-09-2020 - 15:46

Em không có hiểu j hết á .-.


                                                                     Tiền bạc ư?

                                                                                      Rồi sẽ hết.

                                                                     Sắc đẹp ư?

                                                                                      Rồi sẽ phai...

                                                                     Chỉ có

                                                                                      Tri thức đi vào khối óc.

                                                                                      Tình cảm đi vào con tim.

                                                                     Sẽ còn

                                                                                      Mãi với thời gian...

                                                                                                - Trần Phương - 1990 -





2 người đang xem chủ đề

0 thành viên, 2 khách, 0 thành viên ẩn danh