catch_up_value_eq_loss_iff
For 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 x ∈ S, the second player wins from the resulting position, i.e., catch_up_value_aux (S.erase x) 0 x false = CatchUpOutcome.win.
Statement
theorem catch_up_value_eq_loss_iff (S : Finset ℕ) (hS : S.Nonempty) :
catch_up_value S = CatchUpOutcome.loss ↔
∀ x ∈ S, catch_up_value_aux (S.erase x) 0 x false = CatchUpOutcome.win- Formalizes
- Catch-Up: A Game in Which the Lead Alternates (2015)
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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_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…
- 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_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…
- catch_up_outcome_neg_eq_loss_iffNegating a Catch-Up outcome yields a loss if and only if the original outcome is a win.
- CatchUpOutcomeThe three possible outcomes of a game of Catch-Up, from the point of view of a fixed player: win, loss, draw.
Read back from the Lean
For any finite set of natural numbers $S$, assuming $S$ is non-empty, the catch-up game value catch_up_value S is equal to CatchUpOutcome.loss if and only if for every element $x \in S$, the auxiliary game value catch_up_value_aux (S.erase x) 0 x false is equal to CatchUpOutcome.win.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
In Catch-Up on a nonempty set S, Player 1 loses if and only if Player 2 wins after every possible opening move x ∈ S. The proof expands the overall game value into the best outcome among all opening moves, where each move's value is the negation of Player 2's subsequent outcome. Because the best outcome is a loss exactly when all available choices result in a loss, and an outcome is a loss if and only if its negation is a win, Player 1 loses precisely when Player 2 wins against every opening move.
The overall game value being a loss is equivalent to every opening move resulting in a loss for the first player.
Rewriting with `catch_up_value_eq_aux_false` expresses `catch_up_value S` via the auxiliary evaluation `catch_up_value_aux S 0 0 false`. Since S is nonempty, `catch_up_value_aux_zero_zero` expands this into the best outcome (`CatchUpOutcome.best`) among all candidate opening moves x ∈ S, where each move gives the negated outcome of the second player's resulting position. Then `catch_up_outcome_best_eq_loss` rewrites the condition that the best outcome is a loss into the requirement that every move's outcome is a loss.
uses
catch_up_value_eq_aux_false,catch_up_value_aux_zero_zero,catch_up_outcome_best_eq_lossrw [catch_up_value_eq_aux_false, catch_up_value_aux_zero_zero S hS, catch_up_outcome_best_eq_loss]Player 1 loses if and only if Player 2 wins after every opening move x ∈ S.
Simplifying across the list of elements of S transforms membership in S.attach.toList into universal quantification over x ∈ S. Rewriting with `catch_up_outcome_neg_eq_loss_iff` then turns the condition that each move's negated outcome is a loss into the condition that the outcome itself is a win. This makes both sides of the `↔` identical and closes the goal.
uses
catch_up_outcome_neg_eq_loss_iffsimp [catch_up_outcome_neg_eq_loss_iff]
catch_up_value_eq_aux_false- The Catch-Up game value of a set S equals the auxiliary evaluation starting from scores 0 and 0 with the initial-move flag set to false.
catch_up_value_aux_zero_zero- For a nonempty set S starting at scores 0 and 0, the auxiliary game value is the best outcome among all opening moves x ∈ S, where each move yields the negation of the opponent's outcome from the remaining set S \\ {x} with scores 0 and x.
catch_up_outcome_best_eq_loss- The best outcome in a list of outcomes is a loss if and only if every outcome in the list is a loss.
catch_up_outcome_neg_eq_loss_iff- The negation of an outcome is a loss if and only if that outcome is a win.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
/-- Characterization of loss in Catch-Up: Player 1 loses if and only if Player 2 wins after every opening move. -/theorem catch_up_value_eq_loss_iff (S : Finset ℕ) (hS : S.Nonempty) : catch_up_value S = CatchUpOutcome.loss ↔ ∀ x ∈ S, catch_up_value_aux (S.erase x) 0 x false = CatchUpOutcome.win := by rw [catch_up_value_eq_aux_false, catch_up_value_aux_zero_zero S hS, catch_up_outcome_best_eq_loss] simp [catch_up_outcome_neg_eq_loss_iff]