condorcet_finite_strict_separator_integer_weights
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
- condorcet_dimension_le_three_iff_acyclic_weight_separationThe following two universal statements are equivalent. First, every finite election with a positive number of voters and strict rankings…
- Used by 2
- condorcet_strict_half_separator_acyclic_cover_closed_walkIf a finite relation has a nonnegative real strict-half acyclic separator, then every positive finite family of induced acyclic sets…
- condorcet_strict_half_separator_iff_integer_circulationFor every finite directed relation, existence of nonnegative real weights putting every induced acyclic subset strictly below half their…
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.
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).
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}
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.
uses
Set.ofPred_forall,isOpen_iInter_of_finite,isOpen_lthave hO : IsOpen O := by simp only [O,Set.ofPred_forall] apply isOpen_iInter_of_finite intro A apply isOpen_lt <;> fun_prop
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.
uses
max_eq_lefthave hwO : w ∈ O := by intro A simpa only [max_eq_left (hw _)] using hsep A.val A.property
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.
uses
DenseRange.piMap,Rat.denseRange_casthave 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⟩
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 ℚ.
uses
le_max_rightlet 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
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.
uses
condorcet_half_cover_finite_nonnegative_rational_common_denominatorobtain ⟨D,d,hD,hd⟩ := condorcet_half_cover_finite_nonnegative_rational_common_denominator u huThe 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 ℕ.
uses
mul_lt_mul_of_pos_left,mul_sumrefine ⟨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).
- The condition defining O is written with max(x a, 0) rather than requiring x to be nonnegative directly. This extends the condition to an open subset of the entire Euclidean space ℝᵐ (not just the closed positive orthant), so that an open neighborhood of w exists and density of ℚᵐ in ℝᵐ can be applied.
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 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