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.index_split_combine_inverse← index_split_combine_inverse (EconCSLib/Math/FixedPoint/Brouwer_product.lean:185): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- index_splitSplit a flat index
kinto 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 iover alli. - prefix_sumCumulative sum of
cardover indices strictly less thani.
- index_splitSplit a flat index
- Used by 2
- embed_from_productEmbedding of the product of simplices into the big simplex.
- project_embed_id
project_to_product ∘ embed_from_product = id.
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.
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'