condorcet_subset_potential_extend_from_closed_core
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.
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).
dsimp only constructor
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.
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
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}).
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]
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).
uses
Finset.sum_congr,Finset.subset_inter_iff,true_and,if_pos,if_neg,false_and,if_falsehave 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]
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.
rw [hsum] exact key
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.
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]
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.
uses
Finset.erase_eq_selfrw [hsum0, h1] have hErase : (A ∩ V).erase a = A ∩ V := by rw [Finset.erase_eq_self] simp [haV] rw [hErase] simp
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).
· 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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