condorcet_dimension_le_three_iff_acyclic_cover_potential_break
The original universal strict Condorcet winning-set bound of three is equivalent to this assertion: for every finite relation with an outside common predecessor for every set of at most three vertices, every positive finite family U of induced acyclic subsets, and every real vertex potential h, some arrow a to b satisfies 2 times the number of members of U containing a plus h(a) strictly less than the size of the family plus h(b). This is an equivalent reformulation and proves neither side.
Statement
theorem condorcet_dimension_le_three_iff_acyclic_cover_potential_break : (∀ (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)), 0 < n → ∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S) ↔ (∀ (m n : ℕ) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (h : Fin m → ℝ), 0 < n → (∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) → (∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) → ∃ a b, R a b ∧ 2 * ((univ.filter fun v => a ∈ U v).card : ℝ) + h a < (n : ℝ) + h b)
- Source
- IN-380, OP-19 campaign session 8, 2026-10-30. Self-contained helper for the strict-half acyclic-separation route. The general unrestricted one-child equality was refuted in IN-372; this work repairs only the strict-half existence reduction. Standard finite matching, rational density, and circulation weak duality are used. No new election bound or research novelty is claimed. See lean/AFTD/Scratch/In380Oct30/HalfThresholdDerivation.txt.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- condorcet_strict_half_separator_excludes_cover_potentialLet a finite directed relation have a nonnegative real strict-half separator. For every positive number n of induced acyclic vertex…
- condorcet_dimension_le_three_iff_acyclic_weight_separationThe following two universal statements are equivalent. First, every finite election with a positive number of voters and strict rankings…
- is_condorcet_winning_setWith n voters holding strict rankings of m candidates, S is a Condorcet winning set if for every candidate a ∉ S, strictly fewer than n/2…
The proof, explained
The equivalence between the Condorcet winning-set bound of three and the acyclic cover potential-break condition is established by routing both sides through an intermediate characterization: the existence of a non-negative vertex weighting strictly separating all acyclic sets from half the total weight. In the forward direction, the Condorcet bound provides such a separating weight, from which a prior exclusion lemma produces the desired edge breaking the cover-potential inequality. In the reverse direction, linear programming duality equates the separating weight to the non-existence of an acyclic half-cover, and specializing the potential-break hypothesis to the zero potential immediately refutes any such half-cover.
The equivalence reduces to proving the forward and reverse implications separately.
We work in classical logic and split the biconditional into two separate implications: the forward direction (the Condorcet bound implies the potential-break condition) and the reverse direction.
classical constructorThe universal Condorcet winning set bound implies the acyclic cover potential-break condition.
Assume the Condorcet winning set bound of size at most 3 (`hmain`), a relation R with the 3-predecessor property (`hroot`), a family of n > 0 acyclic sets U, and a potential h. By `condorcet_dimension_le_three_iff_acyclic_weight_separation.mp`, `hmain` guarantees a non-negative vertex weighting w strictly separating every acyclic subset from having at least half the total weight. Applying `condorcet_strict_half_separator_excludes_cover_potential` to this separator w yields an edge a → b satisfying 2 * |{v | a ∈ U v}| + h(a) < n + h(b).
uses
condorcet_strict_half_separator_excludes_cover_potential,condorcet_dimension_le_three_iff_acyclic_weight_separation.mp· intro hmain m n R U h hn hroot hU exact condorcet_strict_half_separator_excludes_cover_potential m n hn R U h hU (condorcet_dimension_le_three_iff_acyclic_weight_separation.mp hmain m R hroot)
To deduce the Condorcet bound from the potential-break hypothesis, it suffices to derive a contradiction from the existence of an acyclic half-cover.
Assume the potential-break condition (`hbreak`). By `condorcet_dimension_le_three_iff_acyclic_weight_separation.mpr`, it suffices to construct a strict half-weight separator for any relation R with the 3-predecessor property (`hroot`). By linear programming duality (`condorcet_half_cover_acyclic_half_cover_duality`), such a separator exists if and only if there is no family U of n > 0 acyclic sets covering every vertex at least n/2 times. We assume for contradiction that such an acyclic half-cover exists.
uses
condorcet_dimension_le_three_iff_acyclic_weight_separation.mpr,condorcet_half_cover_acyclic_half_cover_duality· intro hbreak apply condorcet_dimension_le_three_iff_acyclic_weight_separation.mpr intro m R hroot apply (condorcet_half_cover_acyclic_half_cover_duality m R).mp rintro ⟨n,U,hn,hU,hhalf⟩
Evaluating the potential-break hypothesis at the zero potential contradicts the half-cover property.
We instantiate the potential-break hypothesis `hbreak` with the assumed acyclic half-cover U and the identically zero potential h(x) = 0. This provides vertices a, b with R(a, b) such that 2 * |{v | a ∈ U v}| + 0 < n + 0. Simplifying the zeros via `add_zero` gives 2 * |{v | a ∈ U v}| < n. However, because U is a half-cover, vertex a satisfies n ≤ 2 * |{v | a ∈ U v}|. By `not_lt_of_ge`, these two inequalities contradict each other, completing the proof.
uses
add_zero,not_lt_of_geobtain ⟨a,b,hab,hlt⟩ := hbreak m n R U (fun _ => 0) hn hroot hU have hle : (n : ℝ) ≤ 2 * ((univ.filter fun v => a ∈ U v).card : ℝ) := by exact_mod_cast hhalf a simp only [add_zero] at hlt exact (not_lt_of_ge hle) hlt
condorcet_strict_half_separator_excludes_cover_potential- Given a non-negative vertex weighting strictly separating all acyclic subsets from half the total weight, any finite family of acyclic subsets and any vertex potential admit an edge along which twice the number of covering sets plus the potential difference is strictly less than the family size.
condorcet_dimension_le_three_iff_acyclic_weight_separation.mp- If every election profile has a Condorcet winning set of size at most 3, then every relation with the 3-predecessor property admits a non-negative vertex weighting under which every acyclic subset has strictly less than half the total weight.
condorcet_dimension_le_three_iff_acyclic_weight_separation.mpr- If every relation with the 3-predecessor property admits a non-negative vertex weighting under which every acyclic subset has strictly less than half the total weight, then every election profile has a Condorcet winning set of size at most 3.
condorcet_half_cover_acyclic_half_cover_duality- By linear programming duality, a relation admits a non-negative vertex weighting strictly separating all acyclic subsets from half the total weight if and only if there does not exist a finite family of acyclic subsets covering each vertex at least half the time.
add_zero- Adding zero to any element leaves it unchanged (a + 0 = a).
not_lt_of_ge- If a ≤ b, then b < a cannot hold.
- The reverse implication only requires the special case of the potential-break hypothesis where the potential function h is identically zero; the full strength of arbitrary potentials is only used in the forward implication.
- The cast from natural numbers to real numbers in the half-cover inequality (line 27) is handled formally by exact_mod_cast.
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_dimension_le_three_iff_acyclic_cover_potential_break : (∀ (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)), 0 < n → ∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S) ↔ (∀ (m n : ℕ) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (h : Fin m → ℝ), 0 < n → (∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) → (∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) → ∃ a b, R a b ∧ 2 * ((univ.filter fun v => a ∈ U v).card : ℝ) + h a < (n : ℝ) + h b) := by classical constructor · intro hmain m n R U h hn hroot hU exact condorcet_strict_half_separator_excludes_cover_potential m n hn R U h hU (condorcet_dimension_le_three_iff_acyclic_weight_separation.mp hmain m R hroot) · intro hbreak apply condorcet_dimension_le_three_iff_acyclic_weight_separation.mpr intro m R hroot apply (condorcet_half_cover_acyclic_half_cover_duality m R).mp rintro ⟨n,U,hn,hU,hhalf⟩ obtain ⟨a,b,hab,hlt⟩ := hbreak m n R U (fun _ => 0) hn hroot hU have hle : (n : ℝ) ≤ 2 * ((univ.filter fun v => a ∈ U v).card : ℝ) := by exact_mod_cast hhalf a simp only [add_zero] at hlt exact (not_lt_of_ge hle) hlt