AFTD Auto-Formalizing Theoretical Domains

catch_up_value_icc_eq_eval

theoremverified

The value of Catch-Up on {1, ..., N} equals the computable mirror evaluated on the list [1, ..., N]; this is what lets the kernel settle concrete N.

Statement

theorem catch_up_value_icc_eq_eval (N : ℕ) :
    catch_up_value (Finset.Icc 1 N) = catch_up_eval_list N (List.range' 1 N) 0 0 true
Source
step towards the kernel checks catch_up_value_icc_four/seven/eight/eleven (Catch-Up: A Game in Which the Lead Alternates (Game & Puzzle Design 1(2), 2015), Table 2; computable mirror and pruned search of catch_up_value_aux)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • catch_up_valueThe outcome of Catch-Up played on the finite set S of natural numbers, from the first player's point of view, assuming optimal play by…
  • catch_up_eval_listA computable mirror of catch_up_value_aux: the same Catch-Up recursion on a list of the remaining numbers, by structural recursion on a…
  • catch_up_icc_one_eq_range_toFinsetThe set {1, ..., N} of natural numbers is the finset of the list [1, 2, ..., N].
  • catch_up_value_eq_eval_listFor a duplicate-free list l, the value of Catch-Up on the finset of l equals the computable mirror evaluated on l from scores 0, 0 at the…
Used by 6
  • catch_up_value_icc_oneThe game value of Catch-Up played on the interval Finset.Icc 1 1 is CatchUpOutcome.win.
  • catch_up_value_icc_eq_draw_of_searchIf the pruned search on [1, ..., N] from scores 0, 0 at the opening move finds no forced win for the first player but finds that the first…
  • catch_up_value_icc_threeThe game value of Catch-Up played on the interval Finset.Icc 1 3 is CatchUpOutcome.draw.
  • catch_up_value_icc_fourCatch-Up on {1, 2, 3, 4} is a draw under optimal play (the case N = 4 of the Catch-Up conjecture), evaluated by the Lean kernel.
  • catch_up_value_icc_eightCatch-Up on {1, ..., 8} is a draw under optimal play (the case N = 8 of the Catch-Up conjecture), evaluated by the Lean kernel.
  • catch_up_value_icc_sevenCatch-Up on {1, ..., 7} is a draw under optimal play (the case N = 7 of the Catch-Up conjecture), evaluated by the Lean kernel.

Lean source view module on GitHub

/-- Catch-Up on {1, ..., N} through the computable mirror. -/theorem catch_up_value_icc_eq_eval (N : ℕ) :    catch_up_value (Finset.Icc 1 N) = catch_up_eval_list N (List.range' 1 N) 0 0 true := by  rw [catch_up_icc_one_eq_range_toFinset, catch_up_value_eq_eval_list _ List.nodup_range',    List.length_range']
See it in the graphDiscuss this resultChallenge it