condorcet_subset_potential_of_integer_slack
For any family of challenger claims with nonnegative integer weights and an integer-valued subset function, suppose every candidate-removal inequality has deficit at most a fixed natural number delta. There is a natural-valued subset potential satisfying all the exact removal inequalities whose full-set value equals the original full-set value plus delta times the number of candidates minus the original empty-set value. This repairs verified integer rounding deficits; it does not assert a strict half bound.
Statement
theorem condorcet_subset_potential_of_integer_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 + δ) : ∃ 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 + (δ : ℤ) * m - H ∅
- Source
- IN-339 supporting method lemma for the uniform subset-potential route to OP-19. Strict winning-set convention from Condorcet winning sets, Social Choice and Welfare44(3):493-517 (2015); related selector formulation arXiv:2604.19851v2. No new election 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
The proof, explained
The proof constructs an adjusted potential $J(A) = H(A) + \\delta |A| - H(\\emptyset)$ on subsets of candidates. Because removing an element decreases the cardinality by 1, the linear term $\\delta |A|$ contributes an additional $\\delta$ at each step, absorbing the slack deficit from the hypothesis and yielding exact removal inequalities for $J$. By induction on finite subsets, $J(A)$ is shown to be non-negative everywhere, using $J(\\emptyset) = 0$ and the non-negativity of weights. Finally, setting $K(A) = (J(A)).\\text{toNat}$ gives a natural-valued potential whose integer cast coincides with $J$, inheriting both the exact removal inequalities and the desired evaluation on the full set.
Define an adjusted integer potential $J(A) = H(A) + \\delta |A| - H(\\emptyset)$.
We enable classical logic and define an auxiliary potential $J : \\text{Finset}(\\text{Fin } m) \\to \\mathbb{Z}$ by offsetting $H(A)$ by $\\delta |A| - H(\\emptyset)$. This normalizes the empty set to value zero and offsets the value by $\\delta$ per element to absorb the deficit of $\\delta$ incurred at each candidate-removal step.
classical let J : Finset (Fin m) → ℤ := fun A => H A + (δ : ℤ) * A.card - H ∅
$J$ satisfies the exact candidate-removal inequalities with no deficit.
For any subset $A$ and element $a \\in A$, the cardinality identity $|A| = |A \\setminus \\{a\\}| + 1$ holds by `card_erase_add_one`. Expanding the definition of $J$, the difference $\\delta |A| - \\delta |A \\setminus \\{a\\}|$ contributes an extra $\\delta$ to $J(A)$, which precisely cancels the deficit $\\delta$ from the assumed inequality `hslack`. Linear arithmetic (`nlinarith`) closes the inequality for $J$.
uses
card_erase_add_onehave 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 := by exact_mod_cast (card_erase_add_one ha).symm have hs := hslack A a ha dsimp only [J] rw [hcard] nlinarith
$J(A) \\ge 0$ for every subset $A$.
We prove non-negativity by finite-set induction on $A$ using `Finset.induction_on`. In the base case $A = \\emptyset$, $J(\\emptyset) = H(\\emptyset) + 0 - H(\\emptyset) = 0 \\ge 0$. In the inductive step, for $a \\notin A$, we apply the local inequality `hlocal` to $A \\cup \\{a\\}$ and $a$, noting that $a \\in A \\cup \\{a\\}$ by `mem_insert_self` and $(A \\cup \\{a\\}) \\setminus \\{a\\} = A$ by `erase_insert`. Since the challenger weights are non-negative (`positivity`) and $J(A) \\ge 0$ by the induction hypothesis, $J(A \\cup \\{a\\}) \\ge J(A) \\ge 0$, which `omega` verifies.
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 $K(A) = (J(A)).\\text{toNat}$, which agrees with $J(A)$ when cast to integers.
Since $J(A) \\ge 0$ for every subset $A$, we can define $K(A)$ as the natural-number truncation of $J(A)$. By `Int.toNat_of_nonneg`, the integer cast of $K(A)$ equals $J(A)$ identically for all $A$.
uses
Int.toNat_of_nonneglet K : Finset (Fin m) → ℕ := fun A => (J A).toNat have hcast : ∀ A, (K A : ℤ) = J A := by intro A exact Int.toNat_of_nonneg (hnonneg A)
$K$ satisfies the exact candidate-removal inequalities over $\\mathbb{N}$.
We provide $K$ as the existential witness. For any $A$ and $a \\in A$, we take the exact inequality already proved for $J$, replace each occurrence of $J$ with the integer cast of $K$ using our casting equality, and cast the resulting inequality down to the natural numbers.
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 value of $K$ on the universal set is $H(\\text{univ}) + \\delta m - H(\\emptyset)$.
Using the casting equality, $K(\\text{univ})$ cast to an integer equals $J(\\text{univ}) = H(\\text{univ}) + \\delta |\\text{univ}| - H(\\emptyset)$. The cardinality of `univ` on `Fin m` is $m$, by `card_univ` and `Fintype.card_fin`, completing the evaluation.
uses
card_univ,Fintype.card_fin· rw [hcast] simp only [J, card_univ, Fintype.card_fin]
card_erase_add_one- For any element $a$ in a finite set $s$, $|s \\setminus \\{a\\}| + 1 = |s|$.
Finset.induction_on- To prove a property for all finite sets, it suffices to prove it for the empty set and show that inserting a new element preserves the property.
mem_insert_self- An element $a$ belongs to the set $s \\cup \\{a\\}$ obtained by inserting $a$ into $s$.
erase_insert- If an element $a$ is not in $s$, then removing $a$ after inserting it yields $s$ again.
Int.toNat_of_nonneg- For any non-negative integer $a$, converting $a$ to a natural number and casting back to an integer yields $a$.
card_univ- The cardinality of the universal finset `univ` of a finite type is the cardinality of the type.
Fintype.card_fin- The finite type `Fin n` has cardinality $n$.
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_integer_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 + δ) : ∃ 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 + (δ : ℤ) * m - H ∅ := by classical let J : Finset (Fin m) → ℤ := fun A => H A + (δ : ℤ) * A.card - 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 := by exact_mod_cast (card_erase_add_one ha).symm have hs := hslack A a ha dsimp only [J] rw [hcard] nlinarith 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 := by intro A exact 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]