condorcet_subset_potential_of_cardinality_slack
For a finite family of weighted challenger claims, suppose an integer potential has local removal deficit bounded by an arbitrary integer delta(k), where k is the cardinality after removal. There exists a natural-valued valid subset potential whose full-set value is the original full value plus the sum of delta(k) for k below the candidate count, minus the original empty-set value. The increments may be negative. No existence of such small deficits for arbitrary selectors is asserted.
Statement
theorem condorcet_subset_potential_of_cardinality_slack (m q : ℕ) (S : Fin q → Finset (Fin m)) (f : Fin q → Fin m) (w : Fin q → ℕ) (H : Finset (Fin m) → ℤ) (δ : ℕ → ℤ) (hslack : ∀ 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 + δ ((A.erase a).card)) : ∃ K : Finset (Fin m) → ℕ, (∀ A : Finset (Fin m), ∀ a ∈ A, (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) + K (A.erase a) ≤ K A) ∧ ((K univ : ℕ) : ℤ) = H univ + (∑ k ∈ range m, δ k) - H ∅
- Source
- IN-341 supporting verification step for OP-19. Extends the subset-potential route from IN-339. Strict convention: 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 construction and verification helpers, with no new election dimension bound or research advance claimed.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
The proof, explained
To eliminate the cardinality-dependent deficit δ(k), the proof defines an adjusted integer potential J(A) = H(A) + (∑_{k < |A|} δ(k)) - H(∅), which accumulates the slack at each set size so that each removal step exactly absorbs the slack. By induction on the size of A, J is shown to be everywhere non-negative, which enables defining a natural-valued potential K(A) = (J(A)).toNat. Because K agrees with J, it inherits the local deficit-free potential inequality and satisfies the desired boundary value on the universal set.
Define an adjusted potential J on subsets by incorporating cumulative slack and normalizing at the empty set.
Enable classical logic and define J(A) = H(A) + ∑_{k=0}^{|A|-1} δ(k) - H(∅). This potential offsets each local removal deficit δ(|A \ {a}|) by accumulating the slacks up to cardinality |A|, while setting J(∅) = 0.
classical let J : Finset (Fin m) → ℤ := fun A => H A + (∑ k ∈ range A.card, δ k) - H ∅
The adjusted potential J satisfies the local deficit-free potential inequality.
For any subset A and element a ∈ A, card_erase_add_one gives |A| = |A \ {a}| + 1. Rewriting the cumulative sum in J(A) with sum_range_succ isolates the final slack term δ(|A \ {a}|). Combining this with the given hypothesis hslack, linear integer arithmetic (omega) verifies that the slack term cancels, yielding ∑_{i, f(i)=a, S(i) ⊆ A \ {a}} w(i) + J(A \ {a}) ≤ J(A).
uses
card_erase_add_one,sum_range_succhave hlocal : ∀ A : Finset (Fin m), ∀ a ∈ A, ((∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) : ℤ) + J (A.erase a) ≤ J A := by intro A a ha have hcard : A.card = (A.erase a).card + 1 := (card_erase_add_one ha).symm have hs := hslack A a ha dsimp only [J] rw [hcard, sum_range_succ] omega
The potential J is non-negative on all subsets.
We show 0 ≤ J(A) by induction on A using Finset.induction_on. In the base case A = ∅, J(∅) = 0 ≥ 0 holds by definition. For the inductive step A ∪ {a} with a ∉ A, the local inequality for J applied to A ∪ {a} and a (using mem_insert_self and erase_insert) shows J(A ∪ {a}) ≥ J(A) + W, where W is the sum of incoming challenger weights. Since challenger weights are non-negative, W ≥ 0 (by positivity), and linear arithmetic (omega) with the induction hypothesis 0 ≤ J(A) concludes 0 ≤ J(A ∪ {a}).
uses
Finset.induction_on,mem_insert_self,erase_inserthave hnonneg : ∀ A : Finset (Fin m), 0 ≤ J A := by intro A induction A using Finset.induction_on with | empty => simp [J] | @insert a A ha ih => have hl := hlocal (insert a A) a (mem_insert_self a A) have he : (insert a A).erase a = A := erase_insert ha rw [he] at hl have hn : (0 : ℤ) ≤ (∑ i, if f i = a ∧ S i ⊆ A then (w i : ℤ) else 0) := by positivity omega
Define a natural-valued potential K whose integer cast matches J.
We define K(A) = (J(A)).toNat. Because J is non-negative everywhere, Int.toNat_of_nonneg guarantees that casting K(A) back to ℤ recovers J(A) exactly.
uses
Int.toNat_of_nonneglet K : Finset (Fin m) → ℕ := fun A => (J A).toNat have hcast : ∀ A, (K A : ℤ) = J A := fun A => Int.toNat_of_nonneg (hnonneg A)
The natural-valued potential K satisfies the local potential inequality.
We provide K as the witness for the existential quantifier. For any A and a ∈ A, rewriting the local inequality for J in terms of the cast of K and pulling the integer cast out across the arithmetic operations (exact_mod_cast) proves the local inequality for K over ℕ.
refine ⟨K, ?_, ?_⟩ · intro A a ha have hl := hlocal A a ha rw [← hcast (A.erase a), ← hcast A] at hl exact_mod_cast hl
The potential K satisfies the specified boundary identity on the universal set.
Rewriting K(univ) as J(univ), we expand the definition of J at the full universe univ. Simplifying the cardinality |univ| to m via card_univ and Fintype.card_fin yields K(univ) = H(univ) + ∑_{k=0}^{m-1} δ(k) - H(∅).
uses
card_univ,Fintype.card_fin· rw [hcast] simp only [J, card_univ, Fintype.card_fin]
card_erase_add_one- Removing an element a from a finite set s decreases its cardinality by 1: |s \ {a}| + 1 = |s|.
sum_range_succ- Splits off the last term of a summation over a range: ∑_{k=0}^n f(k) = (∑_{k=0}^{n-1} f(k)) + f(n).
Finset.induction_on- Induction principle for finite sets: a property holds for all finite sets if it holds for the empty set and is preserved under adjoining a new element.
mem_insert_self- An element a always belongs to the set obtained by inserting a into s.
erase_insert- Inserting an element a not in s and then erasing a yields s.
Int.toNat_of_nonneg- If an integer a is non-negative, casting its natural truncation a.toNat back to ℤ yields a.
card_univ- The cardinality of the universal finset on a finite type equals the cardinality of that type.
Fintype.card_fin- The cardinality of Fin n is n.
- The definition of K as the natural truncation of J and the subsequent cast conversions are formal artifacts needed because Lean requires K to take values in ℕ while H and δ take values in ℤ.
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_subset_potential_of_cardinality_slack (m q : ℕ) (S : Fin q → Finset (Fin m)) (f : Fin q → Fin m) (w : Fin q → ℕ) (H : Finset (Fin m) → ℤ) (δ : ℕ → ℤ) (hslack : ∀ 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 + δ ((A.erase a).card)) : ∃ K : Finset (Fin m) → ℕ, (∀ A : Finset (Fin m), ∀ a ∈ A, (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) + K (A.erase a) ≤ K A) ∧ ((K univ : ℕ) : ℤ) = H univ + (∑ k ∈ range m, δ k) - H ∅ := by classical let J : Finset (Fin m) → ℤ := fun A => H A + (∑ k ∈ range A.card, δ k) - H ∅ have hlocal : ∀ A : Finset (Fin m), ∀ a ∈ A, ((∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) : ℤ) + J (A.erase a) ≤ J A := by intro A a ha have hcard : A.card = (A.erase a).card + 1 := (card_erase_add_one ha).symm have hs := hslack A a ha dsimp only [J] rw [hcard, sum_range_succ] omega have hnonneg : ∀ A : Finset (Fin m), 0 ≤ J A := by intro A induction A using Finset.induction_on with | empty => simp [J] | @insert a A ha ih => have hl := hlocal (insert a A) a (mem_insert_self a A) have he : (insert a A).erase a = A := erase_insert ha rw [he] at hl have hn : (0 : ℤ) ≤ (∑ i, if f i = a ∧ S i ⊆ A then (w i : ℤ) else 0) := by positivity omega let K : Finset (Fin m) → ℕ := fun A => (J A).toNat have hcast : ∀ A, (K A : ℤ) = J A := fun A => Int.toNat_of_nonneg (hnonneg A) refine ⟨K, ?_, ?_⟩ · intro A a ha have hl := hlocal A a ha rw [← hcast (A.erase a), ← hcast A] at hl exact_mod_cast hl · rw [hcast] simp only [J, card_univ, Fintype.card_fin]