AFTD Auto-Formalizing Theoretical Domains

condorcet_reciprocal_connected_acyclic_weight_separation

theoremverified

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

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.

  1. 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)}|.

    lines 14–15

      classical
      intro hhalf
  2. For 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.

    lines 16–21

    uses condorcet_half_coalitions_partition_of_incompatible

      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
  3. 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.

    lines 22–25

      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
  4. 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).

    lines 26–37

      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
  5. 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).

    lines 38–45

      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
  6. 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).

    lines 46–50

      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)
  7. 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.

    lines 51–59

    uses card_insert_le, card_singleton

      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))
  8. 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.

    lines 70–73

    uses condorcet_half_cover_acyclic_half_cover_duality, condorcet_reciprocal_connected_no_acyclic_half_cover

      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
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.

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_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
See it in the graphDiscuss this resultChallenge it