AFTD Auto-Formalizing Theoretical Domains

condorcet_minimal_rank_core_pareto_antichain

theoremverified

In a globally minimum induced S_k subset of a rank-compatible relation, with every vertex active somewhere, distinct vertices a and b with the activity signature of a contained in that of b must have an active index of a where b is ranked strictly before a. In particular, every same-signature cohort is a Pareto antichain; this supplies no cardinality bound.

Statement

theorem condorcet_minimal_rank_core_pareto_antichain
    {m n k : ℕ} (U : Fin n → Finset (Fin m))
    (p : Fin n → Fin m → ℕ) (B : Finset (Fin m))
    (hactive : ∀ a ∈ B, ∃ v, a ∈ U v)
    (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)
    (hmin : ∀ C : Finset (Fin m),
      (∀ J : Finset (Fin m), J ⊆ C → J.card ≤ k →
        ∃ r, r ∈ C ∧ r ∉ J ∧ ∀ c ∈ J, condorcet_cover_rank_relation U p r c) →
      B.card ≤ C.card) :
    ∀ a ∈ B, ∀ b ∈ B, a ≠ b →
      (∀ v, a ∈ U v → b ∈ U v) →
      ∃ v, a ∈ U v ∧ p v b < p v a
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 2
Used by 2

The proof, explained

The proof proceeds by contradiction. If vertex $a$ weakly rank-dominates $b$ on all coordinates where $a$ is active (and $b$ is active whenever $a$ is), deleting $b$ preserves the $S_k$-covering property by `condorcet_cover_rank_dominated_vertex_delete`. This implies $|B| \le |B \setminus \{b\}|$ by the minimality of $B$, which contradicts the fact that removing an element strictly decreases the set's cardinality.

  1. Assume for contradiction that $a$ weakly rank-dominates $b$ on every coordinate where $a$ is active: $\forall v, a \in U(v) \implies p(v, a) \le p(v, b)$.

    We introduce distinct vertices $a, b \in B$ and the assumption that $b$ is active whenever $a$ is active. Assuming the negation of the conclusion and pushing negations inside the quantifier yields that $p(v, a) \le p(v, b)$ for every index $v$ where $a$ is active.

    lines 17–19

      intro a ha b hb hab hsub
      by_contra h
      push_neg at h
  2. The deleted set $B \setminus \{b\}$ still satisfies the $S_k$-covering property.

    Since $a$ is active at some index, $b$ is active whenever $a$ is, and $a$ weakly dominates $b$ on all those active coordinates, lemma `condorcet_cover_rank_dominated_vertex_delete` guarantees that removing $b$ preserves the property that every subset of size at most $k$ has a covering root in the remaining set.

    lines 20–21

    uses condorcet_cover_rank_dominated_vertex_delete

      have hdelete := condorcet_cover_rank_dominated_vertex_delete U p B a b ha hab
        (hactive a ha) hsub h hroot
  3. The existence of the smaller valid set $B \setminus \{b\}$ contradicts the minimality of $B$.

    By the minimality assumption `hmin`, $|B| \le |B \setminus \{b\}|$ because $B \setminus \{b\}$ satisfies the covering property. However, since $b \in B$, deleting $b$ strictly decreases the cardinality by `card_erase_lt_of_mem`, giving $|B \setminus \{b\}| < |B|$. Linear integer arithmetic (`omega`) detects the contradiction $|B| \le |B \setminus \{b\}| < |B|$.

    lines 22–24

    uses card_erase_lt_of_mem

      have hle := hmin (B.erase b) hdelete
      have hlt := card_erase_lt_of_mem hb
      omega
card_erase_lt_of_mem
Removing an element belonging to a finite set strictly decreases its cardinality: if $a \in s$, then $|s \setminus \{a\}| < |s|$.
condorcet_cover_rank_dominated_vertex_delete
If vertex $a \in B$ is active somewhere, its active indices are included in those of $b$, $a$ weakly dominates $b$ in rank on those indices, and $B$ satisfies the $S_k$-covering property, then the reduced set $B \setminus \{b\}$ also satisfies the $S_k$-covering property.

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_minimal_rank_core_pareto_antichain    {m n k : ℕ} (U : Fin n → Finset (Fin m))    (p : Fin n → Fin m → ℕ) (B : Finset (Fin m))    (hactive : ∀ a ∈ B, ∃ v, a ∈ U v)    (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)    (hmin : ∀ C : Finset (Fin m),      (∀ J : Finset (Fin m), J ⊆ C → J.card ≤ k →        ∃ r, r ∈ C ∧ r ∉ J ∧ ∀ c ∈ J, condorcet_cover_rank_relation U p r c) →      B.card ≤ C.card) :    ∀ a ∈ B, ∀ b ∈ B, a ≠ b →      (∀ v, a ∈ U v → b ∈ U v) →      ∃ v, a ∈ U v ∧ p v b < p v a := by  intro a ha b hb hab hsub  by_contra h  push_neg at h  have hdelete := condorcet_cover_rank_dominated_vertex_delete U p B a b ha hab    (hactive a ha) hsub h hroot  have hle := hmin (B.erase b) hdelete  have hlt := card_erase_lt_of_mem hb  omega
See it in the graphDiscuss this resultChallenge it