condorcet_mutual_bad_outsiders_partition
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- condorcet_obstruction_selector_two_coloringFor any positively sized electorate and any family of half-majority challenger claims, the graph joining mutually cross-member challenger…
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.
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|.
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
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).
uses
Finset.disjoint_left.mpr,mem_filter.mp,lt_asymmhave 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₂)
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).
uses
card_union_of_disjoint,card_univ,Fintype.card_fin,card_le_univhave 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)
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.
have heq : A.card+B.card=n := by omega
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).
uses
eq_of_subset_of_card_le,subset_univ,card_univ,Fintype.card_fin,card_union_of_disjoint,Nat.le_reflhave 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
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.
refine ⟨⟨A.card,by omega⟩,?_⟩
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.
uses
Finset.disjoint_left.mp,mem_univ,mem_union.mp,mem_filter,true_andintro 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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