AFTD Auto-Formalizing Theoretical Domains

condorcet_ordering_score_le_subset_potential

theoremverified

For any finite family of challenger claims and nonnegative integer claim weights, suppose a natural-valued potential on remaining candidate subsets bounds the gain from removing any first candidate plus the potential of the remainder. Then the total weight of claims satisfied by every strict ranking is at most the potential of the full candidate set. Claims whose committee contains their challenger need no extra exclusion hypothesis.

Statement

theorem condorcet_ordering_score_le_subset_potential
    (m q : ℕ) (S : Fin q → Finset (Fin m)) (f : Fin q → Fin m)
    (w : Fin q → ℕ) (H : Finset (Fin m) → ℕ)
    (hstep : ∀ 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)
    (σ : Equiv.Perm (Fin m)) :
    (∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0) ≤ H univ
Source
IN-339 supporting step for the OP-19 campaign. Strict definition: 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 verification and coalition-closure helpers; no new dimension 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.
Used by 5

The proof, explained

The theorem is proved by generalizing the statement to arbitrary candidate subsets $A \subseteq \mathrm{Fin}\, m$ and proceeding by strong induction on the size of $A$. In the inductive step for a nonempty set $A$, we pick a candidate $a \in A$ that minimizes the permutation $\sigma$. The claims satisfied within $A$ partition into those whose challenger is $a$ (whose committee then necessarily avoids $a$ by the minimality of $\sigma(a)$) and those entirely contained within $A \setminus \{a\}$. By the induction hypothesis, the weight of the latter is bounded by $H(A \setminus \{a\})$, and the one-step potential inequality for $a \in A$ bounds the sum of both parts by $H(A)$; evaluating at $A = \mathrm{univ}$ yields the result.

  1. The theorem reduces to proving, by strong induction on candidate subsets $A$, that the total weight of claims satisfied within $A$ is at most $H(A)$.

    We work in classical logic and formulate an auxiliary induction statement `haux`: for any subset $A \subseteq \mathrm{Fin}\, m$, the sum of weights of claims $i$ satisfying $f(i) \in A$, $S(i) \subseteq A$, and $\sigma(f(i)) < \sigma(c)$ for all $c \in S(i)$ is at most $H(A)$. We proceed by strong induction on $A$ using `Finset.strongInductionOn`, assuming as induction hypothesis `ih` that the claim holds for all strict subsets of $A$.

    lines 13–19

    uses Finset.strongInductionOn

      classical
      have haux : ∀ A : Finset (Fin m),
          (∑ i, if f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c)
            then w i else 0) ≤ H A := by
        intro A
        refine Finset.strongInductionOn A ?_
        intro A ih
  2. If $A$ is nonempty, there exists a candidate $a \in A$ that minimizes $\sigma$ on $A$.

    We split into cases on whether $A$ is nonempty. When $A$ is nonempty, `exists_min_image` supplies an element $a \in A$ such that $\sigma(a) \le \sigma(x)$ for all $x \in A$.

    lines 20–21

    uses exists_min_image

        by_cases hne : A.Nonempty
        · obtain ⟨a, ha, hmin⟩ := A.exists_min_image σ hne
  3. A claim $i$ is satisfied within $A$ if and only if either $f(i) = a$ with $S(i) \subseteq A \setminus \{a\}$, or $f(i)$ and $S(i)$ both lie in $A \setminus \{a\}$ with $f(i)$ beating every member of $S(i)$ under $\sigma$.

    For the forward implication, suppose $f(i) \in A$, $S(i) \subseteq A$, and $\sigma(f(i)) < \sigma(c)$ for all $c \in S(i)$. Then $a \notin S(i)$, because otherwise $\sigma(f(i)) < \sigma(a)$, which contradicts the minimality of $\sigma(a)$ on $A$ (`not_lt_of_ge`). Hence $S(i) \subseteq A \setminus \{a\}$ (`mem_erase`). Case-splitting on whether $f(i) = a$ gives either the first disjunct or $f(i) \in A \setminus \{a\}$, which is the second disjunct. Conversely, if $f(i) = a$ and $S(i) \subseteq A \setminus \{a\}$, then $f(i) \in A$ and $S(i) \subseteq A$ (`subset_trans`, `erase_subset`); moreover, for each $c \in S(i)$, $c \in A$ with $c \ne a$, so $\sigma(a) \le \sigma(c)$ and $\sigma(a) \ne \sigma(c)$ (since $\sigma$ is injective), which implies $\sigma(f(i)) = \sigma(a) < \sigma(c)$ (`lt_of_le_of_ne`). In the other case, $f(i) \in A \setminus \{a\}$ immediately implies $f(i) \in A$ (`mem_of_mem_erase`) and $S(i) \subseteq A$, preserving the condition.

    lines 22–47

    uses not_lt_of_ge, mem_erase, subset_trans, erase_subset, lt_of_le_of_ne, mem_of_mem_erase

          have hdecomp : ∀ i : Fin q,
              (f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c)) ↔
                (f i = a ∧ S i ⊆ A.erase a) ∨
                (f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧
                  (∀ c ∈ S i, σ (f i) < σ c)) := by
            intro i
            constructor
            · rintro ⟨hroot, hsub, hpref⟩
              have hnot : a ∉ S i := by
                intro hmem
                exact (not_lt_of_ge (hmin (f i) hroot)) (hpref a hmem)
              have hsub' : S i ⊆ A.erase a := by
                intro c hc
                exact mem_erase.mpr ⟨by intro heq; subst c; exact hnot hc, hsub hc⟩
              by_cases hfa : f i = a
              · exact Or.inl ⟨hfa, hsub'⟩
              · exact Or.inr ⟨mem_erase.mpr ⟨hfa, hroot⟩, hsub', hpref⟩
            · rintro (⟨hfa, hsub⟩ | ⟨hroot, hsub, hpref⟩)
              · refine ⟨hfa ▸ ha, subset_trans hsub (erase_subset a A), ?_⟩
                intro c hc
                rw [hfa]
                have hc' := mem_erase.mp (hsub hc)
                apply lt_of_le_of_ne (hmin c hc'.2)
                intro heq
                exact hc'.1 (σ.injective heq).symm
              · exact ⟨mem_of_mem_erase hroot, subset_trans hsub (erase_subset a A), hpref⟩
  4. The sum of weights of claims satisfied in $A$ decomposes into the sum over claims with $f(i) = a$ and $S(i) \subseteq A \setminus \{a\}$ plus the sum over claims satisfied entirely in $A \setminus \{a\}$.

    Using `sum_add_distrib` and `sum_congr`, we merge the two sums and check summand-by-summand that each claim $i$ contributes identically on both sides. When $f(i) = a \wedge S(i) \subseteq A \setminus \{a\}$ holds, the second condition is false (as $f(i) = a$ contradicts $f(i) \in A \setminus \{a\}$ by `mem_erase`), so the summand simplifies to $w(i) + 0 = w(i)$ by `if_pos`, `if_neg`, and `add_zero`. When the second condition holds, the first is false, giving $0 + w(i) = w(i)$ by `zero_add`. When neither holds, the decomposition equivalence `hdecomp` ensures the original condition is also false, giving $0 = 0 + 0$.

    lines 48–72

    uses sum_add_distrib, sum_congr, mem_erase, if_pos, if_neg, add_zero, zero_add

          have hsum :
              (∑ i, if f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c)
                then w i else 0) =
              (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) +
              (∑ i, if f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧
                (∀ c ∈ S i, σ (f i) < σ c) then w i else 0) := by
            rw [← sum_add_distrib]
            apply sum_congr rfl
            intro i _
            by_cases hl : f i = a ∧ S i ⊆ A.erase a
            · have hnr : ¬(f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧
                    (∀ c ∈ S i, σ (f i) < σ c)) := by
                intro hr
                exact (mem_erase.mp hr.1).1 hl.1
              have horig := (hdecomp i).mpr (Or.inl hl)
              rw [if_pos horig, if_pos hl, if_neg hnr, add_zero]
            · by_cases hr : f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧
                    (∀ c ∈ S i, σ (f i) < σ c)
              · have horig := (hdecomp i).mpr (Or.inr hr)
                rw [if_pos horig, if_neg hl, if_pos hr, zero_add]
              · have hnorig : ¬(f i ∈ A ∧ S i ⊆ A ∧
                    (∀ c ∈ S i, σ (f i) < σ c)) := by
                  intro hh
                  exact ((hdecomp i).mp hh).elim hl hr
                rw [if_neg hnorig, if_neg hl, if_neg hr, zero_add]
  5. The total weight for $A$ is at most $H(A)$, completing the inductive step for nonempty $A$.

    Rewriting the sum with `hsum`, the second component is bounded by $H(A \setminus \{a\})$ by applying the induction hypothesis to the strict subset $A \setminus \{a\} \subsetneq A$ (`erase_ssubset`, `Nat.add_le_add_left`). The hypothesis `hstep` on $a \in A$ bounds the first component plus $H(A \setminus \{a\})$ by $H(A)$. By transitivity of inequality (`le_trans`), the total sum is bounded by $H(A)$.

    lines 73–75

    uses le_trans, Nat.add_le_add_left, erase_ssubset

          rw [hsum]
          exact le_trans (Nat.add_le_add_left (ih (A.erase a) (erase_ssubset ha)) _)
            (hstep A a ha)
  6. When $A$ is empty, the bound holds trivially.

    If $A$ is not nonempty, then $A = \emptyset$ (`not_nonempty_iff_eq_empty`). Substituting $A = \emptyset$, no claim can satisfy $f(i) \in \emptyset$, so every term in the sum is 0 and the sum evaluates to 0. Since $0 \le H(\emptyset)$ in $\mathbb{N}$, simplification closes the goal.

    lines 76–78

    uses not_nonempty_iff_eq_empty

        · have hA : A = ∅ := not_nonempty_iff_eq_empty.mp hne
          subst A
          simp
  7. The main inequality holds: the total weight of claims satisfied by $\sigma$ is at most $H(\mathrm{univ})$.

    Specializing `haux` to the universal candidate set $A = \mathrm{univ}$, the membership and inclusion hypotheses $f(i) \in \mathrm{univ}$ (`mem_univ`) and $S(i) \subseteq \mathrm{univ}$ (`subset_univ`) hold unconditionally. Simplifying with `true_and` leaves only the condition $\forall c \in S(i), \sigma(f(i)) < \sigma(c)$, yielding the desired bound.

    line 79

    uses mem_univ, subset_univ, true_and

      simpa only [mem_univ, subset_univ, true_and] using haux univ
