AFTD Auto-Formalizing Theoretical Domains

condorcet_acyclic_cover_rank_saturation

theoremverified

For any finite relation with the outside common predecessor property for sets of at most k vertices and any finite acyclic cover family, there are injective natural-number rankings such that the rank-compatible relation contains every nonloop original arrow and retains the k-predecessor property on the same vertices. Memberships and their multiplicities are unchanged.

Statement

theorem condorcet_acyclic_cover_rank_saturation
    (m n k : ℕ) (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)) :
    ∃ p : Fin n → Fin m → ℕ,
      (∀ v, Function.Injective (p v)) ∧
      (∀ a b, a ≠ b → R a b → condorcet_cover_rank_relation U p a b) ∧
      (∀ J : Finset (Fin m), J.card ≤ k →
        ∃ a, a ∉ J ∧ ∀ b ∈ J, condorcet_cover_rank_relation U p a b)
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 1

The proof, explained

To construct the required ranking functions, we first topologically sort each set in the acyclic cover into a permutation σ_v of the vertices that preserves all original arrows originating in U(v). Defining the rankings p(v, a) as the numerical values of σ_v(a) guarantees injectivity because each σ_v is a permutation. Every non-loop original arrow a → b is preserved in the Condorcet cover rank relation because σ_v(a) < σ_v(b) whenever a ∈ U(v). The k-common predecessor property is retained directly from R, since an outside predecessor a ∉ J cannot equal any element of J and thus forms non-loop edges to every vertex in J.

  1. For each index v, there exists a permutation σ_v of the vertices that orders a before b whenever a ∈ U(v) and R a b holds.

    Working under classical logic, fix an index v. The restriction of R to U(v) is well-founded by assumption hU. By condorcet_acyclic_cover_wellFounded_sources, the relation requiring a ∈ U(v) and R a b is well-founded on the entire vertex set Fin m. Applying condorcet_acyclic_cover_ranking_of_wellFounded produces a permutation σ_v of Fin m topologically sorting this relation, so that σ_v(a) < σ_v(b) whenever a ∈ U(v) and R a b.

    lines 15–22

    uses condorcet_acyclic_cover_ranking_of_wellFounded, condorcet_acyclic_cover_wellFounded_sources

      classical
      have hp : ∀ v, ∃ σ : Equiv.Perm (Fin m),
          ∀ a b, a ∈ U v → R a b → σ a < σ b := by
        intro v
        obtain ⟨σ,hσ⟩ := condorcet_acyclic_cover_ranking_of_wellFounded m
          (fun a b => a ∈ U v ∧ R a b)
          (condorcet_acyclic_cover_wellFounded_sources R {a | a ∈ U v} (hU v))
        exact ⟨σ,fun a b ha hab => hσ a b ⟨ha,hab⟩⟩
  2. Choose a family of permutations σ and define the ranking functions p(v, a) as their underlying natural-number values.

    Applying the axiom of choice (via choose) to the existential statement yields a function σ associating each index v to such a permutation. The ranking function p is then defined by setting p(v, a) to the underlying natural number value (σ(v)(a)).val.

    lines 23–24

      choose σ hσ using hp
      let p : Fin n → Fin m → ℕ := fun v a => (σ v a).val
  3. Every non-loop arrow of R satisfies the Condorcet cover rank relation.

    Suppose a ≠ b and R a b. By definition of condorcet_cover_rank_relation, we must verify that a ≠ b (which is given) and that for any v with a ∈ U(v) and b ∈ U(v), we have p(v)(a) < p(v)(b). Since a ∈ U(v) and R a b, the ordering property of σ(v) gives σ(v)(a) < σ(v)(b), which means p(v)(a) < p(v)(b).

    lines 25–27

      have hR : ∀ a b, a ≠ b → R a b → condorcet_cover_rank_relation U p a b := by
        intro a b hab h
        exact ⟨hab,fun v ha _ => hσ v a b ha h⟩
  4. Instantiate the existential quantifier with p, reducing the goal to proving injectivity and the common predecessor property.

    Using refine, we provide p as the witness and use the established property hR for the non-loop arrows, leaving injectivity of each p(v) and the preservation of the k-predecessor property as the two remaining goals.

    line 28

      refine ⟨p,?_,hR,?_⟩
  5. For each index v, the ranking function p(v) is injective.

    Suppose p(v)(a) = p(v)(b), meaning the natural numbers (σ(v)(a)).val and (σ(v)(b)).val are equal. By Fin.ext, this implies σ(v)(a) = σ(v)(b). Since σ(v) is a permutation, it is injective, yielding a = b.

    lines 29–30

    uses Fin.ext

      · intro v a b hab
        exact (σ v).injective (Fin.ext hab)
  6. The Condorcet cover rank relation satisfies the k-common predecessor property.

    Given any subset J of at most k vertices, hypothesis hroot provides a vertex a ∉ J such that R a b holds for all b ∈ J. Since a ∉ J, a ≠ b for all b ∈ J, so every edge from a to b ∈ J is a non-loop edge of R. By the established embedding hR, a precedes each b ∈ J in the Condorcet cover rank relation.

    lines 31–33

      · intro J hJ
        obtain ⟨a,ha,har⟩ := hroot J hJ
        exact ⟨a,ha,fun b hb => hR a b (fun heq => ha (heq ▸ hb)) (har b hb)⟩
condorcet_acyclic_cover_wellFounded_sources
If a binary relation is well-founded when restricted to a subset U, then the relation that holds when a ∈ U and the relation holds between a and b is well-founded on the entire type.
condorcet_acyclic_cover_ranking_of_wellFounded
Every well-founded relation on Fin m can be topologically sorted into a permutation σ of Fin m such that R a b implies σ a < σ b.
Fin.ext
Two elements of Fin n are equal if their underlying natural-number values are equal.

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_acyclic_cover_rank_saturation    (m n k : ℕ) (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)) :    ∃ p : Fin n → Fin m → ℕ,      (∀ v, Function.Injective (p v)) ∧      (∀ a b, a ≠ b → R a b → condorcet_cover_rank_relation U p a b) ∧      (∀ J : Finset (Fin m), J.card ≤ k →        ∃ a, a ∉ J ∧ ∀ b ∈ J, condorcet_cover_rank_relation U p a b) := by  classical  have hp : ∀ v, ∃ σ : Equiv.Perm (Fin m),      ∀ a b, a ∈ U v → R a b → σ a < σ b := by    intro v    obtain ⟨σ,hσ⟩ := condorcet_acyclic_cover_ranking_of_wellFounded m      (fun a b => a ∈ U v ∧ R a b)      (condorcet_acyclic_cover_wellFounded_sources R {a | a ∈ U v} (hU v))    exact ⟨σ,fun a b ha hab => hσ a b ⟨ha,hab⟩⟩  choose σ hσ using hp  let p : Fin n → Fin m → ℕ := fun v a => (σ v a).val  have hR : ∀ a b, a ≠ b → R a b → condorcet_cover_rank_relation U p a b := by    intro a b hab h    exact ⟨hab,fun v ha _ => hσ v a b ha h⟩  refine ⟨p,?_,hR,?_⟩  · intro v a b hab    exact (σ v).injective (Fin.ext hab)  · intro J hJ    obtain ⟨a,ha,har⟩ := hroot J hJ    exact ⟨a,ha,fun b hb => hR a b (fun heq => ha (heq ▸ hb)) (har b hb)⟩
See it in the graphDiscuss this resultChallenge it