condorcet_strict_half_separator_excludes_cover_potential
Let a finite directed relation have a nonnegative real strict-half separator. For every positive number n of induced acyclic vertex subsets U and every real vertex potential h, some arrow a to b satisfies 2 times the number of subsets containing a plus h(a) strictly less than n plus h(b). The U family is arbitrary and need not cover any vertex.
Statement
theorem condorcet_strict_half_separator_excludes_cover_potential (m n : ℕ) (hn : 0 < n) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (h : Fin m → ℝ) (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) (hsep : ∃ w : Fin m → ℝ, (∀ a, 0 ≤ w a) ∧ ∀ A : Finset (Fin m), WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) → 2 * (∑ a ∈ A, w a) < ∑ a, w a) : ∃ a b, R a b ∧ 2 * ((univ.filter fun v => a ∈ U v).card : ℝ) + h a < (n : ℝ) + h b
- 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 2
- 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…
- condorcet_edge_circulation_dual_boundGiven nonnegative real edge weights supported on a finite directed relation, with equal incoming and outgoing sums at each vertex, any…
- Used by 1
- condorcet_dimension_le_three_iff_acyclic_cover_potential_breakThe original universal strict Condorcet winning-set bound of three is equivalent to this assertion: for every finite relation with an…
The proof, explained
The proof proceeds by contradiction. Assuming no arrow satisfies the strict inequality, a circulation duality bound implies that $n \sum_a w(a) \le \sum_a w(a) \cdot 2 c(a)$ for an integer circulation $f$ with out-degree weights $w(a) = \sum_b f(a,b)$ and coverage counts $c(a)$. On the other hand, because each of the $n$ subsets $U_v$ is acyclic and $n > 0$, the strict-half separator condition gives $2 \sum_{a \in U_v} w(a) < \sum_a w(a)$ for each $v$, which upon summing over all $v$ and swapping the order of summation yields $\sum_a w(a) \cdot 2 c(a) < n \sum_a w(a)$, contradicting the duality bound.
Extract an integer circulation $f$, vertex out-degree weights $w$, and subset membership counts $c$.
By the equivalence theorem `condorcet_strict_half_separator_iff_integer_circulation`, the existence of a real strict-half separator guarantees the existence of a non-negative integer circulation $f$ supported on arrows of $R$, with in-flow equal to out-flow at every vertex, and satisfying the strict-half condition on all acyclic subsets. The vertex weights $w(a) = \sum_b f(a,b)$ are defined as the outgoing flow from $a$, and $c(a)$ is defined as the number of subsets $U_v$ containing $a$.
uses
condorcet_strict_half_separator_iff_integer_circulationclassical obtain ⟨f,hf,hbalance,hacyc⟩ := (condorcet_strict_half_separator_iff_integer_circulation m R).mp hsep let w : Fin m → ℝ := fun a => ∑ b, (f a b : ℝ) let c : Fin m → ℝ := fun a => ((univ.filter fun v => a ∈ U v).card : ℝ)
Assume for contradiction that no arrow satisfies the condition, yielding a local lower bound along every arrow.
We assume for contradiction that there is no arrow $a \to b$ satisfying $2 c(a) + h(a) < n + h(b)$. Pushing the negation inside shows that for every arrow with $R(a,b)$, the reverse inequality $n + h(b) \le 2 c(a) + h(a)$ holds.
by_contra hbad push_neg at hbad have hlocal : ∀ a b, R a b → (n : ℝ) + h b ≤ 2*c a + h a := by intro a b hab exact hbad a b hab
Apply circulation duality to obtain a bound on the total circulation.
Using `condorcet_edge_circulation_dual_bound` with flow $f$, vertex costs $p(a) = 2 c(a)$, potential $h$, and constant $t = n$, the circulation properties (non-negativity, support on $R$, flow conservation) and the local edge inequality combine to establish $n \sum_a w(a) \le \sum_a w(a) \cdot 2 c(a)$.
uses
condorcet_edge_circulation_dual_boundhave hdual := condorcet_edge_circulation_dual_bound m R (fun a b => (f a b : ℝ)) (fun a => 2*c a) h n (by intro a b; positivity) (by intro a b hab; simp [hf a b hab]) (by intro a; exact_mod_cast hbalance a) hlocal
Summing the separator inequality over all $n$ acyclic subsets yields a strict global inequality.
Since each subset $U_v$ is acyclic by assumption, the circulation acyclicity property guarantees $2 \sum_{a \in U_v} w(a) < \sum_a w(a)$ for every $v$. Because $n > 0$, the index set $\text{Fin } n$ is non-empty (containing $0$). Summing these inequalities over all $v \in \text{Fin } n$ via `sum_lt_sum` yields $\sum_{v} 2 \sum_{a \in U_v} w(a) < \sum_v \sum_a w(a)$.
uses
sum_lt_sum,mem_univhave hstrict : (∑ v : Fin n, 2 * (∑ a ∈ U v, w a)) < ∑ _v : Fin n, ∑ a, w a := by apply sum_lt_sum · intro v hv have hlt : 2 * (∑ a ∈ U v, w a) < ∑ a, w a := by dsimp only [w] exact_mod_cast hacyc (U v) (hU v) exact hlt.le · refine ⟨⟨0,hn⟩,mem_univ _,?_⟩ dsimp only [w] exact_mod_cast hacyc (U ⟨0,hn⟩) (hU ⟨0,hn⟩)
Interchanging the order of summation expresses the left-hand sum in terms of the counts $c(a)$.
Each subset sum $\sum_{a \in U_v} w(a)$ is rewritten as a sum over all vertices using indicator functions via `Fintype.sum_ite_mem`. Swapping the order of summation between $v$ and $a$ with `sum_comm` and collecting the indicator sums into the subset counts $c(a) = |\{v \mid a \in U_v\}|$ shows that $\sum_{v} 2 \sum_{a \in U_v} w(a) = \sum_a w(a) \cdot 2 c(a)$.
uses
sum_congr,Fintype.sum_ite_mem,mul_sum,sum_comm,sum_filterhave hswap : (∑ v : Fin n, 2 * (∑ a ∈ U v, w a)) = ∑ a, w a * (2*c a) := by have hconvert : (∑ v : Fin n, ∑ a ∈ U v, w a) = ∑ v : Fin n, ∑ a : Fin m, if a ∈ U v then w a else 0 := by apply sum_congr rfl intro v hv exact (Fintype.sum_ite_mem (U v) w).symm rw [← mul_sum,hconvert,sum_comm] rw [mul_sum] apply sum_congr rfl intro a ha simp [c,← sum_filter] ring
Derive a contradiction between the summed separator inequality and the circulation duality bound.
Substituting the summation equality into the strict inequality and evaluating the right-hand constant sum $\sum_{v \in \text{Fin } n} \sum_a w(a) = n \sum_a w(a)$ yields $\sum_a w(a) \cdot 2 c(a) < n \sum_a w(a)$. This directly contradicts the dual bound $n \sum_a w(a) \le \sum_a w(a) \cdot 2 c(a)$, closing the proof via `not_lt_of_ge`.
uses
sum_const,card_univ,Fintype.card_fin,nsmul_eq_mul,not_lt_of_gerw [hswap] at hstrict simp only [sum_const,card_univ,Fintype.card_fin,nsmul_eq_mul] at hstrict exact (not_lt_of_ge hdual) hstrict
condorcet_strict_half_separator_iff_integer_circulation- A directed relation admits a non-negative real strict-half separator if and only if it admits an integer circulation (a non-negative integer flow with in-flow equal to out-flow at every vertex) whose vertex out-degrees satisfy the strict-half separator condition on all acyclic subsets.
condorcet_edge_circulation_dual_bound- For any non-negative circulation $f$ on a relation $R$, vertex potential $h$, vertex cost $p$, and constant $t$, if $t + h(b) \le p(a) + h(a)$ holds on every arrow $a \to b$, then $t$ times the total circulation is at most the weighted sum of out-degrees $\sum_a (\sum_b f(a,b)) p(a)$.
sum_lt_sum- If $f(i) \le g(i)$ for all $i \in s$ and $f(i) < g(i)$ for at least one element $i \in s$, then the sum of $f$ over $s$ is strictly less than the sum of $g$ over $s$.
mem_univ- Every element of a finite type belongs to the universal finite set `univ`.
sum_congr- Two finite sums are equal if their index sets are equal and their summands agree at every element of the index set.
Fintype.sum_ite_mem- Summing an indicator expression that equals $f(i)$ when $i \in s$ and $0$ otherwise over all elements of a finite type equals the sum of $f(i)$ over the subset $s$.
mul_sum- Multiplication distributes over finite sums: $a \sum_{i \in s} f(i) = \sum_{i \in s} a f(i)$.
sum_comm- The order of two independent finite summations can be exchanged.
sum_filter- The sum of $f(a)$ over the elements of $s$ satisfying property $p$ equals the sum over all $a \in s$ of the conditional expression that takes value $f(a)$ when $p(a)$ holds and $0$ otherwise.
sum_const- Summing a constant $b$ over a finite set $s$ equals the cardinality of $s$ scalar-multiplied by $b$.
card_univ- The cardinality of the universal set of a finite type equals the cardinality of the type itself.
Fintype.card_fin- The standard finite set `Fin n` has cardinality $n$.
nsmul_eq_mul- Natural number scalar multiplication in a semiring coincides with multiplication by the natural number coerced into the ring: $n • a = n * a$.
not_lt_of_ge- If $a \le b$, then $b$ cannot be strictly less than $a$.
- The circulation duality lemma `condorcet_edge_circulation_dual_bound` abstracts the standard telescoping argument along circulation cycles, where potential terms $h(a)$ and $h(b)$ cancel around closed flows.
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_strict_half_separator_excludes_cover_potential (m n : ℕ) (hn : 0 < n) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (h : Fin m → ℝ) (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) (hsep : ∃ w : Fin m → ℝ, (∀ a, 0 ≤ w a) ∧ ∀ A : Finset (Fin m), WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) → 2 * (∑ a ∈ A, w a) < ∑ a, w a) : ∃ a b, R a b ∧ 2 * ((univ.filter fun v => a ∈ U v).card : ℝ) + h a < (n : ℝ) + h b := by classical obtain ⟨f,hf,hbalance,hacyc⟩ := (condorcet_strict_half_separator_iff_integer_circulation m R).mp hsep let w : Fin m → ℝ := fun a => ∑ b, (f a b : ℝ) let c : Fin m → ℝ := fun a => ((univ.filter fun v => a ∈ U v).card : ℝ) by_contra hbad push_neg at hbad have hlocal : ∀ a b, R a b → (n : ℝ) + h b ≤ 2*c a + h a := by intro a b hab exact hbad a b hab have hdual := condorcet_edge_circulation_dual_bound m R (fun a b => (f a b : ℝ)) (fun a => 2*c a) h n (by intro a b; positivity) (by intro a b hab; simp [hf a b hab]) (by intro a; exact_mod_cast hbalance a) hlocal have hstrict : (∑ v : Fin n, 2 * (∑ a ∈ U v, w a)) < ∑ _v : Fin n, ∑ a, w a := by apply sum_lt_sum · intro v hv have hlt : 2 * (∑ a ∈ U v, w a) < ∑ a, w a := by dsimp only [w] exact_mod_cast hacyc (U v) (hU v) exact hlt.le · refine ⟨⟨0,hn⟩,mem_univ _,?_⟩ dsimp only [w] exact_mod_cast hacyc (U ⟨0,hn⟩) (hU ⟨0,hn⟩) have hswap : (∑ v : Fin n, 2 * (∑ a ∈ U v, w a)) = ∑ a, w a * (2*c a) := by have hconvert : (∑ v : Fin n, ∑ a ∈ U v, w a) = ∑ v : Fin n, ∑ a : Fin m, if a ∈ U v then w a else 0 := by apply sum_congr rfl intro v hv exact (Fintype.sum_ite_mem (U v) w).symm rw [← mul_sum,hconvert,sum_comm] rw [mul_sum] apply sum_congr rfl intro a ha simp [c,← sum_filter] ring rw [hswap] at hstrict simp only [sum_const,card_univ,Fintype.card_fin,nsmul_eq_mul] at hstrict exact (not_lt_of_ge hdual) hstrict