AFTD Auto-Formalizing Theoretical Domains

catch_up_value_aux_zero_zero

theoremverified

For any nonempty set S of pieces, the auxiliary Catch-Up value from scores (0, 0) is the best outcome among all opening moves x ∈ S.

Statement

theorem catch_up_value_aux_zero_zero (S : Finset ℕ) (hS : S.Nonempty) :
    catch_up_value_aux S 0 0 false =
      CatchUpOutcome.best (S.attach.toList.map (fun ⟨x, _⟩ =>
        (catch_up_value_aux (S.erase x) 0 x false).neg))
Source
step towards the Catch-Up conjecture (Catch-Up: A Game in Which the Lead Alternates (Game & Puzzle Design 1(2), 2015), Sec. 3.1; formal-conjectures CatchUpConjecture.lean) (Catch-Up ladder step)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • catch_up_value_auxThe game value of a Catch-Up position for the player about to move. If nothing remains, compare scores. If even all remaining numbers…
  • CatchUpOutcomeThe three possible outcomes of a game of Catch-Up, from the point of view of a fixed player: win, loss, draw.
  • CatchUpOutcome.bestGiven a list of outcomes, the best one for the player who chooses, under the order win > draw > loss (and loss if the list is empty).
  • CatchUpOutcome.negNegation of an outcome: win and loss are exchanged, draw is fixed. Used when the turn passes to the other player.
Used by 7
  • catch_up_value_pairFor any natural numbers x < y, the game value of Catch-Up played on the two-element set {x, y} is CatchUpOutcome.win.
  • catch_up_value_aux_ne_loss_iff_exists_ne_winFor any nonempty finite set S of pieces, Player 1 does not get outcome loss from equal scores 0 if and only if there exists an opening…
  • catch_up_value_eq_win_iffFor any nonempty finite set S of natural numbers, the game value catch_up_value S is CatchUpOutcome.win if and only if there exists some…
  • catch_up_value_eq_loss_iffFor any nonempty finite set S of natural numbers, the game value catch_up_value S is CatchUpOutcome.loss if and only if for every element…
  • catch_up_value_aux_ne_loss_of_ne_winIn Catch-Up from equal scores 0, if an opening move x in S leads to a position where the second player does not win, then the first player…
  • catch_up_value_eq_draw_iff_not_lossThe outcome of Catch-Up on a nonempty set S is a draw if and only if Player 1 does not lose from the initial position and Player 2 does…
  • catch_up_value_singletonFor any strictly positive natural number x, the game value of Catch-Up played on the singleton set {x} is CatchUpOutcome.win.

Lean source view module on GitHub

/-- Unfolding catch_up_value_aux on a nonempty set from scores (0, 0) yields the best outcome of the negated positions after each opening choice. -/theorem catch_up_value_aux_zero_zero (S : Finset ℕ) (hS : S.Nonempty) :    catch_up_value_aux S 0 0 false =      CatchUpOutcome.best (S.attach.toList.map (fun ⟨x, _⟩ =>        (catch_up_value_aux (S.erase x) 0 x false).neg)) := by  conv_lhs => rw [catch_up_value_aux]  have hrem : S ≠ ∅ := Finset.Nonempty.ne_empty hS  simp only [hrem, ite_false]  have hnot_lt : ¬ (0 + ∑ x ∈ S, x < 0) := by omega  simp only [hnot_lt, ite_false]  apply congr_arg CatchUpOutcome.best  apply List.map_congr_left  intro ⟨x, hx⟩ hx_in  dsimp  rw [zero_add]
See it in the graphDiscuss this resultChallenge it