AFTD Auto-Formalizing Theoretical Domains

condorcet_dimension_le_three_iff_acyclic_cover_potential_break

theoremverified

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

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.

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

    lines 15–16

      classical
      constructor
  2. The 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).

    lines 17–19

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

    lines 20–24

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

    lines 25–29

    uses add_zero, not_lt_of_ge

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

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