condorcet_subset_potential_of_ordering_bound
For any finite family of challenger claims with nonnegative integer weights, if every strict candidate ranking has satisfied-claim weight at most a natural number M, there is a natural-valued potential on remaining candidate subsets satisfying all local first-candidate removal inequalities and with full-set value at most M. No outside-challenger hypothesis is needed.
Statement
theorem condorcet_subset_potential_of_ordering_bound (m q : ℕ) (S : Fin q → Finset (Fin m)) (f : Fin q → Fin m) (w : Fin q → ℕ) (M : ℕ) (hbound : ∀ σ : Equiv.Perm (Fin m), (∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0) ≤ M) : ∃ 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) ∧ H univ ≤ M
- 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 3
- condorcet_ordering_score_le_subset_potentialFor any finite family of challenger claims and nonnegative integer claim weights, suppose a natural-valued potential on remaining…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- 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…
The proof, explained
The proof defines a potential function H(A) on subsets of candidates as the maximum over all rankings σ of the restricted score R(A, σ), which sums the weights of claims whose focal candidate and opponents both lie in A and are satisfied by σ. To prove the local removal inequality for a candidate a ∈ A, it takes an optimal ranking σ achieving H(A \ {a}) and constructs a new ranking τ by promoting a to first place (rank 0) via a cyclic shift, while preserving the relative order of all other candidates. A term-by-term comparison shows that claims previously satisfied under σ remain satisfied under τ, while claims with focal candidate a and opponents in A \ {a} become newly satisfied under τ, bounding the total by R(A, τ) ≤ H(A). Finally, H(univ) ≤ M holds directly because R(univ, σ) is the total weight of claims satisfied by σ, which is at most M by the hypothesis.
Define the restricted claim score R(A, σ) and the potential H(A) = max_σ R(A, σ), splitting the goal into the local removal inequality and the upper bound on H(univ).
For any candidate subset A and ranking σ, R(A, σ) sums the weights of claims i whose focal candidate and opponents both lie in A and which are satisfied by σ (that is, σ(f(i)) < σ(c) for all c ∈ S(i)). The potential H(A) is defined as the maximum of R(A, σ) over all candidate permutations σ. The existential goal is provided with witness H, splitting into proving the local inequality upon removing an element a from A, and showing H(univ) ≤ M.
classical let R : Finset (Fin m) → Equiv.Perm (Fin m) → ℕ := fun A σ => ∑ i, if f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c) then w i else 0 let H : Finset (Fin m) → ℕ := fun A => univ.sup (R A) refine ⟨H, ?_, ?_⟩
Given A and a ∈ A, select an optimal permutation σ achieving H(A \ {a}) = R(A \ {a}, σ).
We fix a candidate subset A, an element a, and the assumption a ∈ A. Because the set of candidate rankings is finite and non-empty (containing at least the identity permutation), the supremum defining H(A \ {a}) is attained by some permutation σ.
uses
mem_univ,Finset.sup_mem_of_nonempty· intro A a ha have hne : (univ : Finset (Equiv.Perm (Fin m))).Nonempty := ⟨1, mem_univ _⟩ obtain ⟨σ, hσ, hval⟩ := Finset.sup_mem_of_nonempty (s := univ) (f := R (A.erase a)) hne have hH : H (A.erase a) = R (A.erase a) σ := hval.symm
Construct a ranking τ from σ by cyclically shifting {0, ..., σ(a)} so that candidate a is placed in rank 0.
Because a is a candidate, the number of candidates m is non-zero. Post-composing σ with the cyclic permutation `Fin.cycleRange (σ a)` maps σ(a) to 0, shifts all candidates previously ranked ahead of a up by one rank, and leaves all candidates ranked behind a unchanged. In particular, τ(a) = 0.
uses
lt_of_le_of_lt,Nat.zero_le,Nat.ne_of_gt,Fin.cycleRange_selfhave hm0 : 0 < m := lt_of_le_of_lt (Nat.zero_le a.val) a.isLt letI : NeZero m := ⟨Nat.ne_of_gt hm0⟩ let τ : Equiv.Perm (Fin m) := σ.trans (Fin.cycleRange (σ a)) have hτa : τ a = 0 := by exact Fin.cycleRange_self (σ a)
Under the new ranking τ, candidate a is ranked strictly ahead of every other candidate b ≠ a.
Since τ(a) = 0, for any candidate b ≠ a, the injectivity of τ implies τ(b) ≠ 0. In Fin m, every non-zero element is strictly greater than 0, so τ(a) = 0 < τ(b).
uses
Fin.pos_iff_ne_zero'have htop : ∀ b, b ≠ a → τ a < τ b := by intro b hb rw [hτa] apply (Fin.pos_iff_ne_zero' (τ b)).mpr intro hzero apply hb exact τ.injective (hzero.trans hτa.symm)
The new ranking τ preserves the relative order of any two candidates distinct from a.
Let b, c ≠ a with σ(b) < σ(c). By injectivity, neither σ(b) nor σ(c) equals σ(a). If both were ranked ahead of a under σ, `cycleRange` increments both of their ranks by 1, preserving σ(b) + 1 < σ(c) + 1. If σ(b) < σ(a) < σ(c), then τ(b) = σ(b) + 1 ≤ σ(a) < σ(c) = τ(c), which follows by linear arithmetic. If both were ranked behind a, `cycleRange` fixes both ranks. In every case, τ(b) < τ(c).
uses
Fin.coe_cycleRange_of_lt,Nat.add_lt_add_right,lt_of_le_of_ne,le_of_not_gt,Ne.symm,Fin.cycleRange_of_gt,lt_transhave hkeep : ∀ b c, b ≠ a → c ≠ a → σ b < σ c → τ b < τ c := by intro b c hb hc hbc have hbr : σ b ≠ σ a := fun hh => hb (σ.injective hh) have hcr : σ c ≠ σ a := fun hh => hc (σ.injective hh) change (Fin.cycleRange (σ a) (σ b)).val < (Fin.cycleRange (σ a) (σ c)).val by_cases hbl : σ b < σ a · by_cases hcl : σ c < σ a · rw [Fin.coe_cycleRange_of_lt hbl, Fin.coe_cycleRange_of_lt hcl] exact Nat.add_lt_add_right hbc 1 · have hcg : σ a < σ c := lt_of_le_of_ne (le_of_not_gt hcl) (Ne.symm hcr) rw [Fin.coe_cycleRange_of_lt hbl, Fin.cycleRange_of_gt hcg] have hb' : (σ b).val < (σ a).val := hbl have hc' : (σ a).val < (σ c).val := hcg omega · have hbg : σ a < σ b := lt_of_le_of_ne (le_of_not_gt hbl) (Ne.symm hbr) have hcg : σ a < σ c := lt_trans hbg hbc rw [Fin.cycleRange_of_gt hbg, Fin.cycleRange_of_gt hcg] exact hbc
The sum of the newly satisfied claims upon removing a plus R(A \ {a}, σ) is at most R(A, τ).
We combine the two sums on the left and compare term-by-term with R(A, τ) for each claim i: (1) if f(i) = a and S(i) ⊆ A \ {a}, then f(i) ∈ A and S(i) ⊆ A, and because every opponent c ∈ S(i) differs from a, candidate a beats c under τ, contributing w(i) to both the left sum and R(A, τ) while contributing 0 to R(A \ {a}, σ); (2) if f(i) ∈ A \ {a}, S(i) ⊆ A \ {a}, and σ satisfied the claim, then neither f(i) nor any opponent is a, so by order preservation τ also satisfies the claim, contributing w(i) to both R(A \ {a}, σ) and R(A, τ); (3) otherwise, the left side terms are 0, which is trivially at most the non-negative right-hand term.
uses
sum_add_distrib,sum_le_sum,subset_trans,erase_subset,if_pos,if_neg,add_zero,mem_of_mem_erase,zero_add,Nat.zero_lehave hgain : (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) + R (A.erase a) σ ≤ R A τ := by dsimp only [R] rw [← sum_add_distrib] apply sum_le_sum intro i _ by_cases hl : f i = a ∧ S i ⊆ A.erase a · have hn : ¬(f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧ (∀ c ∈ S i, σ (f i) < σ c)) := by intro hh exact (mem_erase.mp hh.1).1 hl.1 have ht : f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, τ (f i) < τ c) := by refine ⟨hl.1 ▸ ha, subset_trans hl.2 (erase_subset a A), ?_⟩ intro c hc rw [hl.1] exact htop c (mem_erase.mp (hl.2 hc)).1 rw [if_pos hl, if_neg hn, if_pos ht, add_zero] · by_cases hr : f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧ (∀ c ∈ S i, σ (f i) < σ c) · have ht : f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, τ (f i) < τ c) := by refine ⟨mem_of_mem_erase hr.1, subset_trans hr.2.1 (erase_subset a A), ?_⟩ intro c hc exact hkeep (f i) c (mem_erase.mp hr.1).1 (mem_erase.mp (hr.2.1 hc)).1 (hr.2.2 c hc) rw [if_neg hl, if_pos hr, if_pos ht, zero_add] · rw [if_neg hl, if_neg hr, zero_add] exact Nat.zero_le _
The local removal inequality holds: (∑_{i, f(i) = a, S(i) ⊆ A \ {a}} w(i)) + H(A \ {a}) ≤ H(A).
Since H(A \ {a}) = R(A \ {a}, σ), the term-by-term bound establishes that the left-hand sum is at most R(A, τ). Because H(A) is the supremum of R(A, ·) over all rankings, R(A, τ) ≤ H(A).
uses
Finset.le_sup,mem_univrw [hH] exact hgain.trans (Finset.le_sup (mem_univ τ))
The potential on the full candidate set satisfies H(univ) ≤ M.
To bound H(univ) = sup_σ R(univ, σ) by M, it suffices to bound R(univ, σ) ≤ M for every ranking σ. When A = univ, the inclusion conditions f(i) ∈ univ and S(i) ⊆ univ are automatically satisfied, so R(univ, σ) is exactly the total weight of claims satisfied by σ, which is bounded by M by the theorem hypothesis.
uses
Finset.sup_le,mem_univ,subset_univ,true_and· apply Finset.sup_le intro σ _ simpa only [R, mem_univ, subset_univ, true_and] using hbound σ
mem_univ- Every element of a finite type belongs to the universal finset `univ`.
Finset.sup_mem_of_nonempty- On a non-empty finite set, the supremum of a function is attained at some element of the set.
lt_of_le_of_lt- If a ≤ b and b < c, then a < c.
Nat.zero_le- Zero is less than or equal to any natural number.
Nat.ne_of_gt- If b < a, then a ≠ b.
Fin.cycleRange_self- The cyclic shift permutation `cycleRange i` maps the element i to 0.
Fin.pos_iff_ne_zero'- An element of `Fin n` is strictly positive if and only if it is non-zero.
Fin.coe_cycleRange_of_lt- If i < j, the cyclic permutation `j.cycleRange` maps i to i + 1.
Nat.add_lt_add_right- Adding a constant to both sides of a strict inequality preserves the strict inequality.
lt_of_le_of_ne- If a ≤ b and a ≠ b, then a < b.
le_of_not_gt- In a linear order, if b is not strictly less than a, then a ≤ b.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Fin.cycleRange_of_gt- The cyclic shift permutation `i.cycleRange` fixes every element strictly greater than i.
lt_trans- Strict inequality is transitive: if a < b and b < c, then a < c.
sum_add_distrib- The sum of a pointwise sum over a finite set equals the sum of the individual sums.
sum_le_sum- If f(i) ≤ g(i) for every element i in a finite set, then the sum of f is at most the sum of g.
subset_trans- Subset inclusion is transitive: if A ⊆ B and B ⊆ C, then A ⊆ C.
erase_subset- Removing an element from a finite set yields a subset of the original set.
if_pos- If a condition c is true, the if-then-else expression evaluates to its then-branch.
if_neg- If a condition c is false, the if-then-else expression evaluates to its else-branch.
add_zero- Adding zero on the right leaves an element unchanged.
mem_of_mem_erase- If an element belongs to s \ {a}, it belongs to s.
zero_add- Adding zero on the left leaves an element unchanged.
Finset.le_sup- The value of a function at any element of a finite set is at most the supremum over that set.
Finset.sup_le- If every value of a function on a finite set is at most a constant, then the supremum over the set is at most that constant.
subset_univ- Every subset of a finite type is a subset of the universal finset `univ`.
true_and- Conjunction with True simplifies to the proposition itself.
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_subset_potential_of_ordering_bound (m q : ℕ) (S : Fin q → Finset (Fin m)) (f : Fin q → Fin m) (w : Fin q → ℕ) (M : ℕ) (hbound : ∀ σ : Equiv.Perm (Fin m), (∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0) ≤ M) : ∃ 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) ∧ H univ ≤ M := by classical let R : Finset (Fin m) → Equiv.Perm (Fin m) → ℕ := fun A σ => ∑ i, if f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c) then w i else 0 let H : Finset (Fin m) → ℕ := fun A => univ.sup (R A) refine ⟨H, ?_, ?_⟩ · intro A a ha have hne : (univ : Finset (Equiv.Perm (Fin m))).Nonempty := ⟨1, mem_univ _⟩ obtain ⟨σ, hσ, hval⟩ := Finset.sup_mem_of_nonempty (s := univ) (f := R (A.erase a)) hne have hH : H (A.erase a) = R (A.erase a) σ := hval.symm have hm0 : 0 < m := lt_of_le_of_lt (Nat.zero_le a.val) a.isLt letI : NeZero m := ⟨Nat.ne_of_gt hm0⟩ let τ : Equiv.Perm (Fin m) := σ.trans (Fin.cycleRange (σ a)) have hτa : τ a = 0 := by exact Fin.cycleRange_self (σ a) have htop : ∀ b, b ≠ a → τ a < τ b := by intro b hb rw [hτa] apply (Fin.pos_iff_ne_zero' (τ b)).mpr intro hzero apply hb exact τ.injective (hzero.trans hτa.symm) have hkeep : ∀ b c, b ≠ a → c ≠ a → σ b < σ c → τ b < τ c := by intro b c hb hc hbc have hbr : σ b ≠ σ a := fun hh => hb (σ.injective hh) have hcr : σ c ≠ σ a := fun hh => hc (σ.injective hh) change (Fin.cycleRange (σ a) (σ b)).val < (Fin.cycleRange (σ a) (σ c)).val by_cases hbl : σ b < σ a · by_cases hcl : σ c < σ a · rw [Fin.coe_cycleRange_of_lt hbl, Fin.coe_cycleRange_of_lt hcl] exact Nat.add_lt_add_right hbc 1 · have hcg : σ a < σ c := lt_of_le_of_ne (le_of_not_gt hcl) (Ne.symm hcr) rw [Fin.coe_cycleRange_of_lt hbl, Fin.cycleRange_of_gt hcg] have hb' : (σ b).val < (σ a).val := hbl have hc' : (σ a).val < (σ c).val := hcg omega · have hbg : σ a < σ b := lt_of_le_of_ne (le_of_not_gt hbl) (Ne.symm hbr) have hcg : σ a < σ c := lt_trans hbg hbc rw [Fin.cycleRange_of_gt hbg, Fin.cycleRange_of_gt hcg] exact hbc have hgain : (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) + R (A.erase a) σ ≤ R A τ := by dsimp only [R] rw [← sum_add_distrib] apply sum_le_sum intro i _ by_cases hl : f i = a ∧ S i ⊆ A.erase a · have hn : ¬(f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧ (∀ c ∈ S i, σ (f i) < σ c)) := by intro hh exact (mem_erase.mp hh.1).1 hl.1 have ht : f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, τ (f i) < τ c) := by refine ⟨hl.1 ▸ ha, subset_trans hl.2 (erase_subset a A), ?_⟩ intro c hc rw [hl.1] exact htop c (mem_erase.mp (hl.2 hc)).1 rw [if_pos hl, if_neg hn, if_pos ht, add_zero] · by_cases hr : f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧ (∀ c ∈ S i, σ (f i) < σ c) · have ht : f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, τ (f i) < τ c) := by refine ⟨mem_of_mem_erase hr.1, subset_trans hr.2.1 (erase_subset a A), ?_⟩ intro c hc exact hkeep (f i) c (mem_erase.mp hr.1).1 (mem_erase.mp (hr.2.1 hc)).1 (hr.2.2 c hc) rw [if_neg hl, if_pos hr, if_pos ht, zero_add] · rw [if_neg hl, if_neg hr, zero_add] exact Nat.zero_le _ rw [hH] exact hgain.trans (Finset.le_sup (mem_univ τ)) · apply Finset.sup_le intro σ _ simpa only [R, mem_univ, subset_univ, true_and] using hbound σ