finite_family_overlap_multiplicity_identity
For a finite family of finite sets, total incidences equal the covered-set size plus the sum of multiplicity minus one over covered elements.
Statement
theorem finite_family_overlap_multiplicity_identity (α β : Type) [DecidableEq α] [DecidableEq β] (S : Finset α) (N : α → Finset β) : (∑ a ∈ S, (N a).card) = (S.biUnion N).card + ∑ e ∈ S.biUnion N, ((S.filter fun a => e ∈ N a).card - 1)
- Source
- Collision counting for the small-overlap route to OP-110.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- digraph_twenty_profile_overlap_cardinality_boundIf five vertices of a finite part have internal outdegrees 1 through 5 and all other part vertices have internal outdegree seven, the…
- digraph_common_predecessor_overlap_incidence_identityFor a finite digraph, the total excess multiplicity of edges of its common-predecessor graph equals the sum of unordered pairs in its…
The proof, explained
The identity is proved by double counting element-set incidences. By exchanging the order of summation, the total number of incidences ∑_{a ∈ S} |N(a)| equals the sum of element multiplicities ∑_{e ∈ E} m(e) over the union E = ⋃_{a ∈ S} N(a). Because every element in E belongs to at least one set, each multiplicity satisfies m(e) ≥ 1, allowing the termwise decomposition m(e) = 1 + (m(e) - 1). Splitting the sum distributes the 1s into |E| and leaves the sum of multiplicity deficits m(e) - 1.
Let E = ⋃_{a ∈ S} N(a) be the union of all sets in the family.
We enable classical logic and define E to be the union Finset.biUnion N over S of all sets in the family.
classical let E := S.biUnion NThe total size ∑_{a ∈ S} |N(a)| equals the double sum of indicators ∑_{a ∈ S} ∑_{e ∈ E} [e ∈ N(a)].
For each a ∈ S, the set N(a) is contained in the union E (by Finset.mem_biUnion.mpr). Filtering E by membership in N(a) therefore recovers N(a) (by Finset.mem_filter). Using Finset.sum_filter, the cardinality |N(a)| (which is the sum of 1 over N(a)) is expressed as the sum over e ∈ E of the indicator [e ∈ N(a)], and Finset.sum_congr applies this to every term in the outer sum.
uses
Finset.sum_congr,Finset.mem_biUnion.mpr,Finset.sum_filter,Finset.mem_filterhave hcount : (∑ a ∈ S, (N a).card) = ∑ e ∈ E, (S.filter fun a => e ∈ N a).card := by calc (∑ a ∈ S, (N a).card) = ∑ a ∈ S, ∑ e ∈ E, if e ∈ N a then 1 else 0 := by apply Finset.sum_congr rfl intro a ha have hsub : N a ⊆ E := by intro e he exact Finset.mem_biUnion.mpr ⟨a, ha, he⟩ rw [← Finset.sum_filter] have heq : E.filter (fun e => e ∈ N a) = N a := by ext e simp only [Finset.mem_filter] exact ⟨fun h => h.2, fun h => ⟨hsub h, h⟩⟩ rw [heq] simp
Exchanging the summation order shows that total incidences equal the sum of element multiplicities: ∑_{a ∈ S} |N(a)| = ∑_{e ∈ E} |{a ∈ S | e ∈ N(a)}|.
We swap the order of summation using Finset.sum_comm to obtain ∑_{e ∈ E} ∑_{a ∈ S} [e ∈ N(a)]. For each element e ∈ E, Finset.sum_filter recognizes the inner sum of indicators over a ∈ S as the cardinality of the filtered set {a ∈ S | e ∈ N(a)}.
uses
Finset.sum_comm,Finset.sum_congr,Finset.sum_filter_ = ∑ e ∈ E, ∑ a ∈ S, if e ∈ N a then 1 else 0 := by rw [Finset.sum_comm] _ = ∑ e ∈ E, (S.filter fun a => e ∈ N a).card := by apply Finset.sum_congr rfl intro e he rw [← Finset.sum_filter] simp
Every element e ∈ E has multiplicity at least 1: |{a ∈ S | e ∈ N(a)}| ≥ 1.
Since e ∈ E = ⋃_{a ∈ S} N(a), there exists some a ∈ S with e ∈ N(a) by Finset.mem_biUnion.mp. This witness a belongs to {a ∈ S | e ∈ N(a)} (by Finset.mem_filter.mpr), so the filtered set is nonempty, which implies its cardinality is at least 1 by Finset.card_pos.mpr.
uses
Finset.mem_biUnion.mp,Finset.card_pos.mpr,Finset.mem_filter.mprhave hpos : ∀ e ∈ E, 1 ≤ (S.filter fun a => e ∈ N a).card := by intro e he obtain ⟨a, ha, hea⟩ := Finset.mem_biUnion.mp he exact Finset.card_pos.mpr ⟨a, Finset.mem_filter.mpr ⟨ha, hea⟩⟩
The sum of multiplicities can be rewritten by decomposing each term as 1 + (|{a ∈ S | e ∈ N(a)}| - 1).
We replace the total size with the sum of multiplicities established in hcount. Since every element e ∈ E has multiplicity at least 1 (hpos), the arithmetic identity m = 1 + (m - 1) holds over ℕ, which omega verifies termwise; Finset.sum_congr replaces each summand accordingly.
uses
Finset.sum_congrrw [hcount] calc (∑ e ∈ E, (S.filter fun a => e ∈ N a).card) = ∑ e ∈ E, (1 + ((S.filter fun a => e ∈ N a).card - 1)) := by apply Finset.sum_congr rfl intro e he have := hpos e he omega
Distributing the sum yields |E| + ∑_{e ∈ E} (|{a ∈ S | e ∈ N(a)}| - 1).
Using Finset.sum_add_distrib, the sum splits into ∑_{e ∈ E} 1 and ∑_{e ∈ E} (m(e) - 1). The first sum evaluates to |E|, completing the equality.
uses
Finset.sum_add_distrib_ = E.card + ∑ e ∈ E, ((S.filter fun a => e ∈ N a).card - 1) := by rw [Finset.sum_add_distrib] simp
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every element of the index set.
Finset.mem_biUnion.mpr- An element belongs to the union of a family of sets if it belongs to at least one set in the family.
Finset.sum_filter- Summing a function over a filtered subset is equivalent to summing over the base set with an if-then-else indicator.
Finset.mem_filter- An element belongs to a filtered set if and only if it belongs to the base set and satisfies the filtering predicate.
Finset.sum_comm- The order of summation in a finite double sum can be exchanged.
Finset.mem_biUnion.mp- If an element belongs to the union of a family of sets, then it belongs to some set in that family.
Finset.card_pos.mpr- A finite set has strictly positive cardinality (at least 1) if it is nonempty.
Finset.mem_filter.mpr- An element belongs to a filtered set if it belongs to the base set and satisfies the predicate.
Finset.sum_add_distrib- A sum of termwise sums over a finite set equals the sum of the individual sums.
- In Lean, subtraction on natural numbers truncates at zero (0 - 1 = 0). Consequently, the algebraic identity m = 1 + (m - 1) requires the explicit hypothesis m ≥ 1 (proved in step 4 as hpos), a formal detail that would typically be taken for granted on paper.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
theorem finite_family_overlap_multiplicity_identity (α β : Type) [DecidableEq α] [DecidableEq β] (S : Finset α) (N : α → Finset β) : (∑ a ∈ S, (N a).card) = (S.biUnion N).card + ∑ e ∈ S.biUnion N, ((S.filter fun a => e ∈ N a).card - 1) := by classical let E := S.biUnion N have hcount : (∑ a ∈ S, (N a).card) = ∑ e ∈ E, (S.filter fun a => e ∈ N a).card := by calc (∑ a ∈ S, (N a).card) = ∑ a ∈ S, ∑ e ∈ E, if e ∈ N a then 1 else 0 := by apply Finset.sum_congr rfl intro a ha have hsub : N a ⊆ E := by intro e he exact Finset.mem_biUnion.mpr ⟨a, ha, he⟩ rw [← Finset.sum_filter] have heq : E.filter (fun e => e ∈ N a) = N a := by ext e simp only [Finset.mem_filter] exact ⟨fun h => h.2, fun h => ⟨hsub h, h⟩⟩ rw [heq] simp _ = ∑ e ∈ E, ∑ a ∈ S, if e ∈ N a then 1 else 0 := by rw [Finset.sum_comm] _ = ∑ e ∈ E, (S.filter fun a => e ∈ N a).card := by apply Finset.sum_congr rfl intro e he rw [← Finset.sum_filter] simp have hpos : ∀ e ∈ E, 1 ≤ (S.filter fun a => e ∈ N a).card := by intro e he obtain ⟨a, ha, hea⟩ := Finset.mem_biUnion.mp he exact Finset.card_pos.mpr ⟨a, Finset.mem_filter.mpr ⟨ha, hea⟩⟩ rw [hcount] calc (∑ e ∈ E, (S.filter fun a => e ∈ N a).card) = ∑ e ∈ E, (1 + ((S.filter fun a => e ∈ N a).card - 1)) := by apply Finset.sum_congr rfl intro e he have := hpos e he omega _ = E.card + ∑ e ∈ E, ((S.filter fun a => e ∈ N a).card - 1) := by rw [Finset.sum_add_distrib] simp