AFTD Auto-Formalizing Theoretical Domains

condorcet_finite_strict_separator_integer_weights

theoremverified

For any family C of subsets of a finite vertex set, if nonnegative real weights put every member of C strictly below half the total weight, nonnegative integer weights do so as well. The family may be arbitrary; finiteness and strictness are essential to this proof.

Statement

theorem condorcet_finite_strict_separator_integer_weights
    (m : ℕ) (C : Finset (Fin m) → Prop)
    (w : Fin m → ℝ) (hw : ∀ a, 0 ≤ w a)
    (hsep : ∀ A, C A → 2 * (∑ a ∈ A, w a) < ∑ a, w a) :
    ∃ d : Fin m → ℕ, ∀ A, C A → 2 * (∑ a ∈ A, d a) < ∑ a, d a
Source
IN-380, OP-19 campaign session 8, 2026-10-30. Self-contained helper for the strict-half acyclic-separation route. The general unrestricted one-child equality was refuted in IN-372; this work repairs only the strict-half existence reduction. Standard finite matching, rational density, and circulation weak duality are used. No new election bound or research novelty is claimed. See lean/AFTD/Scratch/In380Oct30/HalfThresholdDerivation.txt.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 2

The proof, explained

To find integer weights that strictly separate a finite family of subsets, the proof perturbs the given nonnegative real weights into the rationals and clears denominators. First, the separation condition is formulated over ℝᵐ via the positive-part function max(x, 0), defining a non-empty open set containing the original real weights. Density of ℚᵐ in ℝᵐ provides a rational weight vector in this open set, whose positive part yields nonnegative rational weights satisfying the strict inequalities. Finally, multiplying by a positive common denominator clears fractions to produce the desired nonnegative integer weights.

  1. Define the finite index set K of subsets belonging to C, and the set O ⊆ ℝᵐ of weight vectors whose positive parts strictly separate every member of K.

    We work classically and define K to be the subtype of all subsets A ⊆ {0, …, m-1} satisfying C(A). We then define O to be the set of vectors x ∈ ℝᵐ such that for every A ∈ K, the positive part x⁺ = max(x, 0) satisfies 2 ∑_{a ∈ A} max(x_a, 0) < ∑_a max(x_a, 0).

    lines 11–14

      classical
      let K := {A : Finset (Fin m) // C A}
      let O : Set (Fin m → ℝ) := {x | ∀ A : K,
        2 * (∑ a ∈ A.val, max (x a) 0) < ∑ a, max (x a) 0}
  2. The set O is an open subset of ℝᵐ.

    Since the powerset of a finite set is finite, K is finite. By Set.ofPred_forall, O is the intersection over the finite type K of the sets defined by the strict inequality for each A. For each fixed A, both x ↦ 2 ∑_{a ∈ A} max(x_a, 0) and x ↦ ∑_a max(x_a, 0) are continuous functions, so the strict inequality defines an open set by isOpen_lt. By isOpen_iInter_of_finite, the finite intersection of these open sets is open.

    lines 15–19

    uses Set.ofPred_forall, isOpen_iInter_of_finite, isOpen_lt

      have hO : IsOpen O := by
        simp only [O,Set.ofPred_forall]
        apply isOpen_iInter_of_finite
        intro A
        apply isOpen_lt <;> fun_prop
  3. The given real weight vector w belongs to O.

    Because w has nonnegative components (w_a ≥ 0 for all a), max(w_a, 0) = w_a by max_eq_left. The condition defining membership in O therefore reduces exactly to the separation hypothesis on w for all A ∈ K.

    lines 20–22

    uses max_eq_left

      have hwO : w ∈ O := by
        intro A
        simpa only [max_eq_left (hw _)] using hsep A.val A.property
  4. There exists a rational vector q ∈ ℚᵐ whose real image lies in O.

    The rational numbers are dense in the reals by Rat.denseRange_cast, so their product ℚᵐ is dense in ℝᵐ by DenseRange.piMap. Because O is an open neighborhood containing w, it must contain a rational point q.

    lines 23–25

    uses DenseRange.piMap, Rat.denseRange_cast

      have hdense : DenseRange (fun q : Fin m → ℚ => fun a => (q a : ℝ)) :=
        DenseRange.piMap (fun _ => Rat.denseRange_cast)
      obtain ⟨q,hq⟩ := hdense.exists_mem_open hO ⟨w,hwO⟩
  5. The positive part u = max(q, 0) is a nonnegative rational weight vector that strictly separates every member of C.

    We define u_a = max(q_a, 0) in ℚ, which is nonnegative for all a by le_max_right. Because q ∈ O, its real image satisfies the strict separation inequality for every A ∈ C; since all quantities involved are rational, the inequality holds over ℚ.

    lines 26–32

    uses le_max_right

      let u : Fin m → ℚ := fun a => max (q a) 0
      have hu : ∀ a, 0 ≤ u a := fun a => le_max_right _ _
      have huseq : ∀ A, C A → 2 * (∑ a ∈ A, u a) < ∑ a, u a := by
        intro A hA
        have h := hq ⟨A,hA⟩
        change 2 * (∑ a ∈ A, max (q a : ℝ) 0) < ∑ a, max (q a : ℝ) 0 at h
        exact_mod_cast h
  6. There exist a positive integer common denominator D and nonnegative integer weights d such that D * u_a = d_a for every coordinate a.

    Applying condorcet_half_cover_finite_nonnegative_rational_common_denominator to the nonnegative rational vector u yields a positive integer D and an integer-valued vector d such that D * u_a = d_a for all a.

    lines 33–34

    uses condorcet_half_cover_finite_nonnegative_rational_common_denominator

      obtain ⟨D,d,hD,hd⟩ :=
        condorcet_half_cover_finite_nonnegative_rational_common_denominator u hu
  7. The integer weights d strictly separate every member of C.

    For any A ∈ C, multiplying the strict rational inequality 2 ∑_{a ∈ A} u_a < ∑_a u_a by D > 0 preserves the inequality by mul_lt_mul_of_pos_left. Distributing D into the sums using mul_sum and substituting D * u_a = d_a turns the left side into 2 ∑_{a ∈ A} d_a and the right side into ∑_a d_a. The resulting inequality holds in ℚ and casts directly to ℕ.

    lines 35–46

    uses mul_lt_mul_of_pos_left, mul_sum

      refine ⟨d,?_⟩
      intro A hA
      have h := mul_lt_mul_of_pos_left (huseq A hA) (show (0 : ℚ) < D by exact_mod_cast hD)
      have hDA : (D : ℚ) * (∑ a ∈ A, u a) = ∑ a ∈ A, (d a : ℚ) := by
        simp_rw [mul_sum,hd]
      have hDall : (D : ℚ) * (∑ a, u a) = ∑ a, (d a : ℚ) := by
        simp_rw [mul_sum,hd]
      have hleft : (D : ℚ) * (2 * ∑ a ∈ A, u a) = 2 * ∑ a ∈ A, (d a : ℚ) := by
        rw [← hDA]
        ring
      rw [hleft,hDall] at h
      exact_mod_cast h
Set.ofPred_forall
The set of points satisfying a predicate for all indices is the intersection of the sets of points satisfying it for each individual index.
isOpen_iInter_of_finite
An intersection of a finite collection of open sets is open.
isOpen_lt
For continuous functions f and g into a linearly ordered space with order topology, the set {x | f(x) < g(x)} is open.
max_eq_left
If b ≤ a, then max(a, b) = a.
DenseRange.piMap
The Cartesian product of maps having dense ranges has dense range in the product topology.
Rat.denseRange_cast
The canonical embedding of the rationals into any linearly ordered Archimedean field has dense range.
le_max_right
For any elements a and b in a linear order, b ≤ max(a, b).
condorcet_half_cover_finite_nonnegative_rational_common_denominator
Every nonnegative rational vector indexed by a finite type can be scaled by a positive integer common denominator to obtain nonnegative integer weights.
mul_lt_mul_of_pos_left
Multiplying both sides of a strict inequality by a strictly positive element preserves the strict inequality.
mul_sum
Multiplication distributes across a finite sum: a * ∑ i ∈ s, f(i) = ∑ i ∈ s, a * f(i).

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 4000000set_option maxRecDepth 10000theorem condorcet_finite_strict_separator_integer_weights    (m : ℕ) (C : Finset (Fin m) → Prop)    (w : Fin m → ℝ) (hw : ∀ a, 0 ≤ w a)    (hsep : ∀ A, C A → 2 * (∑ a ∈ A, w a) < ∑ a, w a) :    ∃ d : Fin m → ℕ, ∀ A, C A → 2 * (∑ a ∈ A, d a) < ∑ a, d a := by  classical  let K := {A : Finset (Fin m) // C A}  let O : Set (Fin m → ℝ) := {x | ∀ A : K,    2 * (∑ a ∈ A.val, max (x a) 0) < ∑ a, max (x a) 0}  have hO : IsOpen O := by    simp only [O,Set.ofPred_forall]    apply isOpen_iInter_of_finite    intro A    apply isOpen_lt <;> fun_prop  have hwO : w ∈ O := by    intro A    simpa only [max_eq_left (hw _)] using hsep A.val A.property  have hdense : DenseRange (fun q : Fin m → ℚ => fun a => (q a : ℝ)) :=    DenseRange.piMap (fun _ => Rat.denseRange_cast)  obtain ⟨q,hq⟩ := hdense.exists_mem_open hO ⟨w,hwO⟩  let u : Fin m → ℚ := fun a => max (q a) 0  have hu : ∀ a, 0 ≤ u a := fun a => le_max_right _ _  have huseq : ∀ A, C A → 2 * (∑ a ∈ A, u a) < ∑ a, u a := by    intro A hA    have h := hq ⟨A,hA⟩    change 2 * (∑ a ∈ A, max (q a : ℝ) 0) < ∑ a, max (q a : ℝ) 0 at h    exact_mod_cast h  obtain ⟨D,d,hD,hd⟩ :=    condorcet_half_cover_finite_nonnegative_rational_common_denominator u hu  refine ⟨d,?_⟩  intro A hA  have h := mul_lt_mul_of_pos_left (huseq A hA) (show (0 : ℚ) < D by exact_mod_cast hD)  have hDA : (D : ℚ) * (∑ a ∈ A, u a) = ∑ a ∈ A, (d a : ℚ) := by    simp_rw [mul_sum,hd]  have hDall : (D : ℚ) * (∑ a, u a) = ∑ a, (d a : ℚ) := by    simp_rw [mul_sum,hd]  have hleft : (D : ℚ) * (2 * ∑ a ∈ A, u a) = 2 * ∑ a ∈ A, (d a : ℚ) := by    rw [← hDA]    ring  rw [hleft,hDall] at h  exact_mod_cast h
See it in the graphDiscuss this resultChallenge it