AFTD Auto-Formalizing Theoretical Domains

condorcet_failure_iff_acyclic_half_cover

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • 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

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.

  1. 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.

    lines 15–21

    uses Acc.intro

      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
  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.

    lines 22–26

    uses Acc.intro

      constructor
      intro a
      apply Acc.intro
      intro b hb
      exact hroot ⟨b,hb.1⟩
  3. 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.

    lines 41–49

    uses InvImage.wf, IsWellFounded.wellOrderExtension, Fintype.card_congr, Fintype.card_fin, Fintype.orderIsoFinOfCardEq

      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
  4. 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.

    lines 50–61

      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 }
  5. 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.

    lines 62–66

    uses IsWellFounded.rank_lt_of_rel, Prod.Lex.left

      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')
  6. 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 σ.

    lines 77–80

    uses condorcet_acyclic_cover_wellFounded_sources, condorcet_acyclic_cover_ranking_of_wellFounded

      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)
  7. 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.

    lines 81–88

    uses Finset.sum_congr, if_pos

      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 hgood
  8. 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.

    lines 100–108

    uses condorcet_acyclic_cover_wellFounded_sources, condorcet_acyclic_cover_ranking_of_wellFounded

      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
  9. 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.

    lines 109–119

    uses card_le_card, Nat.mul_le_mul_left, not_lt_of_ge

      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)
  10. 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.

    lines 129–144

    uses Fintype.equivFin

      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
  11. 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.

    lines 145–159

    uses card_image_le

      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⟩
  12. 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.

    lines 160–164

    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
  13. 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.

    lines 165–166

    uses true_and

      · intro a
        simpa only [U,mem_filter,mem_univ,true_and] using hfcount a
  14. 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.

    lines 175–177

    uses condorcet_acyclic_cover_acyclic_half_cover_of_no_winning_three

      constructor
      · rintro ⟨m,P,hP⟩
        exact condorcet_acyclic_cover_acyclic_half_cover_of_no_winning_three n m hn P hP
  15. 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.

    lines 178–180

    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.

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 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⟩
See it in the graphDiscuss this resultChallenge it