AFTD Auto-Formalizing Theoretical Domains

condorcet_half_coalitions_partition_of_incompatible

theoremverified

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

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.

  1. 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|.

    lines 13–16

      let U := univ.filter A
      let V := univ.filter B
      change n ≤ 2 * U.card at hA
      change n ≤ 2 * V.card at hB
  2. 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.

    lines 17–20

    uses Finset.disjoint_left.mpr, mem_filter.mp

      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⟩
  3. 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.

    lines 21–23

    uses card_union_of_disjoint, card_univ, Fintype.card_fin, card_le_univ

      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)
  4. 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.

    line 24

      have heq : U.card + V.card = n := by omega
  5. 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.

    lines 25–28

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

      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
  6. 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.

    lines 29–31

      refine ⟨⟨U.card, by omega⟩, ?_, ?_⟩
      · change U.card = V.card
        omega
  7. 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.

    lines 32–40

    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

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.
See it in the graphDiscuss this resultChallenge it