AFTD Auto-Formalizing Theoretical Domains

condorcet_integer_acyclic_separator_neighbor_mass

theoremverified

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

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

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

    lines 18–25

    uses Nat.find_spec

      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,?_⟩
  2. 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.

    lines 26–33

    uses Nat.lt_of_not_ge

      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
  3. 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)$.

    lines 34–44

    uses Fintype.sum_ite_mem, sum_add_distrib, sum_congr

      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
  4. 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)$.

    lines 45–51

    uses Fintype.sum_ite_mem, sum_add_distrib, sum_congr

      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]
  5. 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)$.

    lines 52–70

    uses condorcet_acyclic_cut_switch, mem_univ, Fintype.sum_ite_mem, sum_add_distrib, sum_congr

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

    lines 71–72

    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.

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