condorcet_half_coalitions_partition_of_incompatible
For two incompatible voter events in a finite electorate, if each has at least half of the voter support, the electorate size is even, the two support sizes are equal, and the events are exact complements for every voter. This logical form can be applied after pooling challenger claims.
Statement
theorem condorcet_half_coalitions_partition_of_incompatible (n : ℕ) (A B : Fin n → Prop) [DecidablePred A] [DecidablePred B] (hA : n ≤ 2 * (univ.filter A).card) (hB : n ≤ 2 * (univ.filter B).card) (hinc : ∀ v, ¬(A v ∧ B v)) : Even n ∧ (univ.filter A).card = (univ.filter B).card ∧ ∀ v, A v ↔ ¬ B v
- Source
- IN-339 supporting step for the OP-19 campaign. Strict definition: Condorcet winning sets, Social Choice and Welfare44(3):493-517 (2015), https://www.lamsade.dauphine.fr/~lang/papers/els15.pdf . Related selector formulation: arXiv:2604.19851v2. These are verification and coalition-closure helpers; no new dimension bound or research advance is asserted.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 3
- condorcet_minimal_predecessor_coalition_completion_exclusionSuch a globally minimal predecessor core cannot have an acyclic half-cover if every undominated (k+1)-set has an additional event of at…
- condorcet_reciprocal_connected_acyclic_weight_separationFor any finite directed relation in which every vertex set of size at most two has an outside common predecessor, if the undirected graph…
- condorcet_acyclic_half_cover_reciprocal_roots_ge_sevenSuppose an S3 finite directed relation has a positive integer acyclic half-cover. If every vertex is connected by reciprocal arrows to one…
The proof, explained
Let U and V be the voter coalitions supporting the two incompatible predicates A and B. Incompatibility implies that U and V are disjoint subsets of the n-voter electorate, so |U| + |V| ≤ n; together with the assumptions that each coalition has at least half-support (n ≤ 2|U| and n ≤ 2|V|), this forces |U| + |V| = n and |U| = |V| = n / 2, proving that n is even and the coalitions have equal size. Furthermore, because their disjoint union fills the entire electorate (U ∪ V = univ), every voter belongs to U if and only if they do not belong to V, making the two predicates exact logical complements.
Define the support coalitions U and V and express the cardinality bounds in terms of them.
We define U = {v ∈ univ | A v} and V = {v ∈ univ | B v} as the sets of voters supporting predicates A and B, and restate the given support bounds as n ≤ 2 * |U| and n ≤ 2 * |V|.
let U := univ.filter A let V := univ.filter B change n ≤ 2 * U.card at hA change n ≤ 2 * V.card at hB
The coalitions U and V are disjoint.
If a voter v belonged to both U and V, then both A v and B v would hold, directly contradicting the incompatibility hypothesis hinc.
uses
Finset.disjoint_left.mpr,mem_filter.mphave hd : Disjoint U V := by apply Finset.disjoint_left.mpr intro v hvU hvV exact hinc v ⟨(mem_filter.mp hvU).2, (mem_filter.mp hvV).2⟩
The sum of coalition sizes satisfies |U| + |V| ≤ n.
Because U and V are disjoint, the cardinality of their union is |U| + |V|. Since U ∪ V is a subset of the electorate Fin n, its cardinality cannot exceed the total electorate size n.
uses
card_union_of_disjoint,card_univ,Fintype.card_fin,card_le_univhave hc : U.card + V.card ≤ n := by rw [← card_union_of_disjoint hd] simpa only [card_univ, Fintype.card_fin] using card_le_univ (U ∪ V)
The sum of coalition sizes equals the electorate size: |U| + |V| = n.
Adding the two hypotheses n ≤ 2 * |U| and n ≤ 2 * |V| yields 2n ≤ 2(|U| + |V|), so n ≤ |U| + |V|. Combined with |U| + |V| ≤ n, linear arithmetic forces |U| + |V| = n.
have heq : U.card + V.card = n := by omega
The union of the two coalitions is the entire electorate: U ∪ V = univ.
The union U ∪ V is a subset of univ with cardinality |U ∪ V| = |U| + |V| = n = |univ|. A subset of a finite set with the same cardinality as the ambient set must equal the ambient set.
uses
eq_of_subset_of_card_le,subset_univ,card_univ,Fintype.card_fin,card_union_of_disjoint,Nat.le_reflhave hfull : U ∪ V = 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 electorate size n is even (with n = 2 * |U|) and the two coalitions have equal size: |U| = |V|.
From n ≤ 2 * |U|, n ≤ 2 * |V|, and |U| + |V| = n, linear arithmetic forces |U| = |V| and n = 2 * |U|. This witnesses that n is even and establishes that both coalitions have identical size.
refine ⟨⟨U.card, by omega⟩, ?_, ?_⟩ · change U.card = V.card omega
For every voter v, A v holds if and only if B v does not hold: A v ↔ ¬ B v.
For any voter v, if v ∈ U, disjointness implies v ∉ V. Conversely, if v ∉ V, since U ∪ V = univ covers all voters, v must lie in U. Unfolding the definitions of U and V yields A v ↔ ¬ B v.
uses
disjoint_left.mp,mem_univ,mem_union.mp,mem_filter,true_and· intro v have hv : v ∈ U ↔ v ∉ V := by constructor · intro hu hv exact disjoint_left.mp hd hu hv · intro hv have hu : v ∈ U ∪ V := by rw [hfull]; exact mem_univ v exact (mem_union.mp hu).resolve_right hv simpa only [U, V, mem_filter, mem_univ, true_and] using hv
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element belongs to both.
mem_filter.mp- If an element belongs to a filtered set, it belongs to the base set and satisfies the predicate.
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 finset `univ` of a finite type equals the cardinality of the type.
Fintype.card_fin- The cardinality of the standard finite type `Fin n` is n.
card_le_univ- The cardinality of any finset is bounded above by the cardinality of the ambient finite type.
eq_of_subset_of_card_le- If a subset of a finite set has cardinality at least that of the superset, the two sets are equal.
subset_univ- Every finset in a finite type is a subset of the universal finset.
Nat.le_refl- Every natural number is less than or equal to itself (reflexivity of ≤).
disjoint_left.mp- If two sets are disjoint, an element of the first set cannot belong to the second set.
mem_univ- Every element of a finite type belongs to the universal finset `univ`.
mem_union.mp- If an element belongs to the union of two sets, it belongs to at least one of the sets.
mem_filter- An element belongs to `filter p s` if and only if it belongs to s and satisfies predicate p.
true_and- The conjunction `True ∧ p` is logically 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 4000000set_option maxRecDepth 10000theorem condorcet_half_coalitions_partition_of_incompatible (n : ℕ) (A B : Fin n → Prop) [DecidablePred A] [DecidablePred B] (hA : n ≤ 2 * (univ.filter A).card) (hB : n ≤ 2 * (univ.filter B).card) (hinc : ∀ v, ¬(A v ∧ B v)) : Even n ∧ (univ.filter A).card = (univ.filter B).card ∧ ∀ v, A v ↔ ¬ B v := by let U := univ.filter A let V := univ.filter B change n ≤ 2 * U.card at hA change n ≤ 2 * V.card at hB have hd : Disjoint U V := by apply Finset.disjoint_left.mpr intro v hvU hvV exact hinc v ⟨(mem_filter.mp hvU).2, (mem_filter.mp hvV).2⟩ have hc : U.card + V.card ≤ n := by rw [← card_union_of_disjoint hd] simpa only [card_univ, Fintype.card_fin] using card_le_univ (U ∪ V) have heq : U.card + V.card = n := by omega have hfull : U ∪ V = 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 ⟨⟨U.card, by omega⟩, ?_, ?_⟩ · change U.card = V.card omega · intro v have hv : v ∈ U ↔ v ∉ V := by constructor · intro hu hv exact disjoint_left.mp hd hu hv · intro hv have hu : v ∈ U ∪ V := by rw [hfull]; exact mem_univ v exact (mem_union.mp hu).resolve_right hv simpa only [U, V, mem_filter, mem_univ, true_and] using hv-- Equality of voter coalitions lets us pool all their preference constraints.-- Each nonempty selected root subfamily must have a sink in that partial order.