catch_up_value_eq_draw_iff_not_loss
theoremverified
The 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 not lose after any opening move from S.
Statement
theorem catch_up_value_eq_draw_iff_not_loss (S : Finset ℕ) (hS : S.Nonempty) :
catch_up_value S = CatchUpOutcome.draw ↔
(catch_up_value_aux S 0 0 false ≠ CatchUpOutcome.loss ∧
∀ x ∈ S, catch_up_value_aux (S.erase x) 0 x 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 8
- catch_up_outcome_neg_eq_win_iffNegating an outcome yields a win if and only if the original outcome was a loss.
- catch_up_value_eq_aux_falseThe game value catch_up_value S is equal to catch_up_value_aux S 0 0 false.
- 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_winUnder Catch-Up's best-outcome aggregation on a list of outcomes, the aggregated outcome is a win if and only if a win appears in the list.
- catch_up_outcome_eq_draw_iffAn outcome in CatchUpOutcome is a draw if and only if it is neither a win nor a loss.
- 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…
- CatchUpOutcomeThe three possible outcomes of a game of Catch-Up, from the point of view of a fixed player: win, loss, draw.
- 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…
- Used by 6
- LinearPMap.IsClosable.add_continuousClosability is preserved upon adding a continuous operator.
- LinearPMap.closure_domain_le_domain_closureLinearPMap.closure_domain_le_domain_closure
- LinearPMap.IsClosed.add_continuousClosedness is preserved upon adding a continuous operator.
- 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…
- LinearPMap.IsClosable.smulLinearPMap.IsClosable.smul
- LinearPMap.HasDenseDomain.orthogonal_range
U.rangeᗮ = U†.kerc.f.LinearMap.orthogonal_rangeandContinuousLinearMap.orthogonal_range
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.
/-- For a nonempty set of pieces S, the outcome of Catch-Up is a draw if and only if Player 1 does not lose from the initial position and Player 2 does not lose after any first move x chosen from S. -/theorem catch_up_value_eq_draw_iff_not_loss (S : Finset ℕ) (hS : S.Nonempty) : catch_up_value S = CatchUpOutcome.draw ↔ (catch_up_value_aux S 0 0 false ≠ CatchUpOutcome.loss ∧ ∀ x ∈ S, catch_up_value_aux (S.erase x) 0 x false ≠ CatchUpOutcome.loss) := by rw [catch_up_value_eq_aux_false] rw [catch_up_outcome_eq_draw_iff] have h_win : (catch_up_value_aux S 0 0 false = CatchUpOutcome.win) ↔ ∃ x ∈ S, catch_up_value_aux (S.erase x) 0 x false = CatchUpOutcome.loss := by rw [catch_up_value_aux_zero_zero S hS] rw [catch_up_outcome_best_eq_win] simp only [List.mem_map, Finset.mem_toList, Finset.mem_attach, true_and, Subtype.exists, exists_prop, catch_up_outcome_neg_eq_win_iff] constructor · rintro ⟨h1, h2⟩ refine ⟨h2, ?_⟩ intro x hx h_loss apply h1 rw [h_win] exact ⟨x, hx, h_loss⟩ · rintro ⟨h1, h2⟩ refine ⟨?_, h1⟩ intro h_w rw [h_win] at h_w rcases h_w with ⟨x, hx, h_loss⟩ exact h2 x hx h_loss