AFTD Auto-Formalizing Theoretical Domains

condorcet_mutual_bad_outsiders_partition

theoremverified

If two challenger claims are incompatible because each challenger lies in the other committee, and each has at least half the voter support, the electorate is even and their supporting voter coalitions are exact complements. This is a necessary condition, not a bound on committee size.

Statement

theorem condorcet_mutual_bad_outsiders_partition
    (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m))
    (S T : Finset (Fin m)) (a b : Fin m) (hba : b ∈ S) (hab : a ∈ T)
    (hS : n ≤ 2 * (univ.filter fun v => ∀ c ∈ S, P v a < P v c).card)
    (hT : n ≤ 2 * (univ.filter fun v => ∀ c ∈ T, P v b < P v c).card) :
    Even n ∧ ∀ v : Fin n,
      (∀ c ∈ S, P v a < P v c) ↔ ¬(∀ c ∈ T, P v b < P v c)
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 3
  • 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…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

The proof, explained

Let A and B be the coalitions of voters who strictly prefer challenger a to every candidate in committee S, and challenger b to every candidate in committee T, respectively. Because b ∈ S and a ∈ T, a voter in both coalitions would simultaneously strictly prefer a to b and b to a, which is impossible; hence A and B are disjoint. Since each coalition has at least half the voters (2|A| ≥ n and 2|B| ≥ n), their disjoint union must have size |A| + |B| ≤ n, forcing both inequalities to be tight: |A| = |B| = n/2 and A ∪ B is the full electorate. Consequently, the electorate size n = 2|A| is even, and the two supporting coalitions partition the voters into exact complements.

  1. Define A and B as the coalitions of voters supporting challenger a against committee S and challenger b against committee T, and restate the hypotheses as n ≤ 2|A| and n ≤ 2|B|.

    We introduce shorthand definitions for the two voter subsets A = {v | ∀ c ∈ S, P v a < P v c} and B = {v | ∀ c ∈ T, P v b < P v c}, and rephrase the voter support assumptions hS and hT in terms of their cardinalities |A| and |B|.

    lines 13–16

      let A := univ.filter fun v : Fin n => ∀ c ∈ S, P v a < P v c
      let B := univ.filter fun v : Fin n => ∀ c ∈ T, P v b < P v c
      change n ≤ 2*A.card at hS
      change n ≤ 2*B.card at hT
  2. The voter coalitions A and B are disjoint.

    Suppose for contradiction that a voter v belongs to both A and B. Since b ∈ S and v ∈ A, voter v strictly prefers a to b. Since a ∈ T and v ∈ B, voter v strictly prefers b to a. By asymmetry of the preference order (lt_asymm), these two strict inequalities cannot simultaneously hold, so A and B share no voters (Finset.disjoint_left.mpr).

    lines 17–22

    uses Finset.disjoint_left.mpr, mem_filter.mp, lt_asymm

      have hd : Disjoint A B := by
        apply Finset.disjoint_left.mpr
        intro v hvA hvB
        have h₁ := (mem_filter.mp hvA).2 b hba
        have h₂ := (mem_filter.mp hvB).2 a hab
        exact (lt_asymm h₁ h₂)
  3. The sum of the sizes of the two coalitions is at most the total number of voters: |A| + |B| ≤ n.

    Because A and B are disjoint, the size of their union equals |A| + |B| (card_union_of_disjoint). Since A ∪ B is a subset of the entire voter set univ of size n (Fintype.card_fin, card_univ), its cardinality is at most n (card_le_univ).

    lines 23–25

    uses card_union_of_disjoint, card_univ, Fintype.card_fin, card_le_univ

      have hc : A.card+B.card ≤ n := by
        rw [← card_union_of_disjoint hd]
        simpa only [card_univ,Fintype.card_fin] using card_le_univ (A∪B)
  4. The sum of the sizes of the two coalitions equals the total number of voters: |A| + |B| = n.

    We have n ≤ 2|A|, n ≤ 2|B|, and |A| + |B| ≤ n. Adding the first two inequalities gives 2n ≤ 2(|A| + |B|), which implies n ≤ |A| + |B|. Combined with |A| + |B| ≤ n, linear arithmetic (omega) forces |A| + |B| = n.

    line 26

      have heq : A.card+B.card=n := by omega
  5. The union of the two coalitions covers the entire electorate: A ∪ B = univ.

    The union A ∪ B is a subset of univ (subset_univ), and its cardinality is |A ∪ B| = |A| + |B| = n = |univ|. A subset of a finite set with the same cardinality must be the entire set (eq_of_subset_of_card_le).

    lines 27–29

    uses eq_of_subset_of_card_le, subset_univ, card_univ, Fintype.card_fin, card_union_of_disjoint, Nat.le_refl

      have hfull : A∪B=univ := by
        apply eq_of_subset_of_card_le (subset_univ _)
        simpa only [card_univ,Fintype.card_fin,card_union_of_disjoint hd,heq] using Nat.le_refl n
  6. The total number of voters n is even.

    From n ≤ 2|A|, n ≤ 2|B|, and |A| + |B| = n, linear arithmetic (omega) determines that n = |A| + |A| (hence each coalition contains exactly half the voters), witnessing that n is even.

    line 30

      refine ⟨⟨A.card,by omega⟩,?_⟩
  7. For every voter v, supporting a against S is equivalent to not supporting b against T.

    We first show that v ∈ A ↔ v ∉ B. If v ∈ A, then v ∉ B because A and B are disjoint (Finset.disjoint_left.mp). Conversely, if v ∉ B, then since A ∪ B is the universal set univ, v must belong to A ∪ B (mem_univ), meaning v ∈ A or v ∈ B (mem_union.mp); since v ∉ B, it follows that v ∈ A. Unfolding the definitions of A and B via mem_filter, mem_univ, and true_and yields the claimed equivalence for the preference conditions.

    lines 31–41

    uses Finset.disjoint_left.mp, mem_univ, mem_union.mp, mem_filter, true_and

      intro v
      have hv : v ∈ A ↔ v ∉ B := by
        constructor
        · intro hA hB
          exact Finset.disjoint_left.mp hd hA hB
        · intro hB
          have hu : v ∈ A∪B := by rw [hfull]; exact mem_univ v
          rcases mem_union.mp hu with hA | hB'
          · exact hA
          · exact (hB hB').elim
      simpa only [A,B,mem_filter,mem_univ,true_and] using hv
lt_asymm
Strict inequality is asymmetric: if x < y, then y < x cannot hold.
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element of the first belongs to the second.
Finset.disjoint_left.mp
If two finite sets are disjoint, then an element of the first cannot belong to the second.
mem_filter.mp
If an element belongs to the filtered set {x ∈ s | p x}, then it belongs to s and satisfies p.
mem_filter
An element belongs to the filtered set {x ∈ s | p x} if and only if it belongs to s and satisfies p.
card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
card_univ
The cardinality of the universal set of a finite type is the cardinality of the type.
Fintype.card_fin
The cardinality of Fin n is n.
card_le_univ
Every subset of a finite type has cardinality at most the cardinality of the full type.
eq_of_subset_of_card_le
If s is a subset of t and |t| ≤ |s|, then s = t.
subset_univ
Every set of elements of a finite type is a subset of the universal set univ.
Nat.le_refl
Every natural number is less than or equal to itself.
mem_univ
Every element of a finite type belongs to the universal set univ.
mem_union.mp
If an element belongs to the union s ∪ t, then it belongs to s or it belongs to t.
true_and
Conjunction with True simplifies away: 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 2000000set_option maxRecDepth 10000theorem condorcet_mutual_bad_outsiders_partition    (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m))    (S T : Finset (Fin m)) (a b : Fin m) (hba : b ∈ S) (hab : a ∈ T)    (hS : n ≤ 2 * (univ.filter fun v => ∀ c ∈ S, P v a < P v c).card)    (hT : n ≤ 2 * (univ.filter fun v => ∀ c ∈ T, P v b < P v c).card) :    Even n ∧ ∀ v : Fin n,      (∀ c ∈ S, P v a < P v c) ↔ ¬(∀ c ∈ T, P v b < P v c) := by  let A := univ.filter fun v : Fin n => ∀ c ∈ S, P v a < P v c  let B := univ.filter fun v : Fin n => ∀ c ∈ T, P v b < P v c  change n ≤ 2*A.card at hS  change n ≤ 2*B.card at hT  have hd : Disjoint A B := by    apply Finset.disjoint_left.mpr    intro v hvA hvB    have h₁ := (mem_filter.mp hvA).2 b hba    have h₂ := (mem_filter.mp hvB).2 a hab    exact (lt_asymm h₁ h₂)  have hc : A.card+B.card ≤ n := by    rw [← card_union_of_disjoint hd]    simpa only [card_univ,Fintype.card_fin] using card_le_univ (A∪B)  have heq : A.card+B.card=n := by omega  have hfull : A∪B=univ := by    apply eq_of_subset_of_card_le (subset_univ _)    simpa only [card_univ,Fintype.card_fin,card_union_of_disjoint hd,heq] using Nat.le_refl n  refine ⟨⟨A.card,by omega⟩,?_⟩  intro v  have hv : v ∈ A ↔ v ∉ B := by    constructor    · intro hA hB      exact Finset.disjoint_left.mp hd hA hB    · intro hB      have hu : v ∈ A∪B := by rw [hfull]; exact mem_univ v      rcases mem_union.mp hu with hA | hB'      · exact hA      · exact (hB hB').elim  simpa only [A,B,mem_filter,mem_univ,true_and] using hv
See it in the graphDiscuss this resultChallenge it