AFTD Auto-Formalizing Theoretical Domains

condorcet_crossed_uniform_family_incidence_bound

theoremverified

For a nonempty r-uniform family F, a set A that is empty or crosses a member of F, and a subfamily B disjoint from A, let Z be the number of sets and d(a) the incidence degree. Then Z times the sum of d over A, plus (rZ-1) times the size of B, is at most (rZ-1)Z.

Statement

theorem condorcet_crossed_uniform_family_incidence_bound
    (m r : ℕ) (hr : 0 < r) (F : Finset (Finset (Fin m))) (hF : F.Nonempty)
    (hcard : ∀ T ∈ F, T.card = r) (A : Finset (Fin m))
    (hcut : A = ∅ ∨ ∃ T ∈ F, (A ∩ T).Nonempty ∧ ¬T ⊆ A)
    (B : Finset (Finset (Fin m))) (hBF : B ⊆ F)
    (hB : ∀ T ∈ B, Disjoint A T) :
    F.card * (∑ a ∈ A, (F.filter fun T => a∈T).card) +
      (r*F.card-1)*B.card ≤ (r*F.card-1)*F.card
Source
IN-383, OP-19 campaign session 9, 2026-10-30. Structural analysis of the S2-to-S3 completion route from IN-362; finite diagnostics audited in experiments9630 and9640. Supports the general campaign only; no new election bound or research novelty is claimed.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

The proof, explained

