condorcet_acyclic_cover_rank_saturation
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
- 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…
- condorcet_failure_iff_acyclic_half_coverFix a positive number n of voters. There exists a finite election with these n voters in which every candidate set of size at most three…
- Used by 1
- 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
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.
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.
uses
condorcet_acyclic_cover_ranking_of_wellFounded,condorcet_acyclic_cover_wellFounded_sourcesclassical 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 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.
choose σ hσ using hp let p : Fin n → Fin m → ℕ := fun v a => (σ v a).val
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).
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⟩
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.
refine ⟨p,?_,hR,?_⟩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.
uses
Fin.ext· intro v a b hab exact (σ v).injective (Fin.ext hab)
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.
· 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
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_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)⟩