AFTD Auto-Formalizing Theoretical Domains

condorcet_subset_potential_extend_from_closed_core

theoremverified

A local subset-potential certificate whose challenger roots and committee members all lie in a candidate core extends to the full candidate universe by intersecting every potential argument with the core. The local inequalities and full-set cost are preserved. This is a certificate-support reduction, not an assumption that an election balance property survives restriction.

Statement

theorem condorcet_subset_potential_extend_from_closed_core
    (C I : Type*) [Fintype C] [DecidableEq C] [Fintype I]
    (V : Finset C) (S : I → Finset C) (f : I → C) (w : I → ℕ)
    (hS : ∀ i, S i ⊆ V) (hf : ∀ i, f i ∈ V)
    (K : Finset C → ℕ)
    (hstep : ∀ A : Finset C, A ⊆ V → ∀ a ∈ A,
      (∑ i, if f i=a ∧ S i ⊆ A.erase a then w i else 0)+K (A.erase a) ≤ K A) :
    let H := fun A : Finset C => K (A ∩ V)
    (∀ A : Finset C, ∀ a ∈ A,
      (∑ i, if f i=a ∧ S i ⊆ A.erase a then w i else 0)+H (A.erase a) ≤ H A) ∧
    H Finset.univ = K V
Source
IN-341 generic support reduction for the OP-19 potential route. An actual failing-selector map may be restricted to a subset closed under all its rooted-triple claims; a potential on such a core can then ignore irrelevant candidates. No existence of a proper closed core, no weight-dispersion theorem, and no new election bound is asserted.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

To extend a local potential certificate K defined on subsets of a core V to the entire candidate universe, one sets H(A) = K(A ∩ V). For any set A and element a ∈ A, the step inequality is verified by case analysis on whether a ∈ V: if a ∈ V, all challenger committees and roots are already contained in V, so the sum and potential terms coincide with those for A ∩ V and satisfy the certificate hypothesis; if a ∉ V, no challenger can have root a, causing the sum to vanish and leaving a trivial inequality K(A ∩ V) ≤ K(A ∩ V). The boundary condition H(univ) = K(V) is immediate since univ ∩ V = V.

  1. The extension problem splits into showing that H(A) = K(A ∩ V) satisfies the inductive potential inequality for all candidate sets A and elements a ∈ A, and that H on the full universe equals K(V).

    We simplify the let-binding defining H and split the conjunction into its two goals: the inductive step inequality for any set A and element a ∈ A, and the boundary condition H(univ) = K(V).

    lines 15–16

      dsimp only
      constructor
  2. To verify the step inequality for arbitrary A and a ∈ A, it suffices to analyze separately whether a ∈ V or a ∉ V.

    We fix an arbitrary subset A and an element a ∈ A. Using Finset.erase_inter, we record the set identity (A \ {a}) ∩ V = (A ∩ V) \ {a}, and then split into two cases based on whether a belongs to the core V.

    lines 17–19

    uses Finset.erase_inter

      · intro A a ha
        have h1 : (A.erase a) ∩ V = (A ∩ V).erase a := Finset.erase_inter a A V
        by_cases haV : a ∈ V
  3. When a ∈ V, the induction hypothesis hstep applies directly to the restricted set A ∩ V and element a ∈ A ∩ V.

    Since A ∩ V ⊆ V (by Finset.inter_subset_right) and a ∈ A ∩ V (by Finset.mem_inter.mpr), the hypothesis hstep yields the step inequality for A ∩ V and a. Rewriting with the set identity puts the potential term in the form K((A ∩ V) \ {a}).

    lines 20–23

    uses Finset.inter_subset_right, Finset.mem_inter.mpr

        · have hB : A ∩ V ⊆ V := Finset.inter_subset_right
          have haB : a ∈ A ∩ V := Finset.mem_inter.mpr ⟨ha, haV⟩
          have key := hstep (A ∩ V) hB a haB
          rw [h1]
  4. When a ∈ V, the challenger sum on A \ {a} is identical to the challenger sum on (A ∩ V) \ {a}.

    Using Finset.sum_congr, we compare the two sums term by term for each challenger i. Since every committee satisfies S(i) ⊆ V (by hS), Finset.subset_inter_iff shows that S(i) ⊆ A \ {a} is logically equivalent to S(i) ⊆ (A ∩ V) \ {a}. A case split on f(i) = a and the subset inclusion shows that each summand evaluates to either w(i) or 0 identically on both sides (using if_pos, if_neg, true_and, false_and, and if_false).

    lines 24–36

    uses Finset.sum_congr, Finset.subset_inter_iff, true_and, if_pos, if_neg, false_and, if_false

          have hsum : (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0)
              = (∑ i, if f i = a ∧ S i ⊆ (A ∩ V).erase a then w i else 0) := by
            apply Finset.sum_congr rfl
            intro i hi
            have hiff : (S i ⊆ A.erase a) ↔ (S i ⊆ (A ∩ V).erase a) := by
              rw [← h1, Finset.subset_inter_iff]
              exact ⟨fun h => ⟨h, hS i⟩, fun h => h.1⟩
            by_cases hfa : f i = a
            · simp only [hfa, true_and]
              by_cases hsub : S i ⊆ A.erase a
              · rw [if_pos hsub, if_pos (hiff.mp hsub)]
              · rw [if_neg hsub, if_neg (fun h => hsub (hiff.mpr h))]
            · simp only [hfa, false_and, if_false]
  5. The step inequality holds in the case a ∈ V.

    Substituting the rewritten challenger sum into the goal, the required inequality matches the core bound obtained from hstep in Step 3.

    lines 37–38

          rw [hsum]
          exact key
  6. When a ∉ V, the challenger sum is identically zero.

    Since every challenger root satisfies f(i) ∈ V (by hf), the condition f(i) = a cannot hold for any index i when a ∉ V. Consequently, every term in the sum is zero, and the sum vanishes by Finset.sum_eq_zero.

    lines 39–43

    uses Finset.sum_eq_zero

        · have hfa : ∀ i, f i ≠ a := fun i h => haV (h ▸ hf i)
          have hsum0 : (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) = 0 := by
            apply Finset.sum_eq_zero
            intro i hi
            simp [hfa i]
  7. The step inequality holds in the case a ∉ V.

    With the sum equal to 0, the inequality reduces to 0 + K((A ∩ V) \ {a}) ≤ K(A ∩ V). Because a ∉ V, the element a cannot belong to A ∩ V, so removing a leaves A ∩ V unchanged by Finset.erase_eq_self. The inequality then simplifies to K(A ∩ V) ≤ K(A ∩ V), which holds trivially.

    lines 44–49

    uses Finset.erase_eq_self

          rw [hsum0, h1]
          have hErase : (A ∩ V).erase a = A ∩ V := by
            rw [Finset.erase_eq_self]
            simp [haV]
          rw [hErase]
          simp
  8. The extended potential of the entire candidate universe equals K(V).

    By definition, H(univ) = K(univ ∩ V). Since the intersection of the universal set with V is simply V, the equation simplifies immediately to K(V) = K(V).

    line 50

      · simp
