AFTD Auto-Formalizing Theoretical Domains

condorcet_acyclic_cover_no_winning_k

theoremverified

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

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.

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

    lines 15–22

    uses condorcet_acyclic_cover_ranking_of_wellFounded, condorcet_acyclic_cover_wellFounded_sources

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

    lines 23–24

      choose P hP using horders
      refine ⟨P,?_⟩
  3. 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.

    lines 25–26

      intro S hS hwin
      obtain ⟨a,ha,hdom⟩ := hroot S hS
  4. 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.

    lines 27–32

    uses mem_univ

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

    lines 33–34

    uses not_lt_of_ge, Nat.mul_le_mul_left, card_le_card

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

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