condorcet_nonpositive_potential_acyclic
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
- condorcet_failure_iff_acyclic_half_coverFix a positive number n of voters. There exists a finite election with these n voters in which every candidate set of size at most three…
- Used by 1
- condorcet_heavy_pair_acyclic_cover_potential_breakFor any finite S3 relation, any nonnegative weighted family of induced acyclic sets and real vertex potential has an arrow violating the…
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$.
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)$.
uses
condorcet_acyclic_cover_ranking_of_wellFounded,condorcet_acyclic_cover_wellFounded_sourcesclassical 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)
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`.
uses
Set.finite_rangelet 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
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)$.
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 ?_
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))$.
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)
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.
uses
Prod.Lex.leftby_cases hlt : h b.val < h a.val · apply Prod.Lex.left change -h a.val < -h b.val linarith
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.
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.
- To construct a well-founded order from the real-valued potential, the proof restricts the image of $-h$ to a subtype $L$, whose well-foundedness follows from finiteness rather than properties of the real numbers.
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 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⟩