AFTD Auto-Formalizing Theoretical Domains

catch_up_value_eq_loss_iff

theoremverifiedformalization

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.

  1. 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.

    lines 5–6

    uses catch_up_value_eq_aux_false, catch_up_value_aux_zero_zero, catch_up_outcome_best_eq_loss

      rw [catch_up_value_eq_aux_false, catch_up_value_aux_zero_zero S hS,
        catch_up_outcome_best_eq_loss]
  2. 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.

    line 7

    uses catch_up_outcome_neg_eq_loss_iff

      simp [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

/-- 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]
See it in the graphDiscuss this resultChallenge it