condorcet_integer_acyclic_separator_neighbor_mass
If a finite directed relation has a nonnegative integer strict-half separator of its induced acyclic sets, it has such a separator w for which every vertex set S has weight at most the weight of its full outgoing neighborhood. The theorem states only these neighbor-mass inequalities and the preserved strict separation.
Statement
theorem condorcet_integer_acyclic_separator_neighbor_mass (m : ℕ) (R : Fin m → Fin m → Prop) [DecidableRel R] (w₀ : Fin m → ℕ) (h₀ : ∀ 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) : ∃ w : Fin m → ℕ, (∀ 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) ∧ ∀ S : Finset (Fin m), (∑ a ∈ S, w a) ≤ ∑ b ∈ univ.filter (fun b => ∃ a ∈ S, R a b), w 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 1
- condorcet_acyclic_cut_switchFor a finite directed relation, let S and N be vertex sets such that every arrow from S ends in N. For every induced acyclic set A, the…
- 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
The proof uses an extremal argument: among all nonnegative integer strict-half separators of acyclic sets, choose one, $w$, that minimizes the total sum $\sum_a w(a)$. If some set $S$ had weight strictly greater than its outgoing neighborhood $N$, zeroing out the weights on the symmetric difference $(S \setminus N) \cup (N \setminus S)$ would produce a new weight function $v$ with strictly smaller total sum. Applying the acyclic cut-switch lemma shows that $v$ remains a strict-half separator for all acyclic sets, contradicting the minimality of the total sum of $w$.
There exists a strict-half separator $w$ of acyclic sets that minimizes the total weight $\sum_a w(a)$.
We consider the predicate $P(k)$ asserting the existence of an acyclic strict-half separator whose weights sum to $k$. The assumed weight function $w_0$ proves that $P(\sum_a w_0(a))$ holds, so the set of realizable total weights is nonempty. By the well-ordering principle on $\mathbb{N}$ (`Nat.find_spec`), we select a separator $w$ whose total sum is minimal. It now suffices to prove the neighbor-mass condition for $w$.
uses
Nat.find_specclassical let P : ℕ → Prop := fun k => ∃ w : Fin m → ℕ, (∀ 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, w a) = k have hex : ∃ k, P k := ⟨∑ a, w₀ a, w₀, h₀, rfl⟩ obtain ⟨w,hw,hsum⟩ := Nat.find_spec hex refine ⟨w,hw,?_⟩
Assuming for contradiction that some set $S$ violates the neighbor condition, we define the difference sets $X = S \setminus N$ and $Y = N \setminus S$ and a modified weight function $v$ zeroed on $X \cup Y$.
Suppose, for contradiction, that some set $S$ has strictly greater total weight than its full outgoing neighborhood $N = \{b \mid \exists a \in S, R(a,b)\}$. By `Nat.lt_of_not_ge`, this means $\sum_{a \in N} w(a) < \sum_{a \in S} w(a)$. We let $X = S \setminus N$ and $Y = N \setminus S$ denote the disjoint difference components, and define a new weight function $v$ that takes value $0$ on $X \cup Y$ and agrees with $w$ elsewhere.
uses
Nat.lt_of_not_geintro S let N := univ.filter (fun b => ∃ a ∈ S, R a b) change (∑ a ∈ S, w a) ≤ ∑ a ∈ N, w a by_contra hbad have hlt : (∑ a ∈ N, w a) < ∑ a ∈ S, w a := Nat.lt_of_not_ge hbad let X := S \ N let Y := N \ S let v : Fin m → ℕ := fun a => if a ∈ X ∪ Y then 0 else w a
The total weight of $Y$ is strictly less than the total weight of $X$.
Because $S = (S \cap N) \cup X$ and $N = (S \cap N) \cup Y$ are disjoint unions, the weights satisfy $w(S) + w(Y) = w(N) + w(X)$. This identity is verified by rewriting each finset sum as a sum of indicator functions over the universe (`Fintype.sum_ite_mem`), distributing addition (`sum_add_distrib`), and checking the four cases of membership in $S$ and $N$ pointwise. Combining this with $w(N) < w(S)$, linear integer arithmetic (`omega`) yields $w(Y) < w(X)$.
uses
Fintype.sum_ite_mem,sum_add_distrib,sum_congrhave hdiff : (∑ a ∈ S, w a) + (∑ a ∈ Y, w a) = (∑ a ∈ N, w a) + (∑ a ∈ X, w a) := by classical rw [← Fintype.sum_ite_mem S w,← Fintype.sum_ite_mem Y w, ← Fintype.sum_ite_mem N w,← Fintype.sum_ite_mem X w] rw [← sum_add_distrib,← sum_add_distrib] apply sum_congr rfl intro a ha by_cases haS : a ∈ S <;> by_cases haN : a ∈ N <;> simp [X,Y,haS,haN] have hXY : (∑ a ∈ Y, w a) < ∑ a ∈ X, w a := by omega
The total weight of $w$ decomposes into the weights of $X$ and $Y$ plus the total weight of $v$.
Since $X$ and $Y$ are disjoint and $v$ is zero on $X \cup Y$ while agreeing with $w$ elsewhere, each vertex $a$ satisfies $w(a) = (\text{if } a \in X \text{ then } w(a) \text{ else } 0) + (\text{if } a \in Y \text{ then } w(a) \text{ else } 0) + v(a)$. Rewriting into sums over the entire universe and checking membership cases verifies that $\sum_a w(a) = w(X) + w(Y) + \sum_a v(a)$.
uses
Fintype.sum_ite_mem,sum_add_distrib,sum_congrhave hpart : (∑ a, w a) = (∑ a ∈ X, w a) + (∑ a ∈ Y, w a) + ∑ a, v a := by rw [← Fintype.sum_ite_mem X w,← Fintype.sum_ite_mem Y w] rw [← sum_add_distrib,← sum_add_distrib] apply sum_congr rfl intro a ha by_cases haS : a ∈ S <;> by_cases haN : a ∈ N <;> simp [X,Y,v,haS,haN]
The reduced weight function $v$ is also a strict-half separator for every acyclic set $A$.
Given an acyclic set $A$, the cut-switch lemma (`condorcet_acyclic_cut_switch`) shows that $A' = X \cup (A \setminus (X \cup Y))$ is also acyclic under $R$, since all edges leaving $S$ enter $N$. Because $w$ is a strict-half separator, $2 w(A') < \sum_a w(a)$. Summing indicator functions shows that $w(A') = w(X) + v(A)$. Substituting this and the decomposition of $\sum_a w(a)$ yields $2(w(X) + v(A)) < w(X) + w(Y) + \sum_a v(a)$. Since $w(Y) < w(X)$, linear integer arithmetic (`omega`) simplifies this to $2 v(A) < \sum_a v(a)$.
uses
condorcet_acyclic_cut_switch,mem_univ,Fintype.sum_ite_mem,sum_add_distrib,sum_congrhave hv : ∀ A : Finset (Fin m), WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) → 2 * (∑ a ∈ A, v a) < ∑ a, v a := by intro A hA have hT := condorcet_acyclic_cut_switch m R S N A (by intro a b ha hab; exact mem_filter.mpr ⟨mem_univ _,a,ha,hab⟩) hA have hbound := hw _ hT have hvalue : (∑ a ∈ X ∪ (A \ (X ∪ Y)), w a) = (∑ a ∈ X, w a) + ∑ a ∈ A, v a := by rw [← Fintype.sum_ite_mem (X ∪ (A \ (X ∪ Y))) w, ← Fintype.sum_ite_mem X w,← Fintype.sum_ite_mem A v] rw [← sum_add_distrib] apply sum_congr rfl intro a ha by_cases haX : a ∈ X <;> by_cases haY : a ∈ Y <;> by_cases haA : a ∈ A <;> simp [v,haX,haY,haA] change 2 * (∑ a ∈ X ∪ (A \ (X ∪ Y)), w a) < ∑ a, w a at hbound rw [hvalue,hpart] at hbound omega
The existence of $v$ contradicts the minimality of $w$, completing the proof.
Since $v$ is an acyclic strict-half separator, its total weight must be at least that of $w$ by the definition of the minimum (`Nat.find_min'`). On the other hand, the total weight decomposition and $w(Y) < w(X)$ (which forces $w(X) > 0$) imply that $\sum_a v(a) < \sum_a w(a)$. Linear arithmetic (`omega`) derives a contradiction from these opposing bounds.
uses
Nat.find_min'have hmin : Nat.find hex ≤ ∑ a, v a := Nat.find_min' hex ⟨v,hv,rfl⟩ omega
Nat.find_spec- The least natural number satisfying a decidable predicate actually satisfies that predicate.
Nat.lt_of_not_ge- For any natural numbers $a$ and $b$, if $b$ is not greater than or equal to $a$, then $b < a$.
Fintype.sum_ite_mem- The sum of an indicator function (evaluating to $f(i)$ when $i \in s$ and $0$ otherwise) over the entire finite type equals the sum of $f$ over the finset $s$.
sum_add_distrib- The sum of a pointwise sum of functions over a finset equals the sum of their individual sums.
sum_congr- If two index sets are equal and two summands agree on every element of the set, their sums are equal.
condorcet_acyclic_cut_switch- If every edge leaving $S$ leads into $N$, and $A$ is an acyclic vertex set under $R$, then replacing the vertices of $A$ belonging to $(S \setminus N) \cup (N \setminus S)$ with $S \setminus N$ yields another acyclic set under $R$.
mem_univ- Every element of a finite type belongs to the universal finset `univ`.
Nat.find_min'- The least natural number satisfying a decidable predicate is less than or equal to any other natural number satisfying it.
- The proof relies on the auxiliary cut-switch lemma `condorcet_acyclic_cut_switch`, which guarantees that replacing vertices in the symmetric difference $(S \setminus N) \cup (N \setminus S)$ preserves acyclicity.
- Finite sums over subsets are repeatedly manipulated by converting them into indicator functions summed over the full domain via `Fintype.sum_ite_mem`, distributing the sum over addition, and simplifying each summand by finite case analysis.
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_integer_acyclic_separator_neighbor_mass (m : ℕ) (R : Fin m → Fin m → Prop) [DecidableRel R] (w₀ : Fin m → ℕ) (h₀ : ∀ 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) : ∃ w : Fin m → ℕ, (∀ 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) ∧ ∀ S : Finset (Fin m), (∑ a ∈ S, w a) ≤ ∑ b ∈ univ.filter (fun b => ∃ a ∈ S, R a b), w b := by classical let P : ℕ → Prop := fun k => ∃ w : Fin m → ℕ, (∀ 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, w a) = k have hex : ∃ k, P k := ⟨∑ a, w₀ a, w₀, h₀, rfl⟩ obtain ⟨w,hw,hsum⟩ := Nat.find_spec hex refine ⟨w,hw,?_⟩ intro S let N := univ.filter (fun b => ∃ a ∈ S, R a b) change (∑ a ∈ S, w a) ≤ ∑ a ∈ N, w a by_contra hbad have hlt : (∑ a ∈ N, w a) < ∑ a ∈ S, w a := Nat.lt_of_not_ge hbad let X := S \ N let Y := N \ S let v : Fin m → ℕ := fun a => if a ∈ X ∪ Y then 0 else w a have hdiff : (∑ a ∈ S, w a) + (∑ a ∈ Y, w a) = (∑ a ∈ N, w a) + (∑ a ∈ X, w a) := by classical rw [← Fintype.sum_ite_mem S w,← Fintype.sum_ite_mem Y w, ← Fintype.sum_ite_mem N w,← Fintype.sum_ite_mem X w] rw [← sum_add_distrib,← sum_add_distrib] apply sum_congr rfl intro a ha by_cases haS : a ∈ S <;> by_cases haN : a ∈ N <;> simp [X,Y,haS,haN] have hXY : (∑ a ∈ Y, w a) < ∑ a ∈ X, w a := by omega have hpart : (∑ a, w a) = (∑ a ∈ X, w a) + (∑ a ∈ Y, w a) + ∑ a, v a := by rw [← Fintype.sum_ite_mem X w,← Fintype.sum_ite_mem Y w] rw [← sum_add_distrib,← sum_add_distrib] apply sum_congr rfl intro a ha by_cases haS : a ∈ S <;> by_cases haN : a ∈ N <;> simp [X,Y,v,haS,haN] have hv : ∀ A : Finset (Fin m), WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) → 2 * (∑ a ∈ A, v a) < ∑ a, v a := by intro A hA have hT := condorcet_acyclic_cut_switch m R S N A (by intro a b ha hab; exact mem_filter.mpr ⟨mem_univ _,a,ha,hab⟩) hA have hbound := hw _ hT have hvalue : (∑ a ∈ X ∪ (A \ (X ∪ Y)), w a) = (∑ a ∈ X, w a) + ∑ a ∈ A, v a := by rw [← Fintype.sum_ite_mem (X ∪ (A \ (X ∪ Y))) w, ← Fintype.sum_ite_mem X w,← Fintype.sum_ite_mem A v] rw [← sum_add_distrib] apply sum_congr rfl intro a ha by_cases haX : a ∈ X <;> by_cases haY : a ∈ Y <;> by_cases haA : a ∈ A <;> simp [v,haX,haY,haA] change 2 * (∑ a ∈ X ∪ (A \ (X ∪ Y)), w a) < ∑ a, w a at hbound rw [hvalue,hpart] at hbound omega have hmin : Nat.find hex ≤ ∑ a, v a := Nat.find_min' hex ⟨v,hv,rfl⟩ omega