AFTD Auto-Formalizing Theoretical Domains

condorcet_nonpositive_potential_acyclic

theoremverified

On a finite directed relation, a vertex set with nonpositive costs is acyclic if a potential drops along arrows by at least the source cost and every zero-cost vertex of the set lies in one induced acyclic set.

Statement

theorem condorcet_nonpositive_potential_acyclic
    (m : ℕ) (R : Fin m → Fin m → Prop) (A B : Finset (Fin m))
    (c h : Fin m → ℝ)
    (hc : ∀ a ∈ A, c a ≤ 0)
    (hzero : ∀ a ∈ A, c a = 0 → a ∈ B)
    (hlocal : ∀ a b, a ∈ A → b ∈ A → R a b → h b ≤ h a + c a)
    (hB : WellFounded (fun a b : {a : Fin m // a ∈ B} => R a.val b.val)) :
    WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val)
Source
IN-380, OP-19 campaign session8, 2026-10-30. FourCoverPotential.lean. Structural support constraint on the new equivalent main route. 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 embedding the vertex set $A$ into the well-founded lexicographic order $L \\times \\mathbb{N}$, where $L$ is the finite set of negated potential values $\\{-h(a)\\}$ and the second component is a topological ranking $\\sigma$ of edges originating in $B$. Along any edge $a \\to b$ in $A$, the local inequality $h(b) \\le h(a) + c(a)$ with $c(a) \\le 0$ guarantees that either the potential strictly decreases, which strictly increases the first component $-h$, or the potential is constant and $c(a) = 0$. In the latter case, the zero-cost hypothesis forces $a \\in B$, so the edge originates in $B$ and strictly increases the second component under $\\sigma$.

  1. There exists a ranking permutation $\\sigma$ of $\\mathrm{Fin}\\ m$ that increases along every edge whose source lies in $B$.

    Because $R$ restricted to $B$ is well-founded (`hB`), `condorcet_acyclic_cover_wellFounded_sources` implies that the relation consisting of all arrows with source in $B$ is well-founded on the whole set $\\mathrm{Fin}\\ m$. Then `condorcet_acyclic_cover_ranking_of_wellFounded` embeds this acyclic relation into a strict topological ranking $\\sigma$, ensuring $\\sigma(a) < \\sigma(b)$ whenever $a \\in B$ and $R(a, b)$.

    lines 14–17

    uses condorcet_acyclic_cover_ranking_of_wellFounded, condorcet_acyclic_cover_wellFounded_sources

      classical
      obtain ⟨σ,hσ⟩ := condorcet_acyclic_cover_ranking_of_wellFounded m
        (fun a b => a ∈ B ∧ R a b)
        (condorcet_acyclic_cover_wellFounded_sources R {a | a ∈ B} hB)
  2. The finite set $L$ of negated potential values taken by $-h$ is well-founded under $<$.

    The set $L$ is defined as the range of $-h : \\mathrm{Fin}\\ m \\to \\mathbb{R}$. Since $\\mathrm{Fin}\\ m$ is finite, this range is a finite subset of $\\mathbb{R}$ by `Set.finite_range`. Any finite subset of a linearly ordered type is well-founded under the strict order $<$, yielding well-foundedness `hwf`.

    lines 18–20

    uses Set.finite_range

      let L := {x : ℝ // x ∈ Set.range (fun a => -h a)}
      have hwf : WellFounded (fun x y : L => x.val < y.val) :=
        (Set.finite_range (fun a => -h a)).wellFoundedOn
  3. It suffices to show that every edge $a \\to b$ between vertices in $A$ strictly increases their rank in the lexicographical product $L \\times \\mathbb{N}$.

    Each vertex $a \\in A$ is assigned the rank $\\mathrm{rank}(a) = (-h(a), \\sigma(a)) \\in L \\times \\mathbb{N}$. The lexicographic product of two well-founded relations is well-founded, and pulling it back along $\\mathrm{rank}$ gives a well-founded relation on $A$. By monotonicity of well-foundedness, it suffices to prove that $R(a, b)$ implies $\\mathrm{rank}(a) <_{\\mathrm{lex}} \\mathrm{rank}(b)$.

    lines 21–23

      let q : Fin m → L := fun a => ⟨-h a,⟨a,rfl⟩⟩
      let rank : {a : Fin m // a ∈ A} → L × ℕ := fun a => (q a.val,(σ a.val).val)
      refine ((hwf.prod_lex Nat.lt_wfRel.wf).onFun (f := rank)).mono ?_
  4. For any edge $a \\to b$ in $A$, the goal reduces to showing $(-h(a), \\sigma(a)) <_{\\mathrm{lex}} (-h(b), \\sigma(b))$.

    Assume $a, b \\in A$ with $R(a, b)$. By `hlocal`, the potential drops by at least the cost: $h(b) \\le h(a) + c(a)$. By `hc`, the cost is nonpositive: $c(a) \\le 0$. The goal is unfolded to the lexicographic comparison of $(q(a), \\sigma(a))$ and $(q(b), \\sigma(b))$.

    lines 24–28

      intro a b hab
      have hle := hlocal a b a.property b.property hab
      have hc₀ := hc a a.property
      change Prod.Lex (fun x y : L => x.val < y.val) (fun x y : ℕ => x < y)
        (q a.val,(σ a.val).val) (q b.val,(σ b.val).val)
  5. If the potential strictly decreases along the arrow ($h(b) < h(a)$), the lexicographic rank strictly increases.

    Assuming $h(b) < h(a)$, negating both sides gives $-h(a) < -h(b)$ by linear arithmetic. Because the first component strictly increases, `Prod.Lex.left` establishes the lexicographic inequality.

    lines 29–32

    uses Prod.Lex.left

      by_cases hlt : h b.val < h a.val
      · apply Prod.Lex.left
        change -h a.val < -h b.val
        linarith
  6. If the potential does not strictly decrease, the cost is zero, so $a \\in B$ and the second component strictly increases under $\\sigma$.

    In the complementary case where $\\neg(h(b) < h(a))$, we have $h(b) \\ge h(a)$. Together with $h(b) \\le h(a) + c(a)$ and $c(a) \\le 0$, linear arithmetic forces both $h(a) = h(b)$ and $c(a) = 0$. Since $h(a) = h(b)$, the first components are equal ($q(a) = q(b)$ by `Subtype.ext`). By `Prod.Lex.right`, it suffices to show $\\sigma(a) < \\sigma(b)$. Since $a \\in A$ and $c(a) = 0$, hypothesis `hzero` places $a$ in $B$. Because $a \\in B$ and $R(a, b)$, the ranking property `hσ` guarantees $\\sigma(a) < \\sigma(b)$, completing the proof.

    lines 33–41

    uses Subtype.ext, Prod.Lex.right

      · have heq : h a.val = h b.val := by linarith
        have hca : c a.val = 0 := by linarith
        have hq : q a.val = q b.val := by
          apply Subtype.ext
          change -h a.val = -h b.val
          rw [heq]
        rw [hq]
        apply Prod.Lex.right
        exact hσ a b ⟨hzero a a.property hca,hab⟩
condorcet_acyclic_cover_ranking_of_wellFounded
Any well-founded relation on a finite set $\\mathrm{Fin}\\ m$ admits a strict topological ranking permutation $\\sigma$ such that $R(a, b) \\implies \\sigma(a) < \\sigma(b)$.
condorcet_acyclic_cover_wellFounded_sources
If a relation $R$ is well-founded when restricted to a subset $U$, then the relation consisting of edges whose source lies in $U$ is well-founded on the entire vertex set.
Set.finite_range
The range of a function defined on a finite domain is a finite set.
Prod.Lex.left
In a lexicographic product relation, a strict inequality in the first component implies strict inequality for the pair.
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal.
Prod.Lex.right
In a lexicographic product relation, if the first components are equal, a strict inequality in the second component implies strict inequality for the pair.

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_nonpositive_potential_acyclic    (m : ℕ) (R : Fin m → Fin m → Prop) (A B : Finset (Fin m))    (c h : Fin m → ℝ)    (hc : ∀ a ∈ A, c a ≤ 0)    (hzero : ∀ a ∈ A, c a = 0 → a ∈ B)    (hlocal : ∀ a b, a ∈ A → b ∈ A → R a b → h b ≤ h a + c a)    (hB : WellFounded (fun a b : {a : Fin m // a ∈ B} => R a.val b.val)) :    WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) := by  classical  obtain ⟨σ,hσ⟩ := condorcet_acyclic_cover_ranking_of_wellFounded m    (fun a b => a ∈ B ∧ R a b)    (condorcet_acyclic_cover_wellFounded_sources R {a | a ∈ B} hB)  let L := {x : ℝ // x ∈ Set.range (fun a => -h a)}  have hwf : WellFounded (fun x y : L => x.val < y.val) :=    (Set.finite_range (fun a => -h a)).wellFoundedOn  let q : Fin m → L := fun a => ⟨-h a,⟨a,rfl⟩⟩  let rank : {a : Fin m // a ∈ A} → L × ℕ := fun a => (q a.val,(σ a.val).val)  refine ((hwf.prod_lex Nat.lt_wfRel.wf).onFun (f := rank)).mono ?_  intro a b hab  have hle := hlocal a b a.property b.property hab  have hc₀ := hc a a.property  change Prod.Lex (fun x y : L => x.val < y.val) (fun x y : ℕ => x < y)    (q a.val,(σ a.val).val) (q b.val,(σ b.val).val)  by_cases hlt : h b.val < h a.val  · apply Prod.Lex.left    change -h a.val < -h b.val    linarith  · have heq : h a.val = h b.val := by linarith    have hca : c a.val = 0 := by linarith    have hq : q a.val = q b.val := by      apply Subtype.ext      change -h a.val = -h b.val      rw [heq]    rw [hq]    apply Prod.Lex.right    exact hσ a b ⟨hzero a a.property hca,hab⟩
See it in the graphDiscuss this resultChallenge it