AFTD Auto-Formalizing Theoretical Domains

condorcet_potential_maximum_neighborhood_half_cover

theoremverified

Suppose a finite relation has outside common predecessors for every set of at most k+1 vertices. If n induced acyclic sets and a real potential satisfy n+h(b) <= 2*coverage(a)+h(a) on every arrow a to b, then some finite relation with the k-predecessor property has an acyclic half-cover with the same n sets. The new relation is obtained by restricting to the predecessors of a maximum-potential vertex.

Statement

theorem condorcet_potential_maximum_neighborhood_half_cover
    (m n k : ℕ) (R : Fin m → Fin m → Prop)
    (U : Fin n → Finset (Fin m)) (h : Fin m → ℝ)
    (hroot : ∀ J : Finset (Fin m), J.card ≤ k+1 →
      ∃ 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))
    (hlocal : ∀ a b, R a b →
      (n : ℝ)+h b ≤ 2*((univ.filter fun v => a∈U v).card : ℝ)+h a) :
    ∃ (q : ℕ) (Q : Fin q → Fin q → Prop) (W : Fin n → Finset (Fin q)),
      (∀ J : Finset (Fin q), J.card ≤ k →
        ∃ a, a ∉ J ∧ ∀ b ∈ J, Q a b) ∧
      (∀ v, WellFounded (fun a b : {a : Fin q // a ∈ W v} => Q a.val b.val)) ∧
      (∀ a, n ≤ 2*(univ.filter fun v => a∈W v).card)
Source
IN-383, OP-19 campaign session 9, 2026-10-30. Structural verification of the maximum-potential neighborhood route suggested in IN-380. Generalization of the existing acyclic-cover reduction, whose strict election definition is from Condorcet winning sets, Social Choice and Welfare 44(3):493-517 (2015), https://www.lamsade.dauphine.fr/~lang/papers/els15.pdf . No new election bound or research novelty is claimed.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The theorem is proved by restricting the relation R to the predecessor neighborhood of a vertex b that maximizes the potential h. The root condition on sets of size at most k+1 ensures, via an auxiliary lemma, that this restricted relation inherits the common predecessor property for all sets of size at most k. Well-foundedness on each induced set is preserved under restriction because the new sets are pullbacks of the original acyclic sets. Finally, because b has maximal potential, the local inequality n + h(b) ≤ 2 * coverage(a) + h(a) reduces to n ≤ 2 * coverage(a) for every predecessor a of b, so the restricted sets form an acyclic half-cover.

  1. The potential function h attains its maximum at some vertex b.

    Applying the root hypothesis hroot to the empty set (which has size 0 ≤ k + 1) yields a vertex r ∉ ∅, proving that the vertex set is nonempty. By exists_max_image, the real-valued potential function h attains a maximum on the universe at some vertex b, so h(x) ≤ h(b) for all vertices x.

    lines 19–21

    uses exists_max_image, mem_univ

      classical
      obtain ⟨r,_,_⟩ := hroot ∅ (by simp)
      obtain ⟨b,_,hb⟩ := exists_max_image univ h ⟨r,mem_univ _⟩
  2. We define the new universe of size q, relation Q, and sets W by restricting to the predecessors D of b and identifying D with Fin q.

    Let D be the subtype of vertices preceding b, and let q = |D| be its cardinality. We fix a bijection e : D ≃ Fin q using Fintype.equivFin. The relation Q on Fin q is defined by pulling back R along e⁻¹, and each set W(v) is defined by pulling back U(v) along e⁻¹. We then provide q, Q, and W as witnesses, leaving three conditions to prove: the k-predecessor property, well-foundedness, and the half-cover property.

    lines 22–27

    uses Fintype.equivFin

      let D := {a : Fin m // R a b}
      let q := Fintype.card D
      let e : D ≃ Fin q := Fintype.equivFin D
      let Q : Fin q → Fin q → Prop := fun a c => R (e.symm a).val (e.symm c).val
      let W : Fin n → Finset (Fin q) := fun v => univ.filter (fun a => (e.symm a).val ∈ U v)
      refine ⟨q,Q,W,?_,?_,?_⟩
  3. The restricted relation Q has an outside common predecessor for every set of at most k vertices.

    Given any subset J ⊆ Fin q with |J| ≤ k, its image under e⁻¹ in D also has size at most k by card_image_le. By condorcet_common_predecessor_neighborhood, there exists a vertex a ∈ D outside e⁻¹(J) that precedes every vertex in e⁻¹(J) under R. Its image e(a) ∈ Fin q does not belong to J and precedes every element of J under Q.

    lines 28–38

    uses card_image_le, condorcet_common_predecessor_neighborhood

      · intro J hJ
        have hJ' : (J.image e.symm).card ≤ k := card_image_le.trans hJ
        obtain ⟨a,ha,har⟩ := condorcet_common_predecessor_neighborhood R k hroot b
          (J.image e.symm) hJ'
        refine ⟨e a,?_,?_⟩
        · intro hmem
          exact ha (mem_image.mpr ⟨e a,hmem,e.symm_apply_apply a⟩)
        · intro c hc
          change R (e.symm (e a)).val (e.symm c).val
          rw [e.symm_apply_apply]
          exact har _ (mem_image.mpr ⟨c,hc,rfl⟩)
  4. For each index v, the relation Q restricted to W(v) is well-founded.

    Each element of W(v) corresponds under e⁻¹ to an element of U(v). This defines an embedding f from the subtype of W(v) to the subtype of U(v) such that Q is the inverse image of R under f. Since R restricted to U(v) is well-founded by assumption hU, InvImage.wf guarantees that Q restricted to W(v) is well-founded.

    lines 39–42

    uses InvImage.wf

      · intro v
        let f : {a : Fin q // a ∈ W v} → {a : Fin m // a∈U v} :=
          fun a => ⟨(e.symm a.val).val,(mem_filter.mp a.property).2⟩
        exact InvImage.wf f (hU v)
  5. Every vertex in Fin q is covered by at least n/2 of the sets W(v).

    For any a ∈ Fin q, its representative e⁻¹(a) belongs to D and therefore precedes the maximum-potential vertex b. The local potential condition hlocal yields n + h(b) ≤ 2 * coverage(e⁻¹(a)) + h(e⁻¹(a)). Because b maximizes h, we have h(e⁻¹(a)) ≤ h(b) by mem_univ, which implies n ≤ 2 * coverage(e⁻¹(a)) over ℝ. By definition of W, a ∈ W(v) if and only if e⁻¹(a) ∈ U(v), so the coverage of a by W is equal to the coverage of e⁻¹(a) by U. Casting the inequality to ℕ proves the half-cover bound.

    lines 43–51

    uses mem_univ

      · intro a
        have hle := hlocal (e.symm a).val b (e.symm a).property
        have hmax := hb (e.symm a).val (mem_univ _)
        have hc : (n : ℝ) ≤ 2*((univ.filter fun v => (e.symm a).val ∈ U v).card : ℝ) := by
          linarith
        have heq : (univ.filter fun v => a ∈ W v) =
            (univ.filter fun v => (e.symm a).val ∈ U v) := by simp [W]
        rw [heq]
        exact_mod_cast hc
exists_max_image
A nonempty finite set contains an element maximizing a given function into a linearly ordered type.
mem_univ
Every element of a finite type belongs to its universal set univ.
Fintype.equivFin
Every finite type α is in bijection with Fin (|α|).
card_image_le
The image of a finite set under any function has cardinality at most that of the original set.
condorcet_common_predecessor_neighborhood
If a relation has an outside common predecessor for every set of at most k+1 vertices, then restricting the relation to the predecessors of any fixed vertex yields a relation with an outside common predecessor for every set of at most k vertices.
InvImage.wf
The pullback (inverse image) of a well-founded relation under any function 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 Finsetopen scoped BigOperatorsset_option maxHeartbeats 4000000set_option maxRecDepth 10000theorem condorcet_potential_maximum_neighborhood_half_cover    (m n k : ℕ) (R : Fin m → Fin m → Prop)    (U : Fin n → Finset (Fin m)) (h : Fin m → ℝ)    (hroot : ∀ J : Finset (Fin m), J.card ≤ k+1 →      ∃ 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))    (hlocal : ∀ a b, R a b →      (n : ℝ)+h b ≤ 2*((univ.filter fun v => a∈U v).card : ℝ)+h a) :    ∃ (q : ℕ) (Q : Fin q → Fin q → Prop) (W : Fin n → Finset (Fin q)),      (∀ J : Finset (Fin q), J.card ≤ k →        ∃ a, a ∉ J ∧ ∀ b ∈ J, Q a b) ∧      (∀ v, WellFounded (fun a b : {a : Fin q // a ∈ W v} => Q a.val b.val)) ∧      (∀ a, n ≤ 2*(univ.filter fun v => a∈W v).card) := by  classical  obtain ⟨r,_,_⟩ := hroot ∅ (by simp)  obtain ⟨b,_,hb⟩ := exists_max_image univ h ⟨r,mem_univ _⟩  let D := {a : Fin m // R a b}  let q := Fintype.card D  let e : D ≃ Fin q := Fintype.equivFin D  let Q : Fin q → Fin q → Prop := fun a c => R (e.symm a).val (e.symm c).val  let W : Fin n → Finset (Fin q) := fun v => univ.filter (fun a => (e.symm a).val ∈ U v)  refine ⟨q,Q,W,?_,?_,?_⟩  · intro J hJ    have hJ' : (J.image e.symm).card ≤ k := card_image_le.trans hJ    obtain ⟨a,ha,har⟩ := condorcet_common_predecessor_neighborhood R k hroot b      (J.image e.symm) hJ'    refine ⟨e a,?_,?_⟩    · intro hmem      exact ha (mem_image.mpr ⟨e a,hmem,e.symm_apply_apply a⟩)    · intro c hc      change R (e.symm (e a)).val (e.symm c).val      rw [e.symm_apply_apply]      exact har _ (mem_image.mpr ⟨c,hc,rfl⟩)  · intro v    let f : {a : Fin q // a ∈ W v} → {a : Fin m // a∈U v} :=      fun a => ⟨(e.symm a.val).val,(mem_filter.mp a.property).2⟩    exact InvImage.wf f (hU v)  · intro a    have hle := hlocal (e.symm a).val b (e.symm a).property    have hmax := hb (e.symm a).val (mem_univ _)    have hc : (n : ℝ) ≤ 2*((univ.filter fun v => (e.symm a).val ∈ U v).card : ℝ) := by      linarith    have heq : (univ.filter fun v => a ∈ W v) =        (univ.filter fun v => (e.symm a).val ∈ U v) := by simp [W]    rw [heq]    exact_mod_cast hc
See it in the graphDiscuss this resultChallenge it