AFTD Auto-Formalizing Theoretical Domains

condorcet_potential_break_of_fixed_electorate_bound

theoremverified

Assume every finite election with exactly n voters has a strict Condorcet winning committee of size at most k. Then on any finite relation with outside common predecessors for sets of size at most k+1, any family of n induced acyclic sets and any real potential have an arrow a to b with 2*coverage(a)+h(a) < n+h(b). The fixed-electorate election bound is an explicit hypothesis, not a result of this theorem.

Statement

theorem condorcet_potential_break_of_fixed_electorate_bound
    (n k : ℕ)
    (hbound : ∀ (m : ℕ) (P : Fin n → Equiv.Perm (Fin m)),
      ∃ S : Finset (Fin m), S.card ≤ k ∧ is_condorcet_winning_set P S)
    (m : ℕ) (R : Fin m → Fin m → Prop)
    (U : Fin n → Finset (Fin m)) (h : Fin m → ℝ)
    (hroot : ∀ J : Finset (Fin m), J.card ≤ k+1 →
      ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b)
    (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) :
    ∃ a b, R a b ∧
      2*((univ.filter fun v => a∈U v).card : ℝ)+h a < (n : ℝ)+h b
Source
IN-383, OP-19 campaign session 9, 2026-10-30. Structural verification of the maximum-potential neighborhood route suggested in IN-380. Generalization of the existing acyclic-cover reduction, whose strict election definition is from Condorcet winning sets, Social Choice and Welfare 44(3):493-517 (2015), https://www.lamsade.dauphine.fr/~lang/papers/els15.pdf . No new election bound or research novelty is claimed.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The proof proceeds by contradiction. Assuming no arrow satisfies 2*coverage(a) + h(a) < n + h(b), `condorcet_potential_maximum_neighborhood_half_cover` extracts a finite relation with an acyclic family covering every candidate at least n/2 times and having outside predecessors for sets of size at most k. From this cover, `condorcet_acyclic_cover_no_winning_k` constructs an n-voter election with no Condorcet winning committee of size at most k. This directly contradicts the hypothesis that every n-voter election has such a winning committee of size at most k.

  1. Assume for contradiction that no edge satisfies the strict potential inequality, so n + h(b) ≤ 2 * coverage(a) + h(a) holds for all edges R a b.

    We proceed by contradiction (`by_contra hbad`) under classical logic. Pushing the negation across the existential quantifier (`push_neg at hbad`) turns the failure of the goal into the universal hypothesis that every edge R a b satisfies n + h(b) ≤ 2 * |{v | a ∈ U(v)}| + h(a).

    lines 17–19

      classical
      by_contra hbad
      push_neg at hbad
  2. There exists a finite relation (q, Q) with outside common predecessors for subsets of size at most k and n acyclic subsets W that cover every candidate at least n/2 times.

    Applying `condorcet_potential_maximum_neighborhood_half_cover` to the relation R, the acyclic sets U, and the potential h—using the predecessor hypothesis `hroot`, acyclicity `hU`, and the negated goal `hbad`—extracts a new finite relation Q on q elements and acyclic subsets W for each of the n voters where every vertex is covered at least n/2 times and all subsets of size at most k have an outside predecessor.

    lines 20–21

    uses condorcet_potential_maximum_neighborhood_half_cover

      obtain ⟨q,Q,W,hQ,hW,hcover⟩ :=
        condorcet_potential_maximum_neighborhood_half_cover m n k R U h hroot hU hbad
  3. There exists an election profile P with n voters on q candidates admitting no Condorcet winning set of size at most k.

    Using `condorcet_acyclic_cover_no_winning_k`, the acyclic half-cover system (q, Q, W) is transformed into an explicit preference profile P of n voters on q candidates such that every committee of size at most k fails to be a Condorcet winning set (`hP`).

    line 22

    uses condorcet_acyclic_cover_no_winning_k

      obtain ⟨P,hP⟩ := condorcet_acyclic_cover_no_winning_k n q k Q W hQ hW hcover
  4. A contradiction is reached, completing the proof.

    Applying the fixed-electorate bound hypothesis `hbound` to q candidates and the profile P yields a Condorcet winning committee S with |S| ≤ k. However, the property `hP` established in the previous step asserts that no committee of size at most k is Condorcet winning, contradicting the existence of S.

    lines 23–24

      obtain ⟨S,hS,hwin⟩ := hbound q P
      exact hP S hS hwin
condorcet_potential_maximum_neighborhood_half_cover
From a finite relation with outside common predecessors for sets of size at most k + 1, n induced acyclic subsets, and a potential satisfying n + h(b) ≤ 2 * coverage(a) + h(a) along all edges, one can construct another finite relation with outside common predecessors for sets of size at most k and n induced acyclic subsets that cover every element at least n/2 times.
condorcet_acyclic_cover_no_winning_k
Given a finite relation with outside common predecessors for sets of size at most k and an acyclic cover of n subsets where every element belongs to at least n/2 subsets, there exists an n-voter preference profile in which no subset of size at most k is a Condorcet winning set.

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_potential_break_of_fixed_electorate_bound    (n k : ℕ)    (hbound : ∀ (m : ℕ) (P : Fin n → Equiv.Perm (Fin m)),      ∃ S : Finset (Fin m), S.card ≤ k ∧ is_condorcet_winning_set P S)    (m : ℕ) (R : Fin m → Fin m → Prop)    (U : Fin n → Finset (Fin m)) (h : Fin m → ℝ)    (hroot : ∀ J : Finset (Fin m), J.card ≤ k+1 →      ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b)    (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) :    ∃ a b, R a b ∧      2*((univ.filter fun v => a∈U v).card : ℝ)+h a < (n : ℝ)+h b := by  classical  by_contra hbad  push_neg at hbad  obtain ⟨q,Q,W,hQ,hW,hcover⟩ :=    condorcet_potential_maximum_neighborhood_half_cover m n k R U h hroot hU hbad  obtain ⟨P,hP⟩ := condorcet_acyclic_cover_no_winning_k n q k Q W hQ hW hcover  obtain ⟨S,hS,hwin⟩ := hbound q P  exact hP S hS hwin
See it in the graphDiscuss this resultChallenge it