AFTD Auto-Formalizing Theoretical Domains

condorcet_strict_half_separator_excludes_cover_potential

theoremverified

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
Used by 1

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.

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

    lines 16–20

    uses condorcet_strict_half_separator_iff_integer_circulation

      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 : ℝ)
  2. 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.

    lines 21–25

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

    lines 26–30

    uses condorcet_edge_circulation_dual_bound

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

    lines 31–41

    uses sum_lt_sum, mem_univ

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

    lines 42–54

    uses sum_congr, Fintype.sum_ite_mem, mul_sum, sum_comm, sum_filter

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

    lines 55–57

    uses sum_const, card_univ, Fintype.card_fin, nsmul_eq_mul, not_lt_of_ge

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

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