condorcet_reciprocal_connected_acyclic_weight_separation
For any finite directed relation in which every vertex set of size at most two has an outside common predecessor, if the undirected graph of reciprocal arrows is connected, there exist nonnegative real weights putting every induced acyclic subset strictly below half the total. Consequently an S3 relation violating the main weight-separation conjecture must have disconnected reciprocal graph. Oriented relations are not covered. There is no bound on the vertex count.
Statement
theorem condorcet_reciprocal_connected_acyclic_weight_separation (m : ℕ) (R : Fin m → Fin m → Prop) (hpred : ∀ J : Finset (Fin m), J.card ≤ 2 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) (hconn : ∀ a b, Relation.ReflTransGen (fun x y => R x y ∧ R y x) a b) : ∃ w : Fin m → ℝ, (∀ a, 0 ≤ w a) ∧ ∀ A : Finset (Fin m), WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) → 2 * (∑ a ∈ A, w a) < ∑ a, w a
- Source
- IN-362 structural reduction for OP-19. Standard complementary-coalition propagation combined with the established finite acyclic-cover duality. No new universal election bound or research advance. Background LP: https://dmtcs.episciences.org/6020/pdf .
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- condorcet_half_coalitions_partition_of_incompatibleFor two incompatible voter events in a finite electorate, if each has at least half of the voter support, the electorate size is even, the…
- 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…
The proof, explained
By linear programming duality, the existence of a nonnegative weight vector putting every acyclic subset strictly below half the total weight is equivalent to the nonexistence of an acyclic half-cover. To rule out such a half-cover, we observe that two vertices connected by a reciprocal edge cannot both belong to an acyclic set, so half-cover arithmetic forces each coalition to contain exactly one of them. Connectedness of the reciprocal graph propagates this complementation property globally, implying that two coalitions containing the endpoints of an edge cover the entire vertex set. Finally, taking minimal elements in these two coalitions and finding an outside common predecessor for the resulting pair of vertices yields a contradiction to minimality.
Assume for contradiction that an acyclic half-cover exists.
We assume for contradiction (intro hhalf) that there is a family of n > 0 acyclic subsets U(v) covering every vertex a at least n/2 times, that is, n ≤ 2 * |{v | a ∈ U(v)}|.
classical intro hhalfFor any reciprocal edge between a and b, every coalition U(v) contains exactly one of a or b.
If both a and b belonged to U(v), the reciprocal arrows R a b and R b a would yield a 2-cycle in the subrelation induced on U(v), contradicting its well-foundedness. Thus a ∈ U(v) and b ∈ U(v) are mutually exclusive. Since each vertex appears in at least n/2 coalitions, condorcet_half_coalitions_partition_of_incompatible implies that the two sets of coalitions partition the index set, so a ∈ U(v) ↔ b ∉ U(v) for every coalition v.
uses
condorcet_half_coalitions_partition_of_incompatiblehave hedge : ∀ a b, R a b → R b a → ∀ v, a ∈ U v ↔ b ∉ U v := by intro a b hab hba exact (condorcet_half_coalitions_partition_of_incompatible n (fun v => a ∈ U v) (fun v => b ∈ U v) (hhalf a) (hhalf b) (by intro v ⟨ha,hb⟩ exact (hU v).asymmetric (a := ⟨a,ha⟩) (b := ⟨b,hb⟩) hab hba)).2.2
There exists a reciprocal edge with distinct endpoints r and t.
Applying the predecessor hypothesis to the empty set yields a vertex r, and applying it to {r} yields a vertex s ≠ r with R s r. Because the reciprocal graph is connected, the path from r to s has a first step, giving a neighbor t such that R r t and R t r.
obtain ⟨r,_,_⟩ := hpred ∅ (by simp) obtain ⟨s,hs,_⟩ := hpred {r} (by simp) have hne : r ≠ s := by intro h; apply hs; simp [h] obtain ⟨t,hrt,_⟩ := (hconn r s).cases_head.resolve_left hne
Every vertex belongs to at least one coalition, yielding coalitions U(v) containing r and U(w) containing t with r ∉ U(w).
From 0 < n and n ≤ 2 * |{v | a ∈ U(v)}|, linear arithmetic implies that each vertex belongs to at least one coalition U(v). In particular, we choose a coalition U(v) containing r and a coalition U(w) containing t. By the reciprocal edge property between r and t, r cannot belong to U(w).
have hex : ∀ a, ∃ v : Fin n, a ∈ U v := by intro a have hpos : 0 < (univ.filter fun v => a ∈ U v).card := by have h := hhalf a omega obtain ⟨v,hv⟩ := card_pos.mp hpos exact ⟨v,(mem_filter.mp hv).2⟩ obtain ⟨v,hrv⟩ := hex r obtain ⟨w,htw⟩ := hex t have hrw : r ∉ U w := by intro h exact (hedge r t hrt.1 hrt.2 w).mp h htw
For every vertex a, a ∈ U(v) ↔ a ∉ U(w).
We induct on the reciprocal path from r to a. In the base case a = r, we already have r ∈ U(v) and r ∉ U(w). For the inductive step along an edge between b and c, the edge property implies b ∈ U(v) ↔ c ∉ U(v) and b ∈ U(w) ↔ c ∉ U(w); combining these with the induction hypothesis b ∈ U(v) ↔ b ∉ U(w) via propositional logic yields c ∈ U(v) ↔ c ∉ U(w).
have hopp : ∀ a, a ∈ U v ↔ a ∉ U w := by intro a induction hconn r a with | refl => tauto | @tail b c hpath hbc ih => have hv := hedge b c hbc.1 hbc.2 v have hw := hedge b c hbc.1 hbc.2 w tauto
The two coalitions U(v) and U(w) cover all vertices of the graph.
For any vertex a, either a ∈ U(w) or a ∉ U(w). In the latter case, the complementarity between U(v) and U(w) implies a ∈ U(v). Hence every vertex belongs to U(v) or U(w).
have hcover : ∀ a, a ∈ U v ∨ a ∈ U w := by intro a by_cases h : a ∈ U w · exact Or.inr h · exact Or.inl ((hopp a).mpr h)
Choosing minimal elements in U(v) and U(w) and taking a common predecessor produces a contradiction.
Because U(v) and U(w) are nonempty (containing r and t respectively) and their induced subrelations are well-founded, each has an R-minimal element: a ∈ U(v) and b ∈ U(w). The set {a, b} has cardinality at most 2 by card_insert_le and card_singleton, so by hypothesis it has a common predecessor z with R z a and R z b. Since U(v) and U(w) cover all vertices, z must belong to U(v) or U(w), contradicting the minimality of a or b.
uses
card_insert_le,card_singletonobtain ⟨a,_,hmina⟩ := (hU v).has_min Set.univ ⟨⟨r,hrv⟩,Set.mem_univ _⟩ obtain ⟨b,_,hminb⟩ := (hU w).has_min Set.univ ⟨⟨t,htw⟩,Set.mem_univ _⟩ have hcard : ({a.val,b.val} : Finset (Fin m)).card ≤ 2 := by have h := card_insert_le a.val ({b.val} : Finset (Fin m)) simpa only [card_singleton] using h obtain ⟨z,_,hz⟩ := hpred {a.val,b.val} hcard rcases hcover z with hzv | hzw · exact hmina ⟨z,hzv⟩ (Set.mem_univ _) (hz a.val (by simp)) · exact hminb ⟨z,hzw⟩ (Set.mem_univ _) (hz b.val (by simp))
There exists a nonnegative weight vector strictly separating every acyclic subset below half the total weight.
By linear programming duality (condorcet_half_cover_acyclic_half_cover_duality), the existence of the desired weight function is equivalent to the impossibility of an acyclic half-cover. We apply this equivalence and conclude using the helper theorem condorcet_reciprocal_connected_no_acyclic_half_cover.
uses
condorcet_half_cover_acyclic_half_cover_duality,condorcet_reciprocal_connected_no_acyclic_half_coverclassical apply (condorcet_half_cover_acyclic_half_cover_duality m R).mp rintro ⟨n,U,hn,hU,hhalf⟩ exact condorcet_reciprocal_connected_no_acyclic_half_cover m n R U hn hpred hconn hU hhalf
condorcet_half_coalitions_partition_of_incompatible- If two predicates on a universe of size n each hold on at least n/2 elements and are mutually exclusive, then n is even, both hold on exactly n/2 elements, and they are exact negations of each other.
card_insert_le- Inserting an element into a finite set s produces a set of cardinality at most |s| + 1.
card_singleton- A singleton set has cardinality 1.
condorcet_half_cover_acyclic_half_cover_duality- In a finite directed relation, no acyclic half-cover exists if and only if there exist nonnegative weights under which every acyclic subset has strictly less than half the total weight.
condorcet_reciprocal_connected_no_acyclic_half_cover- Under the common predecessor and reciprocal connectivity hypotheses, no acyclic half-cover can exist.
- Linear arithmetic (the omega tactic) is used on line 30 to deduce that every vertex belongs to at least one coalition from the half-cover inequality and 0 < n.
- The well-foundedness of the restriction of R to each subset U(v) formalizes that the induced subgraph on U(v) is finite and acyclic.
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_reciprocal_connected_no_acyclic_half_cover (m n : ℕ) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (hn : 0 < n) (hpred : ∀ J : Finset (Fin m), J.card ≤ 2 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) (hconn : ∀ a b, Relation.ReflTransGen (fun x y => R x y ∧ R y x) a b) (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) : ¬ (∀ a, n ≤ 2 * (univ.filter fun v => a ∈ U v).card) := by classical intro hhalf have hedge : ∀ a b, R a b → R b a → ∀ v, a ∈ U v ↔ b ∉ U v := by intro a b hab hba exact (condorcet_half_coalitions_partition_of_incompatible n (fun v => a ∈ U v) (fun v => b ∈ U v) (hhalf a) (hhalf b) (by intro v ⟨ha,hb⟩ exact (hU v).asymmetric (a := ⟨a,ha⟩) (b := ⟨b,hb⟩) hab hba)).2.2 obtain ⟨r,_,_⟩ := hpred ∅ (by simp) obtain ⟨s,hs,_⟩ := hpred {r} (by simp) have hne : r ≠ s := by intro h; apply hs; simp [h] obtain ⟨t,hrt,_⟩ := (hconn r s).cases_head.resolve_left hne have hex : ∀ a, ∃ v : Fin n, a ∈ U v := by intro a have hpos : 0 < (univ.filter fun v => a ∈ U v).card := by have h := hhalf a omega obtain ⟨v,hv⟩ := card_pos.mp hpos exact ⟨v,(mem_filter.mp hv).2⟩ obtain ⟨v,hrv⟩ := hex r obtain ⟨w,htw⟩ := hex t have hrw : r ∉ U w := by intro h exact (hedge r t hrt.1 hrt.2 w).mp h htw have hopp : ∀ a, a ∈ U v ↔ a ∉ U w := by intro a induction hconn r a with | refl => tauto | @tail b c hpath hbc ih => have hv := hedge b c hbc.1 hbc.2 v have hw := hedge b c hbc.1 hbc.2 w tauto have hcover : ∀ a, a ∈ U v ∨ a ∈ U w := by intro a by_cases h : a ∈ U w · exact Or.inr h · exact Or.inl ((hopp a).mpr h) obtain ⟨a,_,hmina⟩ := (hU v).has_min Set.univ ⟨⟨r,hrv⟩,Set.mem_univ _⟩ obtain ⟨b,_,hminb⟩ := (hU w).has_min Set.univ ⟨⟨t,htw⟩,Set.mem_univ _⟩ have hcard : ({a.val,b.val} : Finset (Fin m)).card ≤ 2 := by have h := card_insert_le a.val ({b.val} : Finset (Fin m)) simpa only [card_singleton] using h obtain ⟨z,_,hz⟩ := hpred {a.val,b.val} hcard rcases hcover z with hzv | hzw · exact hmina ⟨z,hzv⟩ (Set.mem_univ _) (hz a.val (by simp)) · exact hminb ⟨z,hzw⟩ (Set.mem_univ _) (hz b.val (by simp))theorem condorcet_reciprocal_connected_acyclic_weight_separation (m : ℕ) (R : Fin m → Fin m → Prop) (hpred : ∀ J : Finset (Fin m), J.card ≤ 2 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) (hconn : ∀ a b, Relation.ReflTransGen (fun x y => R x y ∧ R y x) a b) : ∃ w : Fin m → ℝ, (∀ a, 0 ≤ w a) ∧ ∀ A : Finset (Fin m), WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) → 2 * (∑ a ∈ A, w a) < ∑ a, w a := by classical apply (condorcet_half_cover_acyclic_half_cover_duality m R).mp rintro ⟨n,U,hn,hU,hhalf⟩ exact condorcet_reciprocal_connected_no_acyclic_half_cover m n R U hn hpred hconn hU hhalf