AFTD Auto-Formalizing Theoretical Domains

condorcet_dimension_le_four_of_odd_three

theoremverified

If every finite strict-ranking election with a positive odd number of voters has a strict Condorcet winning set of size at most three, then every finite strict-ranking election with a positive number of voters has one of size at most four. This is a conditional reduction, not a proof of either universal existence premise.

Statement

theorem condorcet_dimension_le_four_of_odd_three
    (hodd : ∀ (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)),
      0 < n → Odd n → ∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S) :
    ∀ (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)), 0 < n →
      ∃ S : Finset (Fin m), S.card ≤ 4 ∧ is_condorcet_winning_set P S
Source
IN-341 supporting reduction for the weaker universal-four target in OP-19. The remove-one-voter/add-that-voter-top-candidate argument is already in the proof of Proposition4 of Condorcet winning sets, Social Choice and Welfare44(3):493-517 (2015), https://www.lamsade.dauphine.fr/~lang/papers/els15.pdf . This helper is not new research.
Verified
29 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…

The proof, explained

The proof proceeds by case analysis on the parity of the number of voters n. If n is odd, the hypothesis directly yields a Condorcet winning set of size at most 3, which is also at most 4. If n is even (with n = k + 1 for positive odd k), the voter profile is split into the first k voters and the single final voter. Applying the hypothesis to the first k voters yields a winning set S of size at most 3, and adjoining the final voter's unique top choice c produces a set S ∪ {c} of size at most 4. Because the final voter cannot prefer any candidate to their own top choice c, any alternative candidate a ∉ S ∪ {c} can beat S ∪ {c} only among the first k voters, where the number of such voters is strictly less than k/2 < n/2, so S ∪ {c} is a winning set for the entire electorate.

  1. If the number of voters n is odd, the election has a Condorcet winning set of size at most 4.

    We introduce the parameters n, m, the profile P, and the assumption 0 < n, and split into cases based on whether n is odd. If n is odd, the hypothesis hodd immediately supplies a Condorcet winning set S with |S| ≤ 3. Since |S| ≤ 3 ≤ 4, S directly satisfies the goal.

    lines 9–12

      intro n m P hn
      by_cases hodd_n : Odd n
      · obtain ⟨S, hSc, hSw⟩ := hodd n m P hn hodd_n
        exact ⟨S, by omega, hSw⟩
  2. The case n = 0 is impossible, and if there are no candidates (m = 0), the empty set is a Condorcet winning set.

    When n is not odd, n = 0 contradicts 0 < n. When n = k + 1, we case-split on m: if m = 0, the candidate set is empty, so the empty set ∅ has size 0 ≤ 4 and vacuously satisfies the winning condition via isEmptyElim since there are no candidates outside ∅.

    lines 13–19

    uses isEmptyElim

      · cases n with
        | zero => omega
        | succ k =>
          cases m with
          | zero =>
            refine ⟨∅, by simp, fun a _ => isEmptyElim a⟩
          | succ m' =>
  3. When n = k + 1 is positive and even, k is positive and odd.

    Because k + 1 is not odd, Nat.not_odd_iff_even.mp establishes that k + 1 is even, so k + 1 = 2r for some r. The case r = 0 is impossible since k + 1 ≥ 1. For r = r' + 1 ≥ 1, we have k = 2r' + 1, which demonstrates by linear arithmetic that k > 0 and k is odd with witness r'.

    lines 20–31

    uses Nat.not_odd_iff_even.mp

            have heven : Even (k + 1) := Nat.not_odd_iff_even.mp hodd_n
            have hk_pos : 0 < k := by
              rcases heven with ⟨r, hr⟩
              cases r with
              | zero => omega
              | succ r => omega
            have hk_odd : Odd k := by
              rcases heven with ⟨r, hr⟩
              cases r with
              | zero => omega
              | succ r =>
                refine ⟨r, by omega⟩
  4. The union of a winning set of size at most 3 for the first k voters and the last voter's top choice has size at most 4.

    Restricting P to the first k voters yields a sub-election P_prefix with an odd number k > 0 of voters. By the hypothesis hodd, this sub-election has a Condorcet winning set S with |S| ≤ 3. We let c be the candidate ranked first (rank 0) by the last voter (voter k). By Finset.card_insert_le, the set S ∪ {c} has cardinality at most |S| + 1 ≤ 4.

    lines 32–35

    uses Finset.card_insert_le

            let P_prefix : Fin k → Equiv.Perm (Fin (m' + 1)) := fun i => P (Fin.castSucc i)
            obtain ⟨S, hSc, hSw⟩ := hodd k (m' + 1) P_prefix hk_pos hk_odd
            let c : Fin (m' + 1) := (P (Fin.last k)).symm 0
            refine ⟨insert c S, by have := Finset.card_insert_le c S; omega, ?_⟩
  5. For any alternative candidate a ∉ S ∪ {c}, the last voter does not rank a ahead of all candidates in S ∪ {c}.

    Consider any candidate a ∉ S ∪ {c}. Then a ∉ S by Finset.mem_insert_of_mem. Let p(v) state that voter v prefers a to all of S ∪ {c}, and q(i) state that prefix voter i prefers a to all of S. For the last voter to satisfy p, they would have to rank a ahead of c (using Finset.mem_insert_self). However, c was chosen as the last voter's rank-0 choice (via Equiv.apply_symm_apply), which would imply that the rank of a is strictly negative, an impossibility for natural numbers.

    lines 36–47

    uses Finset.mem_insert_of_mem, Finset.mem_insert_self, Equiv.apply_symm_apply

            intro a ha
            have ha_S : a ∉ S := fun h => ha (Finset.mem_insert_of_mem h)
            have hSw_a := hSw a ha_S
            let p : Fin (k + 1) → Prop := fun v => ∀ b ∈ insert c S, P v a < P v b
            let q : Fin k → Prop := fun i => ∀ b ∈ S, P_prefix i a < P_prefix i b
            have hp_last : ¬ p (Fin.last k) := by
              intro h
              have hlt := h c (Finset.mem_insert_self c S)
              dsimp [c] at hlt
              rw [Equiv.apply_symm_apply] at hlt
              have : (P (Fin.last k) a).val < 0 := hlt
              omega
  6. The number of voters among all k + 1 voters who prefer a to S ∪ {c} equals the number of such voters among the first k voters.

    By Fin.univ_castSuccEmb and Finset.map_eq_image, the universe of all k + 1 voters is partitioned into the last voter and the embedding of the first k voters. Because the last voter does not satisfy p, Finset.filter_cons_of_neg removes them from the filtered set. By Finset.filter_map and Finset.card_map, the count of voters satisfying p across all k + 1 voters equals the count of prefix voters satisfying p ∘ Fin.castSucc.

    lines 48–54

    uses Finset.map_eq_image, Fin.univ_castSuccEmb, Finset.filter_cons_of_neg, Finset.filter_map, Finset.card_map

            obtain ⟨h1, h2⟩ : ∃ (h : Fin.last k ∉ Finset.univ.map Fin.castSuccEmb),
                (Finset.univ : Finset (Fin (k + 1))) = Finset.cons (Fin.last k) (Finset.univ.map Fin.castSuccEmb) h :=
              ⟨by simp [Finset.map_eq_image], Fin.univ_castSuccEmb k⟩
            have hp_eq : (Finset.univ.filter p).card = (Finset.univ.filter (fun i : Fin k => p (Fin.castSucc i))).card := by
              rw [h2, Finset.filter_cons_of_neg p (Fin.last k) (Finset.univ.map Fin.castSuccEmb) h1 hp_last,
                  Finset.filter_map, Finset.card_map]
              rfl
  7. Any prefix voter who prefers a to S ∪ {c} also prefers a to S.

    By Finset.card_le_card, it suffices to prove set inclusion. If a prefix voter i ranks a ahead of every candidate in S ∪ {c}, then since every b ∈ S belongs to S ∪ {c} (via Finset.mem_insert_of_mem), voter i also ranks a ahead of every b ∈ S. Rewriting the membership conditions with Finset.mem_filter, Finset.mem_univ, and true_and completes the subset verification.

    lines 55–60

    uses Finset.card_le_card, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert_of_mem

            have h_sub : (Finset.univ.filter (fun i : Fin k => p (Fin.castSucc i))).card ≤ (Finset.univ.filter q).card := by
              apply Finset.card_le_card
              intro i hi
              simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hi ⊢
              intro b hb
              exact hi b (Finset.mem_insert_of_mem hb)
  8. Strictly fewer than half of the k + 1 voters prefer a to S ∪ {c}, establishing that S ∪ {c} is a Condorcet winning set.

    The goal requires showing 2 * |{v : p(v)}| < k + 1. Combining the equality and inequality from previous steps gives |{v : p(v)}| ≤ |{i < k : q(i)}|. Because S was a Condorcet winning set for the prefix profile, we have 2 * |{i < k : q(i)}| < k. Linear integer arithmetic yields 2 * |{v : p(v)}| ≤ 2 * |{i < k : q(i)}| ≤ k - 1 < k + 1, completing the proof.

    lines 61–63

            change 2 * (Finset.univ.filter p).card < k + 1
            have : (Finset.univ.filter q).card = (Finset.univ.filter (fun v => ∀ b ∈ S, P_prefix v a < P_prefix v b)).card := rfl
            omega
isEmptyElim
From a term belonging to an empty type, any conclusion can be deduced (the principle of explosion for empty types).
Nat.not_odd_iff_even.mp
A natural number that is not odd is even.
Finset.card_insert_le
Inserting an element into a finite set increases its cardinality by at most 1.
Finset.mem_insert_of_mem
An element belonging to a set s also belongs to insert b s.
Finset.mem_insert_self
An element a belongs to insert a s.
Equiv.apply_symm_apply
Applying a permutation to the image of an element under its inverse returns the original element.
Finset.map_eq_image
Mapping a finite set under an embedding is equal to the image under the embedding's underlying function.
Fin.univ_castSuccEmb
The universal set of Fin (n + 1) decomposes into the singleton of the last element Fin.last n and the embedded image of Finset.univ for Fin n under Fin.castSuccEmb.
Finset.filter_cons_of_neg
Filtering a set extended by an element that does not satisfy predicate p gives the same result as filtering the original set.
Finset.filter_map
Filtering the mapped image of a set under an embedding equals mapping the subset filtered by the pull-back predicate.
Finset.card_map
An embedding between types preserves the cardinality of finite sets.
Finset.card_le_card
A subset of a finite set has cardinality less than or equal to the cardinality of the containing set.
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the original set and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to its universal set Finset.univ.
true_and
Conjunction of True with any proposition 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 BigOperatorstheorem condorcet_dimension_le_four_of_odd_three    (hodd : ∀ (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)),      0 < n → Odd n → ∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S) :    ∀ (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)), 0 < n →      ∃ S : Finset (Fin m), S.card ≤ 4 ∧ is_condorcet_winning_set P S := by  intro n m P hn  by_cases hodd_n : Odd n  · obtain ⟨S, hSc, hSw⟩ := hodd n m P hn hodd_n    exact ⟨S, by omega, hSw⟩  · cases n with    | zero => omega    | succ k =>      cases m with      | zero =>        refine ⟨∅, by simp, fun a _ => isEmptyElim a⟩      | succ m' =>        have heven : Even (k + 1) := Nat.not_odd_iff_even.mp hodd_n        have hk_pos : 0 < k := by          rcases heven with ⟨r, hr⟩          cases r with          | zero => omega          | succ r => omega        have hk_odd : Odd k := by          rcases heven with ⟨r, hr⟩          cases r with          | zero => omega          | succ r =>            refine ⟨r, by omega⟩        let P_prefix : Fin k → Equiv.Perm (Fin (m' + 1)) := fun i => P (Fin.castSucc i)        obtain ⟨S, hSc, hSw⟩ := hodd k (m' + 1) P_prefix hk_pos hk_odd        let c : Fin (m' + 1) := (P (Fin.last k)).symm 0        refine ⟨insert c S, by have := Finset.card_insert_le c S; omega, ?_⟩        intro a ha        have ha_S : a ∉ S := fun h => ha (Finset.mem_insert_of_mem h)        have hSw_a := hSw a ha_S        let p : Fin (k + 1) → Prop := fun v => ∀ b ∈ insert c S, P v a < P v b        let q : Fin k → Prop := fun i => ∀ b ∈ S, P_prefix i a < P_prefix i b        have hp_last : ¬ p (Fin.last k) := by          intro h          have hlt := h c (Finset.mem_insert_self c S)          dsimp [c] at hlt          rw [Equiv.apply_symm_apply] at hlt          have : (P (Fin.last k) a).val < 0 := hlt          omega        obtain ⟨h1, h2⟩ : ∃ (h : Fin.last k ∉ Finset.univ.map Fin.castSuccEmb),            (Finset.univ : Finset (Fin (k + 1))) = Finset.cons (Fin.last k) (Finset.univ.map Fin.castSuccEmb) h :=          ⟨by simp [Finset.map_eq_image], Fin.univ_castSuccEmb k⟩        have hp_eq : (Finset.univ.filter p).card = (Finset.univ.filter (fun i : Fin k => p (Fin.castSucc i))).card := by          rw [h2, Finset.filter_cons_of_neg p (Fin.last k) (Finset.univ.map Fin.castSuccEmb) h1 hp_last,              Finset.filter_map, Finset.card_map]          rfl        have h_sub : (Finset.univ.filter (fun i : Fin k => p (Fin.castSucc i))).card ≤ (Finset.univ.filter q).card := by          apply Finset.card_le_card          intro i hi          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hi ⊢          intro b hb          exact hi b (Finset.mem_insert_of_mem hb)        change 2 * (Finset.univ.filter p).card < k + 1        have : (Finset.univ.filter q).card = (Finset.univ.filter (fun v => ∀ b ∈ S, P_prefix v a < P_prefix v b)).card := rfl        omega
See it in the graphDiscuss this resultChallenge it