AFTD Auto-Formalizing Theoretical Domains

condorcet_cover_rank_relation_acyclic

theoremverified

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.

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

    line 8

    uses measure

      refine (measure (fun a : {a : Fin m // a ∈ U v} => p v a.val)).wf.mono ?_
  2. 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.

    lines 9–10

      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

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