AFTD Auto-Formalizing Theoretical Domains

condorcet_equal_coalition_root_sink

theoremverified

In a positive finite electorate, let a family of challenger claims all have exactly the same voter coalition as one claim with at least half support. Every nonempty finite subfamily of those claims has a challenger whose committee contains no challenger of that subfamily. This is an acyclicity necessity for pooled coalitions, not a winning-set guarantee.

Statement

theorem condorcet_equal_coalition_root_sink
    (ι : Type*) [DecidableEq ι] (n m : ℕ) (hn : 0 < n)
    (P : Fin n → Equiv.Perm (Fin m))
    (S : ι → Finset (Fin m)) (f : ι → Fin m)
    (I : Finset ι) (i₀ : ι)
    (hbad : n ≤ 2 * (univ.filter fun v => ∀ c ∈ S i₀, P v (f i₀) < P v c).card)
    (heq : ∀ i ∈ I, ∀ v, (∀ c ∈ S i, P v (f i) < P v c) ↔
        (∀ c ∈ S i₀, P v (f i₀) < P v c)) :
    ∀ J ⊆ I, J.Nonempty → ∃ i ∈ J, ∀ j ∈ J, f j ∉ S i
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
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…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

The proof, explained

Because the supporting coalition for the base claim i₀ contains at least half of the positive electorate, it contains at least one voter v. Since every claim in I shares this exact same coalition, voter v strictly prefers f(i) to every candidate in committee S(i) for all i ∈ I. For any nonempty subfamily J ⊆ I, we select a claim i ∈ J maximizing the preference score P(v, f(i)). If any challenger f(j) for j ∈ J were in committee S(i), voter v would have to strictly prefer f(i) to f(j), which contradicts the maximality of P(v, f(i)).

  1. The coalition of voters supporting claim i₀ has strictly positive size.

    Since the electorate has positive size n > 0 (from `hn`) and at least half of the electorate supports claim i₀ (n ≤ 2 * card, from `hbad`), linear integer arithmetic (`omega`) implies that the coalition of supporting voters has cardinality strictly greater than zero.

    lines 15–17

      classical
      have hpos : 0 < (univ.filter fun v => ∀ c ∈ S i₀, P v (f i₀) < P v c).card := by
        omega
  2. There exists a voter v who strictly prefers f(i₀) to every candidate in committee S(i₀).

    By `card_pos`, a finite set with positive cardinality is nonempty, so we can extract a voter v from the supporting coalition (`hv`). Unfolding set membership with `mem_filter` shows that v satisfies the coalition condition: voter v ranks f(i₀) strictly ahead of every candidate c in S(i₀) (`hv₀`).

    lines 18–19

    uses card_pos, mem_filter

      obtain ⟨v, hv⟩ := card_pos.mp hpos
      have hv₀ := (mem_filter.mp hv).2
  3. For any nonempty subfamily J ⊆ I, there is an index i ∈ J that maximizes voter v's preference rank P(v, f(i)), and it suffices to show that no challenger f(j) for j ∈ J belongs to S(i).

    Let J ⊆ I be a nonempty subfamily (`intro J hJI hJ`). By `exists_max_image`, because J is finite and nonempty, there exists an element i ∈ J maximizing the value P(v, f(·)), meaning P(v, f(j)) ≤ P(v, f(i)) for all j ∈ J. We choose this i as our witness.

    lines 20–22

    uses exists_max_image

      intro J hJI hJ
      obtain ⟨i, hi, hmax⟩ := J.exists_max_image (fun i => P v (f i)) hJ
      refine ⟨i, hi, ?_⟩
  4. No challenger f(j) for j ∈ J belongs to committee S(i).

    Suppose for contradiction that f(j) ∈ S(i) for some j ∈ J. Because i ∈ J ⊆ I, the hypothesis `heq` ensures that voter v belongs to the coalition for claim i just as for i₀, meaning v strictly prefers f(i) to all candidates in S(i). Evaluating at f(j) ∈ S(i) gives P(v, f(i)) < P(v, f(j)). But by maximality of i, P(v, f(j)) ≤ P(v, f(i)). By `not_lt_of_ge`, these two inequalities contradict each other.

    lines 23–25

    uses not_lt_of_ge

      intro j hj hmem
      have hvi := (heq i (hJI hi) v).mpr hv₀
      exact (not_lt_of_ge (hmax j hj)) (hvi (f j) hmem)
card_pos
A finite set has strictly positive cardinality if and only if it is nonempty.
mem_filter
An element belongs to a filtered finite set if and only if it belongs to the original set and satisfies the predicate.
exists_max_image
Every nonempty finite set contains an element maximizing a given function into a linearly ordered type.
not_lt_of_ge
If a ≤ b in a preorder, then b < a does not hold.

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_equal_coalition_root_sink    (ι : Type*) [DecidableEq ι] (n m : ℕ) (hn : 0 < n)    (P : Fin n → Equiv.Perm (Fin m))    (S : ι → Finset (Fin m)) (f : ι → Fin m)    (I : Finset ι) (i₀ : ι)    (hbad : n ≤ 2 * (univ.filter fun v => ∀ c ∈ S i₀, P v (f i₀) < P v c).card)    (heq : ∀ i ∈ I, ∀ v, (∀ c ∈ S i, P v (f i) < P v c) ↔        (∀ c ∈ S i₀, P v (f i₀) < P v c)) :    ∀ J ⊆ I, J.Nonempty → ∃ i ∈ J, ∀ j ∈ J, f j ∉ S i := by  classical  have hpos : 0 < (univ.filter fun v => ∀ c ∈ S i₀, P v (f i₀) < P v c).card := by    omega  obtain ⟨v, hv⟩ := card_pos.mp hpos  have hv₀ := (mem_filter.mp hv).2  intro J hJI hJ  obtain ⟨i, hi, hmax⟩ := J.exists_max_image (fun i => P v (f i)) hJ  refine ⟨i, hi, ?_⟩  intro j hj hmem  have hvi := (heq i (hJI hi) v).mpr hv₀  exact (not_lt_of_ge (hmax j hj)) (hvi (f j) hmem)-- A visible three-claim cycle in one coalition already excludes feasibility.
See it in the graphDiscuss this resultChallenge it