AFTD Auto-Formalizing Theoretical Domains

condorcet_cover_rank_dominated_vertex_delete

theoremverified

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

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}.

  1. 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.

    lines 15–16

    uses erase_subset

      intro J hJ hcard
      obtain ⟨r,hrB,hrJ,hr⟩ := hroot J (hJ.trans (erase_subset _ _)) hcard
  2. 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.

    line 17

      by_cases hrb : r = b
  3. When 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.

    lines 18–23

    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
  4. 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.

    lines 24–28

    uses mem_erase.mpr, trans_lt

        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)
  5. 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.

    line 29

    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

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⟩
See it in the graphDiscuss this resultChallenge it