condorcet_acyclic_half_cover_of_no_winning_k
For any n and k, a finite n-voter election with no strict Condorcet winning set of size at most k yields a finite relation with outside common predecessors for all sets of at most k vertices and an acyclic half-cover with the same n voters.
Statement
theorem condorcet_acyclic_half_cover_of_no_winning_k (n m k : ℕ) (P : Fin n → Equiv.Perm (Fin m)) (hfail : ∀ S : Finset (Fin m), S.card ≤ k → ¬is_condorcet_winning_set P S) : ∃ (q : ℕ) (R : Fin q → Fin q → Prop) (U : Fin n → Finset (Fin q)), (∀ J : Finset (Fin q), J.card ≤ k → ∃ a,a∉J ∧ ∀ b∈J,R a b) ∧ (∀ v,WellFounded (fun a b : {a : Fin q // a∈U v} => R a.val b.val)) ∧ (∀ a,n≤2*(univ.filter fun v => a∈U v).card)
- 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 1
- 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…
- Used by 1
- condorcet_failure_k_iff_acyclic_half_coverFor fixed voter count n and committee bound k, some finite n-voter election has no strict Condorcet winning committee of size at most k if…
The proof, explained
The proof explicitly constructs the vertex set Fin q as the collection of all candidate subsets of size at most k. Because no such subset is a Condorcet winning set, each subset S(i) comes with an outside candidate f(i) preferred to all of S(i) by at least half the voters. Defining R(i, j) to hold when f(j) ∈ S(i) guarantees that any subset J of size at most k has an outside predecessor corresponding to the set f(J). Restricting R to the set U(v) of vertices where voter v prefers f(i) to S(i) is well-founded because steps strictly decrease the voter's preference rank of f(i), and each vertex belongs to U(v) for at least half the voters by construction.
Index all candidate subsets of size at most k by the finite set Fin q.
Let I be the subtype of candidate subsets T ⊆ Fin m with |T| ≤ k, and let q = |I|. Using Fintype.equivFin, we fix a bijection e between I and Fin q, defining S(i) to be the candidate subset corresponding to vertex i ∈ Fin q.
uses
Fintype.equivFinclassical let I := {T : Finset (Fin m) // T.card≤k} let q := Fintype.card I let e : I ≃ Fin q := Fintype.equivFin I let S : Fin q → Finset (Fin m) := fun i => (e.symm i).val
For each vertex i, choose an outside candidate f(i) ∉ S(i) preferred to all of S(i) by at least n / 2 voters.
Because each S(i) has cardinality at most k, the hypothesis hfail ensures that S(i) is not a Condorcet winning set. Unfolding is_condorcet_winning_set and pushing negations, there exists a candidate outside S(i) preferred to all of S(i) by at least n / 2 voters. The axiom of choice (`choose`) selects such a candidate f(i) for each i ∈ Fin q, yielding both that f(i) ∉ S(i) and the voter count inequality.
uses
is_condorcet_winning_sethave hchoose : ∀ i : Fin q,∃ a,a∉S i ∧ n≤2*(univ.filter fun v => ∀ c∈S i,P v a < P v c).card := by intro i have h := hfail (S i) (e.symm i).property unfold is_condorcet_winning_set at h push_neg at h exact h choose f hfout hfcount using hchoose
Define the relation R and the voter subsets U(v), reducing the goal to three claims.
We define the directed relation R(i, j) on vertices to mean that the chosen candidate f(j) belongs to S(i). For each voter v, U(v) is defined as the set of vertices i where voter v prefers f(i) to every candidate in S(i). Providing q, R, and U as witnesses splits the proof into verifying the predecessor property for small sets, well-foundedness on each U(v), and the half-cover condition.
let R : Fin q → Fin q → Prop := fun i j => f j∈S i let U : Fin n → Finset (Fin q) := fun v => univ.filter fun i => ∀ c∈S i,P v (f i) < P v c refine ⟨q,R,U,?_,?_,?_⟩
Every subset J ⊆ Fin q with |J| ≤ k has a common predecessor i ∉ J with R(i, j) for all j ∈ J.
Given J of size at most k, let T = f(J) be its image under f. By card_image_le, |T| ≤ |J| ≤ k, so T corresponds via e to a vertex i ∈ Fin q with S(i) = T. If i were in J, then f(i) would belong to f(J) = S(i), contradicting f(i) ∉ S(i). Hence i ∉ J. Furthermore, for every j ∈ J, f(j) ∈ f(J) = S(i), which by definition means R(i, j) holds.
uses
card_image_le· intro J hJ let T := J.image f have hT : T.card≤k := (card_image_le).trans hJ let i := e ⟨T,hT⟩ have hi : S i=T := by simp [S,i] refine ⟨i,?_,?_⟩ · intro hiJ apply hfout i rw [hi] exact mem_image.mpr ⟨i,hiJ,rfl⟩ · intro j hj change f j∈S i rw [hi] exact mem_image.mpr ⟨j,hj,rfl⟩
For every voter v, the relation R restricted to U(v) is well-founded.
We pull back the well-founded order on ℕ via the measure mapping each vertex a ∈ U(v) to voter v's preference rank of f(a), namely P(v)(f(a)). If R(a, b) holds for a, b ∈ U(v), then f(b) ∈ S(a). Because a ∈ U(v), voter v prefers f(a) to all candidates in S(a), meaning P(v)(f(a)) < P(v)(f(b)). Thus R strictly decreases this rank on U(v), proving well-foundedness.
uses
measure· intro v refine (measure (fun a : {a : Fin q // a∈U v} => (P v (f a.val)).val)).wf.mono ?_ intro a b hab have hactive := (mem_filter.mp a.property).2 exact hactive (f b.val) hab
Each vertex belongs to U(v) for at least n / 2 voters.
By definition of U, vertex a belongs to U(v) exactly when voter v prefers f(a) to all candidates in S(a). Simplifying membership in U(v) using mem_filter and true_and, the number of such voters is at least n / 2 by the property guaranteed when choosing f.
uses
mem_filter,true_and· intro a simpa only [U,mem_filter,mem_univ,true_and] using hfcount a
Fintype.equivFin- Every finite type α has an explicit bijection with Fin |α|.
is_condorcet_winning_set- A candidate set S is a Condorcet winning set if every outside candidate is preferred to all of S by strictly fewer than n / 2 voters.
card_image_le- The cardinality of the image of a finite set s under any function f is at most the cardinality of s: |f(s)| ≤ |s|.
measure- Pulling back the standard strict well-order on ℕ along a measure function α → ℕ yields a well-founded relation on α.
mem_filter- An element a belongs to the filtered set filter p s if and only if a ∈ s and p(a) holds.
true_and- The logical conjunction True ∧ p is equivalent to p.
- The theorem formalizes acyclicity on each voter's subgraph as a `WellFounded` relation: on finite sets, a relation is well-founded if and only if it is acyclic.
- Voter preferences are represented as permutations `P v : Equiv.Perm (Fin m)`, where smaller values represent higher preference rank: $P(v)(a) < P(v)(b)$ means voter $v$ strictly prefers candidate $a$ over candidate $b$.
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_acyclic_half_cover_of_no_winning_k (n m k : ℕ) (P : Fin n → Equiv.Perm (Fin m)) (hfail : ∀ S : Finset (Fin m), S.card ≤ k → ¬is_condorcet_winning_set P S) : ∃ (q : ℕ) (R : Fin q → Fin q → Prop) (U : Fin n → Finset (Fin q)), (∀ J : Finset (Fin q), J.card ≤ k → ∃ a,a∉J ∧ ∀ b∈J,R a b) ∧ (∀ v,WellFounded (fun a b : {a : Fin q // a∈U v} => R a.val b.val)) ∧ (∀ a,n≤2*(univ.filter fun v => a∈U v).card) := by classical let I := {T : Finset (Fin m) // T.card≤k} let q := Fintype.card I let e : I ≃ Fin q := Fintype.equivFin I let S : Fin q → Finset (Fin m) := fun i => (e.symm i).val have hchoose : ∀ i : Fin q,∃ a,a∉S i ∧ n≤2*(univ.filter fun v => ∀ c∈S i,P v a < P v c).card := by intro i have h := hfail (S i) (e.symm i).property unfold is_condorcet_winning_set at h push_neg at h exact h choose f hfout hfcount using hchoose let R : Fin q → Fin q → Prop := fun i j => f j∈S i let U : Fin n → Finset (Fin q) := fun v => univ.filter fun i => ∀ c∈S i,P v (f i) < P v c refine ⟨q,R,U,?_,?_,?_⟩ · intro J hJ let T := J.image f have hT : T.card≤k := (card_image_le).trans hJ let i := e ⟨T,hT⟩ have hi : S i=T := by simp [S,i] refine ⟨i,?_,?_⟩ · intro hiJ apply hfout i rw [hi] exact mem_image.mpr ⟨i,hiJ,rfl⟩ · intro j hj change f j∈S i rw [hi] exact mem_image.mpr ⟨j,hj,rfl⟩ · intro v refine (measure (fun a : {a : Fin q // a∈U v} => (P v (f a.val)).val)).wf.mono ?_ intro a b hab have hactive := (mem_filter.mp a.property).2 exact hactive (f b.val) hab · intro a simpa only [U,mem_filter,mem_univ,true_and] using hfcount a