condorcet_ordering_score_le_subset_potential
For any finite family of challenger claims and nonnegative integer claim weights, suppose a natural-valued potential on remaining candidate subsets bounds the gain from removing any first candidate plus the potential of the remainder. Then the total weight of claims satisfied by every strict ranking is at most the potential of the full candidate set. Claims whose committee contains their challenger need no extra exclusion hypothesis.
Statement
theorem condorcet_ordering_score_le_subset_potential (m q : ℕ) (S : Fin q → Finset (Fin m)) (f : Fin q → Fin m) (w : Fin q → ℕ) (H : Finset (Fin m) → ℕ) (hstep : ∀ A : Finset (Fin m), ∀ a ∈ A, (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) + H (A.erase a) ≤ H A) (σ : Equiv.Perm (Fin m)) : (∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0) ≤ H univ
- 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 2
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- Used by 5
- condorcet_winning_family_of_subset_potentialsIf every outside-challenger selector for a finite committee family has nonnegative integer weights and a subset potential satisfying the…
- condorcet_stationary_weight_restriction_obstructionThere exist an enumeration of all56 three-candidate subsets of eight candidates, an outside challenger for every triple, bijective member…
- condorcet_subset_potential_of_ordering_boundFor any finite family of challenger claims with nonnegative integer weights, if every strict candidate ranking has satisfied-claim weight…
- condorcet_ordering_certificate_iff_subset_potentialFor any finite family of challenger claims and fixed nonnegative integer claim weights, a strict half-weight score bound for every strict…
- condorcet_winning_family_of_subset_potentials_oddFix a relation R on the candidates. Suppose every outside-challenger selector whose roots are R-related to all committee members has…
The proof, explained
The theorem is proved by generalizing the statement to arbitrary candidate subsets $A \subseteq \mathrm{Fin}\, m$ and proceeding by strong induction on the size of $A$. In the inductive step for a nonempty set $A$, we pick a candidate $a \in A$ that minimizes the permutation $\sigma$. The claims satisfied within $A$ partition into those whose challenger is $a$ (whose committee then necessarily avoids $a$ by the minimality of $\sigma(a)$) and those entirely contained within $A \setminus \{a\}$. By the induction hypothesis, the weight of the latter is bounded by $H(A \setminus \{a\})$, and the one-step potential inequality for $a \in A$ bounds the sum of both parts by $H(A)$; evaluating at $A = \mathrm{univ}$ yields the result.
The theorem reduces to proving, by strong induction on candidate subsets $A$, that the total weight of claims satisfied within $A$ is at most $H(A)$.
We work in classical logic and formulate an auxiliary induction statement `haux`: for any subset $A \subseteq \mathrm{Fin}\, m$, the sum of weights of claims $i$ satisfying $f(i) \in A$, $S(i) \subseteq A$, and $\sigma(f(i)) < \sigma(c)$ for all $c \in S(i)$ is at most $H(A)$. We proceed by strong induction on $A$ using `Finset.strongInductionOn`, assuming as induction hypothesis `ih` that the claim holds for all strict subsets of $A$.
uses
Finset.strongInductionOnclassical have haux : ∀ A : Finset (Fin m), (∑ i, if f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c) then w i else 0) ≤ H A := by intro A refine Finset.strongInductionOn A ?_ intro A ih
If $A$ is nonempty, there exists a candidate $a \in A$ that minimizes $\sigma$ on $A$.
We split into cases on whether $A$ is nonempty. When $A$ is nonempty, `exists_min_image` supplies an element $a \in A$ such that $\sigma(a) \le \sigma(x)$ for all $x \in A$.
uses
exists_min_imageby_cases hne : A.Nonempty · obtain ⟨a, ha, hmin⟩ := A.exists_min_image σ hne
A claim $i$ is satisfied within $A$ if and only if either $f(i) = a$ with $S(i) \subseteq A \setminus \{a\}$, or $f(i)$ and $S(i)$ both lie in $A \setminus \{a\}$ with $f(i)$ beating every member of $S(i)$ under $\sigma$.
For the forward implication, suppose $f(i) \in A$, $S(i) \subseteq A$, and $\sigma(f(i)) < \sigma(c)$ for all $c \in S(i)$. Then $a \notin S(i)$, because otherwise $\sigma(f(i)) < \sigma(a)$, which contradicts the minimality of $\sigma(a)$ on $A$ (`not_lt_of_ge`). Hence $S(i) \subseteq A \setminus \{a\}$ (`mem_erase`). Case-splitting on whether $f(i) = a$ gives either the first disjunct or $f(i) \in A \setminus \{a\}$, which is the second disjunct. Conversely, if $f(i) = a$ and $S(i) \subseteq A \setminus \{a\}$, then $f(i) \in A$ and $S(i) \subseteq A$ (`subset_trans`, `erase_subset`); moreover, for each $c \in S(i)$, $c \in A$ with $c \ne a$, so $\sigma(a) \le \sigma(c)$ and $\sigma(a) \ne \sigma(c)$ (since $\sigma$ is injective), which implies $\sigma(f(i)) = \sigma(a) < \sigma(c)$ (`lt_of_le_of_ne`). In the other case, $f(i) \in A \setminus \{a\}$ immediately implies $f(i) \in A$ (`mem_of_mem_erase`) and $S(i) \subseteq A$, preserving the condition.
uses
not_lt_of_ge,mem_erase,subset_trans,erase_subset,lt_of_le_of_ne,mem_of_mem_erasehave hdecomp : ∀ i : Fin q, (f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c)) ↔ (f i = a ∧ S i ⊆ A.erase a) ∨ (f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧ (∀ c ∈ S i, σ (f i) < σ c)) := by intro i constructor · rintro ⟨hroot, hsub, hpref⟩ have hnot : a ∉ S i := by intro hmem exact (not_lt_of_ge (hmin (f i) hroot)) (hpref a hmem) have hsub' : S i ⊆ A.erase a := by intro c hc exact mem_erase.mpr ⟨by intro heq; subst c; exact hnot hc, hsub hc⟩ by_cases hfa : f i = a · exact Or.inl ⟨hfa, hsub'⟩ · exact Or.inr ⟨mem_erase.mpr ⟨hfa, hroot⟩, hsub', hpref⟩ · rintro (⟨hfa, hsub⟩ | ⟨hroot, hsub, hpref⟩) · refine ⟨hfa ▸ ha, subset_trans hsub (erase_subset a A), ?_⟩ intro c hc rw [hfa] have hc' := mem_erase.mp (hsub hc) apply lt_of_le_of_ne (hmin c hc'.2) intro heq exact hc'.1 (σ.injective heq).symm · exact ⟨mem_of_mem_erase hroot, subset_trans hsub (erase_subset a A), hpref⟩
The sum of weights of claims satisfied in $A$ decomposes into the sum over claims with $f(i) = a$ and $S(i) \subseteq A \setminus \{a\}$ plus the sum over claims satisfied entirely in $A \setminus \{a\}$.
Using `sum_add_distrib` and `sum_congr`, we merge the two sums and check summand-by-summand that each claim $i$ contributes identically on both sides. When $f(i) = a \wedge S(i) \subseteq A \setminus \{a\}$ holds, the second condition is false (as $f(i) = a$ contradicts $f(i) \in A \setminus \{a\}$ by `mem_erase`), so the summand simplifies to $w(i) + 0 = w(i)$ by `if_pos`, `if_neg`, and `add_zero`. When the second condition holds, the first is false, giving $0 + w(i) = w(i)$ by `zero_add`. When neither holds, the decomposition equivalence `hdecomp` ensures the original condition is also false, giving $0 = 0 + 0$.
uses
sum_add_distrib,sum_congr,mem_erase,if_pos,if_neg,add_zero,zero_addhave hsum : (∑ i, if f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c) then w i else 0) = (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) + (∑ i, if f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧ (∀ c ∈ S i, σ (f i) < σ c) then w i else 0) := by rw [← sum_add_distrib] apply sum_congr rfl intro i _ by_cases hl : f i = a ∧ S i ⊆ A.erase a · have hnr : ¬(f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧ (∀ c ∈ S i, σ (f i) < σ c)) := by intro hr exact (mem_erase.mp hr.1).1 hl.1 have horig := (hdecomp i).mpr (Or.inl hl) rw [if_pos horig, if_pos hl, if_neg hnr, add_zero] · by_cases hr : f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧ (∀ c ∈ S i, σ (f i) < σ c) · have horig := (hdecomp i).mpr (Or.inr hr) rw [if_pos horig, if_neg hl, if_pos hr, zero_add] · have hnorig : ¬(f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c)) := by intro hh exact ((hdecomp i).mp hh).elim hl hr rw [if_neg hnorig, if_neg hl, if_neg hr, zero_add]
The total weight for $A$ is at most $H(A)$, completing the inductive step for nonempty $A$.
Rewriting the sum with `hsum`, the second component is bounded by $H(A \setminus \{a\})$ by applying the induction hypothesis to the strict subset $A \setminus \{a\} \subsetneq A$ (`erase_ssubset`, `Nat.add_le_add_left`). The hypothesis `hstep` on $a \in A$ bounds the first component plus $H(A \setminus \{a\})$ by $H(A)$. By transitivity of inequality (`le_trans`), the total sum is bounded by $H(A)$.
uses
le_trans,Nat.add_le_add_left,erase_ssubsetrw [hsum] exact le_trans (Nat.add_le_add_left (ih (A.erase a) (erase_ssubset ha)) _) (hstep A a ha)
When $A$ is empty, the bound holds trivially.
If $A$ is not nonempty, then $A = \emptyset$ (`not_nonempty_iff_eq_empty`). Substituting $A = \emptyset$, no claim can satisfy $f(i) \in \emptyset$, so every term in the sum is 0 and the sum evaluates to 0. Since $0 \le H(\emptyset)$ in $\mathbb{N}$, simplification closes the goal.
uses
not_nonempty_iff_eq_empty· have hA : A = ∅ := not_nonempty_iff_eq_empty.mp hne subst A simp
The main inequality holds: the total weight of claims satisfied by $\sigma$ is at most $H(\mathrm{univ})$.
Specializing `haux` to the universal candidate set $A = \mathrm{univ}$, the membership and inclusion hypotheses $f(i) \in \mathrm{univ}$ (`mem_univ`) and $S(i) \subseteq \mathrm{univ}$ (`subset_univ`) hold unconditionally. Simplifying with `true_and` leaves only the condition $\forall c \in S(i), \sigma(f(i)) < \sigma(c)$, yielding the desired bound.
uses
mem_univ,subset_univ,true_andsimpa only [mem_univ, subset_univ, true_and] using haux univ
Finset.strongInductionOn- Strong induction on finite sets: to prove a property holds for all finite sets, it suffices to prove it for any set assuming it holds for all of its strict subsets.
exists_min_image- Every nonempty finite set contains an element that minimizes a given function into a linearly ordered type.
not_lt_of_ge- If $a \le b$ in a preorder, then $b$ cannot be strictly less than $a$.
mem_erase- An element belongs to $s$ with $b$ removed if and only if it is not equal to $b$ and belongs to $s$.
subset_trans- Subset inclusion is transitive: if $a \subseteq b$ and $b \subseteq c$, then $a \subseteq c$.
erase_subset- Removing an element from a finite set yields a subset of the original set.
lt_of_le_of_ne- In a partial order, if $a \le b$ and $a \ne b$, then $a < b$.
mem_of_mem_erase- If an element belongs to $s$ with $a$ removed, then it belongs to $s$.
sum_add_distrib- The sum of a pointwise sum of two functions over a finite set equals the sum of the first function plus the sum of the second function.
sum_congr- Two sums over finite sets are equal if the sets of indices are equal and the summands agree on every element.
if_pos- If a condition $c$ is true, the conditional expression `if c then t else e` evaluates to $t$.
if_neg- If a condition $c$ is false, the conditional expression `if c then t else e` evaluates to $e$.
add_zero- Adding zero on the right leaves an element unchanged.
zero_add- Adding zero on the left leaves an element unchanged.
le_trans- Inequality is transitive: if $a \le b$ and $b \le c$, then $a \le c$.
Nat.add_le_add_left- Adding a natural number $k$ to both sides of an inequality preserves the inequality.
erase_ssubset- Removing an element that belongs to a finite set yields a strictly smaller subset.
not_nonempty_iff_eq_empty- A finite set is not nonempty if and only if it is the empty set.
mem_univ- Every element of a finite type belongs to the universal finite set `univ`.
subset_univ- Every finite set of elements of a finite type is a subset of `univ`.
true_and- The conjunction of `True` and $p$ simplifies to $p$.
- The proof strengthens the claim to an auxiliary statement `haux` bounding the weighted sum over any subset $A$ of candidates by $H(A)$, enabling strong induction on $A$ before specializing to $A = \mathrm{univ}$.
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_ordering_score_le_subset_potential (m q : ℕ) (S : Fin q → Finset (Fin m)) (f : Fin q → Fin m) (w : Fin q → ℕ) (H : Finset (Fin m) → ℕ) (hstep : ∀ A : Finset (Fin m), ∀ a ∈ A, (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) + H (A.erase a) ≤ H A) (σ : Equiv.Perm (Fin m)) : (∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0) ≤ H univ := by classical have haux : ∀ A : Finset (Fin m), (∑ i, if f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c) then w i else 0) ≤ H A := by intro A refine Finset.strongInductionOn A ?_ intro A ih by_cases hne : A.Nonempty · obtain ⟨a, ha, hmin⟩ := A.exists_min_image σ hne have hdecomp : ∀ i : Fin q, (f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c)) ↔ (f i = a ∧ S i ⊆ A.erase a) ∨ (f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧ (∀ c ∈ S i, σ (f i) < σ c)) := by intro i constructor · rintro ⟨hroot, hsub, hpref⟩ have hnot : a ∉ S i := by intro hmem exact (not_lt_of_ge (hmin (f i) hroot)) (hpref a hmem) have hsub' : S i ⊆ A.erase a := by intro c hc exact mem_erase.mpr ⟨by intro heq; subst c; exact hnot hc, hsub hc⟩ by_cases hfa : f i = a · exact Or.inl ⟨hfa, hsub'⟩ · exact Or.inr ⟨mem_erase.mpr ⟨hfa, hroot⟩, hsub', hpref⟩ · rintro (⟨hfa, hsub⟩ | ⟨hroot, hsub, hpref⟩) · refine ⟨hfa ▸ ha, subset_trans hsub (erase_subset a A), ?_⟩ intro c hc rw [hfa] have hc' := mem_erase.mp (hsub hc) apply lt_of_le_of_ne (hmin c hc'.2) intro heq exact hc'.1 (σ.injective heq).symm · exact ⟨mem_of_mem_erase hroot, subset_trans hsub (erase_subset a A), hpref⟩ have hsum : (∑ i, if f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c) then w i else 0) = (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) + (∑ i, if f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧ (∀ c ∈ S i, σ (f i) < σ c) then w i else 0) := by rw [← sum_add_distrib] apply sum_congr rfl intro i _ by_cases hl : f i = a ∧ S i ⊆ A.erase a · have hnr : ¬(f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧ (∀ c ∈ S i, σ (f i) < σ c)) := by intro hr exact (mem_erase.mp hr.1).1 hl.1 have horig := (hdecomp i).mpr (Or.inl hl) rw [if_pos horig, if_pos hl, if_neg hnr, add_zero] · by_cases hr : f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧ (∀ c ∈ S i, σ (f i) < σ c) · have horig := (hdecomp i).mpr (Or.inr hr) rw [if_pos horig, if_neg hl, if_pos hr, zero_add] · have hnorig : ¬(f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c)) := by intro hh exact ((hdecomp i).mp hh).elim hl hr rw [if_neg hnorig, if_neg hl, if_neg hr, zero_add] rw [hsum] exact le_trans (Nat.add_le_add_left (ih (A.erase a) (erase_ssubset ha)) _) (hstep A a ha) · have hA : A = ∅ := not_nonempty_iff_eq_empty.mp hne subst A simp simpa only [mem_univ, subset_univ, true_and] using haux univ