condorcet_ordering_certificate_iff_subset_potential
For any finite family of challenger claims and fixed nonnegative integer claim weights, a strict half-weight score bound for every strict ranking is equivalent to the existence of a natural-valued remaining-subset potential satisfying all local first-candidate removal inequalities and the same strict half-weight full-set bound. Unrestricted potentials add no loss to the ordering-certificate method; bounding their degree is an extra restriction.
Statement
theorem condorcet_ordering_certificate_iff_subset_potential (m q : ℕ) (S : Fin q → Finset (Fin m)) (f : Fin q → Fin m) (w : Fin q → ℕ) : (∀ σ : Equiv.Perm (Fin m), 2 * (∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0) < ∑ i, w i) ↔ ∃ H : Finset (Fin m) → ℕ, (∀ 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) ∧ 2 * H univ < ∑ i, w i
- Source
- IN-339 verification route for OP-19, extending the uniform ordering-certificate reduction and the exact strict-majority convention in Condorcet winning sets, Social Choice and Welfare44(3):493-517 (2015). Related selector formulation arXiv:2604.19851v2. This is a certificate equivalence, not a new winning-set bound or research advance.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- condorcet_ordering_score_le_subset_potentialFor any finite family of challenger claims and nonnegative integer claim weights, suppose a natural-valued potential on remaining…
- 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…
The proof, explained
The proof establishes the equivalence by bridging rankings and subset potentials through the maximum score. In the forward direction, the supremum of the score function over all rankings is attained at some ranking because the set of permutations is finite and nonempty; the assumed bound on that ranking implies $2M < \\sum_i w_i$, and `condorcet_subset_potential_of_ordering_bound` turns this upper bound $M$ into a valid subset potential $H$ with $H(\\mathrm{univ}) \\le M$. Conversely, `condorcet_ordering_score_le_subset_potential` shows that the score of any ranking is bounded by $H(\\mathrm{univ})$, so the strict bound on $H(\\mathrm{univ})$ immediately transfers to every ranking.
To prove the equivalence, we first consider the forward direction: assume that every ranking satisfies the strict half-weight score bound.
Using classical logic, we split the if-and-only-if statement into two implications. In the forward direction, we assume the hypothesis that $2 \\cdot \\mathrm{score}(\\sigma) < \\sum_i w_i$ for every permutation $\\sigma$.
classical constructor · intro hcert
The maximum score $M$ over all rankings is attained at some permutation $\\sigma$ and satisfies $2M < \\sum_i w_i$.
We define the score function on permutations and let $M$ be its supremum over all permutations on $m$ elements. By `Finset.le_sup` and `mem_univ`, every permutation has score at most $M$. Since the set of permutations is nonempty (the identity permutation belongs to it by `mem_univ`), `Finset.sup_mem_of_nonempty` guarantees that the supremum $M$ is attained at some permutation $\\sigma$. Applying the forward hypothesis to $\\sigma$ gives $2M = 2 \\cdot \\mathrm{score}(\\sigma) < \\sum_i w_i$.
uses
Finset.le_sup,mem_univ,Finset.sup_mem_of_nonemptylet score : Equiv.Perm (Fin m) → ℕ := fun σ => ∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0 let M : ℕ := univ.sup score have hM : ∀ σ, score σ ≤ M := fun σ => Finset.le_sup (mem_univ σ) have hne : (univ : Finset (Equiv.Perm (Fin m))).Nonempty := ⟨1, mem_univ _⟩ obtain ⟨σ, _, heq⟩ := Finset.sup_mem_of_nonempty (s := univ) (f := score) hne have hstrict : 2 * M < ∑ i, w i := by change 2 * (univ.sup score) < _ rw [← heq] exact hcert σ
There exists a subset potential $H$ satisfying all local candidate-removal inequalities and $2 \\cdot H(\\mathrm{univ}) < \\sum_i w_i$.
Because every ranking has score bounded by $M$, `condorcet_subset_potential_of_ordering_bound` produces a potential $H$ satisfying the candidate-removal step inequalities with $H(\\mathrm{univ}) \\le M$. Multiplying by 2 via `Nat.mul_le_mul_left` gives $2 \\cdot H(\\mathrm{univ}) \\le 2M$, and combining this with $2M < \\sum_i w_i$ via `lt_of_le_of_lt` yields $2 \\cdot H(\\mathrm{univ}) < \\sum_i w_i$, completing the forward direction.
uses
condorcet_subset_potential_of_ordering_bound,Nat.mul_le_mul_left,lt_of_le_of_ltobtain ⟨H, hstep, hfull⟩ := condorcet_subset_potential_of_ordering_bound m q S f w M hM exact ⟨H, hstep, lt_of_le_of_lt (Nat.mul_le_mul_left 2 hfull) hstrict⟩
Conversely, the existence of such a potential $H$ implies that every ranking satisfies the strict half-weight score bound.
For the backward direction, assume given a potential $H$ satisfying the step inequalities and $2 \\cdot H(\\mathrm{univ}) < \\sum_i w_i$. For any permutation $\\sigma$, `condorcet_ordering_score_le_subset_potential` bounds its score by $H(\\mathrm{univ})$. Multiplying this inequality by 2 with `Nat.mul_le_mul_left` and chaining with $2 \\cdot H(\\mathrm{univ}) < \\sum_i w_i$ via `lt_of_le_of_lt` shows that $2 \\cdot \\mathrm{score}(\\sigma) < \\sum_i w_i$.
uses
Nat.mul_le_mul_left,condorcet_ordering_score_le_subset_potential,lt_of_le_of_lt· rintro ⟨H, hstep, hstrict⟩ σ exact lt_of_le_of_lt (Nat.mul_le_mul_left 2 (condorcet_ordering_score_le_subset_potential m q S f w H hstep σ)) hstrict
Finset.le_sup- In a semilattice with a bottom element, the value of a function at any element of a finite set is bounded above by the supremum of the function over that set.
mem_univ- Every element of a finite type belongs to the universal finite set `univ`.
Finset.sup_mem_of_nonempty- On a nonempty finite set, the supremum of a function into a linear order with a bottom element is attained by the function at some element of the set.
condorcet_subset_potential_of_ordering_bound- If every ranking has score at most $M$, then there exists a subset potential $H$ satisfying the local candidate-removal step inequalities such that $H(\\mathrm{univ}) \\le M$.
condorcet_ordering_score_le_subset_potential- For any subset potential $H$ satisfying the candidate-removal step inequalities, the score of any ranking $\\sigma$ is bounded above by $H(\\mathrm{univ})$.
lt_of_le_of_lt- If $a \\le b$ and $b < c$ in a preorder, then $a < c$.
Nat.mul_le_mul_left- Multiplication by a natural number preserves non-strict inequalities between natural numbers ($n \\le m \\implies k \\cdot n \\le k \\cdot m$).
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 6000000set_option maxRecDepth 10000theorem condorcet_ordering_certificate_iff_subset_potential (m q : ℕ) (S : Fin q → Finset (Fin m)) (f : Fin q → Fin m) (w : Fin q → ℕ) : (∀ σ : Equiv.Perm (Fin m), 2 * (∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0) < ∑ i, w i) ↔ ∃ H : Finset (Fin m) → ℕ, (∀ 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) ∧ 2 * H univ < ∑ i, w i := by classical constructor · intro hcert let score : Equiv.Perm (Fin m) → ℕ := fun σ => ∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0 let M : ℕ := univ.sup score have hM : ∀ σ, score σ ≤ M := fun σ => Finset.le_sup (mem_univ σ) have hne : (univ : Finset (Equiv.Perm (Fin m))).Nonempty := ⟨1, mem_univ _⟩ obtain ⟨σ, _, heq⟩ := Finset.sup_mem_of_nonempty (s := univ) (f := score) hne have hstrict : 2 * M < ∑ i, w i := by change 2 * (univ.sup score) < _ rw [← heq] exact hcert σ obtain ⟨H, hstep, hfull⟩ := condorcet_subset_potential_of_ordering_bound m q S f w M hM exact ⟨H, hstep, lt_of_le_of_lt (Nat.mul_le_mul_left 2 hfull) hstrict⟩ · rintro ⟨H, hstep, hstrict⟩ σ exact lt_of_le_of_lt (Nat.mul_le_mul_left 2 (condorcet_ordering_score_le_subset_potential m q S f w H hstep σ)) hstrict