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