condorcet_cover_rank_dominated_vertex_delete
Inside an induced S_k subset B of a rank-compatible relation, a vertex b can be deleted when a distinct vertex a in B is active somewhere, its activity signature is contained in that of b, and its rank is at most that of b on every index where a is active. The remaining induced subset retains S_k.
Statement
theorem condorcet_cover_rank_dominated_vertex_delete
{m n k : ℕ} (U : Fin n → Finset (Fin m))
(p : Fin n → Fin m → ℕ) (B : Finset (Fin m)) (a b : Fin m)
(ha : a ∈ B) (hab : a ≠ b) (hne : ∃ v, a ∈ U v)
(hsub : ∀ v, a ∈ U v → b ∈ U v)
(hle : ∀ v, a ∈ U v → p v a ≤ p v b)
(hroot : ∀ J : Finset (Fin m), J ⊆ B → J.card ≤ k →
∃ r, r ∈ B ∧ r ∉ J ∧ ∀ c ∈ J, condorcet_cover_rank_relation U p r c) :
∀ J : Finset (Fin m), J ⊆ B.erase b → J.card ≤ k →
∃ r, r ∈ B.erase b ∧ r ∉ J ∧
∀ c ∈ J, condorcet_cover_rank_relation U p r c- Source
- IN-391, OP-19 campaign session10, 2026-10-30. General rank-saturation and dominance-deletion route for the acyclic half-cover reformulation. Supporting structural lemmas only; no election bound or research novelty is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- condorcet_cover_rank_relationThe loopless rank-compatible relation: an arrow a to b is permitted precisely when a differs from b and a has a strictly smaller…
- Used by 1
- condorcet_minimal_rank_core_pareto_antichainIn a globally minimum induced S_k subset of a rank-compatible relation, with every vertex active somewhere, distinct vertices a and b with…
The proof, explained
To show that B \ {b} retains the S_k property, consider any subset J ⊆ B \ {b} of size at most k. Because J is also a subset of B, the S_k property of B supplies a root vertex r ∈ B \ J that covers every element of J. If r ≠ b, then r already belongs to B \ {b} and witnesses the property. If r = b, the dominating vertex a cannot be in J, because b covering a would contradict the rank condition p(v, a) ≤ p(v, b) at an index where a is active; vertex a then covers every element of J by transitivity of ranks, serving as the required root in B \ {b}.
Given J ⊆ B \ {b} with |J| ≤ k, there is a root vertex r ∈ B \ J that covers every element of J.
Fix an arbitrary subset J ⊆ B \ {b} with |J| ≤ k. Since B \ {b} ⊆ B (by erase_subset), we have J ⊆ B. The S_k property of B (hroot) then provides a vertex r ∈ B such that r ∉ J and r covers every c ∈ J under the Condorcet cover rank relation.
uses
erase_subsetintro J hJ hcard obtain ⟨r,hrB,hrJ,hr⟩ := hroot J (hJ.trans (erase_subset _ _)) hcard
Split into cases depending on whether r = b or r ≠ b.
We distinguish two cases for the root r found for J: either r is the deleted vertex b, or r is distinct from b.
by_cases hrb : r = bWhen r = b, the dominating vertex a cannot belong to J.
Substituting b for r, suppose for contradiction that a ∈ J. By hypothesis (hne), a is active at some voter/index v. By activity containment (hsub), b is also active at v. Since b covers every element of J, it covers a ∈ J, which means p(v, b) < p(v, a). But the rank domination hypothesis (hle) guarantees p(v, a) ≤ p(v, b), contradicting the strict inequality via not_lt_of_ge. Thus a ∉ J.
uses
not_lt_of_ge· subst r have haJ : a ∉ J := by intro haj obtain ⟨v,hv⟩ := hne have hlt := (hr a haj).2 v (hsub v hv) hv exact (not_lt_of_ge (hle v hv)) hlt
When r = b, the vertex a serves as the covering root for J in B \ {b}.
Since a ∈ B and a ≠ b, a ∈ B \ {b} (by mem_erase.mpr). We already showed a ∉ J. For any c ∈ J, a ≠ c because a ∉ J while c ∈ J. Moreover, for any index v where both a and c are active, b is also active at v by activity containment (hsub). Since b covers c, we have p(v, b) < p(v, c). Combined with p(v, a) ≤ p(v, b) from hle, transitivity (trans_lt) gives p(v, a) < p(v, c). Hence a covers every c ∈ J.
uses
mem_erase.mpr,trans_ltrefine ⟨a,mem_erase.mpr ⟨hab,ha⟩,haJ,?_⟩ intro c hc refine ⟨fun heq => haJ (heq ▸ hc),?_⟩ intro v hav hcv exact (hle v hav).trans_lt ((hr c hc).2 v (hsub v hav) hcv)
When r ≠ b, r itself remains a valid covering root for J in B \ {b}.
Since r ∈ B and r ≠ b, r ∈ B \ {b} (by mem_erase.mpr). Since r ∉ J and r covers every c ∈ J by construction, r directly satisfies all required conditions.
uses
mem_erase.mpr· exact ⟨r,mem_erase.mpr ⟨hrb,hrB⟩,hrJ,hr⟩
erase_subset- Erasing an element from a finite set yields a subset of the original set.
mem_erase.mpr- An element belongs to a finite set with b erased if and only if it is distinct from b and belongs to the original set; here used in the right-to-left direction.
not_lt_of_ge- If a ≤ b, then b < a is false.
trans_lt- If a ≤ b and b < c, then a < c.
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 Finsetset_option maxHeartbeats 4000000theorem condorcet_cover_rank_dominated_vertex_delete {m n k : ℕ} (U : Fin n → Finset (Fin m)) (p : Fin n → Fin m → ℕ) (B : Finset (Fin m)) (a b : Fin m) (ha : a ∈ B) (hab : a ≠ b) (hne : ∃ v, a ∈ U v) (hsub : ∀ v, a ∈ U v → b ∈ U v) (hle : ∀ v, a ∈ U v → p v a ≤ p v b) (hroot : ∀ J : Finset (Fin m), J ⊆ B → J.card ≤ k → ∃ r, r ∈ B ∧ r ∉ J ∧ ∀ c ∈ J, condorcet_cover_rank_relation U p r c) : ∀ J : Finset (Fin m), J ⊆ B.erase b → J.card ≤ k → ∃ r, r ∈ B.erase b ∧ r ∉ J ∧ ∀ c ∈ J, condorcet_cover_rank_relation U p r c := by intro J hJ hcard obtain ⟨r,hrB,hrJ,hr⟩ := hroot J (hJ.trans (erase_subset _ _)) hcard by_cases hrb : r = b · subst r have haJ : a ∉ J := by intro haj obtain ⟨v,hv⟩ := hne have hlt := (hr a haj).2 v (hsub v hv) hv exact (not_lt_of_ge (hle v hv)) hlt refine ⟨a,mem_erase.mpr ⟨hab,ha⟩,haJ,?_⟩ intro c hc refine ⟨fun heq => haJ (heq ▸ hc),?_⟩ intro v hav hcv exact (hle v hav).trans_lt ((hr c hc).2 v (hsub v hav) hcv) · exact ⟨r,mem_erase.mpr ⟨hrb,hrB⟩,hrJ,hr⟩