The proof splits on whether A is empty or crosses some set in F. If A = ∅, the incidence sum vanishes and the bound reduces to (r|F| - 1)|B| ≤ (r|F| - 1)|F|, which follows from B ⊆ F. When A crosses some T ∈ F, we consider the subfamily I ⊆ F of sets intersecting A; double counting shows the incidence sum s equals ∑_{T ∈ I} |A ∩ T| < r|I|, where the inequality is strict because A ∩ T ⊊ T for the crossing set. This yields |F|s + |F| ≤ (r|F|)|I|, and since I and B are disjoint subfamilies of F, |I| + |B| ≤ |F|; combining these two inequalities via linear arithmetic completes the proof.

  1. The desired inequality holds in the case where A = ∅.

    We work classically and split into cases according to `hcut`. If A = ∅, the incidence sum over A is over the empty set and equals 0. The first term |F| · 0 vanishes, simplifying the inequality to (r|F| - 1)|B| ≤ (r|F| - 1)|F|, which follows directly because B ⊆ F implies |B| ≤ |F|.

    lines 14–17

    uses sum_empty, mul_zero, zero_add, Nat.mul_le_mul_left, card_le_card

      classical
      rcases hcut with rfl | ⟨T,hTF,hAT,hTA⟩
      · simp only [sum_empty,mul_zero,zero_add]
        exact Nat.mul_le_mul_left _ (card_le_card hBF)
  2. The sum of incidences s = ∑ a ∈ A, |{T ∈ F : a ∈ T}| equals ∑ T ∈ F, |A ∩ T|.

    In the remaining case, let T ∈ F cross A. We define I ⊆ F as the subfamily of sets intersecting A, and s as the sum of incidence degrees over A. Expressing each cardinality as a sum of 1s and exchanging the order of summation rewrites s = ∑ a ∈ A, ∑ T ∈ F, (if a ∈ T then 1 else 0) into ∑ T ∈ F, ∑ a ∈ A ∩ T, 1 = ∑ T ∈ F, |A ∩ T|.

    lines 18–26

    uses card_eq_sum_ones, sum_filter, sum_comm, sum_congr, filter_mem_eq_inter

      · let I := F.filter fun T => (A ∩ T).Nonempty
        let s := ∑ a ∈ A, (F.filter fun T => a∈T).card
        have hcount : s = ∑ T ∈ F, (A ∩ T).card := by
          dsimp only [s]
          simp only [card_eq_sum_ones,sum_filter]
          rw [sum_comm]
          apply sum_congr rfl
          intro T hT
          rw [← sum_filter,filter_mem_eq_inter]
  3. The sum ∑ T ∈ F, |A ∩ T| equals ∑ T ∈ I, |A ∩ T|.

    For any member T ∈ F not in I, the intersection A ∩ T is empty by definition of I, so |A ∩ T| = 0. Therefore, restricting the domain of summation from F to I preserves the sum.

    lines 27–34

    uses sum_subset, filter_subset, card_eq_zero.mpr, not_nonempty_iff_eq_empty.mp, mem_filter.mpr

        have hrestrict : (∑ T ∈ F, (A ∩ T).card) = ∑ T ∈ I, (A ∩ T).card := by
          symm
          apply sum_subset (filter_subset _ _)
          intro T hTF hTI
          apply card_eq_zero.mpr
          apply not_nonempty_iff_eq_empty.mp
          intro h
          exact hTI (mem_filter.mpr ⟨hTF,h⟩)
  4. The total incidence sum satisfies the strict inequality s < r|I|.

    For every T ∈ I, the intersection A ∩ T is a subset of T, so |A ∩ T| ≤ |T| = r. Furthermore, for the specific crossing set T ∈ F given by the hypothesis, A ∩ T is nonempty and T ⊈ A, which implies that A ∩ T is a strict subset of T; hence |A ∩ T| < |T| = r. Summing these bounds over all T ∈ I yields s = ∑ T ∈ I, |A ∩ T| < ∑ T ∈ I, r = r|I|.

    lines 35–51

    uses mem_filter.mp, card_le_card, inter_subset_right, card_lt_card, Finset.ssubset_iff_subset_ne.mpr, inter_subset_left, sum_lt_sum, mem_filter.mpr, Nat.mul_comm

        have hinc : s < r*I.card := by
          rw [hcount,hrestrict]
          have hle : ∀ T ∈ I, (A ∩ T).card ≤ r := by
            intro T hT
            rw [← hcard T (mem_filter.mp hT).1]
            exact card_le_card inter_subset_right
          have hlt : (A ∩ T).card < r := by
            rw [← hcard T hTF]
            apply card_lt_card
            apply Finset.ssubset_iff_subset_ne.mpr
            refine ⟨inter_subset_right,?_⟩
            intro heq
            apply hTA
            rw [← heq]
            exact inter_subset_left
          have hsum := sum_lt_sum hle ⟨T,mem_filter.mpr ⟨hTF,hAT⟩,hlt⟩
          simpa [Nat.mul_comm] using hsum
  5. The subfamilies I and B are disjoint.

    Every member of I intersects A, whereas every member of B is disjoint from A by hypothesis `hB`. Hence no member can belong to both I and B.

    lines 52–57

    uses disjoint_left.mpr, mem_filter.mp, mem_inter.mp, disjoint_left.mp

        have hdis : Disjoint I B := by
          apply disjoint_left.mpr
          intro T hTI hTB
          obtain ⟨a,ha⟩ := (mem_filter.mp hTI).2
          obtain ⟨haA,haT⟩ := mem_inter.mp ha
          exact disjoint_left.mp (hB T hTB) haA haT
  6. The cardinalities satisfy |I| + |B| ≤ |F|.

    Because I and B are disjoint subfamilies of F, the cardinality of their union is |I| + |B|. Since I ∪ B ⊆ F, this is at most |F|.

    lines 58–60

    uses card_union_of_disjoint, card_le_card, union_subset, filter_subset

        have hIB : I.card+B.card ≤ F.card := by
          rw [← card_union_of_disjoint hdis]
          exact card_le_card (union_subset (filter_subset _ _) hBF)
  7. Setting c = r|F| - 1, we have c + 1 = r|F|.

    Because F is nonempty and r > 0, |F| ≥ 1 and so r|F| ≥ 1. Subtracting 1 and adding 1 therefore cancels to give r|F|.

    lines 61–63

    uses card_pos.mpr, Nat.sub_add_cancel

        let c := r*F.card-1
        have hz : 0 < F.card := card_pos.mpr hF
        have hc : c+1 = r*F.card := Nat.sub_add_cancel (by nlinarith)
  8. The bound |F|s + |F| ≤ (c + 1)|I| holds.

    From the strict inequality s < r|I| between natural numbers, we have s + 1 ≤ r|I|. Multiplying both sides by |F| yields |F|s + |F| = |F|(s + 1) ≤ |F|(r|I|) = (c + 1)|I|, since c + 1 = r|F|.

    lines 64–68

    uses Nat.mul_le_mul_left

        have hx : F.card*s+F.card ≤ (c+1)*I.card := by
          calc
            F.card*s+F.card = F.card*(s+1) := by ring
            _ ≤ F.card*(r*I.card) := Nat.mul_le_mul_left _ (by omega)
            _ = (c+1)*I.card := by rw [hc]; ring
  9. The incidence bound |F|s + (r|F| - 1)|B| ≤ (r|F| - 1)|F| holds.

    Multiplying |I| + |B| ≤ |F| by c + 1 gives (c + 1)(|I| + |B|) ≤ (c + 1)|F|. Combining this with |F|s + |F| ≤ (c + 1)|I| and c = r|F| - 1 via linear arithmetic (`nlinarith`) establishes |F|s + c|B| ≤ c|F|, which is the desired inequality.

    lines 69–71

    uses Nat.mul_le_mul_left

        have hy := Nat.mul_le_mul_left (c+1) hIB
        change F.card*s+c*B.card ≤ c*F.card
        nlinarith
