AFTD Auto-Formalizing Theoretical Domains

finite_family_overlap_multiplicity_identity

theoremverified

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

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.

  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.

    lines 6–7

      classical
      let E := S.biUnion N
  2. The 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.

    lines 8–24

    uses Finset.sum_congr, Finset.mem_biUnion.mpr, Finset.sum_filter, Finset.mem_filter

      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
  3. 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)}.

    lines 25–31

    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
  4. 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.

    lines 32–35

    uses Finset.mem_biUnion.mp, Finset.card_pos.mpr, Finset.mem_filter.mpr

      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⟩⟩
  5. 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.

    lines 36–43

    uses Finset.sum_congr

      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
  6. 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.

    lines 44–46

    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.

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

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
See it in the graphDiscuss this resultChallenge it