condorcet_failure_iff_acyclic_half_cover
Fix 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 fails to be a strict Condorcet winning set if and only if there exist a finite directed relation R and n vertex subsets U, one per voter, with three properties: every set J of at most three graph vertices has an outside vertex related by R to all members of J; R restricted to each U is acyclic; and every graph vertex belongs to at least half of the n subsets. The graph vertex count may differ from the original election candidate count. On finite types acyclicity is expressed by WellFounded of the restricted relation. This is an equivalent reformulation and supplies no graph witness or new dimension bound.
Statement
theorem condorcet_failure_iff_acyclic_half_cover (n : ℕ) (hn : 0 < n) : (∃ (m : ℕ) (P : Fin n → Equiv.Perm (Fin m)), ∀ S : Finset (Fin m),S.card≤3 → ¬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≤3 → ∃ 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-348 structural reformulation helper for OP-19, with the unchanged strict definition in Condorcet winning sets, Social Choice and Welfare44(3):493-517 (2015), https://www.lamsade.dauphine.fr/~lang/papers/els15.pdf . Related acyclic-cover framework: https://arxiv.org/abs/2609.35186 and https://arxiv.org/abs/2610.29043 . Large-girth common-predecessor examples appear in Theorem11 of https://drops.dagstuhl.de/storage/00lipics/lipics-vol040-approx-random2015/LIPIcs.APPROX-RANDOM.2015.78/LIPIcs.APPROX-RANDOM.2015.78.pdf ; their existence is not assumed or formalized by this helper. No claim of novelty or research advance. An earlier informal fixed-witness acyclic-cover research proposal is recorded at https://www.proofatlas.ai/collaboration/condorcet-winning-sets-equality-overthrow/ (checked2026-10-29). That unaudited route map does not supply the Lean proof or an election theorem; the present helper is not claimed as a novel research result.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - supportThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…
- Pi.Lex.finiteA dependent product of finite, indexed by finite, is a finite.
- Used by 8
- condorcet_acyclic_cover_rank_saturationFor any finite relation with the outside common predecessor property for sets of at most k vertices and any finite acyclic cover family,…
- condorcet_nonpositive_potential_acyclicOn a finite directed relation, a vertex set with nonpositive costs is acyclic if a potential drops along arrows by at least the source…
- condorcet_common_predecessor_neighborhoodIn a finite relation in which every set of at most k+1 vertices has an outside common predecessor, the relation induced on the…
- 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,…
- condorcet_acyclic_cover_uniformizeAn acyclic family covering every vertex at least q times can be trimmed, independently at each vertex, to an acyclic subfamily with…
- condorcet_dimension_le_three_iff_acyclic_weight_separationThe following two universal statements are equivalent. First, every finite election with a positive number of voters and strict rankings…
- condorcet_acyclic_cut_switchFor a finite directed relation, let S and N be vertex sets such that every arrow from S ends in N. For every induced acyclic set A, the…
- condorcet_cover_rank_relationThe loopless rank-compatible relation: an arrow a to b is permitted precisely when a differs from b and a has a strictly smaller…
The proof, explained
The theorem establishes that an election has no Condorcet winning candidate set of size at most 3 if and only if there exists a directed graph with an acyclic half cover and a dominating root property. In the forward direction, vertices index candidate subsets of size at most 3, edges record candidate containment, and acyclicity follows because edges strictly decrease voter rankings. In the backward direction, voter preference rankings are obtained by topologically sorting the well-founded relation on each voter subset, ensuring that the dominating root of any 3-candidate set is preferred by at least half the voters and defeats it.
Every element of U is accessible under the source-restricted relation.
We proceed by well-founded induction on u ∈ U using the well-foundedness of R on U. By definition of accessibility (Acc.intro), u is accessible if all its R-predecessors in U are accessible, which is supplied directly by the induction hypothesis.
uses
Acc.introhave hroot : ∀ u : U, Acc (fun a b : A => a ∈ U ∧ R a b) u.val := by intro u induction u using h.induction with | h u ih => apply Acc.intro intro a ha exact ih ⟨a,ha.1⟩ ha.2
The source-restricted relation is well-founded on the entire type A.
To show well-foundedness, every element a ∈ A must be accessible. Any predecessor b of a under the source-restricted relation must satisfy b ∈ U, hence is accessible by the previous step, so Acc.intro establishes accessibility for all of A.
uses
Acc.introconstructor intro a apply Acc.intro intro b hb exact hroot ⟨b,hb.1⟩
The well-founded relation R extends to a linear order on a copy of Fin m, yielding an order isomorphism with Fin m.
We pull back R to a wrapper type A around Fin m using InvImage.wf to obtain a well-founded relation r. By IsWellFounded.wellOrderExtension, r extends to a linear order on A. Using Fintype.card_congr and Fintype.card_fin, A has cardinality m, so Fintype.orderIsoFinOfCardEq yields an order isomorphism between A and Fin m.
uses
InvImage.wf,IsWellFounded.wellOrderExtension,Fintype.card_congr,Fintype.card_fin,Fintype.orderIsoFinOfCardEqclassical let A := condorcet_acyclic_cover_order_vertex m let r : A → A → Prop := fun a b => R a.val b.val letI : IsWellFounded A r := ⟨InvImage.wf condorcet_acyclic_cover_order_vertex.val hR⟩ let ord : LinearOrder A := IsWellFounded.wellOrderExtension r letI : LinearOrder A := ord have hcard : Fintype.card A = m := by exact (Fintype.card_congr (condorcet_acyclic_cover_order_vertex_equiv m)).trans (Fintype.card_fin m) let e := (@Fintype.orderIsoFinOfCardEq A ord inferInstance m hcard).symm
The order isomorphism defines a permutation σ of Fin m.
The permutation σ maps each candidate a to its image under the order isomorphism, with inverse given by the underlying value of the inverse isomorphism. The left inverse property holds by definition, and the right inverse holds because reconstructing the wrapper structure from its value recovers the original element.
let σ : Equiv.Perm (Fin m) := { toFun := fun a => e ⟨a⟩ invFun := fun a => (e.symm a).val left_inv := by intro a; simp right_inv := by intro a change e (condorcet_acyclic_cover_order_vertex.mk (e.symm a).val) = a have h : condorcet_acyclic_cover_order_vertex.mk (e.symm a).val = e.symm a := by cases e.symm a rfl rw [h] exact e.apply_symm_apply a }
The permutation σ strictly preserves R.
Because the order isomorphism is strictly monotone, it suffices to show that R a b implies a < b in the extended linear order. By IsWellFounded.rank_lt_of_rel, r a b implies rank a < rank b, which implies a < b in the lexicographic well-order extension by Prod.Lex.left.
uses
IsWellFounded.rank_lt_of_rel,Prod.Lex.leftrefine ⟨σ,?_⟩ intro a b hab apply e.strictMono have hab' : r (condorcet_acyclic_cover_order_vertex.mk a) (condorcet_acyclic_cover_order_vertex.mk b) := hab exact Prod.Lex.left _ _ (IsWellFounded.rank_lt_of_rel (r := r) hab')
There exists a ranking σ preserving R on the support of non-zero weights.
Let U be the set of values f i with non-zero weight w i ≠ 0. Since R is well-founded on U, condorcet_acyclic_cover_wellFounded_sources shows the source-restricted relation is well-founded, and condorcet_acyclic_cover_ranking_of_wellFounded extends it to a ranking permutation σ.
uses
condorcet_acyclic_cover_wellFounded_sources,condorcet_acyclic_cover_ranking_of_wellFoundedclassical let U : Set (Fin m) := {a | ∃ i,w i ≠ 0 ∧ f i=a} obtain ⟨σ,hσ⟩ := condorcet_acyclic_cover_ranking_of_wellFounded m (fun a b => a∈U ∧ R a b) (condorcet_acyclic_cover_wellFounded_sources R U hacyclic)
The weighted sum of indicators where f i defeats S i equals the total weight sum.
Using Finset.sum_congr, we compare terms for each i. If w i = 0, both sides are zero. If w i ≠ 0, then f i ∈ U, so σ ranks f i ahead of all elements of S i because R (f i) c for all c ∈ S i; thus the if-condition is satisfied by if_pos and the term evaluates to w i.
uses
Finset.sum_congr,if_posrefine ⟨σ, Finset.sum_congr rfl ?_⟩ intro i hi by_cases hw : w i = 0 · simp [hw] · have hgood : ∀ c ∈ S i, σ (f i) < σ c := by intro c hc exact hσ (f i) c ⟨⟨i,hw,rfl⟩,hcomp i c hc⟩ exact if_pos hgood
Each voter v can be assigned a preference ranking P v that preserves R on edges starting in U v.
For each voter v, the relation R restricted to U v is well-founded. By condorcet_acyclic_cover_wellFounded_sources, restricting the relation to sources in U v preserves well-foundedness, and condorcet_acyclic_cover_ranking_of_wellFounded extends it to a total ranking permutation. Applying the axiom of choice yields the voter preference profile P.
uses
condorcet_acyclic_cover_wellFounded_sources,condorcet_acyclic_cover_ranking_of_wellFoundedclassical 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
No candidate set S of size at most three is Condorcet winning under P.
Suppose S has size at most 3 and is Condorcet winning. By the dominating root property, some candidate a ∉ S satisfies R a c for all c ∈ S. Whenever a ∈ U v, voter v ranks a ahead of all c ∈ S, so {v | a ∈ U v} is a subset of the voters preferring a to all of S. Since a belongs to at least half the voter sets (hhalf), monotonicity of cardinality (card_le_card) and Nat.mul_le_mul_left imply at least n/2 voters prefer a to S. This contradicts the definition of Condorcet winning by not_lt_of_ge.
uses
card_le_card,Nat.mul_le_mul_left,not_lt_of_gerefine ⟨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) have hb := (hhalf a).trans (Nat.mul_le_mul_left 2 (card_le_card hsub)) exact (not_lt_of_ge hb) (hwin a ha)
Index candidate sets of size at most 3, select defeating candidates, and define the graph relation R and voter sets U.
Let I be the subtype of candidate subsets of size at most 3, indexed as Fin q via Fintype.equivFin. Since no S i is Condorcet winning, negating the definition provides a candidate f i ∉ S i preferred to all of S i by at least n/2 voters. We define a directed relation by R i j :↔ f j ∈ S i and voter subsets U v by the indices i where voter v prefers f i to S i.
uses
Fintype.equivFinclassical let I := {T : Finset (Fin m) // T.card≤3} 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
Every subset J of at most three graph vertices has an outside dominating vertex under R.
Given J with |J| ≤ 3, its image T = f(J) has |T| ≤ 3 by card_image_le. Let i be the vertex indexing T. If i ∈ J, then f i ∈ f(J) = S i, contradicting f i ∉ S i; hence i ∉ J. Furthermore, for every j ∈ J, f j ∈ f(J) = S i, which means R i j.
uses
card_image_lerefine ⟨q,R,U,?_,?_,?_⟩ · intro J hJ let T := J.image f have hT : T.card≤3 := (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 each voter v, the relation R restricted to U v is acyclic (well-founded).
We define a measure on U v by the voter rank P v (f a). If R a b holds with a, b ∈ U v, then f b ∈ S a. Because a ∈ U v, voter v prefers f a to all members of S a, which means P v (f a) < P v (f b). The measure strictly decreases along every R-edge in U v, establishing well-foundedness via measure.
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
Every graph vertex belongs to at least half of the voter subsets U v.
By definition of U and the choice of f, the number of voters v for which vertex a belongs to U v is precisely the number of voters preferring f a to all of S a, which is at least n/2.
uses
true_and· intro a simpa only [U,mem_filter,mem_univ,true_and] using hfcount a
The forward implication: Condorcet failure implies the existence of an acyclic half cover.
Given an election with n voters in which every candidate set of size at most 3 fails to be Condorcet winning, condorcet_acyclic_cover_acyclic_half_cover_of_no_winning_three constructs the graph relation R and voter subsets U with the dominating root, acyclicity, and half-cover properties.
uses
condorcet_acyclic_cover_acyclic_half_cover_of_no_winning_threeconstructor · rintro ⟨m,P,hP⟩ exact condorcet_acyclic_cover_acyclic_half_cover_of_no_winning_three n m hn P hP
The backward implication: an acyclic half cover implies an election with no winning 3-candidate sets.
Given an acyclic half cover (q, R, U) with dominating roots, condorcet_acyclic_cover_no_winning_three_of_acyclic_half_cover constructs voter preference rankings P on Fin q such that no candidate set of size at most 3 is Condorcet winning.
uses
condorcet_acyclic_cover_no_winning_three_of_acyclic_half_cover· rintro ⟨q,R,U,hroot,hacyclic,hhalf⟩ obtain ⟨P,hP⟩ := condorcet_acyclic_cover_no_winning_three_of_acyclic_half_cover n q hn R U hroot hacyclic hhalf exact ⟨q,P,hP⟩
Acc.intro- An element x is accessible under a relation if every predecessor y of x is accessible.
InvImage.wf- The inverse image of a well-founded relation under any function is well-founded.
IsWellFounded.wellOrderExtension- Every well-founded relation can be extended to a linear well-order on the underlying type.
Fintype.card_congr- An equivalence between two finite types implies that they have the same cardinality.
Fintype.card_fin- The cardinality of Fin n is n.
Fintype.orderIsoFinOfCardEq- Any linearly ordered finite type of cardinality k is order-isomorphic to Fin k.
Prod.Lex.left- In a lexicographic product order, a strict inequality in the first component implies strict inequality for the pair.
IsWellFounded.rank_lt_of_rel- Under a well-founded relation, a related pair satisfies rank a < rank b.
condorcet_acyclic_cover_wellFounded_sources- If a relation restricted to a subset U is well-founded, then the relation requiring the source to be in U is well-founded on the whole type.
condorcet_acyclic_cover_ranking_of_wellFounded- Every well-founded relation on Fin m extends to a linear ranking (permutation) σ such that σ a < σ b whenever R a b.
Finset.sum_congr- Two sums over finite sets are equal if the index sets are equal and the summands agree on all elements.
if_pos- An if-then-else expression evaluates to the 'then' branch whenever the condition holds.
Nat.mul_le_mul_left- Multiplying both sides of an inequality of natural numbers by a positive constant preserves the inequality.
card_le_card- A subset has cardinality at most the cardinality of the superset.
not_lt_of_ge- If a ≤ b, then b cannot be strictly less than a.
Fintype.equivFin- Every finite type is equivalent to Fin of its cardinality.
card_image_le- The cardinality of the image of a finite set under a function is at most the cardinality of the original set.
measure- Constructs a well-founded relation on a type by pulling back the standard order on natural numbers via a measure function.
true_and- Conjunction of True with any proposition p simplifies to p.
condorcet_acyclic_cover_acyclic_half_cover_of_no_winning_three- Given an election where no 3-candidate set is Condorcet winning, constructs an acyclic half cover with a dominating root property.
condorcet_acyclic_cover_no_winning_three_of_acyclic_half_cover- Given an acyclic half cover with a dominating root property, constructs an election where no candidate set of size at most three is Condorcet winning.
- The graph vertices in the cover correspond to size-at-most-3 subsets of the original election candidates rather than individual candidates, so the vertex count q differs from the candidate count m.
- To topologically sort an acyclic relation on a finite set in Lean, the relation is pulled back to a wrapper type, extended to a linear order using IsWellFounded.wellOrderExtension, and transported via Fintype.orderIsoFinOfCardEq.
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 10000-- High-girth common-predecessor constructions from the literature show-- why a uniform bounded-support certificate cannot be assumed. This file-- proves the local finite implication; it does not formalize that existence-- construction or claim a new election bound.theorem condorcet_acyclic_cover_wellFounded_sources {A : Type*} (R : A → A → Prop) (U : Set A) (h : WellFounded (fun a b : U => R a.val b.val)) : WellFounded (fun a b : A => a ∈ U ∧ R a b) := by have hroot : ∀ u : U, Acc (fun a b : A => a ∈ U ∧ R a b) u.val := by intro u induction u using h.induction with | h u ih => apply Acc.intro intro a ha exact ih ⟨a,ha.1⟩ ha.2 constructor intro a apply Acc.intro intro b hb exact hroot ⟨b,hb.1⟩structure condorcet_acyclic_cover_order_vertex (m : ℕ) where val : Fin mderiving Fintypedef condorcet_acyclic_cover_order_vertex_equiv (m : ℕ) : condorcet_acyclic_cover_order_vertex m ≃ Fin m where toFun := condorcet_acyclic_cover_order_vertex.val invFun := condorcet_acyclic_cover_order_vertex.mk left_inv _ := rfl right_inv _ := rfltheorem condorcet_acyclic_cover_ranking_of_wellFounded (m : ℕ) (R : Fin m → Fin m → Prop) (hR : WellFounded R) : ∃ σ : Equiv.Perm (Fin m), ∀ a b, R a b → σ a < σ b := by classical let A := condorcet_acyclic_cover_order_vertex m let r : A → A → Prop := fun a b => R a.val b.val letI : IsWellFounded A r := ⟨InvImage.wf condorcet_acyclic_cover_order_vertex.val hR⟩ let ord : LinearOrder A := IsWellFounded.wellOrderExtension r letI : LinearOrder A := ord have hcard : Fintype.card A = m := by exact (Fintype.card_congr (condorcet_acyclic_cover_order_vertex_equiv m)).trans (Fintype.card_fin m) let e := (@Fintype.orderIsoFinOfCardEq A ord inferInstance m hcard).symm let σ : Equiv.Perm (Fin m) := { toFun := fun a => e ⟨a⟩ invFun := fun a => (e.symm a).val left_inv := by intro a; simp right_inv := by intro a change e (condorcet_acyclic_cover_order_vertex.mk (e.symm a).val) = a have h : condorcet_acyclic_cover_order_vertex.mk (e.symm a).val = e.symm a := by cases e.symm a rfl rw [h] exact e.apply_symm_apply a } refine ⟨σ,?_⟩ intro a b hab apply e.strictMono have hab' : r (condorcet_acyclic_cover_order_vertex.mk a) (condorcet_acyclic_cover_order_vertex.mk b) := hab exact Prod.Lex.left _ _ (IsWellFounded.rank_lt_of_rel (r := r) hab')theorem condorcet_acyclic_cover_ordering_certificate_needs_cyclic_root_support (m q : ℕ) (S : Fin q → Finset (Fin m)) (f : Fin q → Fin m) (w : Fin q → ℕ) (R : Fin m → Fin m → Prop) (hcomp : ∀ i, ∀ c ∈ S i, R (f i) c) (hacyclic : WellFounded (fun a b : {a : Fin m // ∃ i, w i ≠ 0 ∧ f i = a} => R a.val b.val)) : ∃ σ : Equiv.Perm (Fin m), (∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0) = ∑ i,w i := by classical let U : Set (Fin m) := {a | ∃ i,w i ≠ 0 ∧ f i=a} obtain ⟨σ,hσ⟩ := condorcet_acyclic_cover_ranking_of_wellFounded m (fun a b => a∈U ∧ R a b) (condorcet_acyclic_cover_wellFounded_sources R U hacyclic) refine ⟨σ, Finset.sum_congr rfl ?_⟩ intro i hi by_cases hw : w i = 0 · simp [hw] · have hgood : ∀ c ∈ S i, σ (f i) < σ c := by intro c hc exact hσ (f i) c ⟨⟨i,hw,rfl⟩,hcomp i c hc⟩ exact if_pos hgoodtheorem condorcet_acyclic_cover_no_winning_three_of_acyclic_half_cover (n m : ℕ) (hn : 0 < n) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (hroot : ∀ S : Finset (Fin m), S.card ≤ 3 → ∃ 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 ≤ 3 → ¬ 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) have hb := (hhalf a).trans (Nat.mul_le_mul_left 2 (card_le_card hsub)) exact (not_lt_of_ge hb) (hwin a ha)theorem condorcet_acyclic_cover_acyclic_half_cover_of_no_winning_three (n m : ℕ) (_hn : 0 < n) (P : Fin n → Equiv.Perm (Fin m)) (hfail : ∀ S : Finset (Fin m), S.card ≤ 3 → ¬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 ≤ 3 → ∃ 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≤3} 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≤3 := (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 atheorem condorcet_failure_iff_acyclic_half_cover (n : ℕ) (hn : 0 < n) : (∃ (m : ℕ) (P : Fin n → Equiv.Perm (Fin m)), ∀ S : Finset (Fin m),S.card≤3 → ¬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≤3 → ∃ 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 constructor · rintro ⟨m,P,hP⟩ exact condorcet_acyclic_cover_acyclic_half_cover_of_no_winning_three n m hn P hP · rintro ⟨q,R,U,hroot,hacyclic,hhalf⟩ obtain ⟨P,hP⟩ := condorcet_acyclic_cover_no_winning_three_of_acyclic_half_cover n q hn R U hroot hacyclic hhalf exact ⟨q,P,hP⟩