Finset.strongInductionOn
Strong induction on finite sets: to prove a property holds for all finite sets, it suffices to prove it for any set assuming it holds for all of its strict subsets.
exists_min_image
Every nonempty finite set contains an element that minimizes a given function into a linearly ordered type.
not_lt_of_ge
If $a \le b$ in a preorder, then $b$ cannot be strictly less than $a$.
mem_erase
An element belongs to $s$ with $b$ removed if and only if it is not equal to $b$ and belongs to $s$.
subset_trans
Subset inclusion is transitive: if $a \subseteq b$ and $b \subseteq c$, then $a \subseteq c$.
erase_subset
Removing an element from a finite set yields a subset of the original set.
lt_of_le_of_ne
In a partial order, if $a \le b$ and $a \ne b$, then $a < b$.
mem_of_mem_erase
If an element belongs to $s$ with $a$ removed, then it belongs to $s$.
sum_add_distrib
The sum of a pointwise sum of two functions over a finite set equals the sum of the first function plus the sum of the second function.
sum_congr
Two sums over finite sets are equal if the sets of indices are equal and the summands agree on every element.
if_pos
If a condition $c$ is true, the conditional expression `if c then t else e` evaluates to $t$.
if_neg
If a condition $c$ is false, the conditional expression `if c then t else e` evaluates to $e$.
add_zero
Adding zero on the right leaves an element unchanged.
zero_add
Adding zero on the left leaves an element unchanged.
le_trans
Inequality is transitive: if $a \le b$ and $b \le c$, then $a \le c$.
Nat.add_le_add_left
Adding a natural number $k$ to both sides of an inequality preserves the inequality.
erase_ssubset
Removing an element that belongs to a finite set yields a strictly smaller subset.
not_nonempty_iff_eq_empty
A finite set is not nonempty if and only if it is the empty set.
mem_univ
Every element of a finite type belongs to the universal finite set `univ`.
subset_univ
Every finite set of elements of a finite type is a subset of `univ`.
true_and
The conjunction of `True` and $p$ simplifies to $p$.

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_ordering_score_le_subset_potential    (m q : ℕ) (S : Fin q → Finset (Fin m)) (f : Fin q → Fin m)    (w : Fin q → ℕ) (H : Finset (Fin m) → ℕ)    (hstep : ∀ 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)    (σ : Equiv.Perm (Fin m)) :    (∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0) ≤ H univ := by  classical  have haux : ∀ A : Finset (Fin m),      (∑ i, if f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c)        then w i else 0) ≤ H A := by    intro A    refine Finset.strongInductionOn A ?_    intro A ih    by_cases hne : A.Nonempty    · obtain ⟨a, ha, hmin⟩ := A.exists_min_image σ hne      have hdecomp : ∀ i : Fin q,          (f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c)) ↔            (f i = a ∧ S i ⊆ A.erase a) ∨            (f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧              (∀ c ∈ S i, σ (f i) < σ c)) := by        intro i        constructor        · rintro ⟨hroot, hsub, hpref⟩          have hnot : a ∉ S i := by            intro hmem            exact (not_lt_of_ge (hmin (f i) hroot)) (hpref a hmem)          have hsub' : S i ⊆ A.erase a := by            intro c hc            exact mem_erase.mpr ⟨by intro heq; subst c; exact hnot hc, hsub hc⟩          by_cases hfa : f i = a          · exact Or.inl ⟨hfa, hsub'⟩          · exact Or.inr ⟨mem_erase.mpr ⟨hfa, hroot⟩, hsub', hpref⟩        · rintro (⟨hfa, hsub⟩ | ⟨hroot, hsub, hpref⟩)          · refine ⟨hfa ▸ ha, subset_trans hsub (erase_subset a A), ?_⟩            intro c hc            rw [hfa]            have hc' := mem_erase.mp (hsub hc)            apply lt_of_le_of_ne (hmin c hc'.2)            intro heq            exact hc'.1 (σ.injective heq).symm          · exact ⟨mem_of_mem_erase hroot, subset_trans hsub (erase_subset a A), hpref⟩      have hsum :          (∑ i, if f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c)            then w i else 0) =          (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) +          (∑ i, if f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧            (∀ c ∈ S i, σ (f i) < σ c) then w i else 0) := by        rw [← sum_add_distrib]        apply sum_congr rfl        intro i _        by_cases hl : f i = a ∧ S i ⊆ A.erase a        · have hnr : ¬(f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧                (∀ c ∈ S i, σ (f i) < σ c)) := by            intro hr            exact (mem_erase.mp hr.1).1 hl.1          have horig := (hdecomp i).mpr (Or.inl hl)          rw [if_pos horig, if_pos hl, if_neg hnr, add_zero]        · by_cases hr : f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧                (∀ c ∈ S i, σ (f i) < σ c)          · have horig := (hdecomp i).mpr (Or.inr hr)            rw [if_pos horig, if_neg hl, if_pos hr, zero_add]          · have hnorig : ¬(f i ∈ A ∧ S i ⊆ A ∧                (∀ c ∈ S i, σ (f i) < σ c)) := by              intro hh              exact ((hdecomp i).mp hh).elim hl hr            rw [if_neg hnorig, if_neg hl, if_neg hr, zero_add]      rw [hsum]      exact le_trans (Nat.add_le_add_left (ih (A.erase a) (erase_ssubset ha)) _)        (hstep A a ha)    · have hA : A = ∅ := not_nonempty_iff_eq_empty.mp hne      subst A      simp  simpa only [mem_univ, subset_univ, true_and] using haux univ
See it in the graphDiscuss this resultChallenge it