AFTD Auto-Formalizing Theoretical Domains

biclique_incidence_sum

theoremverified

For finite disjoint-sided bicliques, total vertex incidence counted by vertices equals total side cardinality counted by bicliques.

Statement

theorem biclique_incidence_sum {I R : Type*} [Fintype I] [Fintype R] [DecidableEq I]
    (A B : R → Finset I) (hdis : ∀ r, Disjoint (A r) (B r)) :
    (∑ i, (univ.filter (fun r => i ∈ A r ∪ B r)).card) =
      ∑ r, ((A r).card + (B r).card)
Source
Uniform full-root-gap and current-scale fullness reduction for OP-205 / RT-1 following arXiv:2610.15635. The reusable finite ordered-cover classification formalizes the deficiency-one structure described in arXiv:1103.3693 Corollary 2.5.6. Explicit full-class or middle-fullness hypotheses remain structural assumptions where used; optimal original counts have not been shown to imply them. No graph covering value or research advance is claimed.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The theorem is proved by a double-counting argument on vertex-biclique incidence pairs. By rewriting cardinalities as sums of indicator functions and swapping the summation order, the total incidence counted over vertices is shown to equal the sum of biclique sizes ∑ r, |A r ∪ B r|. Because each biclique has disjoint sides A r and B r, the cardinality |A r ∪ B r| splits termwise into |A r| + |B r|, completing the proof.

  1. The total incidence counted over vertices equals the sum of biclique sizes: ∑ i, |{r | i ∈ A r ∪ B r}| = ∑ r, |A r ∪ B r|.

    We establish this intermediate identity (he) via double counting. Using classical decidability, card_eq_sum_ones and sum_filter rewrite the set cardinalities into sums of indicator functions (1 if i ∈ A r ∪ B r else 0). Exchanging the order of summation with sum_comm shifts the sum over R to the outside and the sum over I to the inside. By sum_congr, it suffices to equate the inner sums for each r ∈ R: applying sum_filter in reverse rewrites the indicator sum back to a sum of 1s over {i ∈ univ | i ∈ A r ∪ B r}, which filter_mem_eq_inter and univ_inter simplify to the sum of 1s over A r ∪ B r, matching |A r ∪ B r|.

    lines 9–17

    uses card_eq_sum_ones, sum_filter, sum_comm, sum_congr, filter_mem_eq_inter, univ_inter

      classical
      have he : (∑ i, (univ.filter (fun r => i ∈ A r ∪ B r)).card) =
          ∑ r, (A r ∪ B r).card := by
        simp only [card_eq_sum_ones, sum_filter]
        rw [sum_comm]
        apply sum_congr rfl
        intro r hr
        rw [← sum_filter]
        simp only [filter_mem_eq_inter, univ_inter]
  2. It suffices to show that ∑ r, |A r ∪ B r| = ∑ r, (|A r| + |B r|).

    Rewriting the left-hand side of the goal with the double-counting identity he replaces the vertex-incidence sum with the sum of biclique sizes ∑ r, |A r ∪ B r|.

    line 18

      rw [he]
  3. For each r ∈ R, |A r ∪ B r| = |A r| + |B r|, completing the equality of sums.

    By hypothesis hdis, the sets A r and B r are disjoint for every r, so card_union_of_disjoint equates |A r ∪ B r| with |A r| + |B r|. Applying sum_congr with reflexivity on the index sets matches the terms across the summation over R.

    line 19

    uses sum_congr, card_union_of_disjoint

      exact sum_congr rfl (fun r hr => card_union_of_disjoint (hdis r))
card_eq_sum_ones
The cardinality of a finite set s equals the sum of 1 over all elements of s.
card_union_of_disjoint
If two finite sets are disjoint, the cardinality of their union is the sum of their cardinalities.
filter_mem_eq_inter
Filtering a finite set s by membership in a finite set t yields the intersection s ∩ t.
sum_comm
The order of summation in a finite double sum can be swapped.
sum_congr
Two finite sums are equal if their index sets are equal and their summands agree on every element of the index set.
sum_filter
The sum of a function over elements of s satisfying a predicate p equals the sum over all elements of s of the indicator if p a then f a else 0.
univ_inter
The intersection of the universal finite set with any finite subset s is s itself.

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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem biclique_incidence_sum {I R : Type*} [Fintype I] [Fintype R] [DecidableEq I]    (A B : R → Finset I) (hdis : ∀ r, Disjoint (A r) (B r)) :    (∑ i, (univ.filter (fun r => i ∈ A r ∪ B r)).card) =      ∑ r, ((A r).card + (B r).card) := by  classical  have he : (∑ i, (univ.filter (fun r => i ∈ A r ∪ B r)).card) =      ∑ r, (A r ∪ B r).card := by    simp only [card_eq_sum_ones, sum_filter]    rw [sum_comm]    apply sum_congr rfl    intro r hr    rw [← sum_filter]    simp only [filter_mem_eq_inter, univ_inter]  rw [he]  exact sum_congr rfl (fun r hr => card_union_of_disjoint (hdis r))
See it in the graphDiscuss this resultChallenge it