condorcet_small_complement_fractional_cover
For k at least two, let a finite nonnegative real-weighted family of subsets have unit weighted coverage at every element of a specified finite set T. Suppose each positive-weight member misses at most k elements of T, and the total weight is strictly less than k+1. Then at most k positive-weight members cover T.
Statement
theorem condorcet_small_complement_fractional_cover {m n k : ℕ} (hk : 2 ≤ k) (T : Finset (Fin n)) (A : Fin m → Finset (Fin n)) (w : Fin m → ℝ) (hw : ∀ a, 0 ≤ w a) (hmiss : ∀ a, 0 < w a → (T \ A a).card ≤ k) (hload : ∀ v ∈ T, (∑ a : Fin m, if v ∈ A a then w a else 0) = 1) (hmass : (∑ a : Fin m, w a) < (k + 1 : ℕ)) : ∃ J : Finset (Fin m), J.card ≤ k ∧ (∀ a ∈ J, 0 < w a) ∧ ∀ v ∈ T, ∃ a ∈ J, v ∈ A a
- Source
- IN-391, OP-19 campaign session10, 2026-10-30. Supporting lemmas and precisely scoped method diagnostics for the rank-saturated acyclic-cover route. The main election theorem remains open; no new election bound or novelty is claimed.
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- condorcet_cover_rank_relationThe loopless rank-compatible relation: an arrow a to b is permitted precisely when a differs from b and a has a strictly smaller…
The proof, explained
We first establish two helpers: an elementwise selector function exists via the axiom of choice, and double sums can be evaluated via set intersections. To cover T with at most k positive-weight sets (k ≥ 2), if |T| ≤ k we select one set per element. When |T| > k, if some set misses at most k - 1 elements or two sets overlap on the complement by at least 2 elements, taking those sets and covering the remaining elements individually yields a cover of size at most k. Otherwise, every set misses exactly k elements and complement intersections have size at most 1, which double-counting coverage over both the complement of a set and all of T shows is mathematically impossible under the total weight bound.
For any subset S ⊆ T, there exists a function choosing for each v ∈ S a set of positive weight containing v.
For each element v, if v ∈ S, its fractional coverage sum equals 1. If every set containing v had weight 0, the sum would be 0 by Finset.sum_eq_zero, a contradiction; thus some set a satisfies w(a) > 0 and v ∈ A(a). If v ∉ S, an arbitrary index is chosen via Classical.arbitrary. The axiom of choice extracts a function f selecting a positive-weight set covering each v ∈ S.
uses
Finset.sum_eq_zero,Classical.arbitraryhave h_ex : ∀ v : Fin n, ∃ a : Fin m, v ∈ S → 0 < w a ∧ v ∈ A a := by intro v by_cases hv : v ∈ S · have h_sum := hload v (hST hv) have : ∃ a : Fin m, 0 < w a ∧ v ∈ A a := by by_contra h_none have h_zero : (∑ a : Fin m, if v ∈ A a then w a else 0) = 0 := by apply Finset.sum_eq_zero intro a _ split_ifs with h_in · have hwa : w a = 0 := by have h_not : ¬ (0 < w a ∧ v ∈ A a) := fun h => h_none ⟨a, h⟩ have h_not_pos : ¬ (0 < w a) := fun hp => h_not ⟨hp, h_in⟩ have := hw a linarith exact hwa · rfl linarith rcases this with ⟨a, ha⟩ exact ⟨a, fun _ => ha⟩ · exact ⟨Classical.arbitrary (Fin m), fun h => (hv h).elim⟩ choose f hf using h_ex exact ⟨f, fun v hv => hf v hv⟩
The double sum ∑_{v ∈ S} ∑_a [v ∈ A(a)] w(a) equals ∑_a w(a) · |S ∩ A(a)|.
We interchange the order of summation using sum_comm. Applying sum_congr, for each index a we rewrite the conditional sum over S as a sum over the filtered set {v ∈ S | v ∈ A(a)} via sum_filter. This filtered set is precisely S ∩ A(a). Summing the constant w(a) over S ∩ A(a) yields |S ∩ A(a)| · w(a) by sum_const and nsmul_eq_mul, which rearranges to w(a) · |S ∩ A(a)|.
uses
sum_comm,sum_congr,sum_filter,sum_const,nsmul_eq_mulrw [sum_comm] apply sum_congr rfl intro a _ rw [← sum_filter] have : (filter (fun v => v ∈ A a) S) = S ∩ A a := by ext v simp [mem_inter] rw [this, sum_const, nsmul_eq_mul] ring
If T is empty, the empty family J = ∅ trivially satisfies all conditions.
When |T| ≤ k and T = ∅, taking J = ∅ has cardinality 0 ≤ k, vacuously satisfies that all elements have positive weight, and vacuously covers every element of T.
by_cases hT : T.card ≤ k · by_cases h_emp : T = ∅ · use ∅ refine ⟨by simp, fun a ha => by simp at ha, fun v hv => by simp [h_emp] at hv⟩
When 0 < |T| ≤ k, selecting one positive-weight set covering each element of T yields a valid cover of size at most k.
Because T is nonempty, there is an element v₀ ∈ T; its unit coverage implies the family of sets is nonempty, as an empty family would have total sum 0. Using condorcet_choose_cov_on, we choose a function f mapping each v ∈ T to an index with w(f(v)) > 0 and v ∈ A(f(v)). The image J = f(T) has cardinality at most |T| ≤ k by card_image_le, contains only indices of positive weight, and covers T by mem_image_of_mem.
uses
Finset.sum_of_isEmpty,condorcet_choose_cov_on,subset_rfl,card_image_le,mem_image_of_mem· have hT_nonempty : T.Nonempty := nonempty_iff_ne_empty.mpr h_emp rcases hT_nonempty with ⟨v0, hv0⟩ have : Nonempty (Fin m) := by have h := hload v0 hv0 by_contra h_empty have hm0 : IsEmpty (Fin m) := not_nonempty_iff.mp h_empty have : (∑ a : Fin m, if v0 ∈ A a then w a else 0) = 0 := Finset.sum_of_isEmpty _ linarith rcases condorcet_choose_cov_on T A w hw hload T subset_rfl with ⟨f, hf⟩ use T.image f refine ⟨by have := card_image_le (s := T) (f := f); omega, ?_, ?_⟩ · intro x hx rcases mem_image.mp hx with ⟨v, hv, rfl⟩ exact (hf v hv).1 · intro v hv exact ⟨f v, mem_image_of_mem f hv, (hf v hv).2⟩
When |T| > k, both T and the indexing set Fin m are nonempty.
Since |T| > k ≥ 2, T is nonempty, so there exists some v₀ ∈ T. The load condition at v₀ requires the coverage sum to equal 1, which implies Fin m cannot be empty by Finset.sum_of_isEmpty.
uses
Finset.sum_of_isEmpty· have hT_gt : k < T.card := not_le.mp hT have hT_nonempty : T.Nonempty := by by_contra hc have : T = ∅ := not_nonempty_iff_eq_empty.mp hc subst this simp at hT_gt rcases hT_nonempty with ⟨v0, hv0⟩ have : Nonempty (Fin m) := by have h := hload v0 hv0 by_contra h_empty have hm0 : IsEmpty (Fin m) := not_nonempty_iff.mp h_empty have : (∑ a : Fin m, if v0 ∈ A a then w a else 0) = 0 := Finset.sum_of_isEmpty _ linarith
If some positive-weight set A(a) misses at most k - 1 elements of T, then a together with sets covering each missed element forms a cover of size at most k.
Applying condorcet_choose_cov_on to the complement T \\ A(a) ⊆ T (via sdiff_subset) provides a selector f choosing positive-weight sets covering each missed element. Letting J = {a} ∪ f(T \\ A(a)), its size is at most 1 + |T \\ A(a)| ≤ 1 + (k - 1) = k by card_insert_le and card_image_le. Every element of J has positive weight, and each v ∈ T is covered by a (by mem_insert_self) if v ∈ A(a), or by f(v) ∈ J (by mem_insert_of_mem) if v ∈ T \\ A(a).
uses
condorcet_choose_cov_on,sdiff_subset,card_insert_le,card_image_le,mem_insert_self,mem_insert_of_mem,mem_image_of_memby_cases h_less : ∃ a, 0 < w a ∧ (T \ A a).card ≤ k - 1 · rcases h_less with ⟨a, hwa, hR⟩ rcases condorcet_choose_cov_on T A w hw hload (T \ A a) sdiff_subset with ⟨f, hf⟩ let J := insert a ((T \ A a).image f) use J refine ⟨?_, ?_, ?_⟩ · dsimp [J] have h1 := card_insert_le a ((T \ A a).image f) have h2 := card_image_le (s := T \ A a) (f := f) omega · intro x hx simp only [J, mem_insert, mem_image] at hx rcases hx with rfl | ⟨v, hv, rfl⟩ · exact hwa · exact (hf v hv).1 · intro v hv by_cases h : v ∈ A a · exact ⟨a, mem_insert_self a _, h⟩ · have hmem : v ∈ T \ A a := mem_sdiff.mpr ⟨hv, h⟩ refine ⟨f v, mem_insert_of_mem (mem_image_of_mem f hmem), (hf v hmem).2⟩
If two positive-weight sets A(a) and A(b) overlap on T \\ A(a) by at least 2 elements, adjoining both to sets covering the remainder gives a cover of size at most k.
Since |T \\ A(a)| ≤ k and |(T \\ A(a)) ∩ A(b)| ≥ 2, the remaining uncovered set (T \\ A(a)) \\ A(b) has cardinality at most k - 2 by card_sdiff and inter_comm. Using condorcet_choose_cov_on on this subset (valid by subset_trans and sdiff_subset), we select positive-weight covering sets via a function f. Defining J = {a, b} ∪ f((T \\ A(a)) \\ A(b)), bounding its size using card_insert_le and card_image_le yields |J| ≤ 2 + (k - 2) = k. All elements of J have positive weight, and every v ∈ T is covered by a, b, or f(v).
uses
condorcet_choose_cov_on,subset_trans,sdiff_subset,card_sdiff,inter_comm,card_insert_le,card_image_le,mem_insert_self,mem_insert_of_mem,mem_image_of_mem· have h_not_less : ∀ a, 0 < w a → k - 1 < (T \ A a).card := by intro a ha by_contra hc exact h_less ⟨a, ha, not_lt.mp hc⟩ by_cases h_pair : ∃ a b, 0 < w a ∧ 0 < w b ∧ 2 ≤ ((T \ A a) ∩ A b).card · rcases h_pair with ⟨a, b, hwa, hwb, h_inter⟩ rcases condorcet_choose_cov_on T A w hw hload ((T \ A a) \ A b) (subset_trans sdiff_subset sdiff_subset) with ⟨f, hf⟩ let J := insert a (insert b (((T \ A a) \ A b).image f)) use J have hR_card : ((T \ A a) \ A b).card ≤ k - 2 := by have hS_card : (T \ A a).card ≤ k := hmiss a hwa rw [card_sdiff, inter_comm] omega refine ⟨?_, ?_, ?_⟩ · dsimp [J] have h1 := card_insert_le a (insert b (((T \ A a) \ A b).image f)) have h2 := card_insert_le b (((T \ A a) \ A b).image f) have h3 := card_image_le (s := (T \ A a) \ A b) (f := f) omega · intro x hx simp only [J, mem_insert, mem_image] at hx rcases hx with rfl | rfl | ⟨v, hv, rfl⟩ · exact hwa · exact hwb · exact (hf v hv).1 · intro v hv by_cases ha : v ∈ A a · exact ⟨a, mem_insert_self a _, ha⟩ · by_cases hb : v ∈ A b · exact ⟨b, mem_insert_of_mem (mem_insert_self b _), hb⟩ · have hmem : v ∈ (T \ A a) \ A b := by rw [mem_sdiff, mem_sdiff] exact ⟨⟨hv, ha⟩, hb⟩ refine ⟨f v, mem_insert_of_mem (mem_insert_of_mem (mem_image_of_mem f hmem)), (hf v hmem).2⟩
In the remaining branch, every positive-weight set misses exactly k elements of T, any two positive-weight sets overlap on the complement by at most 1 element, and there exists at least one positive-weight set.
Because no positive-weight set misses ≤ k - 1 elements and every positive-weight set misses ≤ k elements, every such set misses exactly k elements. Furthermore, no pair overlaps on the complement by ≥ 2 elements, so any two positive-weight sets overlap on the complement by at most 1 element. Finally, since the sum of weights covering v₀ ∈ T is 1, not all weights can be 0 by Finset.sum_eq_zero, providing an index a with w(a) > 0.
uses
Finset.sum_eq_zero· have h_not_pair : ∀ a b, 0 < w a → 0 < w b → ((T \ A a) ∩ A b).card < 2 := by intro a b ha hb by_contra hc exact h_pair ⟨a, b, ha, hb, not_lt.mp hc⟩ have h_eq_k : ∀ a, 0 < w a → (T \ A a).card = k := by intro a ha have h1 := hmiss a ha have h2 := h_not_less a ha omega have h_inter_le : ∀ a b, 0 < w a → 0 < w b → ((T \ A a) ∩ A b).card ≤ 1 := by intro a b ha hb have := h_not_pair a b ha hb omega have h_sum_v0 := hload v0 hv0 have h_ex_a : ∃ a, 0 < w a := by by_contra hc have h_zero : (∑ a : Fin m, if v0 ∈ A a then w a else 0) = 0 := by apply Finset.sum_eq_zero intro a _ split_ifs · have : ¬ (0 < w a) := fun hp => hc ⟨a, hp⟩ have : w a = 0 := by linarith [hw a] exact this · rfl linarith rcases h_ex_a with ⟨a, hwa⟩
The total weight ∑ b, w b strictly exceeds k.
Double-counting the coverage over T \\ A(a) using condorcet_sum_double_inter, sum_congr, and sum_const with nsmul_eq_mul shows that k = |T \\ A(a)| = ∑ b, w(b) |(T \\ A(a)) ∩ A(b)|. In this sum, the b = a term vanishes because (T \\ A(a)) ∩ A(a) = ∅. For each b ≠ a, the intersection size is at most 1, so the summand is at most w(b). Splitting the sum with Finset.add_sum_erase and mem_univ, and applying sum_le_sum, gives k ≤ ∑_{b ≠ a} w(b) = (∑ b, w(b)) - w(a). Since w(a) > 0, this implies ∑ b, w(b) > k.
uses
condorcet_sum_double_inter,sum_congr,sum_const,nsmul_eq_mul,Finset.add_sum_erase,mem_univ,sum_le_sumhave h_sum_sdiff : ((T \ A a).card : ℝ) = ∑ b : Fin m, w b * ((T \ A a) ∩ A b).card := by have h1 : (∑ v ∈ T \ A a, ∑ b : Fin m, if v ∈ A b then w b else 0) = ∑ b : Fin m, w b * ((T \ A a) ∩ A b).card := condorcet_sum_double_inter (T \ A a) A w have h2 : (∑ v ∈ T \ A a, ∑ b : Fin m, if v ∈ A b then w b else 0) = ∑ v ∈ T \ A a, (1 : ℝ) := by apply sum_congr rfl intro v hv exact hload v (mem_sdiff.mp hv).1 rw [h2, sum_const, nsmul_eq_mul, mul_one] at h1 exact h1 have h_card_sdiff_k : ((T \ A a).card : ℝ) = (k : ℝ) := by rw [h_eq_k a hwa] rw [h_card_sdiff_k] at h_sum_sdiff have h_bound : (∑ b : Fin m, w b * ((T \ A a) ∩ A b).card) ≤ (∑ b : Fin m, w b) - w a := by have h_disj : (T \ A a) ∩ A a = ∅ := by ext v simp have h_card_a : (((T \ A a) ∩ A a).card : ℝ) = 0 := by simp [h_disj] have h_le : ∀ b : Fin m, b ≠ a → w b * ((T \ A a) ∩ A b).card ≤ w b := by intro b _ by_cases hwb : 0 < w b · have h1 : (((T \ A a) ∩ A b).card : ℝ) ≤ 1 := by exact_mod_cast (h_inter_le a b hwa hwb) nlinarith [hw b] · have : w b = 0 := by linarith [hw b] simp [this] have h_sum : (∑ b : Fin m, w b * ((T \ A a) ∩ A b).card) = w a * (((T \ A a) ∩ A a).card : ℝ) + ∑ b ∈ univ.erase a, w b * ((T \ A a) ∩ A b).card := by exact (Finset.add_sum_erase univ (fun b => w b * ((T \ A a) ∩ A b).card) (mem_univ a)).symm rw [h_sum, h_card_a, mul_zero, zero_add] have h_erase : (∑ b ∈ univ.erase a, w b * ((T \ A a) ∩ A b).card) ≤ ∑ b ∈ univ.erase a, w b := by apply sum_le_sum intro b hb exact h_le b (mem_erase.mp hb).1 have h_orig : (∑ b ∈ univ.erase a, w b) = (∑ b : Fin m, w b) - w a := by have := (Finset.add_sum_erase univ w (mem_univ a)).symm linarith linarith have h_gt_k : (k : ℝ) < ∑ b : Fin m, w b := by linarith [h_sum_sdiff, h_bound]
The cardinality of T satisfies |T| = (∑ b, w b) · (|T| - k).
Summing coverage over all of T gives |T| = ∑ b, w(b) |T ∩ A(b)| by condorcet_sum_double_inter, sum_congr, and sum_const with nsmul_eq_mul. For any b with w(b) > 0, identified via lt_of_le_of_ne and Ne.symm, the set misses exactly k elements, so |T ∩ A(b)| = |T| - k by card_sdiff_of_subset and sdiff_subset. Using Nat.cast_sub and factoring the constant difference (|T| - k) out of the sum yields |T| = (∑ b, w(b)) (|T| - k).
uses
condorcet_sum_double_inter,sum_congr,sum_const,nsmul_eq_mul,lt_of_le_of_ne,Ne.symm,card_sdiff_of_subset,sdiff_subset,Nat.cast_subhave hkT : k ≤ T.card := by omega have h_sum_T : (T.card : ℝ) = (∑ b : Fin m, w b) * (T.card - k : ℝ) := by have h1 : (∑ v ∈ T, ∑ b : Fin m, if v ∈ A b then w b else 0) = ∑ b : Fin m, w b * (T ∩ A b).card := condorcet_sum_double_inter T A w have h2 : (∑ v ∈ T, ∑ b : Fin m, if v ∈ A b then w b else 0) = ∑ v ∈ T, (1 : ℝ) := by apply sum_congr rfl intro v hv exact hload v hv rw [h2, sum_const, nsmul_eq_mul, mul_one] at h1 have h3 : ∀ b : Fin m, w b * (T ∩ A b).card = w b * (T.card - k : ℝ) := by intro b by_cases hwb : w b = 0 · simp [hwb] · have hpos : 0 < w b := lt_of_le_of_ne (hw b) (Ne.symm hwb) have hcard : (T ∩ A b).card = T.card - k := by have hsdiff : (T \ A b).card = k := h_eq_k b hpos have h_inter : (T ∩ A b).card = T.card - (T \ A b).card := by have h_sub : T ∩ A b = T \ (T \ A b) := by ext x simp only [mem_inter, mem_sdiff] tauto rw [h_sub, card_sdiff_of_subset sdiff_subset] omega rw [hcard, Nat.cast_sub hkT] have h4 : (∑ b : Fin m, w b * (T ∩ A b).card) = ∑ b : Fin m, w b * (T.card - k : ℝ) := by apply sum_congr rfl intro b _ exact h3 b rw [h4, ← sum_mul] at h1 exact h1
Both cases |T| = k + 1 and |T| ≥ k + 2 lead to contradictions, completing the proof.
If |T| = k + 1, then |T| - k = 1, so the relation gives ∑ b, w(b) = k + 1, contradicting the hypothesis that total weight is strictly less than k + 1. If |T| ≥ k + 2, since k ≥ 2, the inequality |T| ≤ k(|T| - k) holds; dividing by |T| - k > 0 using mul_le_mul_iff_of_pos_right gives ∑ b, w(b) ≤ k, which contradicts the lower bound ∑ b, w(b) > k.
uses
mul_le_mul_iff_of_pos_rightby_cases ht_eq : T.card = k + 1 · have h_sub_1 : (T.card - k : ℝ) = 1 := by rw [ht_eq] push_cast ring rw [h_sub_1, mul_one] at h_sum_T have hmass_real : (∑ a : Fin m, w a) < (k + 1 : ℝ) := by exact_mod_cast hmass rw [← h_sum_T, ht_eq] at hmass_real push_cast at hmass_real linarith · have ht_ge : k + 2 ≤ T.card := by omega have hk_pos : (0 : ℝ) < (T.card - k : ℝ) := by have : (k : ℝ) + 2 ≤ (T.card : ℝ) := by exact_mod_cast ht_ge linarith have h_le_k : (∑ b : Fin m, w b) ≤ (k : ℝ) := by have h2 : (T.card : ℝ) ≤ (k : ℝ) * (T.card - k : ℝ) := by have : (k : ℝ) + 2 ≤ (T.card : ℝ) := by exact_mod_cast ht_ge have hk_ge_2 : (2 : ℝ) ≤ (k : ℝ) := by exact_mod_cast hk nlinarith nth_rw 1 [h_sum_T] at h2 exact (mul_le_mul_iff_of_pos_right hk_pos).mp h2 linarith
condorcet_choose_cov_on- For any subset S of T, there is a choice function selecting for each element of S a set of positive weight covering it.
Classical.arbitrary- Returns an arbitrary element of a nonempty type.
sum_comm- Finite summation operators commute with each other.
sum_congr- Two sums are equal if their index sets are equal and their summands are pointwise equal on the index set.
sum_filter- A sum over elements satisfying a predicate equals the sum over the entire set with an if-then-else condition.
sum_const- The sum of a constant value over a finite set equals the cardinality of the set times the constant.
nsmul_eq_mul- Natural number scalar multiplication in a semiring is ordinary multiplication by the coerced natural.
Finset.sum_of_isEmpty- A sum over a finite set whose index type is empty equals zero.
subset_rfl- Any set is a subset of itself.
card_image_le- The cardinality of the image of a finite set under any function is at most the cardinality of the domain set.
mem_image_of_mem- If an element belongs to a set, its image under a function belongs to the image of that set.
sdiff_subset- The set difference s \\ t is a subset of s.
card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1.
mem_insert_self- An element belongs to the set obtained by inserting it into any set.
mem_insert_of_mem- If an element belongs to a set, it also belongs to the set obtained by inserting any element.
subset_trans- Subset inclusion is transitive.
card_sdiff- The cardinality of the difference t \\ s is the cardinality of t minus the cardinality of s ∩ t.
inter_comm- Intersection of sets is commutative.
Finset.sum_eq_zero- If every term in a finite sum is zero, the sum is zero.
condorcet_sum_double_inter- Summing the weighted coverage over elements of S equals the sum over all sets of their weight times the cardinality of their intersection with S.
Finset.add_sum_erase- Splitting off the term at an element a from a sum over s yields f(a) plus the sum over s without a.
mem_univ- Every element of a finite type belongs to the universal finite set.
sum_le_sum- A sum of smaller-or-equal terms is less than or equal to the sum of larger-or-equal terms.
lt_of_le_of_ne- A non-strict inequality together with inequality implies strict inequality.
Ne.symm- Inequality is symmetric.
card_sdiff_of_subset- If s is a subset of t, the cardinality of t \\ s is |t| - |s|.
Nat.cast_sub- Coercion from natural numbers to a ring preserves subtraction when m ≤ n.
mul_le_mul_iff_of_pos_right- Multiplying by a strictly positive number preserves and reflects non-strict inequality.
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 Finset BigOperatorstheorem condorcet_choose_cov_on {m n : ℕ} [Nonempty (Fin m)] (T : Finset (Fin n)) (A : Fin m → Finset (Fin n)) (w : Fin m → ℝ) (hw : ∀ a, 0 ≤ w a) (hload : ∀ v ∈ T, (∑ a : Fin m, if v ∈ A a then w a else 0) = 1) (S : Finset (Fin n)) (hST : S ⊆ T) : ∃ f : Fin n → Fin m, (∀ v ∈ S, 0 < w (f v) ∧ v ∈ A (f v)) := by have h_ex : ∀ v : Fin n, ∃ a : Fin m, v ∈ S → 0 < w a ∧ v ∈ A a := by intro v by_cases hv : v ∈ S · have h_sum := hload v (hST hv) have : ∃ a : Fin m, 0 < w a ∧ v ∈ A a := by by_contra h_none have h_zero : (∑ a : Fin m, if v ∈ A a then w a else 0) = 0 := by apply Finset.sum_eq_zero intro a _ split_ifs with h_in · have hwa : w a = 0 := by have h_not : ¬ (0 < w a ∧ v ∈ A a) := fun h => h_none ⟨a, h⟩ have h_not_pos : ¬ (0 < w a) := fun hp => h_not ⟨hp, h_in⟩ have := hw a linarith exact hwa · rfl linarith rcases this with ⟨a, ha⟩ exact ⟨a, fun _ => ha⟩ · exact ⟨Classical.arbitrary (Fin m), fun h => (hv h).elim⟩ choose f hf using h_ex exact ⟨f, fun v hv => hf v hv⟩theorem condorcet_sum_double_inter {m n : ℕ} (S : Finset (Fin n)) (A : Fin m → Finset (Fin n)) (w : Fin m → ℝ) : (∑ v ∈ S, ∑ a : Fin m, if v ∈ A a then w a else 0) = ∑ a : Fin m, w a * (S ∩ A a).card := by rw [sum_comm] apply sum_congr rfl intro a _ rw [← sum_filter] have : (filter (fun v => v ∈ A a) S) = S ∩ A a := by ext v simp [mem_inter] rw [this, sum_const, nsmul_eq_mul] ringtheorem condorcet_small_complement_fractional_cover {m n k : ℕ} (hk : 2 ≤ k) (T : Finset (Fin n)) (A : Fin m → Finset (Fin n)) (w : Fin m → ℝ) (hw : ∀ a, 0 ≤ w a) (hmiss : ∀ a, 0 < w a → (T \ A a).card ≤ k) (hload : ∀ v ∈ T, (∑ a : Fin m, if v ∈ A a then w a else 0) = 1) (hmass : (∑ a : Fin m, w a) < (k + 1 : ℕ)) : ∃ J : Finset (Fin m), J.card ≤ k ∧ (∀ a ∈ J, 0 < w a) ∧ ∀ v ∈ T, ∃ a ∈ J, v ∈ A a := by by_cases hT : T.card ≤ k · by_cases h_emp : T = ∅ · use ∅ refine ⟨by simp, fun a ha => by simp at ha, fun v hv => by simp [h_emp] at hv⟩ · have hT_nonempty : T.Nonempty := nonempty_iff_ne_empty.mpr h_emp rcases hT_nonempty with ⟨v0, hv0⟩ have : Nonempty (Fin m) := by have h := hload v0 hv0 by_contra h_empty have hm0 : IsEmpty (Fin m) := not_nonempty_iff.mp h_empty have : (∑ a : Fin m, if v0 ∈ A a then w a else 0) = 0 := Finset.sum_of_isEmpty _ linarith rcases condorcet_choose_cov_on T A w hw hload T subset_rfl with ⟨f, hf⟩ use T.image f refine ⟨by have := card_image_le (s := T) (f := f); omega, ?_, ?_⟩ · intro x hx rcases mem_image.mp hx with ⟨v, hv, rfl⟩ exact (hf v hv).1 · intro v hv exact ⟨f v, mem_image_of_mem f hv, (hf v hv).2⟩ · have hT_gt : k < T.card := not_le.mp hT have hT_nonempty : T.Nonempty := by by_contra hc have : T = ∅ := not_nonempty_iff_eq_empty.mp hc subst this simp at hT_gt rcases hT_nonempty with ⟨v0, hv0⟩ have : Nonempty (Fin m) := by have h := hload v0 hv0 by_contra h_empty have hm0 : IsEmpty (Fin m) := not_nonempty_iff.mp h_empty have : (∑ a : Fin m, if v0 ∈ A a then w a else 0) = 0 := Finset.sum_of_isEmpty _ linarith by_cases h_less : ∃ a, 0 < w a ∧ (T \ A a).card ≤ k - 1 · rcases h_less with ⟨a, hwa, hR⟩ rcases condorcet_choose_cov_on T A w hw hload (T \ A a) sdiff_subset with ⟨f, hf⟩ let J := insert a ((T \ A a).image f) use J refine ⟨?_, ?_, ?_⟩ · dsimp [J] have h1 := card_insert_le a ((T \ A a).image f) have h2 := card_image_le (s := T \ A a) (f := f) omega · intro x hx simp only [J, mem_insert, mem_image] at hx rcases hx with rfl | ⟨v, hv, rfl⟩ · exact hwa · exact (hf v hv).1 · intro v hv by_cases h : v ∈ A a · exact ⟨a, mem_insert_self a _, h⟩ · have hmem : v ∈ T \ A a := mem_sdiff.mpr ⟨hv, h⟩ refine ⟨f v, mem_insert_of_mem (mem_image_of_mem f hmem), (hf v hmem).2⟩ · have h_not_less : ∀ a, 0 < w a → k - 1 < (T \ A a).card := by intro a ha by_contra hc exact h_less ⟨a, ha, not_lt.mp hc⟩ by_cases h_pair : ∃ a b, 0 < w a ∧ 0 < w b ∧ 2 ≤ ((T \ A a) ∩ A b).card · rcases h_pair with ⟨a, b, hwa, hwb, h_inter⟩ rcases condorcet_choose_cov_on T A w hw hload ((T \ A a) \ A b) (subset_trans sdiff_subset sdiff_subset) with ⟨f, hf⟩ let J := insert a (insert b (((T \ A a) \ A b).image f)) use J have hR_card : ((T \ A a) \ A b).card ≤ k - 2 := by have hS_card : (T \ A a).card ≤ k := hmiss a hwa rw [card_sdiff, inter_comm] omega refine ⟨?_, ?_, ?_⟩ · dsimp [J] have h1 := card_insert_le a (insert b (((T \ A a) \ A b).image f)) have h2 := card_insert_le b (((T \ A a) \ A b).image f) have h3 := card_image_le (s := (T \ A a) \ A b) (f := f) omega · intro x hx simp only [J, mem_insert, mem_image] at hx rcases hx with rfl | rfl | ⟨v, hv, rfl⟩ · exact hwa · exact hwb · exact (hf v hv).1 · intro v hv by_cases ha : v ∈ A a · exact ⟨a, mem_insert_self a _, ha⟩ · by_cases hb : v ∈ A b · exact ⟨b, mem_insert_of_mem (mem_insert_self b _), hb⟩ · have hmem : v ∈ (T \ A a) \ A b := by rw [mem_sdiff, mem_sdiff] exact ⟨⟨hv, ha⟩, hb⟩ refine ⟨f v, mem_insert_of_mem (mem_insert_of_mem (mem_image_of_mem f hmem)), (hf v hmem).2⟩ · have h_not_pair : ∀ a b, 0 < w a → 0 < w b → ((T \ A a) ∩ A b).card < 2 := by intro a b ha hb by_contra hc exact h_pair ⟨a, b, ha, hb, not_lt.mp hc⟩ have h_eq_k : ∀ a, 0 < w a → (T \ A a).card = k := by intro a ha have h1 := hmiss a ha have h2 := h_not_less a ha omega have h_inter_le : ∀ a b, 0 < w a → 0 < w b → ((T \ A a) ∩ A b).card ≤ 1 := by intro a b ha hb have := h_not_pair a b ha hb omega have h_sum_v0 := hload v0 hv0 have h_ex_a : ∃ a, 0 < w a := by by_contra hc have h_zero : (∑ a : Fin m, if v0 ∈ A a then w a else 0) = 0 := by apply Finset.sum_eq_zero intro a _ split_ifs · have : ¬ (0 < w a) := fun hp => hc ⟨a, hp⟩ have : w a = 0 := by linarith [hw a] exact this · rfl linarith rcases h_ex_a with ⟨a, hwa⟩ have h_sum_sdiff : ((T \ A a).card : ℝ) = ∑ b : Fin m, w b * ((T \ A a) ∩ A b).card := by have h1 : (∑ v ∈ T \ A a, ∑ b : Fin m, if v ∈ A b then w b else 0) = ∑ b : Fin m, w b * ((T \ A a) ∩ A b).card := condorcet_sum_double_inter (T \ A a) A w have h2 : (∑ v ∈ T \ A a, ∑ b : Fin m, if v ∈ A b then w b else 0) = ∑ v ∈ T \ A a, (1 : ℝ) := by apply sum_congr rfl intro v hv exact hload v (mem_sdiff.mp hv).1 rw [h2, sum_const, nsmul_eq_mul, mul_one] at h1 exact h1 have h_card_sdiff_k : ((T \ A a).card : ℝ) = (k : ℝ) := by rw [h_eq_k a hwa] rw [h_card_sdiff_k] at h_sum_sdiff have h_bound : (∑ b : Fin m, w b * ((T \ A a) ∩ A b).card) ≤ (∑ b : Fin m, w b) - w a := by have h_disj : (T \ A a) ∩ A a = ∅ := by ext v simp have h_card_a : (((T \ A a) ∩ A a).card : ℝ) = 0 := by simp [h_disj] have h_le : ∀ b : Fin m, b ≠ a → w b * ((T \ A a) ∩ A b).card ≤ w b := by intro b _ by_cases hwb : 0 < w b · have h1 : (((T \ A a) ∩ A b).card : ℝ) ≤ 1 := by exact_mod_cast (h_inter_le a b hwa hwb) nlinarith [hw b] · have : w b = 0 := by linarith [hw b] simp [this] have h_sum : (∑ b : Fin m, w b * ((T \ A a) ∩ A b).card) = w a * (((T \ A a) ∩ A a).card : ℝ) + ∑ b ∈ univ.erase a, w b * ((T \ A a) ∩ A b).card := by exact (Finset.add_sum_erase univ (fun b => w b * ((T \ A a) ∩ A b).card) (mem_univ a)).symm rw [h_sum, h_card_a, mul_zero, zero_add] have h_erase : (∑ b ∈ univ.erase a, w b * ((T \ A a) ∩ A b).card) ≤ ∑ b ∈ univ.erase a, w b := by apply sum_le_sum intro b hb exact h_le b (mem_erase.mp hb).1 have h_orig : (∑ b ∈ univ.erase a, w b) = (∑ b : Fin m, w b) - w a := by have := (Finset.add_sum_erase univ w (mem_univ a)).symm linarith linarith have h_gt_k : (k : ℝ) < ∑ b : Fin m, w b := by linarith [h_sum_sdiff, h_bound] have hkT : k ≤ T.card := by omega have h_sum_T : (T.card : ℝ) = (∑ b : Fin m, w b) * (T.card - k : ℝ) := by have h1 : (∑ v ∈ T, ∑ b : Fin m, if v ∈ A b then w b else 0) = ∑ b : Fin m, w b * (T ∩ A b).card := condorcet_sum_double_inter T A w have h2 : (∑ v ∈ T, ∑ b : Fin m, if v ∈ A b then w b else 0) = ∑ v ∈ T, (1 : ℝ) := by apply sum_congr rfl intro v hv exact hload v hv rw [h2, sum_const, nsmul_eq_mul, mul_one] at h1 have h3 : ∀ b : Fin m, w b * (T ∩ A b).card = w b * (T.card - k : ℝ) := by intro b by_cases hwb : w b = 0 · simp [hwb] · have hpos : 0 < w b := lt_of_le_of_ne (hw b) (Ne.symm hwb) have hcard : (T ∩ A b).card = T.card - k := by have hsdiff : (T \ A b).card = k := h_eq_k b hpos have h_inter : (T ∩ A b).card = T.card - (T \ A b).card := by have h_sub : T ∩ A b = T \ (T \ A b) := by ext x simp only [mem_inter, mem_sdiff] tauto rw [h_sub, card_sdiff_of_subset sdiff_subset] omega rw [hcard, Nat.cast_sub hkT] have h4 : (∑ b : Fin m, w b * (T ∩ A b).card) = ∑ b : Fin m, w b * (T.card - k : ℝ) := by apply sum_congr rfl intro b _ exact h3 b rw [h4, ← sum_mul] at h1 exact h1 by_cases ht_eq : T.card = k + 1 · have h_sub_1 : (T.card - k : ℝ) = 1 := by rw [ht_eq] push_cast ring rw [h_sub_1, mul_one] at h_sum_T have hmass_real : (∑ a : Fin m, w a) < (k + 1 : ℝ) := by exact_mod_cast hmass rw [← h_sum_T, ht_eq] at hmass_real push_cast at hmass_real linarith · have ht_ge : k + 2 ≤ T.card := by omega have hk_pos : (0 : ℝ) < (T.card - k : ℝ) := by have : (k : ℝ) + 2 ≤ (T.card : ℝ) := by exact_mod_cast ht_ge linarith have h_le_k : (∑ b : Fin m, w b) ≤ (k : ℝ) := by have h2 : (T.card : ℝ) ≤ (k : ℝ) * (T.card - k : ℝ) := by have : (k : ℝ) + 2 ≤ (T.card : ℝ) := by exact_mod_cast ht_ge have hk_ge_2 : (2 : ℝ) ≤ (k : ℝ) := by exact_mod_cast hk nlinarith nth_rw 1 [h_sum_T] at h2 exact (mul_le_mul_iff_of_pos_right hk_pos).mp h2 linarith