condorcet_minimal_rank_core_pareto_antichain
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
- condorcet_cover_rank_dominated_vertex_deleteInside 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,…
- 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 2
- condorcet_critical_rank_core_source_exchangeFor positive k and n=k+q, a nonempty induced S_k subset of a rank relation whose vertices all have q active indices and satisfy the…
- condorcet_acyclic_cover_rank_minimumFor positive q, every finite S_k relation with an n-set acyclic family covering every vertex at least q times yields a trimmed exactly-q…
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.
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.
intro a ha b hb hab hsub by_contra h push_neg at h
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.
uses
condorcet_cover_rank_dominated_vertex_deletehave hdelete := condorcet_cover_rank_dominated_vertex_delete U p B a b ha hab (hactive a ha) hsub h hrootThe 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|$.
uses
card_erase_lt_of_memhave 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
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_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