sum_empty
The sum of any function over the empty finset is 0.
mul_zero
Multiplying any element by zero yields zero.
zero_add
Zero added to any element leaves it unchanged.
Nat.mul_le_mul_left
Multiplying both sides of an inequality of natural numbers on the left preserves the inequality.
card_le_card
If one finite set is a subset of another, its cardinality is at most the other's.
card_eq_sum_ones
The cardinality of a finite set equals the sum of 1 over all its elements.
sum_filter
Summing over a filtered set is equal to summing over the original set with an indicator function.
sum_comm
The order of two nested finite summations can be exchanged.
sum_congr
Two finite sums are equal if their index sets are equal and their summands agree pointwise.
filter_mem_eq_inter
Filtering a finite set by membership in another finite set yields their intersection.
sum_subset
If a subset contains all elements where a function is nonzero, summing over the subset gives the same value as summing over the superset.
filter_subset
Filtering a finite set by a predicate produces a subset of the original set.
card_eq_zero.mpr
An empty finite set has cardinality 0.
not_nonempty_iff_eq_empty.mp
A finite set that is not nonempty is the empty set.
mem_filter.mpr
An element in a set that satisfies a predicate belongs to the filtered set.
mem_filter.mp
An element of a filtered set belongs to the original set and satisfies the predicate.
inter_subset_right
The intersection of two sets is a subset of the second set.
card_lt_card
A strict subset of a finite set has strictly smaller cardinality.
Finset.ssubset_iff_subset_ne.mpr
A subset that is not equal to the whole set is a strict subset.
inter_subset_left
The intersection of two sets is a subset of the first set.
sum_lt_sum
If one term-by-term comparison is non-strict and at least one term is strictly smaller, the sum is strictly smaller.
Nat.mul_comm
Multiplication of natural numbers is commutative.
disjoint_left.mpr
Two sets are disjoint if every element of the first set is not in the second set.
disjoint_left.mp
If two sets are disjoint, then every element of the first set does not belong to the second set.
mem_inter.mp
An element in the intersection of two sets belongs to both sets.
card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
union_subset
If two sets are both subsets of a third set, their union is also a subset of the third set.
card_pos.mpr
A nonempty finite set has strictly positive cardinality.
Nat.sub_add_cancel
For natural numbers with m ≤ n, (n - m) + m = n.

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 Finsetopen scoped BigOperatorsset_option maxHeartbeats 30000000set_option maxRecDepth 20000theorem condorcet_crossed_uniform_family_incidence_bound    (m r : ℕ) (hr : 0 < r) (F : Finset (Finset (Fin m))) (hF : F.Nonempty)    (hcard : ∀ T ∈ F, T.card = r) (A : Finset (Fin m))    (hcut : A = ∅ ∨ ∃ T ∈ F, (A ∩ T).Nonempty ∧ ¬T ⊆ A)    (B : Finset (Finset (Fin m))) (hBF : B ⊆ F)    (hB : ∀ T ∈ B, Disjoint A T) :    F.card * (∑ a ∈ A, (F.filter fun T => a∈T).card) +      (r*F.card-1)*B.card ≤ (r*F.card-1)*F.card := by  classical  rcases hcut with rfl | ⟨T,hTF,hAT,hTA⟩  · simp only [sum_empty,mul_zero,zero_add]    exact Nat.mul_le_mul_left _ (card_le_card hBF)  · let I := F.filter fun T => (A ∩ T).Nonempty    let s := ∑ a ∈ A, (F.filter fun T => a∈T).card    have hcount : s = ∑ T ∈ F, (A ∩ T).card := by      dsimp only [s]      simp only [card_eq_sum_ones,sum_filter]      rw [sum_comm]      apply sum_congr rfl      intro T hT      rw [← sum_filter,filter_mem_eq_inter]    have hrestrict : (∑ T ∈ F, (A ∩ T).card) = ∑ T ∈ I, (A ∩ T).card := by      symm      apply sum_subset (filter_subset _ _)      intro T hTF hTI      apply card_eq_zero.mpr      apply not_nonempty_iff_eq_empty.mp      intro h      exact hTI (mem_filter.mpr ⟨hTF,h⟩)    have hinc : s < r*I.card := by      rw [hcount,hrestrict]      have hle : ∀ T ∈ I, (A ∩ T).card ≤ r := by        intro T hT        rw [← hcard T (mem_filter.mp hT).1]        exact card_le_card inter_subset_right      have hlt : (A ∩ T).card < r := by        rw [← hcard T hTF]        apply card_lt_card        apply Finset.ssubset_iff_subset_ne.mpr        refine ⟨inter_subset_right,?_⟩        intro heq        apply hTA        rw [← heq]        exact inter_subset_left      have hsum := sum_lt_sum hle ⟨T,mem_filter.mpr ⟨hTF,hAT⟩,hlt⟩      simpa [Nat.mul_comm] using hsum    have hdis : Disjoint I B := by      apply disjoint_left.mpr      intro T hTI hTB      obtain ⟨a,ha⟩ := (mem_filter.mp hTI).2      obtain ⟨haA,haT⟩ := mem_inter.mp ha      exact disjoint_left.mp (hB T hTB) haA haT    have hIB : I.card+B.card ≤ F.card := by      rw [← card_union_of_disjoint hdis]      exact card_le_card (union_subset (filter_subset _ _) hBF)    let c := r*F.card-1    have hz : 0 < F.card := card_pos.mpr hF    have hc : c+1 = r*F.card := Nat.sub_add_cancel (by nlinarith)    have hx : F.card*s+F.card ≤ (c+1)*I.card := by      calc        F.card*s+F.card = F.card*(s+1) := by ring        _ ≤ F.card*(r*I.card) := Nat.mul_le_mul_left _ (by omega)        _ = (c+1)*I.card := by rw [hc]; ring    have hy := Nat.mul_le_mul_left (c+1) hIB    change F.card*s+c*B.card ≤ c*F.card    nlinarith
See it in the graphDiscuss this resultChallenge it