condorcet_potential_break_of_fixed_electorate_bound
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
- condorcet_potential_maximum_neighborhood_half_coverSuppose a finite relation has outside common predecessors for every set of at most k+1 vertices. If n induced acyclic sets and a real…
- condorcet_acyclic_cover_no_winning_kFor any voter count n and committee bound k, a finite relation having outside common predecessors for all sets of at most k vertices,…
- is_condorcet_winning_setWith n voters holding strict rankings of m candidates, S is a Condorcet winning set if for every candidate a ∉ S, strictly fewer than n/2…
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.
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).
classical by_contra hbad push_neg at hbad
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.
uses
condorcet_potential_maximum_neighborhood_half_coverobtain ⟨q,Q,W,hQ,hW,hcover⟩ := condorcet_potential_maximum_neighborhood_half_cover m n k R U h hroot hU hbadThere 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`).
uses
condorcet_acyclic_cover_no_winning_kobtain ⟨P,hP⟩ := condorcet_acyclic_cover_no_winning_k n q k Q W hQ hW hcoverA 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.
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
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_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