Finset.erase_inter
Erasing an element from a set before taking the intersection with another set is equal to taking the intersection and then erasing the element: (s \ {a}) ∩ t = (s ∩ t) \ {a}.
Finset.inter_subset_right
The intersection of two sets is a subset of the second set: s₁ ∩ s₂ ⊆ s₂.
Finset.mem_inter.mpr
If an element belongs to s and to t, then it belongs to s ∩ t.
Finset.sum_congr
Two finite sums are equal if their index sets are identical and their terms agree at each index.
Finset.subset_inter_iff
A set s is a subset of an intersection t ∩ u if and only if s ⊆ t and s ⊆ u.
true_and
The proposition True ∧ p simplifies to p.
if_pos
If a condition c holds, then the conditional expression if c then t else e evaluates to t.
if_neg
If a condition c does not hold, then the conditional expression if c then t else e evaluates to e.
false_and
The proposition False ∧ p simplifies to False.
if_false
A conditional expression if False then t else e simplifies to e.
Finset.sum_eq_zero
A sum over a finite set is zero if every term in the sum is zero.
Finset.erase_eq_self
Erasing an element a from a set s yields s if and only if a ∉ s.

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 BigOperatorstheorem condorcet_subset_potential_extend_from_closed_core    (C I : Type*) [Fintype C] [DecidableEq C] [Fintype I]    (V : Finset C) (S : I → Finset C) (f : I → C) (w : I → ℕ)    (hS : ∀ i, S i ⊆ V) (hf : ∀ i, f i ∈ V)    (K : Finset C → ℕ)    (hstep : ∀ A : Finset C, A ⊆ V → ∀ a ∈ A,      (∑ i, if f i=a ∧ S i ⊆ A.erase a then w i else 0)+K (A.erase a) ≤ K A) :    let H := fun A : Finset C => K (A ∩ V)    (∀ A : Finset C, ∀ a ∈ A,      (∑ i, if f i=a ∧ S i ⊆ A.erase a then w i else 0)+H (A.erase a) ≤ H A) ∧    H Finset.univ = K V := by  dsimp only  constructor  · intro A a ha    have h1 : (A.erase a) ∩ V = (A ∩ V).erase a := Finset.erase_inter a A V    by_cases haV : a ∈ V    · have hB : A ∩ V ⊆ V := Finset.inter_subset_right      have haB : a ∈ A ∩ V := Finset.mem_inter.mpr ⟨ha, haV⟩      have key := hstep (A ∩ V) hB a haB      rw [h1]      have hsum : (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0)          = (∑ i, if f i = a ∧ S i ⊆ (A ∩ V).erase a then w i else 0) := by        apply Finset.sum_congr rfl        intro i hi        have hiff : (S i ⊆ A.erase a) ↔ (S i ⊆ (A ∩ V).erase a) := by          rw [← h1, Finset.subset_inter_iff]          exact ⟨fun h => ⟨h, hS i⟩, fun h => h.1⟩        by_cases hfa : f i = a        · simp only [hfa, true_and]          by_cases hsub : S i ⊆ A.erase a          · rw [if_pos hsub, if_pos (hiff.mp hsub)]          · rw [if_neg hsub, if_neg (fun h => hsub (hiff.mpr h))]        · simp only [hfa, false_and, if_false]      rw [hsum]      exact key    · have hfa : ∀ i, f i ≠ a := fun i h => haV (h ▸ hf i)      have hsum0 : (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) = 0 := by        apply Finset.sum_eq_zero        intro i hi        simp [hfa i]      rw [hsum0, h1]      have hErase : (A ∩ V).erase a = A ∩ V := by        rw [Finset.erase_eq_self]        simp [haV]      rw [hErase]      simp  · simp
See it in the graphDiscuss this resultChallenge it