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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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