AFTD Auto-Formalizing Theoretical Domains

condorcet_subset_potential_of_cardinality_slack

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

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.

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

    lines 17–19

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

    lines 20–28

    uses card_erase_add_one, sum_range_succ

      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
  3. 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}).

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

    lines 40–41

    uses Int.toNat_of_nonneg

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

    lines 42–46

      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 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(∅).

    lines 47–48

    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.

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