AFTD Auto-Formalizing Theoretical Domains

catch_up_value_aux_ne_loss_of_ne_win

theoremverified

In 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 does not lose from the start.

Statement

theorem catch_up_value_aux_ne_loss_of_ne_win (S : Finset ℕ) {x : ℕ} (hx : x ∈ S)
    (h : catch_up_value_aux (S.erase x) 0 x false ≠ CatchUpOutcome.win) :
    catch_up_value_aux S 0 0 false ≠ CatchUpOutcome.loss
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 5
  • catch_up_value_aux_zero_zeroFor 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.
  • catch_up_outcome_best_eq_lossUnder Catch-Up's best-outcome aggregation on a list of outcomes, the aggregated outcome is a loss if and only if every outcome in the list…
  • CatchUpOutcome.negNegation of an outcome: win and loss are exchanged, draw is fixed. Used when the turn passes to the other player.
  • 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.
Used by 1
  • catch_up_value_triple_drawFor any natural numbers x < y < z such that x + y = z, the game value of Catch-Up played on the three-element set {x, y, z} is…

Lean source view module on GitHub

/-- If there is an opening move x in S after which Player 2 does not win, then Player 1 does not lose from the initial position with equal scores 0. -/theorem catch_up_value_aux_ne_loss_of_ne_win (S : Finset ℕ) {x : ℕ} (hx : x ∈ S)    (h : catch_up_value_aux (S.erase x) 0 x false ≠ CatchUpOutcome.win) :    catch_up_value_aux S 0 0 false ≠ CatchUpOutcome.loss := by  have hS : S.Nonempty := ⟨x, hx⟩  rw [catch_up_value_aux_zero_zero S hS]  intro h_loss  rw [catch_up_outcome_best_eq_loss] at h_loss  have h_in : (catch_up_value_aux (S.erase x) 0 x false).neg ∈      S.attach.toList.map (fun ⟨y, _⟩ => (catch_up_value_aux (S.erase y) 0 y false).neg) := by    refine List.mem_map.2 ⟨⟨x, hx⟩, ?_, rfl⟩    simp  have h_eq := h_loss _ h_in  cases h_val : catch_up_value_aux (S.erase x) 0 x false with  | win => exact h h_val  | loss => rw [h_val] at h_eq; cases h_eq  | draw => rw [h_val] at h_eq; cases h_eq
See it in the graphDiscuss this resultChallenge it