condorcet_acyclic_cover_no_winning_k
For any voter count n and committee bound k, a finite relation having outside common predecessors for all sets of at most k vertices, together with n induced acyclic sets covering each vertex at least half the time, yields an election with those n voters and no strict Condorcet winning set of size at most k. No positivity assumption on n is needed for this implication.
Statement
theorem condorcet_acyclic_cover_no_winning_k (n m k : ℕ) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (hroot : ∀ S : Finset (Fin m), S.card ≤ k → ∃ a, a ∉ S ∧ ∀ c ∈ S, R a c) (hacyclic : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) (hhalf : ∀ a, n ≤ 2*(univ.filter fun v => a∈U v).card) : ∃ P : Fin n → Equiv.Perm (Fin m), ∀ S : Finset (Fin m), S.card ≤ k → ¬ is_condorcet_winning_set P S
- 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 2
- condorcet_failure_iff_acyclic_half_coverFix a positive number n of voters. There exists a finite election with these n voters in which every candidate set of size at most three…
- 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 2
- condorcet_potential_break_of_fixed_electorate_boundAssume every finite election with exactly n voters has a strict Condorcet winning committee of size at most k. Then on any finite relation…
- 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 an election profile P by extending the acyclic relation R on each voter's subset U(v) to a full preference ranking on the candidates. To show that no committee S of size at most k is Condorcet winning under P, we argue by contradiction: the predecessor hypothesis provides an outsider a ∉ S that dominates every member of S under R. Consequently, every voter whose set U(v) contains a prefers a over all of S, which constitutes at least half the electorate by the coverage hypothesis. This contradicts the definition of a Condorcet winning set, which demands that any outsider be preferred to the entire committee by strictly fewer than half the voters.
For each voter v, there exists a full preference ranking σ such that σ(a) < σ(b) whenever a ∈ U(v) and R(a, b).
We work in a classical logic setting. For each voter v, the hypothesis hacyclic asserts that R restricted to U(v) is well-founded. Lemma condorcet_acyclic_cover_wellFounded_sources extends this to show that the relation (a ∈ U(v) ∧ R(a, b)) is well-founded on the whole candidate set Fin m. Applying condorcet_acyclic_cover_ranking_of_wellFounded then extends this well-founded relation into a total ranking (permutation) σ on Fin m that respects R on U(v).
uses
condorcet_acyclic_cover_ranking_of_wellFounded,condorcet_acyclic_cover_wellFounded_sourcesclassical have horders : ∀ v, ∃ σ : Equiv.Perm (Fin m), ∀ a b, a∈U v → R a b → σ a < σ b := by intro v obtain ⟨σ,hσ⟩ := condorcet_acyclic_cover_ranking_of_wellFounded m (fun a b => a∈U v ∧ R a b) (condorcet_acyclic_cover_wellFounded_sources R {a | a∈U v} (hacyclic v)) exact ⟨σ,fun a b ha hab => hσ a b ⟨ha,hab⟩⟩
We obtain a profile P of rankings for all n voters, reducing the theorem to showing that no committee S of size at most k is Condorcet winning under P.
Using the axiom of choice (`choose`) on the family of rankings constructed in the previous step, we obtain a voter preference profile P : Fin n → Equiv.Perm (Fin m) satisfying P(v)(a) < P(v)(b) whenever a ∈ U(v) and R(a, b). We propose P as the required election profile.
choose P hP using horders refine ⟨P,?_⟩Assuming for contradiction that some committee S with |S| ≤ k is a Condorcet winning set, there is an outside candidate a ∉ S that dominates every member of S under R.
We introduce an arbitrary committee S with |S| ≤ k and assume for contradiction that S is a Condorcet winning set under P. By the hypothesis hroot, since |S| ≤ k, there exists an outside common predecessor: a candidate a ∉ S such that R(a, c) holds for every c ∈ S.
intro S hS hwin obtain ⟨a,ha,hdom⟩ := hroot S hS
Every voter whose acyclic set contains a strictly prefers a to all candidates in S.
We establish the set inclusion {v | a ∈ U(v)} ⊆ {v | ∀ c ∈ S, P(v)(a) < P(v)(c)}. For any voter v with a ∈ U(v) and any candidate c ∈ S, we have R(a, c) by the predecessor property of a. By the defining property of voter v's preference ranking P(v), the conditions a ∈ U(v) and R(a, c) imply P(v)(a) < P(v)(c). Since every voter v is trivially an element of `univ` by `mem_univ`, voter v belongs to the filtered set of voters who rank a above all of S.
uses
mem_univhave hsub : (univ.filter fun v => a∈U v) ⊆ (univ.filter fun v => ∀ c∈S,P v a < P v c) := by intro v hv refine mem_filter.mpr ⟨mem_univ v,?_⟩ intro c hc exact hP v a c (mem_filter.mp hv).2 (hdom c hc)
The number of voters preferring a to all of S contradicts the assumption that S is a Condorcet winning set.
By the coverage hypothesis hhalf, at least half the electorate covers candidate a: n ≤ 2 * |{v | a ∈ U(v)}|. By the inclusion proved in the previous step, monotonicity of cardinality (`card_le_card`) and left multiplication by 2 (`Nat.mul_le_mul_left`) imply n ≤ 2 * |{v | ∀ c ∈ S, P(v)(a) < P(v)(c)}|. However, because S was assumed to be a Condorcet winning set and a ∉ S, the definition of `is_condorcet_winning_set` requires strictly fewer than half the voters to prefer a to all of S, meaning 2 * |{v | ∀ c ∈ S, P(v)(a) < P(v)(c)}| < n. Via `not_lt_of_ge`, these two inequalities contradict each other, concluding the proof.
uses
not_lt_of_ge,Nat.mul_le_mul_left,card_le_cardexact (not_lt_of_ge ((hhalf a).trans (Nat.mul_le_mul_left 2 (card_le_card hsub)))) (hwin a ha)
condorcet_acyclic_cover_ranking_of_wellFounded- Any well-founded binary relation on Fin m can be extended to a permutation (linear ranking) σ such that σ a < σ b whenever the relation holds between a and b.
condorcet_acyclic_cover_wellFounded_sources- If the restriction of a relation R to a set U is well-founded, then the relation (a ∈ U ∧ R a b) is well-founded on the entire domain.
mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
card_le_card- If a finite set s is a subset of t, then the cardinality of s is at most the cardinality of t.
Nat.mul_le_mul_left- Multiplying both sides of a natural number inequality n ≤ m on the left by k preserves the inequality: k * n ≤ k * m.
not_lt_of_ge- If a ≤ b in a preorder, then b is not strictly less than a (¬ b < a).
- In this formalization, a voter's preference ranking is represented by a permutation σ : Equiv.Perm (Fin m), where σ(a) < σ(b) means that candidate a is ranked ahead of (preferred to) candidate b.
- The definition `is_condorcet_winning_set P S` requires that for every outsider a ∉ S, strictly fewer than n / 2 voters prefer a to all candidates in S, formulated as 2 * #{v | ∀ b ∈ S, P v a < P v b} < n.
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_cover_no_winning_k (n m k : ℕ) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (hroot : ∀ S : Finset (Fin m), S.card ≤ k → ∃ a, a ∉ S ∧ ∀ c ∈ S, R a c) (hacyclic : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) (hhalf : ∀ a, n ≤ 2*(univ.filter fun v => a∈U v).card) : ∃ P : Fin n → Equiv.Perm (Fin m), ∀ S : Finset (Fin m), S.card ≤ k → ¬ is_condorcet_winning_set P S := by classical have horders : ∀ v, ∃ σ : Equiv.Perm (Fin m), ∀ a b, a∈U v → R a b → σ a < σ b := by intro v obtain ⟨σ,hσ⟩ := condorcet_acyclic_cover_ranking_of_wellFounded m (fun a b => a∈U v ∧ R a b) (condorcet_acyclic_cover_wellFounded_sources R {a | a∈U v} (hacyclic v)) exact ⟨σ,fun a b ha hab => hσ a b ⟨ha,hab⟩⟩ choose P hP using horders refine ⟨P,?_⟩ intro S hS hwin obtain ⟨a,ha,hdom⟩ := hroot S hS have hsub : (univ.filter fun v => a∈U v) ⊆ (univ.filter fun v => ∀ c∈S,P v a < P v c) := by intro v hv refine mem_filter.mpr ⟨mem_univ v,?_⟩ intro c hc exact hP v a c (mem_filter.mp hv).2 (hdom c hc) exact (not_lt_of_ge ((hhalf a).trans (Nat.mul_le_mul_left 2 (card_le_card hsub)))) (hwin a ha)