AFTD Auto-Formalizing Theoretical Domains

spider_grundy_val_one_one_one

theoremverifiedformalization

The Grundy value of the spider tree S(1, 1, 1) satisfies spider_grundy_val 1 1 1 = 1.

Statement

theorem spider_grundy_val_one_one_one : spider_grundy_val 1 1 1 = 1
Formalizes
arXiv:2610.15145, Table 4
Verified
19 Oct 2026
Axioms
Quot.soundpropext
Built on 1
  • spider_grundy_valThe Grundy value spider_grundy_val of the 3-legged spider tree with leg parameters x, y, z : ℕ is defined as spider_gamma (x + y + z + 1)…

Read back from the Lean

The value of spider_grundy_val 1 1 1 is equal to 1.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem asserts that the Grundy value (nim-value) of the symmetric spider graph S(1, 1, 1) is 1. The function `spider_grundy_val` is defined constructively by bounded recursion over legal game transitions, computing the minimal excludant (mex) of reachable states. Because the arguments are concrete numbers and the definitions are executable, the proof proceeds entirely by computational evaluation via the `decide` tactic.

  1. spider_grundy_val 1 1 1 = 1 automation

    The statement is an equality between two concrete natural numbers. Because `spider_grundy_val` and its auxiliary functions (`spider_gamma`, `spider_rho`, `spider_rho_star`, `spider_update_centre`, and `nat_mex_list`) are fully computable recursive definitions, Lean's `decide` tactic evaluates `spider_grundy_val 1 1 1` by finite computation and verifies that it reduces to 1.

    line 2

    theorem spider_grundy_val_one_one_one : spider_grundy_val 1 1 1 = 1 := by first | (simp_all; done) | omega | decide | linarith | positivity | (aesop; done)

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Grundy value of the symmetric spider S(1, 1, 1) is 1. -/theorem spider_grundy_val_one_one_one : spider_grundy_val 1 1 1 = 1 := by first | (simp_all; done) | omega | decide | linarith | positivity | (aesop; done)
See it in the graphDiscuss this resultChallenge it