AFTD Auto-Formalizing Theoretical Domains

catch_up_value_aux_empty_eq_draw_iff

theoremverified

In a Catch-Up position with an empty set of remaining pieces, the game value for the mover is CatchUpOutcome.draw if and only if the mover's score equals the opponent's score.

Statement

theorem catch_up_value_aux_empty_eq_draw_iff (s_me s_opp : ℕ) (isFirstMove : Bool) :
    catch_up_value_aux ∅ s_me s_opp isFirstMove = CatchUpOutcome.draw ↔ s_me = s_opp
Source
Catch-Up: A Game in Which the Lead Alternates (2015)
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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_aux_emptyIn a Catch-Up position with an empty set of remaining pieces, the game value for the mover is a win if the mover's score is strictly…
  • 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 all natural numbers s_me and s_opp, and for any boolean isFirstMove, catch_up_value_aux ∅ s_me s_opp isFirstMove evaluates to CatchUpOutcome.draw if and only if s_me = s_opp.

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

The proof unfolds the terminal evaluation of the game on an empty set of pieces into a three-way case distinction: a win if the mover leads, a loss if the opponent leads, and a draw otherwise. Splitting on these score inequalities and simplifying reduces each branch to an elementary linear arithmetic fact, verified by omega.

  1. Evaluating catch_up_value_aux on an empty set reduces to checking whether the score-comparison conditional equals draw.

    We rewrite using catch_up_value_aux_empty, which expresses the terminal value of the game as a nested if-then-else: win if s_me > s_opp, loss if s_opp > s_me, and draw otherwise.

    line 4

    uses catch_up_value_aux_empty

      rw [catch_up_value_aux_empty]
  2. The condition evaluates to draw if and only if s_me = s_opp.

    Splitting on the if-then-else conditions yields three cases: if s_me > s_opp, the position is a win (not a draw) and the scores are unequal, so both sides of the equivalence are false; if s_opp > s_me, the position is a loss and the scores are unequal, so again both sides are false; and if neither inequality holds, the position is a draw and trichotomy of natural numbers implies s_me = s_opp, so both sides are true. Simplification and linear arithmetic (omega) close each branch.

    line 5

      split_ifs <;> simp <;> omega
catch_up_value_aux_empty
When the remaining pieces set is empty, the game outcome is a win if s_me > s_opp, a loss if s_opp > s_me, and a draw otherwise.

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

/-- When no pieces remain in Catch-Up, the position is a draw if and only if the player scores are equal. -/theorem catch_up_value_aux_empty_eq_draw_iff (s_me s_opp : ℕ) (isFirstMove : Bool) :    catch_up_value_aux ∅ s_me s_opp isFirstMove = CatchUpOutcome.draw ↔ s_me = s_opp := by  rw [catch_up_value_aux_empty]  split_ifs <;> simp <;> omega
See it in the graphDiscuss this resultChallenge it