condorcet_cover_rank_relation_acyclic
Every activity set induces a well-founded relation in the rank-compatible relation, without any injectivity assumption on the ranks.
Statement
theorem condorcet_cover_rank_relation_acyclic {m n : ℕ} (U : Fin n → Finset (Fin m)) (p : Fin n → Fin m → ℕ) (v : Fin n) : WellFounded (fun a b : {a : Fin m // a ∈ U v} => condorcet_cover_rank_relation U p a.val b.val)
- 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 1
- 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 theorem states that for any voter v, the relation `condorcet_cover_rank_relation` restricted to the active alternatives {a : Fin m // a ∈ U v} is well-founded. The proof works by reducing well-foundedness to the natural well-ordering of ℕ via the rank function a ↦ p v a as a measure. By definition, if alternative a relates to alternative b and both belong to U v, then voter v strictly ranks a below b, so p v a < p v b. Because the relation is a subrelation of the well-founded relation induced by this measure, it is itself well-founded.
To show that the relation is well-founded on the subtype {a : Fin m // a ∈ U v}, it suffices to show that whenever a is related to b, we have p v a < p v b.
We define a measure on the subtype by mapping each active alternative a to its rank p v a in ℕ. By `measure`, this pulls back the standard well-ordering of ℕ to a well-founded relation on the subtype. By monotonicity of well-founded relations, it suffices to prove that the given relation is a subrelation of this measure relation.
uses
measurerefine (measure (fun a : {a : Fin m // a ∈ U v} => p v a.val)).wf.mono ?_
The relation is a subrelation of the rank measure relation: whenever a relates to b, p v a < p v b.
Consider any two alternatives a and b in the subtype {a : Fin m // a ∈ U v}, and assume they satisfy `condorcet_cover_rank_relation`. By definition, this relation requires that for every voter v', if a ∈ U v' and b ∈ U v' then p v' a < p v' b. Specializing this condition to voter v, and using the subtype properties proving that a ∈ U v and b ∈ U v, directly yields p v a < p v b.
intro a b hab exact hab.2 v a.property b.property
measure- Constructs a well-founded relation on a type α by pulling back the standard well-ordering on ℕ along a given function f : α → ℕ.
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_cover_rank_relation_acyclic {m n : ℕ} (U : Fin n → Finset (Fin m)) (p : Fin n → Fin m → ℕ) (v : Fin n) : WellFounded (fun a b : {a : Fin m // a ∈ U v} => condorcet_cover_rank_relation U p a.val b.val) := by refine (measure (fun a : {a : Fin m // a ∈ U v} => p v a.val)).wf.mono ?_ intro a b hab exact hab.2 v a.property b.property