AFTD Auto-Formalizing Theoretical Domains

condorcet_acyclic_cover_uniformize

theoremverified

An acyclic family covering every vertex at least q times can be trimmed, independently at each vertex, to an acyclic subfamily with exactly q memberships per vertex. The relation is unchanged.

Statement

theorem condorcet_acyclic_cover_uniformize
    (m n q : ℕ) (R : Fin m → Fin m → Prop)
    (U : Fin n → Finset (Fin m))
    (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),
      (∀ v, V v ⊆ U v) ∧
      (∀ v, WellFounded (fun a b : {a : Fin m // a ∈ V v} => R a.val b.val)) ∧
      (∀ a, (univ.filter fun v => a ∈ V v).card = q)
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 1
Used by 1

The proof, explained

The proof proceeds by dualizing the incidence between elements and sets. By the covering hypothesis and the axiom of choice, each element a is assigned a set S(a) of exactly q indices v for which a ∈ U v. Defining the subfamily by V v = {a | v ∈ S(a)} guarantees that each element belongs to exactly q sets in V, and that V v ⊆ U v. Finally, the well-foundedness of R on each V v is inherited from U v via the canonical subtype inclusion.

  1. For each element a, there exists a set of indices S(a) of size q such that a ∈ U v for all v ∈ S(a).

    By hypothesis `hcover`, the set of indices v such that a ∈ U v has cardinality at least q. Applying `exists_subset_card_eq`, every finite set of size at least q contains a subset of size exactly q. Using the axiom of choice (`choose`), we select a function S associating to each element a such a subset S(a) with cardinality q.

    lines 14–19

    uses exists_subset_card_eq

      classical
      have hex : ∀ a : Fin m, ∃ S : Finset (Fin n),
          S ⊆ univ.filter (fun v => a ∈ U v) ∧ S.card = q := by
        intro a
        exact exists_subset_card_eq (hcover a)
      choose S hsub hcard using hex
  2. Defining V v = {a | v ∈ S(a)}, every set V v is a subset of U v.

    We define the family V by transposing membership: a ∈ V v if and only if v ∈ S(a). If a ∈ V v, then v ∈ S(a) ⊆ {w | a ∈ U w}, which means a ∈ U v. Thus V v ⊆ U v for every index v.

    lines 20–23

      let V : Fin n → Finset (Fin m) := fun v => univ.filter fun a => v ∈ S a
      have hVU : ∀ v, V v ⊆ U v := by
        intro v a ha
        exact (mem_filter.mp (hsub a (mem_filter.mp ha).2)).2
  3. The relation R restricted to each V v is well-founded.

    We instantiate the existential witness with the family V and supply the inclusion proof V v ⊆ U v. For each v, the canonical inclusion map from {a // a ∈ V v} to {a // a ∈ U v} pulls back the relation R on U v to the relation R on V v. Since the relation on U v is well-founded by `hU v`, `InvImage.wf` implies that the restricted relation on V v is also well-founded.

    lines 24–27

    uses InvImage.wf

      refine ⟨V,hVU,?_,?_⟩
      · intro v
        exact InvImage.wf (fun a : {a : Fin m // a ∈ V v} =>
          (⟨a.val,hVU v a.property⟩ : {a : Fin m // a ∈ U v})) (hU v)
  4. For every element a, the number of sets V v containing a is exactly q.

    By definition of V, an element a belongs to V v if and only if v ∈ S(a), so {v | a ∈ V v} is identical to S(a). Since S(a) was chosen to have cardinality q, rewriting with this equality shows that #{v | a ∈ V v} = q, which completes the proof.

    lines 28–32

      · intro a
        have heq : univ.filter (fun v => a ∈ V v) = S a := by
          ext v
          simp [V]
        rw [heq,hcard]
exists_subset_card_eq
A finite set with cardinality at least q contains a subset with cardinality exactly q.
InvImage.wf
The inverse image (pullback) of a well-founded relation under any mapping is well-founded.

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_uniformize    (m n q : ℕ) (R : Fin m → Fin m → Prop)    (U : Fin n → Finset (Fin m))    (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),      (∀ v, V v ⊆ U v) ∧      (∀ v, WellFounded (fun a b : {a : Fin m // a ∈ V v} => R a.val b.val)) ∧      (∀ a, (univ.filter fun v => a ∈ V v).card = q) := by  classical  have hex : ∀ a : Fin m, ∃ S : Finset (Fin n),      S ⊆ univ.filter (fun v => a ∈ U v) ∧ S.card = q := by    intro a    exact exists_subset_card_eq (hcover a)  choose S hsub hcard using hex  let V : Fin n → Finset (Fin m) := fun v => univ.filter fun a => v ∈ S a  have hVU : ∀ v, V v ⊆ U v := by    intro v a ha    exact (mem_filter.mp (hsub a (mem_filter.mp ha).2)).2  refine ⟨V,hVU,?_,?_⟩  · intro v    exact InvImage.wf (fun a : {a : Fin m // a ∈ V v} =>      (⟨a.val,hVU v a.property⟩ : {a : Fin m // a ∈ U v})) (hU v)  · intro a    have heq : univ.filter (fun v => a ∈ V v) = S a := by      ext v      simp [V]    rw [heq,hcard]
See it in the graphDiscuss this resultChallenge it