AFTD Auto-Formalizing Theoretical Domains

catch_up_value_eq_win_iff

theoremverified

For any nonempty finite set S of natural numbers, the game value catch_up_value S is CatchUpOutcome.win if and only if there exists some element x ∈ S such that the second player loses from the resulting position, i.e., catch_up_value_aux (S.erase x) 0 x false = CatchUpOutcome.loss.

Statement

theorem catch_up_value_eq_win_iff (S : Finset ℕ) (hS : S.Nonempty) :
    catch_up_value S = CatchUpOutcome.win ↔
      ∃ x ∈ S, catch_up_value_aux (S.erase x) 0 x false = CatchUpOutcome.loss
Source
google-deepmind/formal-conjectures, FormalConjectures/Paper/CatchUpConjecture.lean
Verified
01 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • 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_neg_eq_win_iffNegating an outcome yields a win if and only if the original outcome was 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 3
  • catch_up_value_pairFor any natural numbers x < y, the game value of Catch-Up played on the two-element set {x, y} is CatchUpOutcome.win.
  • catch_up_value_triple_win_of_sum_ltFor 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…
  • catch_up_value_triple_win_of_sum_gtFor 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…

Read back from the Lean

For any finite set of natural numbers $S$, assuming $S$ is nonempty, the overall game value catch_up_value S is equal to CatchUpOutcome.win if and only if there exists some element $x \in S$ such that catch_up_value_aux (S.erase x) 0 x false equals CatchUpOutcome.loss.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The game value of Catch-Up on a nonempty set S is a win for the first player if and only if there is an opening move x in S leading to a loss for the second player. -/theorem catch_up_value_eq_win_iff (S : Finset ℕ) (hS : S.Nonempty) :    catch_up_value S = CatchUpOutcome.win ↔      ∃ x ∈ S, catch_up_value_aux (S.erase x) 0 x false = CatchUpOutcome.loss := by  rw [catch_up_value_eq_aux_false, catch_up_value_aux_zero_zero S hS,    catch_up_outcome_best_eq_win]  simp only [List.mem_map, Finset.mem_toList, Finset.mem_attach, true_and,    catch_up_outcome_neg_eq_win_iff]  exact ⟨fun ⟨⟨x, hx⟩, h⟩ => ⟨x, hx, h⟩, fun ⟨x, hx, h⟩ => ⟨⟨x, hx⟩, h⟩⟩
See it in the graphDiscuss this resultChallenge it