condorcet_equal_coalition_root_sink
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
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)).
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.
classical have hpos : 0 < (univ.filter fun v => ∀ c ∈ S i₀, P v (f i₀) < P v c).card := by omega
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₀`).
uses
card_pos,mem_filterobtain ⟨v, hv⟩ := card_pos.mp hpos have hv₀ := (mem_filter.mp hv).2
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.
uses
exists_max_imageintro J hJI hJ obtain ⟨i, hi, hmax⟩ := J.exists_max_image (fun i => P v (f i)) hJ refine ⟨i, hi, ?_⟩
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.
uses
not_lt_of_geintro 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
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_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.