AFTD Auto-Formalizing Theoretical Domains

is_condorcet_winning_set_nonempty

theoremverifiedoriginal

In an election with at least one voter and at least one candidate, every Condorcet winning set is nonempty.

Statement

theorem is_condorcet_winning_set_nonempty {n m : ℕ} (hn : 0 < n) (hm : 0 < m)
    (P : Fin n → Equiv.Perm (Fin m)) {S : Finset (Fin m)}
    (hS : is_condorcet_winning_set P S) : S.Nonempty
Related work
folklore
Verified
20 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…

Read back from the Lean

Given positive integers $n$ and $m$, a family of permutations $P : \text{Fin } n \to \text{Equiv.Perm}(\text{Fin } m)$, and a finset $S \subseteq \text{Fin } m$, if $S$ is a Condorcet winning set with respect to $P$ (in the sense of is_condorcet_winning_set), then $S$ is nonempty.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof proceeds by contradiction: suppose the Condorcet winning set S is empty. Because there is at least one candidate (m > 0), we can consider candidate 0, which does not belong to S. By the definition of a Condorcet winning set, strictly fewer than half of the voters may prefer candidate 0 to every element of S. However, since S is empty, every voter vacuously satisfies this condition, so all n voters are counted. This requires 2n < n, which contradicts the hypothesis that there is at least one voter (n > 0).

  1. Assume for contradiction that S is empty.

    We proceed by contradiction (`by_contra`). Since a finite set is nonempty if and only if it is not the empty set (`Finset.nonempty_iff_ne_empty`), double negation elimination (`not_not`) turns the assumption into `S = ∅`.

    lines 5–6

    uses Finset.nonempty_iff_ne_empty, not_not

      by_contra h_empty
      rw [Finset.nonempty_iff_ne_empty, not_not] at h_empty
  2. Candidate 0 is not in S, so the Condorcet winning condition gives 2 * |{v | ∀ b ∈ ∅, P v 0 < P v b}| < n.

    Since there is at least one candidate (m > 0), the first candidate `⟨0, hm⟩` exists and, because S is empty, is not in S. Applying the definition of a Condorcet winning set (`hS`) to candidate 0 states that strictly fewer than half of the voters prefer candidate 0 to every candidate in S. Replacing S with `∅` yields the inequality `2 * |{v | ∀ b ∈ ∅, P v ⟨0, hm⟩ < P v b}| < n`.

    lines 7–9

      have ha : (⟨0, hm⟩ : Fin m) ∉ S := by simp [h_empty]
      have h_cond := hS ⟨0, hm⟩ ha
      rw [h_empty] at h_cond
  3. The set of voters who prefer candidate 0 to every candidate in the empty set is the entire voter set Fin n.

    By set extensionality (`ext`), a voter v belongs to this set if and only if v belongs to `Finset.univ`. The condition `∀ b ∈ ∅, ...` is vacuously true for every voter, so simplification (`simp`) proves the voter set is all of `Finset.univ`.

    lines 10–12

      have h_all : ({v | ∀ b ∈ (∅ : Finset (Fin m)), (P v) ⟨0, hm⟩ < (P v) b} : Finset (Fin n)) = Finset.univ := by
        ext v
        simp
  4. The Condorcet winning inequality simplifies to 2n < n.

    Rewriting the set of voters as `Finset.univ`, its cardinality is the cardinality of `Fin n` (`Finset.card_univ`), which is n (`Fintype.card_fin`). The inequality becomes `2 * n < n`.

    lines 13–14

    uses Finset.card_univ, Fintype.card_fin

      rw [h_all] at h_cond
      simp only [Finset.card_univ, Fintype.card_fin] at h_cond
  5. The inequality 2n < n yields a contradiction.

    Because there is at least one voter (n > 0), the inequality 2n < n is impossible. Linear arithmetic (`omega`) closes the goal with a contradiction.

    line 15

      omega
Finset.nonempty_iff_ne_empty
A finite set is nonempty if and only if it is not equal to the empty set.
not_not
The double negation of a proposition is logically equivalent to the proposition.
Finset.card_univ
The cardinality of the universal finset of a finite type is the cardinality of the type.
Fintype.card_fin
The cardinality of `Fin n` is `n`.

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

/-- Every Condorcet winning set is nonempty in an election with at least one voter and at least one candidate. -/theorem is_condorcet_winning_set_nonempty {n m : ℕ} (hn : 0 < n) (hm : 0 < m)    (P : Fin n → Equiv.Perm (Fin m)) {S : Finset (Fin m)}    (hS : is_condorcet_winning_set P S) : S.Nonempty := by  by_contra h_empty  rw [Finset.nonempty_iff_ne_empty, not_not] at h_empty  have ha : (⟨0, hm⟩ : Fin m) ∉ S := by simp [h_empty]  have h_cond := hS ⟨0, hm⟩ ha  rw [h_empty] at h_cond  have h_all : ({v | ∀ b ∈ (∅ : Finset (Fin m)), (P v) ⟨0, hm⟩ < (P v) b} : Finset (Fin n)) = Finset.univ := by    ext v    simp  rw [h_all] at h_cond  simp only [Finset.card_univ, Fintype.card_fin] at h_cond  omega
See it in the graphDiscuss this resultChallenge it