AFTD Auto-Formalizing Theoretical Domains

condorcet_acyclic_cover_rank_minimum

theoremverified

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

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.

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

    lines 27–28

    uses condorcet_acyclic_cover_uniformize

      classical
      obtain ⟨V,hVU,hV,hVc⟩ := condorcet_acyclic_cover_uniformize m n q R U hU hcover
  2. There 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.

    line 29

    uses condorcet_acyclic_cover_rank_saturation

      obtain ⟨p,hp,_,hpr⟩ := condorcet_acyclic_cover_rank_saturation m n k R V hroot hV
  3. The 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.

    lines 30–38

    uses mem_univ

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

    lines 39–42

    uses mem_univ

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

    lines 43–46

    uses subset_refl

      have hcard : k < B.card := by
        by_contra! h
        obtain ⟨a,ha,hanot,_⟩ := hB B (subset_refl _) h
        exact hanot ha
  6. 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.

    lines 47–52

    uses condorcet_minimal_rank_core_pareto_antichain

      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⟩
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

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