AFTD Auto-Formalizing Theoretical Domains

condorcet_acyclic_half_cover_of_no_winning_k

theoremverified

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

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.

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

    lines 13–17

    uses Fintype.equivFin

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

    lines 18–25

    uses is_condorcet_winning_set

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

    lines 26–29

      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,?_,?_,?_⟩
  4. 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.

    lines 30–43

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

    lines 44–48

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

    lines 49–50

    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.

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