AFTD Auto-Formalizing Theoretical Domains

condorcet_small_complement_fractional_cover

theoremverified

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.

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

    lines 9–31

    uses Finset.sum_eq_zero, Classical.arbitrary

      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⟩
  2. 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)|.

    lines 37–45

    uses sum_comm, sum_congr, sum_filter, sum_const, nsmul_eq_mul

      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]
      ring
  3. 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.

    lines 55–58

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

    lines 59–74

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

    lines 75–87

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

    lines 88–107

    uses condorcet_choose_cov_on, sdiff_subset, card_insert_le, card_image_le, mem_insert_self, mem_insert_of_mem, mem_image_of_mem

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

    lines 108–142

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

    lines 143–168

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

    lines 169–208

    uses condorcet_sum_double_inter, sum_congr, sum_const, nsmul_eq_mul, Finset.add_sum_erase, mem_univ, sum_le_sum

            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]
  10. 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).

    lines 209–239

    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_sub

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

    lines 240–262

    uses mul_le_mul_iff_of_pos_right

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

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