condorcet_acyclic_cover_rank_minimum
For 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 family, injective rankings, and a minimum-cardinality induced S_k subset B in the saturated rank relation. B has more than k vertices and the contained-signature Pareto antichain property. No bound on repeated activity types is asserted.
Statement
theorem condorcet_acyclic_cover_rank_minimum (m n k q : ℕ) (hq : 0 < q) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (hroot : ∀ J : Finset (Fin m), J.card ≤ k → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) (hcover : ∀ a, q ≤ (univ.filter fun v => a ∈ U v).card) : ∃ (V : Fin n → Finset (Fin m)) (p : Fin n → Fin m → ℕ) (B : Finset (Fin m)), (∀ v, V v ⊆ U v) ∧ (∀ a, (univ.filter fun v => a ∈ V v).card = q) ∧ (∀ v, Function.Injective (p v)) ∧ k < B.card ∧ (∀ J : Finset (Fin m), J ⊆ B → J.card ≤ k → ∃ r, r ∈ B ∧ r ∉ J ∧ ∀ c ∈ J, condorcet_cover_rank_relation V p r c) ∧ (∀ C : Finset (Fin m), (∀ J : Finset (Fin m), J ⊆ C → J.card ≤ k → ∃ r, r ∈ C ∧ r ∉ J ∧ ∀ c ∈ J, condorcet_cover_rank_relation V p r c) → B.card ≤ C.card) ∧ (∀ a ∈ B, ∀ b ∈ B, a ≠ b → (∀ v, a ∈ V v → b ∈ V v) → ∃ v, a ∈ V v ∧ p v b < p v a)
- Source
- IN-391, OP-19 campaign session10, 2026-10-30. Supporting lemmas and precisely scoped method diagnostics for the rank-saturated acyclic-cover route. The main election theorem remains open; no new election bound or novelty is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- condorcet_acyclic_cover_uniformizeAn acyclic family covering every vertex at least q times can be trimmed, independently at each vertex, to an acyclic subfamily with…
- condorcet_acyclic_cover_rank_saturationFor any finite relation with the outside common predecessor property for sets of at most k vertices and any finite acyclic cover family,…
- 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…
- 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…
The proof, explained
The proof first trims the covering family U to a subcover V where each vertex is covered exactly q times, and constructs injective rankings p v whose induced Condorcet cover rank relation satisfies the global S_k property. It then defines the family of all induced S_k subsets, which is nonempty because the full universe satisfies the condition, and selects an induced S_k subset B of minimum cardinality. This minimality forces |B| > k, as otherwise B could not provide an external dominating root for itself. Finally, since q > 0 ensures every vertex is active in at least one component, the Pareto antichain theorem for minimal rank cores guarantees that B satisfies the contained-signature Pareto antichain property.
There exists a subcover V ⊆ U covering each vertex exactly q times while preserving acyclicity of each set.
Using classical reasoning and the lemma condorcet_acyclic_cover_uniformize applied to the initial acyclic cover U, we extract a trimmed family V such that V v ⊆ U v for each component v, the restriction of R to each V v remains well-founded, and every vertex a belongs to exactly q sets in V.
uses
condorcet_acyclic_cover_uniformizeclassical obtain ⟨V,hVU,hV,hVc⟩ := condorcet_acyclic_cover_uniformize m n q R U hU hcoverThere exist injective rankings p v on each component whose induced Condorcet cover rank relation satisfies the global S_k property.
Applying condorcet_acyclic_cover_rank_saturation to the uniformized cover V and the assumed root condition hroot yields injective rankings p v : Fin m → ℕ for each v. The resulting Condorcet cover rank relation extends R and ensures that every subset of vertices of size at most k has a common dominating root.
uses
condorcet_acyclic_cover_rank_saturationobtain ⟨p,hp,_,hpr⟩ := condorcet_acyclic_cover_rank_saturation m n k R V hroot hVThe collection F of all induced S_k subsets is nonempty, containing the universal set.
We define a subset B to be good if every subset J ⊆ B with |J| ≤ k has a dominating root r ∈ B \ J in the Condorcet cover rank relation. We collect these subsets into the family F. The full vertex set univ is good by the global S_k property established in the previous step, so univ ∈ F.
uses
mem_univlet good : Finset (Fin m) → Prop := fun B => ∀ J : Finset (Fin m), J ⊆ B → J.card ≤ k → ∃ r, r ∈ B ∧ r ∉ J ∧ ∀ c ∈ J, condorcet_cover_rank_relation V p r c let F := univ.filter good have huniv : (univ : Finset (Fin m)) ∈ F := by refine mem_filter.mpr ⟨mem_univ _,?_⟩ intro J _ hJ obtain ⟨r,hr,hrel⟩ := hpr J hJ exact ⟨r,mem_univ _,hr,hrel⟩
There exists an induced S_k subset B of minimum cardinality.
Because F is a nonempty finite set of subsets, it has an element B that minimizes the cardinality function. Thus B is good, and |B| ≤ |C| for any good subset C.
uses
mem_univobtain ⟨B,hBF,hBmin⟩ := F.exists_min_image Finset.card ⟨univ,huniv⟩ have hB : good B := (mem_filter.mp hBF).2 have hmin : ∀ C : Finset (Fin m), good C → B.card ≤ C.card := fun C hC => hBmin C (mem_filter.mpr ⟨mem_univ _,hC⟩)
The set B has strictly more than k elements.
Suppose, for contradiction, that |B| ≤ k. Since B ⊆ B by subset_refl, the good property of B applied to J = B would yield a dominating root a ∈ B \ B, which is an immediate contradiction.
uses
subset_reflhave hcard : k < B.card := by by_contra! h obtain ⟨a,ha,hanot,_⟩ := hB B (subset_refl _) h exact hanot ha
The triple (V, p, B) satisfies all required properties, including the contained-signature Pareto antichain condition.
We provide V, p, and B as witnesses. All required properties except the Pareto antichain condition have already been established. To complete the proof, condorcet_minimal_rank_core_pareto_antichain reduces the Pareto antichain condition for the minimal good set B to showing that every vertex a ∈ B is active in at least one component V v. Because each vertex belongs to exactly q sets in V and q > 0, the set of indices covering a has strictly positive size and is therefore nonempty, supplying an active component v.
uses
condorcet_minimal_rank_core_pareto_antichainrefine ⟨V,p,B,hVU,hVc,hp,hcard,hB,hmin,?_⟩ apply condorcet_minimal_rank_core_pareto_antichain V p B _ hB hmin intro a _ have hpos : 0 < (univ.filter fun v => a ∈ V v).card := by rw [hVc]; exact hq obtain ⟨v,hv⟩ := card_pos.mp hpos exact ⟨v,(mem_filter.mp hv).2⟩
condorcet_acyclic_cover_uniformize- From an acyclic cover of a finite set where each element is covered at least q times, there exists a subcover where each element is covered exactly q times and each set remains well-founded (acyclic) under the relation.
condorcet_acyclic_cover_rank_saturation- For an S_k relation with an acyclic cover, there exist injective rankings on each component whose induced Condorcet cover rank relation satisfies the S_k property on the full vertex set.
mem_univ- Every element of a finite type belongs to the universal set univ.
subset_refl- Set inclusion is reflexive: every set is a subset of itself (A ⊆ A).
condorcet_minimal_rank_core_pareto_antichain- Any minimum-cardinality induced S_k subset under the Condorcet cover rank relation whose elements are all active in at least one component satisfies the contained-signature Pareto antichain 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 100000000set_option maxRecDepth 30000theorem condorcet_acyclic_cover_rank_minimum (m n k q : ℕ) (hq : 0 < q) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (hroot : ∀ J : Finset (Fin m), J.card ≤ k → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) (hcover : ∀ a, q ≤ (univ.filter fun v => a ∈ U v).card) : ∃ (V : Fin n → Finset (Fin m)) (p : Fin n → Fin m → ℕ) (B : Finset (Fin m)), (∀ v, V v ⊆ U v) ∧ (∀ a, (univ.filter fun v => a ∈ V v).card = q) ∧ (∀ v, Function.Injective (p v)) ∧ k < B.card ∧ (∀ J : Finset (Fin m), J ⊆ B → J.card ≤ k → ∃ r, r ∈ B ∧ r ∉ J ∧ ∀ c ∈ J, condorcet_cover_rank_relation V p r c) ∧ (∀ C : Finset (Fin m), (∀ J : Finset (Fin m), J ⊆ C → J.card ≤ k → ∃ r, r ∈ C ∧ r ∉ J ∧ ∀ c ∈ J, condorcet_cover_rank_relation V p r c) → B.card ≤ C.card) ∧ (∀ a ∈ B, ∀ b ∈ B, a ≠ b → (∀ v, a ∈ V v → b ∈ V v) → ∃ v, a ∈ V v ∧ p v b < p v a) := by classical obtain ⟨V,hVU,hV,hVc⟩ := condorcet_acyclic_cover_uniformize m n q R U hU hcover obtain ⟨p,hp,_,hpr⟩ := condorcet_acyclic_cover_rank_saturation m n k R V hroot hV let good : Finset (Fin m) → Prop := fun B => ∀ J : Finset (Fin m), J ⊆ B → J.card ≤ k → ∃ r, r ∈ B ∧ r ∉ J ∧ ∀ c ∈ J, condorcet_cover_rank_relation V p r c let F := univ.filter good have huniv : (univ : Finset (Fin m)) ∈ F := by refine mem_filter.mpr ⟨mem_univ _,?_⟩ intro J _ hJ obtain ⟨r,hr,hrel⟩ := hpr J hJ exact ⟨r,mem_univ _,hr,hrel⟩ obtain ⟨B,hBF,hBmin⟩ := F.exists_min_image Finset.card ⟨univ,huniv⟩ have hB : good B := (mem_filter.mp hBF).2 have hmin : ∀ C : Finset (Fin m), good C → B.card ≤ C.card := fun C hC => hBmin C (mem_filter.mpr ⟨mem_univ _,hC⟩) have hcard : k < B.card := by by_contra! h obtain ⟨a,ha,hanot,_⟩ := hB B (subset_refl _) h exact hanot ha refine ⟨V,p,B,hVU,hVc,hp,hcard,hB,hmin,?_⟩ apply condorcet_minimal_rank_core_pareto_antichain V p B _ hB hmin intro a _ have hpos : 0 < (univ.filter fun v => a ∈ V v).card := by rw [hVc]; exact hq obtain ⟨v,hv⟩ := card_pos.mp hpos exact ⟨v,(mem_filter.mp hv).2⟩