AFTD Auto-Formalizing Theoretical Domains

index_split_combine_inverse

theoremverifiedformalizationimported Lean

index_split is a left inverse to index_combine.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Filter in
variable {I : Type*} [Fintype I] [DecidableEq I] [Inhabited I] [LinearOrder I] (card : I → ℕ+) in
lemma index_split_combine_inverse (p : Σ i, Fin (card i)) : index_split card (index_combine card p) = p
Formalizes
EconCSLib, `index_split_combine_inverse`
Lean proof
By xbei (from the file's git history), from github.com/gametheoryinlean/EconCSLib at 1a88f809b538 (Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • index_splitSplit a flat index k into its block/index pair (i, j).
  • index_split_specSpecification of index_split: bounds and value relation for (i, j).
  • index_combineCombine a block/index pair (i, j) back into a flat index.
  • total_cardTotal number of coordinates: the sum of card i over all i.
  • prefix_sumCumulative sum of card over indices strictly less than i.
Used by 2

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Filter invariable {I : Type*} [Fintype I] [DecidableEq I] [Inhabited I] [LinearOrder I] (card : I → ℕ+) in/-- `index_split` is a left inverse to `index_combine`. -/lemma index_split_combine_inverse (p : Σ i, Fin (card i)) : index_split card (index_combine card p) = p := by  classical  cases p with  | mk i j =>    let k : Fin (total_card card) := index_combine card ⟨i, j⟩    have hspec := index_split_spec card k    have prefix_sum_mono_lt : ∀ {a b : I}, a < b →        prefix_sum card a + (card a : ℕ) ≤ prefix_sum card b := by      intro a b hlt      have h_subset : (Finset.univ.filter (· ≤ a)) ⊆ (Finset.univ.filter (· < b)) := by        intro x hx        rcases Finset.mem_filter.mp hx with ⟨hxU, hxle⟩        exact Finset.mem_filter.mpr ⟨hxU, lt_of_le_of_lt hxle hlt⟩      have h_eq_a : (Finset.univ.filter (· ≤ a)).sum (fun j => (card j : ℕ)) =          (Finset.univ.filter (· < a)).sum (fun j => (card j : ℕ)) + (card a : ℕ) := by        have h_split : Finset.univ.filter (· ≤ a) =            Finset.univ.filter (· < a) ∪ {a} := by          ext j; simp [Finset.mem_filter, le_iff_lt_or_eq, or_comm]        have h_disj : Disjoint (Finset.univ.filter (· < a)) {a} := by simp        rw [h_split, Finset.sum_union h_disj]; simp      have h_le : (Finset.univ.filter (· ≤ a)).sum (fun j => (card j : ℕ)) ≤          (Finset.univ.filter (· < b)).sum (fun j => (card j : ℕ)) :=        Finset.sum_le_sum_of_subset_of_nonneg h_subset (by          intro j _ _; exact Nat.zero_le _)      simpa [prefix_sum, h_eq_a] using h_le    have hk_le : prefix_sum card i ≤ k.val := by      simp [k, index_combine]    have hk_lt : k.val < prefix_sum card i + (card i : ℕ) := by      simp [k, index_combine, add_lt_add_iff_left]    have hnot_lt1 : ¬ (index_split card k).1 < i := by      intro hlt      have hmono := prefix_sum_mono_lt hlt      have : k.val < prefix_sum card i := Nat.lt_of_lt_of_le hspec.2.1 hmono      exact (not_lt_of_ge hk_le) this    have hnot_lt2 : ¬ i < (index_split card k).1 := by      intro hlt      have hmono := prefix_sum_mono_lt hlt      have : k.val < prefix_sum card (index_split card k).1 := Nat.lt_of_lt_of_le hk_lt hmono      exact (not_lt_of_ge hspec.1) this    have hi : (index_split card k).1 = i :=      le_antisymm (le_of_not_gt hnot_lt2) (le_of_not_gt hnot_lt1)    have hj_spec : (index_split card k).2.val = k.val - prefix_sum card (index_split card k).1 := hspec.2.2    have hj_spec_i : (index_split card k).2.val = k.val - prefix_sum card i := by      simpa [hi] using hj_spec    have hj_val : (index_split card k).2.val = j.val := by      simpa [k, index_combine, Nat.add_sub_cancel_left] using hj_spec_i    cases hsplit : index_split card k with    | mk i' j' =>      have hi' : i' = i := by simpa [hsplit] using hi      subst hi'      have hj' : j' = j := by        apply Fin.ext        rw [hsplit] at hj_val        exact hj_val      simpa [hsplit] using hj'
See it in the graphDiscuss this resultChallenge it