AFTD Auto-Formalizing Theoretical Domains

condorcet_subset_potential_of_ordering_bound

theoremverified

For any finite family of challenger claims with nonnegative integer weights, if every strict candidate ranking has satisfied-claim weight at most a natural number M, there is a natural-valued potential on remaining candidate subsets satisfying all local first-candidate removal inequalities and with full-set value at most M. No outside-challenger hypothesis is needed.

Statement

theorem condorcet_subset_potential_of_ordering_bound
    (m q : ℕ) (S : Fin q → Finset (Fin m)) (f : Fin q → Fin m)
    (w : Fin q → ℕ) (M : ℕ)
    (hbound : ∀ σ : Equiv.Perm (Fin m),
      (∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0) ≤ M) :
    ∃ H : Finset (Fin m) → ℕ,
      (∀ 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) ∧
      H univ ≤ M
Source
IN-339 verification route for OP-19, extending the uniform ordering-certificate reduction and the exact strict-majority convention in Condorcet winning sets, Social Choice and Welfare44(3):493-517 (2015). Related selector formulation arXiv:2604.19851v2. This is a certificate equivalence, not a new winning-set bound or research advance.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

The proof, explained

The proof defines a potential function H(A) on subsets of candidates as the maximum over all rankings σ of the restricted score R(A, σ), which sums the weights of claims whose focal candidate and opponents both lie in A and are satisfied by σ. To prove the local removal inequality for a candidate a ∈ A, it takes an optimal ranking σ achieving H(A \ {a}) and constructs a new ranking τ by promoting a to first place (rank 0) via a cyclic shift, while preserving the relative order of all other candidates. A term-by-term comparison shows that claims previously satisfied under σ remain satisfied under τ, while claims with focal candidate a and opponents in A \ {a} become newly satisfied under τ, bounding the total by R(A, τ) ≤ H(A). Finally, H(univ) ≤ M holds directly because R(univ, σ) is the total weight of claims satisfied by σ, which is at most M by the hypothesis.

  1. Define the restricted claim score R(A, σ) and the potential H(A) = max_σ R(A, σ), splitting the goal into the local removal inequality and the upper bound on H(univ).

    For any candidate subset A and ranking σ, R(A, σ) sums the weights of claims i whose focal candidate and opponents both lie in A and which are satisfied by σ (that is, σ(f(i)) < σ(c) for all c ∈ S(i)). The potential H(A) is defined as the maximum of R(A, σ) over all candidate permutations σ. The existential goal is provided with witness H, splitting into proving the local inequality upon removing an element a from A, and showing H(univ) ≤ M.

    lines 15–19

      classical
      let R : Finset (Fin m) → Equiv.Perm (Fin m) → ℕ := fun A σ =>
        ∑ i, if f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c) then w i else 0
      let H : Finset (Fin m) → ℕ := fun A => univ.sup (R A)
      refine ⟨H, ?_, ?_⟩
  2. Given A and a ∈ A, select an optimal permutation σ achieving H(A \ {a}) = R(A \ {a}, σ).

    We fix a candidate subset A, an element a, and the assumption a ∈ A. Because the set of candidate rankings is finite and non-empty (containing at least the identity permutation), the supremum defining H(A \ {a}) is attained by some permutation σ.

    lines 20–23

    uses mem_univ, Finset.sup_mem_of_nonempty

      · intro A a ha
        have hne : (univ : Finset (Equiv.Perm (Fin m))).Nonempty := ⟨1, mem_univ _⟩
        obtain ⟨σ, hσ, hval⟩ := Finset.sup_mem_of_nonempty (s := univ) (f := R (A.erase a)) hne
        have hH : H (A.erase a) = R (A.erase a) σ := hval.symm
  3. Construct a ranking τ from σ by cyclically shifting {0, ..., σ(a)} so that candidate a is placed in rank 0.

    Because a is a candidate, the number of candidates m is non-zero. Post-composing σ with the cyclic permutation `Fin.cycleRange (σ a)` maps σ(a) to 0, shifts all candidates previously ranked ahead of a up by one rank, and leaves all candidates ranked behind a unchanged. In particular, τ(a) = 0.

    lines 24–28

    uses lt_of_le_of_lt, Nat.zero_le, Nat.ne_of_gt, Fin.cycleRange_self

        have hm0 : 0 < m := lt_of_le_of_lt (Nat.zero_le a.val) a.isLt
        letI : NeZero m := ⟨Nat.ne_of_gt hm0⟩
        let τ : Equiv.Perm (Fin m) := σ.trans (Fin.cycleRange (σ a))
        have hτa : τ a = 0 := by
          exact Fin.cycleRange_self (σ a)
  4. Under the new ranking τ, candidate a is ranked strictly ahead of every other candidate b ≠ a.

    Since τ(a) = 0, for any candidate b ≠ a, the injectivity of τ implies τ(b) ≠ 0. In Fin m, every non-zero element is strictly greater than 0, so τ(a) = 0 < τ(b).

    lines 29–35

    uses Fin.pos_iff_ne_zero'

        have htop : ∀ b, b ≠ a → τ a < τ b := by
          intro b hb
          rw [hτa]
          apply (Fin.pos_iff_ne_zero' (τ b)).mpr
          intro hzero
          apply hb
          exact τ.injective (hzero.trans hτa.symm)
  5. The new ranking τ preserves the relative order of any two candidates distinct from a.

    Let b, c ≠ a with σ(b) < σ(c). By injectivity, neither σ(b) nor σ(c) equals σ(a). If both were ranked ahead of a under σ, `cycleRange` increments both of their ranks by 1, preserving σ(b) + 1 < σ(c) + 1. If σ(b) < σ(a) < σ(c), then τ(b) = σ(b) + 1 ≤ σ(a) < σ(c) = τ(c), which follows by linear arithmetic. If both were ranked behind a, `cycleRange` fixes both ranks. In every case, τ(b) < τ(c).

    lines 36–53

    uses Fin.coe_cycleRange_of_lt, Nat.add_lt_add_right, lt_of_le_of_ne, le_of_not_gt, Ne.symm, Fin.cycleRange_of_gt, lt_trans

        have hkeep : ∀ b c, b ≠ a → c ≠ a → σ b < σ c → τ b < τ c := by
          intro b c hb hc hbc
          have hbr : σ b ≠ σ a := fun hh => hb (σ.injective hh)
          have hcr : σ c ≠ σ a := fun hh => hc (σ.injective hh)
          change (Fin.cycleRange (σ a) (σ b)).val < (Fin.cycleRange (σ a) (σ c)).val
          by_cases hbl : σ b < σ a
          · by_cases hcl : σ c < σ a
            · rw [Fin.coe_cycleRange_of_lt hbl, Fin.coe_cycleRange_of_lt hcl]
              exact Nat.add_lt_add_right hbc 1
            · have hcg : σ a < σ c := lt_of_le_of_ne (le_of_not_gt hcl) (Ne.symm hcr)
              rw [Fin.coe_cycleRange_of_lt hbl, Fin.cycleRange_of_gt hcg]
              have hb' : (σ b).val < (σ a).val := hbl
              have hc' : (σ a).val < (σ c).val := hcg
              omega
          · have hbg : σ a < σ b := lt_of_le_of_ne (le_of_not_gt hbl) (Ne.symm hbr)
            have hcg : σ a < σ c := lt_trans hbg hbc
            rw [Fin.cycleRange_of_gt hbg, Fin.cycleRange_of_gt hcg]
            exact hbc
  6. The sum of the newly satisfied claims upon removing a plus R(A \ {a}, σ) is at most R(A, τ).

    We combine the two sums on the left and compare term-by-term with R(A, τ) for each claim i: (1) if f(i) = a and S(i) ⊆ A \ {a}, then f(i) ∈ A and S(i) ⊆ A, and because every opponent c ∈ S(i) differs from a, candidate a beats c under τ, contributing w(i) to both the left sum and R(A, τ) while contributing 0 to R(A \ {a}, σ); (2) if f(i) ∈ A \ {a}, S(i) ⊆ A \ {a}, and σ satisfied the claim, then neither f(i) nor any opponent is a, so by order preservation τ also satisfies the claim, contributing w(i) to both R(A \ {a}, σ) and R(A, τ); (3) otherwise, the left side terms are 0, which is trivially at most the non-negative right-hand term.

    lines 54–80

    uses sum_add_distrib, sum_le_sum, subset_trans, erase_subset, if_pos, if_neg, add_zero, mem_of_mem_erase, zero_add, Nat.zero_le

        have hgain :
            (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) + R (A.erase a) σ ≤ R A τ := by
          dsimp only [R]
          rw [← sum_add_distrib]
          apply sum_le_sum
          intro i _
          by_cases hl : f i = a ∧ S i ⊆ A.erase a
          · have hn : ¬(f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧
                (∀ c ∈ S i, σ (f i) < σ c)) := by
              intro hh
              exact (mem_erase.mp hh.1).1 hl.1
            have ht : f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, τ (f i) < τ c) := by
              refine ⟨hl.1 ▸ ha, subset_trans hl.2 (erase_subset a A), ?_⟩
              intro c hc
              rw [hl.1]
              exact htop c (mem_erase.mp (hl.2 hc)).1
            rw [if_pos hl, if_neg hn, if_pos ht, add_zero]
          · by_cases hr : f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧
                (∀ c ∈ S i, σ (f i) < σ c)
            · have ht : f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, τ (f i) < τ c) := by
                refine ⟨mem_of_mem_erase hr.1, subset_trans hr.2.1 (erase_subset a A), ?_⟩
                intro c hc
                exact hkeep (f i) c (mem_erase.mp hr.1).1
                  (mem_erase.mp (hr.2.1 hc)).1 (hr.2.2 c hc)
              rw [if_neg hl, if_pos hr, if_pos ht, zero_add]
            · rw [if_neg hl, if_neg hr, zero_add]
              exact Nat.zero_le _
  7. The local removal inequality holds: (∑_{i, f(i) = a, S(i) ⊆ A \ {a}} w(i)) + H(A \ {a}) ≤ H(A).

    Since H(A \ {a}) = R(A \ {a}, σ), the term-by-term bound establishes that the left-hand sum is at most R(A, τ). Because H(A) is the supremum of R(A, ·) over all rankings, R(A, τ) ≤ H(A).

    lines 81–82

    uses Finset.le_sup, mem_univ

        rw [hH]
        exact hgain.trans (Finset.le_sup (mem_univ τ))
  8. The potential on the full candidate set satisfies H(univ) ≤ M.

    To bound H(univ) = sup_σ R(univ, σ) by M, it suffices to bound R(univ, σ) ≤ M for every ranking σ. When A = univ, the inclusion conditions f(i) ∈ univ and S(i) ⊆ univ are automatically satisfied, so R(univ, σ) is exactly the total weight of claims satisfied by σ, which is bounded by M by the theorem hypothesis.

    lines 83–85

    uses Finset.sup_le, mem_univ, subset_univ, true_and

      · apply Finset.sup_le
        intro σ _
        simpa only [R, mem_univ, subset_univ, true_and] using hbound σ
