Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
rooted tree; unprovability; Kirby--Paris Theorem
rooted tree; unprovability; Kirby--Paris Theorem
Summary:
L. Kirby and J. Paris introduced the Hercules and Hydra game on rooted trees as a natural example of an undecidable statement in Peano Arithmetic. One can show that Hercules has a ``short'' strategy (he wins in a primitively recursive number of moves) and also a ``long'' strategy (the finiteness of the game cannot be proved in Peano Arithmetic). We investigate the conflict of the ``short'' and ``long'' intentions (a problem suggested by J. Ne{\v s}et{\v r}il). After each move of Hercules (trying to kill Hydra fast) there follow $k$ moves of Hidden Hydra Helper (making the same type of moves as Hercules but trying to keep Hydra alive as long as possible). We prove that for $k=1$ Hercules can make the game short, while for $k\geq 2$ Hidden Hydra Helper has a strategy for making the game long.
References:
[1] Kirby L., Paris J.: Accessible independence results for Peano Arithmetic. Bulletin of the London Math. Soc 14, 1982. MR 0663480 | Zbl 0501.03017
[2] Loebl M.: Hercules and Hydra, the game on rooted finite trees. Comment. Math. Univ. Carolinae 26 (1985), 259-267. MR 0803922
[3] Loebl M.: Hercules and Hydra. Comment. Math. Univ. Carolinae 29 (1988), 85-95. MR 0937552 | Zbl 0666.05024
[4] Buchholz W., Wainer S.: Provably computable functions and the fast growing hierarchy. in: {Logic and Combinatorics}, Contemporary Mathematics, vol. 65, AMS 1986. MR 0891248 | Zbl 0635.03056
Search
Partner of
