AFTD Auto-Formalizing Theoretical Domains

condorcet_winning_family_of_ordering_certificates

theoremverified

If every outsider selector on a finite committee family admits nonnegative integer weights such that every strict ranking satisfies claims of strictly less than half the total weight, every positive finite electorate has a Condorcet winning committee in that family. The universal certificate-existence hypothesis is explicit and unresolved for all triples.

Statement

theorem condorcet_winning_family_of_ordering_certificates
    (m q : ℕ) (S : Fin q → Finset (Fin m))
    (hcert : ∀ f : Fin q → Fin m, (∀ i, f i ∉ S i) →
      ∃ w : Fin q → ℕ, ∀ σ : Equiv.Perm (Fin m),
        2*(∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0) < ∑ i, w i) :
    ∀ (n : ℕ) (hn : 0 < n) (P : Fin n → Equiv.Perm (Fin m)),
      ∃ i, is_condorcet_winning_set P (S i)
Source
Structural helpers for OP-19, following the strict definition in Social Choice and Welfare44(3):493-517 (2015), https://www.lamsade.dauphine.fr/~lang/papers/els15.pdf , and the selector/ordering framework in arXiv:2604.19851v2. No new Condorcet dimension bound or research advance is claimed.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

The theorem is proved by contradiction: assuming no committee S_i is Condorcet winning, every committee S_i admits an outsider candidate preferred to the entire committee by at least half of the voters. By the axiom of choice, these choices define an outsider selector function f. Applying the hypothesis to f provides a certificate weight vector w, which by an auxiliary lemma guarantees that some committee S_i is preferred to f(i) by more than half the voters. This contradicts the choice of f having majority support against S_i.

  1. Assume for contradiction that no committee in the family is a Condorcet winning set.

    We fix an electorate of size n > 0 with preference profile P, enable classical logic, and assume for contradiction that no index i gives a Condorcet winning set S_i.

    lines 13–15

      classical
      intro n hn P
      by_contra hnone
  2. Every committee S_i admits an outside candidate who defeats it with at least half of the vote.

    Fix an arbitrary committee S_i. Since it is not a Condorcet winning set, we unfold the definition of `is_condorcet_winning_set` and push negations to find an outsider a ∉ S_i such that at least half the voters (n ≤ 2 * |{v | ∀ c ∈ S_i, P_v(a) < P_v(c)}|) prefer a to every member of S_i.

    lines 16–22

    uses is_condorcet_winning_set

      have hbad : ∀ i, ∃ a : Fin m, a ∉ S i ∧
          n ≤ 2*(univ.filter fun v => ∀ c ∈ S i, P v a < P v c).card := by
        intro i
        have hi : ¬is_condorcet_winning_set P (S i) := fun h => hnone ⟨i,h⟩
        unfold is_condorcet_winning_set at hi
        push_neg at hi
        exact hi
  3. There exists an outsider selector f choosing for each committee an outsider with majority support against it.

    Using the axiom of choice (`choose`), we obtain a selector function f : Fin q → Fin m such that for each i, f(i) ∉ S_i and at least half the electorate prefers f(i) to all elements of S_i.

    line 23

      choose f hf hmaj using hbad
  4. There exists a weight certificate w for the selector f.

    Because f(i) ∉ S_i holds for every i, the hypothesis `hcert` supplies a certificate weight vector w : Fin q → ℕ satisfying the sub-majority weight inequality for every ranking.

    line 24

      obtain ⟨w,hw⟩ := hcert f hf
  5. There exists some committee S_i against which strictly fewer than half the voters prefer the outsider f(i).

    Applying `condorcet_ordering_certificate_excludes_common_obstruction` to the profile P, selector f, and certificate weights w produces an index i for which strictly fewer than half the voters prefer f(i) to all candidates in S_i.

    line 25

    uses condorcet_ordering_certificate_excludes_common_obstruction

      obtain ⟨i,hi⟩ := condorcet_ordering_certificate_excludes_common_obstruction n m q hn P S f w hw
  6. Contradiction.

    For the committee S_i identified by the certificate lemma, the outsider f(i) has both weak majority support (at least n/2 voters prefer f(i) to all of S_i) by definition of f, and strict minority support (strictly fewer than n/2 voters prefer f(i) to all of S_i) by the certificate lemma. Linear integer arithmetic (`omega`) derives False from this contradiction.

    lines 26–27

      have := hmaj i
      omega
is_condorcet_winning_set
A committee S is a Condorcet winning set for an electorate profile P if for every candidate a outside S, strictly fewer than half the voters rank a ahead of all members of S.
condorcet_ordering_certificate_excludes_common_obstruction
If nonnegative weights w satisfy the ordering certificate condition for an outsider selector f, then in any positive finite electorate profile P there exists some committee S_i such that strictly fewer than half of the voters prefer f(i) to every member of S_i.

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 2000000set_option maxRecDepth 10000theorem condorcet_winning_family_of_ordering_certificates    (m q : ℕ) (S : Fin q → Finset (Fin m))    (hcert : ∀ f : Fin q → Fin m, (∀ i, f i ∉ S i) →      ∃ w : Fin q → ℕ, ∀ σ : Equiv.Perm (Fin m),        2*(∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0) < ∑ i, w i) :    ∀ (n : ℕ) (hn : 0 < n) (P : Fin n → Equiv.Perm (Fin m)),      ∃ i, is_condorcet_winning_set P (S i) := by  classical  intro n hn P  by_contra hnone  have hbad : ∀ i, ∃ a : Fin m, a ∉ S i ∧      n ≤ 2*(univ.filter fun v => ∀ c ∈ S i, P v a < P v c).card := by    intro i    have hi : ¬is_condorcet_winning_set P (S i) := fun h => hnone ⟨i,h⟩    unfold is_condorcet_winning_set at hi    push_neg at hi    exact hi  choose f hf hmaj using hbad  obtain ⟨w,hw⟩ := hcert f hf  obtain ⟨i,hi⟩ := condorcet_ordering_certificate_excludes_common_obstruction n m q hn P S f w hw  have := hmaj i  omega
See it in the graphDiscuss this resultChallenge it