AFTD Auto-Formalizing Theoretical Domains

catch_up_outcome_best_eq_win

theoremverified

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

Statement

theorem catch_up_outcome_best_eq_win (os : List CatchUpOutcome) :
    CatchUpOutcome.best os = CatchUpOutcome.win ↔ CatchUpOutcome.win ∈ os
Source
google-deepmind/formal-conjectures
Verified
01 Oct 2026
Axioms
propext
Built on 2
  • CatchUpOutcomeThe three possible outcomes of a game of Catch-Up, from the point of view of a fixed player: win, loss, draw.
  • CatchUpOutcome.bestGiven a list of outcomes, the best one for the player who chooses, under the order win > draw > loss (and loss if the list is empty).
Used by 8
  • catch_up_outcome_best_eq_iteThe best outcome of a list depends only on which outcomes occur in it: win if a win occurs, otherwise draw if a draw occurs, otherwise loss.
  • catch_up_value_aux_icc_opening_one_ne_win_iffWhen N ≥ 3, Player 2 does not win after Player 1 opens with 1 iff for every response y from {2, ..., N}, Player 1 does not lose from the…
  • 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_best_map_eq_win_iffThe best outcome over a mapped list is a win if and only if some element maps to a win.
  • 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_value_eq_win_iffFor 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…
  • catch_up_value_eq_draw_iff_not_lossThe 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…
  • catch_up_value_singletonFor any strictly positive natural number x, the game value of Catch-Up played on the singleton set {x} is CatchUpOutcome.win.

Read back from the Lean

For every list os of CatchUpOutcome values, CatchUpOutcome.best os equals CatchUpOutcome.win if and only if CatchUpOutcome.win is an element of os.

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

lemma catch_up_outcome_best_foldl_win_spec (f : CatchUpOutcome → CatchUpOutcome → CatchUpOutcome)    (hf : ∀ a b, f a b = if a = .win ∨ b = .win then .win      else if a = .draw ∨ b = .draw then .draw else .loss)    (os : List CatchUpOutcome) (acc : CatchUpOutcome) :    os.foldl f acc = CatchUpOutcome.win ↔ acc = CatchUpOutcome.win ∨ CatchUpOutcome.win ∈ os := by  induction os generalizing acc with  | nil => simp  | cons head tail ih =>    rw [List.foldl_cons, ih, hf, List.mem_cons]    cases acc <;> cases head <;> simp/-- The best outcome of a list of Catch-Up outcomes is a win if and only if a win is in the list. -/theorem catch_up_outcome_best_eq_win (os : List CatchUpOutcome) :    CatchUpOutcome.best os = CatchUpOutcome.win ↔ CatchUpOutcome.win ∈ os := by  unfold CatchUpOutcome.best  rw [catch_up_outcome_best_foldl_win_spec _ (by intro a b; cases a <;> cases b <;> rfl)]  simp
See it in the graphDiscuss this resultChallenge it