op1370_boolean_interval_cancellation
theoremverified
The alternating sum over a Boolean interval is one for equal endpoints and zero otherwise.
Statement
theorem op1370_boolean_interval_cancellation {α : Type*} [DecidableEq α] (A B : Finset α) (hAB : A ⊆ B) : (∑ X ∈ Finset.Icc A B, (-1 : ℤ) ^ (X \ A).card) = if A = B then 1 else 0
- Source
- Filed by the prover as a step towards another result
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- op1370_uniform_hull_weighted_entryUniform weights on the interval hull of any finite set family produce a scalar identity in the signed weighted-incidence matrix.
Lean source view module on GitHub
open Finset Matrix Polynomial open scoped BigOperators theorem op1370_boolean_interval_cancellation {α : Type*} [DecidableEq α] (A B : Finset α) (hAB : A ⊆ B) : (∑ X ∈ Finset.Icc A B, (-1 : ℤ) ^ (X \ A).card) = if A = B then 1 else 0 := by classical have hd (Y : Finset α) (hY : Y ∈ (B \ A).powerset) : Disjoint A Y := Finset.disjoint_of_subset_right (Finset.mem_powerset.mp hY) Finset.disjoint_sdiff rw [Finset.Icc_eq_image_powerset hAB, Finset.sum_image] · calc (∑ Y ∈ (B \ A).powerset, (-1 : ℤ) ^ ((A ∪ Y) \ A).card) = ∑ Y ∈ (B \ A).powerset, (-1 : ℤ) ^ Y.card := by apply Finset.sum_congr rfl intro Y hY rw [Finset.union_sdiff_cancel_left (hd Y hY)] _ = if B \ A = ∅ then 1 else 0 := Finset.sum_powerset_neg_one_pow_card _ = if A = B then 1 else 0 := by by_cases h : A = B · subst B simp · have hn : B \ A ≠ ∅ := by intro he have hBA : B ⊆ A := Finset.sdiff_eq_empty_iff_subset.mp he exact h (Finset.Subset.antisymm hAB hBA) simp [h, hn] · intro Y hY Z hZ h have hh := congrArg (fun X : Finset α => X \ A) h simpa only [Finset.union_sdiff_cancel_left (hd Y hY), Finset.union_sdiff_cancel_left (hd Z hZ)] using hh