AFTD Auto-Formalizing Theoretical Domains

condorcet_four_acyclic_sets_potential_break

theoremverified

For every finite S3 relation, every four induced acyclic sets with arbitrary strictly positive real coefficients and every real vertex potential have an arrow violating the weighted half-cover potential inequality. This excludes four positive support sets in this certificate format, without bounding the support needed in the main conjecture.

Statement

theorem condorcet_four_acyclic_sets_potential_break
    (m : ℕ) (R : Fin m → Fin m → Prop)
    (U : Fin 4 → Finset (Fin m)) (d : Fin 4 → ℝ) (h : Fin m → ℝ)
    (hd : ∀ v, 0 < d v)
    (hroot : ∀ J : Finset (Fin m), J.card ≤ 3 →
      ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b)
    (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) :
    ∃ a b, R a b ∧
      2 * (∑ v, if a ∈ U v then d v else 0) + h a < (∑ v, d v) + h b
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

The proof, explained

The proof partitions the four acyclic sets into two pairs, $\{0, 1\}$ and $\{2, 3\}$. By comparing their weights, at least one pair must be 'heavy'—meaning its weight sum is at least half of the total weight across all four sets. In either case, the result follows by applying `condorcet_heavy_pair_acyclic_cover_potential_break` with the heavy pair and a third distinct index with positive weight.

  1. It suffices to prove the existence of a violating arrow in two cases: either $d(2) + d(3) \le d(0) + d(1)$ or $d(0) + d(1) < d(2) + d(3)$.

    Using classical logic, we split into cases depending on whether the pair $\{0, 1\}$ has at least as much total weight as the pair $\{2, 3\}$.

    lines 15–16

      classical
      by_cases hpair : d 2+d 3 ≤ d 0+d 1
  2. A violating arrow exists when $d(2) + d(3) \le d(0) + d(1)$.

    Since $d(2) + d(3) \le d(0) + d(1)$, the pair $\{0, 1\}$ carries at least half the total weight: $d(0) + d(1) + d(2) + d(3) \le 2(d(0) + d(1))$. We invoke `condorcet_heavy_pair_acyclic_cover_potential_break` with heavy pair $i = 0, j = 1$ and a third index $k = 2$. The index distinctness conditions ($0 \neq 1$, $0 \neq 2$, $1 \neq 2$) are checked by computation, the positivity and acyclicity hypotheses are supplied directly, and the heavy-pair inequality is verified by expanding the sum over `Fin 4` with `Fin.sum_univ_four` followed by linear arithmetic.

    lines 17–20

    uses condorcet_heavy_pair_acyclic_cover_potential_break, Fin.sum_univ_four

      · refine condorcet_heavy_pair_acyclic_cover_potential_break m 4 R U d h 0 1 2
          (by decide) (by decide) (by decide) (fun v => (hd v).le) (hd 2) ?_ hroot hU
        simp only [Fin.sum_univ_four]
        linarith
  3. A violating arrow exists when $d(0) + d(1) < d(2) + d(3)$.

    When $d(2) + d(3) > d(0) + d(1)$, the pair $\{2, 3\}$ instead carries at least half the total weight: $d(0) + d(1) + d(2) + d(3) \le 2(d(2) + d(3))$. Symmetrically, we invoke `condorcet_heavy_pair_acyclic_cover_potential_break` with heavy pair $i = 2, j = 3$ and third index $k = 0$. The distinctness conditions ($2 \neq 3$, $2 \neq 0$, $3 \neq 0$) are checked by computation, the remaining hypotheses come from the assumptions, and the heavy-pair inequality is closed by expanding the sum with `Fin.sum_univ_four` and linear arithmetic.

    lines 21–24

    uses condorcet_heavy_pair_acyclic_cover_potential_break, Fin.sum_univ_four

      · refine condorcet_heavy_pair_acyclic_cover_potential_break m 4 R U d h 2 3 0
          (by decide) (by decide) (by decide) (fun v => (hd v).le) (hd 0) ?_ hroot hU
        simp only [Fin.sum_univ_four]
        linarith
condorcet_heavy_pair_acyclic_cover_potential_break
In a tournament relation where every subset of at most 3 vertices has an in-dominating root, if a family of acyclic sets has a 'heavy pair' of indices whose combined weight is at least half the total weight, and another distinct index has positive weight, then there exists an arrow violating the potential inequality.
Fin.sum_univ_four
The sum of a function $f$ over the four-element type `Fin 4` is equal to $f(0) + f(1) + f(2) + f(3)$.

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_four_acyclic_sets_potential_break    (m : ℕ) (R : Fin m → Fin m → Prop)    (U : Fin 4 → Finset (Fin m)) (d : Fin 4 → ℝ) (h : Fin m → ℝ)    (hd : ∀ v, 0 < d v)    (hroot : ∀ J : Finset (Fin m), J.card ≤ 3 →      ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b)    (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) :    ∃ a b, R a b ∧      2 * (∑ v, if a ∈ U v then d v else 0) + h a < (∑ v, d v) + h b := by  classical  by_cases hpair : d 2+d 3 ≤ d 0+d 1  · refine condorcet_heavy_pair_acyclic_cover_potential_break m 4 R U d h 0 1 2      (by decide) (by decide) (by decide) (fun v => (hd v).le) (hd 2) ?_ hroot hU    simp only [Fin.sum_univ_four]    linarith  · refine condorcet_heavy_pair_acyclic_cover_potential_break m 4 R U d h 2 3 0      (by decide) (by decide) (by decide) (fun v => (hd v).le) (hd 0) ?_ hroot hU    simp only [Fin.sum_univ_four]    linarith
See it in the graphDiscuss this resultChallenge it