condorcet_crossed_uniform_family_incidence_bound
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- Used by 1
- condorcet_minimal_predecessor_completion_integer_certificateFor a globally minimal S_k core and a nonempty uniform family F containing every undominated (k+1)-set, the incidence weights Z*d(a) on…
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.
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|.
uses
sum_empty,mul_zero,zero_add,Nat.mul_le_mul_left,card_le_cardclassical 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)
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|.
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]
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.
uses
sum_subset,filter_subset,card_eq_zero.mpr,not_nonempty_iff_eq_empty.mp,mem_filter.mprhave 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⟩)
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|.
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_commhave 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
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.
uses
disjoint_left.mpr,mem_filter.mp,mem_inter.mp,disjoint_left.mphave 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
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|.
uses
card_union_of_disjoint,card_le_card,union_subset,filter_subsethave hIB : I.card+B.card ≤ F.card := by rw [← card_union_of_disjoint hdis] exact card_le_card (union_subset (filter_subset _ _) hBF)
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|.
uses
card_pos.mpr,Nat.sub_add_cancellet 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)
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|.
uses
Nat.mul_le_mul_lefthave 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
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.
uses
Nat.mul_le_mul_lefthave 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
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.
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