AFTD Auto-Formalizing Theoretical Domains

condorcet_subset_potential_of_integer_slack

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

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.

  1. 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.

    lines 17–18

      classical
      let J : Finset (Fin m) → ℤ := fun A => H A + (δ : ℤ) * A.card - H ∅
  2. $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$.

    lines 19–28

    uses card_erase_add_one

      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
  3. $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.

    lines 29–39

    uses Finset.induction_on, mem_insert_self, erase_insert

      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
  4. 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$.

    lines 40–43

    uses Int.toNat_of_nonneg

      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)
  5. $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.

    lines 44–48

      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
  6. 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.

    lines 49–50

    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

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]
See it in the graphDiscuss this resultChallenge it