AFTD Auto-Formalizing Theoretical Domains

catch_up_best_attach_map_congr

theoremverified

If F and G agree on every element of a list l of natural numbers, then the best outcome of F over the attached elements of l's finset equals the best outcome of G over l.

Statement

theorem catch_up_best_attach_map_congr (l : List ℕ) (F G : ℕ → CatchUpOutcome)
    (hFG : ∀ x ∈ l, F x = G x) :
    CatchUpOutcome.best (l.toFinset.attach.toList.map (fun x => F x.1)) =
      CatchUpOutcome.best (l.map G)
Source
step towards the kernel checks catch_up_value_icc_four/seven/eight/eleven (Catch-Up: A Game in Which the Lead Alternates (Game & Puzzle Design 1(2), 2015), Table 2; computable mirror and pruned search of catch_up_value_aux)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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).
  • 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.
Used by 1
  • catch_up_value_aux_eq_eval_listFor every fuel n, every duplicate-free list l of length at most n, and all scores and opening flags, the Catch-Up value of the finset of l…

Lean source view module on GitHub

/-- `best` over the finset of `l` equals `best` over `l` for functions agreeing on `l`. -/theorem catch_up_best_attach_map_congr (l : List ℕ) (F G : ℕ → CatchUpOutcome)    (hFG : ∀ x ∈ l, F x = G x) :    CatchUpOutcome.best (l.toFinset.attach.toList.map (fun x => F x.1)) =      CatchUpOutcome.best (l.map G) := by  have hm : ∀ o, o ∈ l.toFinset.attach.toList.map (fun x => F x.1) ↔ o ∈ l.map G := by    intro o    simp only [List.mem_map, Finset.mem_toList, Finset.mem_attach, true_and, Subtype.exists,      List.mem_toFinset]    constructor    · rintro ⟨x, hx, rfl⟩; exact ⟨x, hx, (hFG x hx).symm⟩    · rintro ⟨x, hx, rfl⟩; exact ⟨x, hx, hFG x hx⟩  rw [catch_up_outcome_best_eq_ite, catch_up_outcome_best_eq_ite]  simp only [hm]
See it in the graphDiscuss this resultChallenge it