mem_univ
Every element of a finite type belongs to the universal finset `univ`.
Finset.sup_mem_of_nonempty
On a non-empty finite set, the supremum of a function is attained at some element of the set.
lt_of_le_of_lt
If a ≤ b and b < c, then a < c.
Nat.zero_le
Zero is less than or equal to any natural number.
Nat.ne_of_gt
If b < a, then a ≠ b.
Fin.cycleRange_self
The cyclic shift permutation `cycleRange i` maps the element i to 0.
Fin.pos_iff_ne_zero'
An element of `Fin n` is strictly positive if and only if it is non-zero.
Fin.coe_cycleRange_of_lt
If i < j, the cyclic permutation `j.cycleRange` maps i to i + 1.
Nat.add_lt_add_right
Adding a constant to both sides of a strict inequality preserves the strict inequality.
lt_of_le_of_ne
If a ≤ b and a ≠ b, then a < b.
le_of_not_gt
In a linear order, if b is not strictly less than a, then a ≤ b.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Fin.cycleRange_of_gt
The cyclic shift permutation `i.cycleRange` fixes every element strictly greater than i.
lt_trans
Strict inequality is transitive: if a < b and b < c, then a < c.
sum_add_distrib
The sum of a pointwise sum over a finite set equals the sum of the individual sums.
sum_le_sum
If f(i) ≤ g(i) for every element i in a finite set, then the sum of f is at most the sum of g.
subset_trans
Subset inclusion is transitive: if A ⊆ B and B ⊆ C, then A ⊆ C.
erase_subset
Removing an element from a finite set yields a subset of the original set.
if_pos
If a condition c is true, the if-then-else expression evaluates to its then-branch.
if_neg
If a condition c is false, the if-then-else expression evaluates to its else-branch.
add_zero
Adding zero on the right leaves an element unchanged.
mem_of_mem_erase
If an element belongs to s \ {a}, it belongs to s.
zero_add
Adding zero on the left leaves an element unchanged.
Finset.le_sup
The value of a function at any element of a finite set is at most the supremum over that set.
Finset.sup_le
If every value of a function on a finite set is at most a constant, then the supremum over the set is at most that constant.
subset_univ
Every subset of a finite type is a subset of the universal finset `univ`.
true_and
Conjunction with True simplifies to the proposition itself.

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 6000000set_option maxRecDepth 10000theorem condorcet_subset_potential_of_ordering_bound    (m q : ℕ) (S : Fin q → Finset (Fin m)) (f : Fin q → Fin m)    (w : Fin q → ℕ) (M : ℕ)    (hbound : ∀ σ : Equiv.Perm (Fin m),      (∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0) ≤ M) :    ∃ H : Finset (Fin m) → ℕ,      (∀ 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) ∧      H univ ≤ M := by  classical  let R : Finset (Fin m) → Equiv.Perm (Fin m) → ℕ := fun A σ =>    ∑ i, if f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, σ (f i) < σ c) then w i else 0  let H : Finset (Fin m) → ℕ := fun A => univ.sup (R A)  refine ⟨H, ?_, ?_⟩  · intro A a ha    have hne : (univ : Finset (Equiv.Perm (Fin m))).Nonempty := ⟨1, mem_univ _⟩    obtain ⟨σ, hσ, hval⟩ := Finset.sup_mem_of_nonempty (s := univ) (f := R (A.erase a)) hne    have hH : H (A.erase a) = R (A.erase a) σ := hval.symm    have hm0 : 0 < m := lt_of_le_of_lt (Nat.zero_le a.val) a.isLt    letI : NeZero m := ⟨Nat.ne_of_gt hm0⟩    let τ : Equiv.Perm (Fin m) := σ.trans (Fin.cycleRange (σ a))    have hτa : τ a = 0 := by      exact Fin.cycleRange_self (σ a)    have htop : ∀ b, b ≠ a → τ a < τ b := by      intro b hb      rw [hτa]      apply (Fin.pos_iff_ne_zero' (τ b)).mpr      intro hzero      apply hb      exact τ.injective (hzero.trans hτa.symm)    have hkeep : ∀ b c, b ≠ a → c ≠ a → σ b < σ c → τ b < τ c := by      intro b c hb hc hbc      have hbr : σ b ≠ σ a := fun hh => hb (σ.injective hh)      have hcr : σ c ≠ σ a := fun hh => hc (σ.injective hh)      change (Fin.cycleRange (σ a) (σ b)).val < (Fin.cycleRange (σ a) (σ c)).val      by_cases hbl : σ b < σ a      · by_cases hcl : σ c < σ a        · rw [Fin.coe_cycleRange_of_lt hbl, Fin.coe_cycleRange_of_lt hcl]          exact Nat.add_lt_add_right hbc 1        · have hcg : σ a < σ c := lt_of_le_of_ne (le_of_not_gt hcl) (Ne.symm hcr)          rw [Fin.coe_cycleRange_of_lt hbl, Fin.cycleRange_of_gt hcg]          have hb' : (σ b).val < (σ a).val := hbl          have hc' : (σ a).val < (σ c).val := hcg          omega      · have hbg : σ a < σ b := lt_of_le_of_ne (le_of_not_gt hbl) (Ne.symm hbr)        have hcg : σ a < σ c := lt_trans hbg hbc        rw [Fin.cycleRange_of_gt hbg, Fin.cycleRange_of_gt hcg]        exact hbc    have hgain :        (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) + R (A.erase a) σ ≤ R A τ := by      dsimp only [R]      rw [← sum_add_distrib]      apply sum_le_sum      intro i _      by_cases hl : f i = a ∧ S i ⊆ A.erase a      · have hn : ¬(f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧            (∀ c ∈ S i, σ (f i) < σ c)) := by          intro hh          exact (mem_erase.mp hh.1).1 hl.1        have ht : f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, τ (f i) < τ c) := by          refine ⟨hl.1 ▸ ha, subset_trans hl.2 (erase_subset a A), ?_⟩          intro c hc          rw [hl.1]          exact htop c (mem_erase.mp (hl.2 hc)).1        rw [if_pos hl, if_neg hn, if_pos ht, add_zero]      · by_cases hr : f i ∈ A.erase a ∧ S i ⊆ A.erase a ∧            (∀ c ∈ S i, σ (f i) < σ c)        · have ht : f i ∈ A ∧ S i ⊆ A ∧ (∀ c ∈ S i, τ (f i) < τ c) := by            refine ⟨mem_of_mem_erase hr.1, subset_trans hr.2.1 (erase_subset a A), ?_⟩            intro c hc            exact hkeep (f i) c (mem_erase.mp hr.1).1              (mem_erase.mp (hr.2.1 hc)).1 (hr.2.2 c hc)          rw [if_neg hl, if_pos hr, if_pos ht, zero_add]        · rw [if_neg hl, if_neg hr, zero_add]          exact Nat.zero_le _    rw [hH]    exact hgain.trans (Finset.le_sup (mem_univ τ))  · apply Finset.sup_le    intro σ _    simpa only [R, mem_univ, subset_univ, true_and] using hbound σ
See it in the graphDiscuss this resultChallenge it