Description
Hercules-Hydra game: Hydra is a rooted finite tree; Hercules chops a leaf; Hydra grows n copies of the subtree above the chopped node's parent (n = distance from root). Hercules always wins, but termination is unprovable in PA. Proof: assign ordinals to trees; each move strictly decreases ordinal; requires ε₀ induction.
Source: Kirby, L. & Paris, J., "Accessible Independence Results for Peano Arithmetic", Bull. London Math. Soc. 14 (1982)
Dependency Flowchart
graph TD
DefHydra["Def: Hydra = rooted finite tree; heads = leaves"]
DefMove["Def: Move: chop leaf; parent node grows n copies of subtree above it"]
DefOrdTree["Def: Ordinal assignment: tree T ↦ ω^T₁ + ω^T₂ + ... (Cantor normal form)"]
LemOrdDec["Lem: Each move strictly decreases tree ordinal"]
LemWellFound["Lem: Ordinals well-founded ⇒ no infinite descending chain"]
ThmHercules["Thm: Hercules always wins (any strategy)"]
RefGoodstein["Ref: Goodstein / Indicators (Part 10)"]
LemHydraEps0["Lem: Hydra termination equivalent to ε₀ well-founded"]
LemEps0PA["Lem: PA ⊬ ε₀ well-founded"]
ThmHydraUnprov["Thm: Kirby-Paris: Hydra termination unprovable in PA"]
CorHydraProv["Cor: Provable in PA + TI(ε₀) or ACA₀"]
DefHydra --> DefMove
DefMove --> DefOrdTree
DefOrdTree --> LemOrdDec
LemOrdDec --> LemWellFound
LemWellFound --> ThmHercules
RefGoodstein --> LemHydraEps0
ThmHercules --> LemHydraEps0
LemHydraEps0 --> ThmHydraUnprov
LemEps0PA --> ThmHydraUnprov
ThmHydraUnprov --> CorHydraProv
classDef definition fill:#b197fc,color:#fff,stroke:#9775fa
classDef lemma fill:#74c0fc,color:#fff,stroke:#4dabf7
classDef theorem fill:#51cf66,color:#fff,stroke:#40c057
classDef corollary fill:#1abc9c,color:#fff,stroke:#16a085
classDef ref fill:#bdc3c7,color:#333,stroke:#95a5a6
class RefGoodstein ref
class DefHydra,DefMove,DefOrdTree definition
class LemOrdDec,LemWellFound,LemHydraEps0,LemEps0PA lemma
class ThmHercules,ThmHydraUnprov theorem
class CorHydraProv corollary
Color Scheme
Purple Definitions
Blue Lemmas
Teal Theorems
Green Corollaries
Gray References
Process Statistics
- Nodes: 11
- Edges: 12
- Axioms: 0
- Definitions: 3
- Lemmas: 4
- Theorems: 2
- Corollaries: 1
- References: 1