Peano Arithmetic & Paris — Part 11: Hydra Game

Mathematics Foundations / Combinatorics Source: Kirby & Paris 1982 Cite
Primary: Kirby & Paris
Publication: Hydra game, independence of PA
Year: 1982
URL: Wikipedia

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