AFTD Auto-Formalizing Theoretical Domains

catch_up_value_aux_eq_eval_list

theoremverified

For 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 equals the computable mirror catch_up_eval_list n l.

Statement

theorem catch_up_value_aux_eq_eval_list (n : ℕ) :
    ∀ (l : List ℕ), l.Nodup → l.length ≤ n → ∀ (s_me s_opp : ℕ) (first : Bool),
      catch_up_value_aux l.toFinset s_me s_opp first = catch_up_eval_list n l s_me s_opp first
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 4
  • 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_eval_listA computable mirror of catch_up_value_aux: the same Catch-Up recursion on a list of the remaining numbers, by structural recursion on a…
  • catch_up_best_attach_map_congrIf 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…
  • catch_up_toFinset_eraseFor a list l of natural numbers without duplicates, erasing a from the finset of l is the finset of l with a erased.
Used by 1
  • catch_up_value_eq_eval_listFor a duplicate-free list l, the value of Catch-Up on the finset of l equals the computable mirror evaluated on l from scores 0, 0 at the…

Lean source view module on GitHub

/-- The computable mirror agrees with `catch_up_value_aux` whenever the fuel covers the list. -/theorem catch_up_value_aux_eq_eval_list (n : ℕ) :    ∀ (l : List ℕ), l.Nodup → l.length ≤ n → ∀ (s_me s_opp : ℕ) (first : Bool),      catch_up_value_aux l.toFinset s_me s_opp first = catch_up_eval_list n l s_me s_opp first := by  induction n with  | zero =>    intro l _ hlen s_me s_opp first    have : l = [] := List.eq_nil_of_length_eq_zero (by omega)    subst this    rw [catch_up_value_aux.eq_def]    simp [catch_up_eval_list]  | succ n ih =>    intro l hl hlen s_me s_opp first    cases l with    | nil =>      rw [catch_up_value_aux.eq_def]      simp [catch_up_eval_list]    | cons h t =>      rw [catch_up_value_aux.eq_def]      have hne : (h :: t).toFinset ≠ ∅ := by simp      have hsum : (h :: t).toFinset.sum (fun x => x) = (h :: t).sum := by        rw [List.sum_toFinset _ hl, List.map_id']      simp only [hne, if_false, hsum, catch_up_eval_list]      by_cases hlt : s_me + (h :: t).sum < s_opp      · simp only [hlt, if_true]      · simp only [hlt, if_false]        refine catch_up_best_attach_map_congr (h :: t)          (fun y => if first = true then              (catch_up_value_aux ((h :: t).toFinset.erase y) s_opp (s_me + y) false).neg            else if s_me + y ≥ s_opp then              (catch_up_value_aux ((h :: t).toFinset.erase y) s_opp (s_me + y) false).neg            else catch_up_value_aux ((h :: t).toFinset.erase y) (s_me + y) s_opp false)          (fun y => if first = true then              (catch_up_eval_list n ((h :: t).erase y) s_opp (s_me + y) false).neg            else if s_me + y ≥ s_opp then              (catch_up_eval_list n ((h :: t).erase y) s_opp (s_me + y) false).neg            else catch_up_eval_list n ((h :: t).erase y) (s_me + y) s_opp false) ?_        intro x hx        have hlen' : ((h :: t).erase x).length ≤ n := by          rw [List.length_erase_of_mem hx]; simp at hlen ⊢; omega        simp only [catch_up_toFinset_erase hl, ih _ (hl.erase x) hlen']
See it in the graphDiscuss this resultChallenge it