AFTD Auto-Formalizing Theoretical Domains

condorcet_stationary_certificate_exists

theoremverified

Explicit constructive witnesses (S, f, d, next, p) on 8 candidates and 56 triples, verified by finite decision, satisfying the subset properties, coverage of all triples, transition law, the C=139, K=70 local potential inequality, and the unrestricted 3-claim certificate of total weight 3 with full-set value 1.

Statement

theorem condorcet_stationary_certificate_exists :
    ∃ (S : Fin 56 → Finset (Fin 8)) (f : Fin 56 → Fin 8)
      (d : Fin 56 → Fin 3 → Fin 8) (next : Fin 56 → Fin 3 → Fin 56)
      (p : Fin 56 → ℕ),
      (∀ i, (S i).card = 3 ∧ f i ∉ S i ∧ Function.Injective (d i) ∧
        S i = Finset.univ.image (d i)) ∧
      (∀ T : Finset (Fin 8), T.card = 3 → ∃ i, S i = T) ∧
      (∀ i j, S (next i j) = insert (f i) ((S i).erase (d i j))) ∧
      (∀ i, 70 + 3 * p i ≤ 139 * (if ∀ b ∈ S i, f i < b then 1 else 0) + ∑ k : Fin 3, p (next i k)) ∧
      (∃ (w : Fin 56 → ℕ) (H : Finset (Fin 8) → ℕ),
        (∀ A : Finset (Fin 8), ∀ a ∈ A,
          (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) + H (A.erase a) ≤ H A) ∧
        2 * H Finset.univ < ∑ i, w i)
Source
step towards condorcet_stationary_weight_restriction_obstruction
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof establishes the existence of the reset selector, transition system, local potential, and dual certificate by providing explicit finite lookup tables on 8 candidates and 56 triples. First, the candidate witnesses (S, f, d, next, p) are instantiated from concrete precomputed lists, and Lean's decision procedure verifies by exhaustive finite evaluation that each triple has size 3, all 56 triples are covered, transitions update triples as prescribed, and the C=139, K=70 potential drift inequality holds. Second, the certificate pair (w, H) is instantiated with explicit weights concentrated on three specific triples and an indicator function for subsets containing {5, 6, 7}. Finally, the remaining certificate inequalities over all 256 subsets of candidates are closed by exhaustive finite decision.

  1. Explicit witnesses (S, f, d, next, p) satisfy the triple structure, coverage, transition law, and the local potential drift inequality with C = 139 and K = 70.

    We instantiate the existential quantifiers for the triple family S, reset selector f, indexing d, transition function next, and potential p with the explicit lookup tables defined above. The four conjuncts require that each S(i) is a 3-element subset indexed injectively by d(i) with f(i) ∉ S(i), that all 56 triples are present, that next(i, j) replaces d(i, j) by f(i) in S(i), and that the potential drift inequality 70 + 3 p(i) ≤ 139 · 1_{∀ b ∈ S(i), f(i) < b} + ∑_{k=0}^2 p(next(i, k)) holds for all i ∈ {0, …, 55}. Because all quantifiers range over the finite sets {0, …, 55} and {0, 1, 2}, each of these four conditions is closed by direct finite evaluation (`decide`), leaving only the existential claim for the dual certificate (w, H).

    lines 96–101

      refine ⟨condorcet_stationary_certificate_exists_S,
              condorcet_stationary_certificate_exists_f,
              condorcet_stationary_certificate_exists_d,
              condorcet_stationary_certificate_exists_next,
              condorcet_stationary_certificate_exists_p,
              by decide, by decide, by decide, by decide, ?_⟩
  2. The certificate witnesses (w, H) satisfy the subset submodularity inequality and exceed twice the potential of the grand coalition.

    We instantiate the weight function w and subset potential H with their explicit definitions: w assigns weight 1 to triples 18, 19, and 20 (and 0 elsewhere), while H(A) indicates whether {5, 6, 7} ⊆ A. The two remaining conditions assert that ∑_{i : f(i)=a, S(i) ⊆ A \ {a}} w(i) + H(A \ {a}) ≤ H(A) for every subset A ⊆ {0, …, 7} and element a ∈ A, and that 2 H({0, …, 7}) < ∑_i w(i) (which evaluates to 2 · 1 < 3). Both conditions are finite propositions over the 2^8 = 256 subsets of candidates and are verified by exhaustive computation (`decide`).

    lines 102–104

      exact ⟨condorcet_stationary_certificate_exists_w,
             condorcet_stationary_certificate_exists_H,
             by decide, by decide⟩

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

def condorcet_stationary_certificate_exists_SList : List (Finset (Fin 8)) :=  [{0,1,2},{0,1,3},{0,1,4},{0,1,5},{0,1,6},{0,1,7},   {0,2,3},{0,2,4},{0,2,5},{0,2,6},{0,2,7},   {0,3,4},{0,3,5},{0,3,6},{0,3,7},   {0,4,5},{0,4,6},{0,4,7},   {0,5,6},{0,5,7},{0,6,7},   {1,2,3},{1,2,4},{1,2,5},{1,2,6},{1,2,7},   {1,3,4},{1,3,5},{1,3,6},{1,3,7},   {1,4,5},{1,4,6},{1,4,7},   {1,5,6},{1,5,7},{1,6,7},   {2,3,4},{2,3,5},{2,3,6},{2,3,7},   {2,4,5},{2,4,6},{2,4,7},   {2,5,6},{2,5,7},{2,6,7},   {3,4,5},{3,4,6},{3,4,7},   {3,5,6},{3,5,7},{3,6,7},   {4,5,6},{4,5,7},{4,6,7},{5,6,7}]def condorcet_stationary_certificate_exists_fList : List (Fin 8) :=  [7,7,7,7,7,6,7,7,7,7,6,7,7,7,6,7,7,6,7,6,5,0,0,0,0,6,0,0,0,6,0,0,6,0,6,5,   1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,4]def condorcet_stationary_certificate_exists_dList : List (Fin 3 → Fin 8) :=  [![0,1,2],![0,1,3],![0,1,4],![0,1,5],![0,1,6],![0,1,7],   ![0,2,3],![0,2,4],![0,2,5],![0,2,6],![0,2,7],   ![0,3,4],![0,3,5],![0,3,6],![0,3,7],   ![0,4,5],![0,4,6],![0,4,7],   ![0,5,6],![0,5,7],![0,6,7],   ![1,2,3],![1,2,4],![1,2,5],![1,2,6],![1,2,7],   ![1,3,4],![1,3,5],![1,3,6],![1,3,7],   ![1,4,5],![1,4,6],![1,4,7],   ![1,5,6],![1,5,7],![1,6,7],   ![2,3,4],![2,3,5],![2,3,6],![2,3,7],   ![2,4,5],![2,4,6],![2,4,7],   ![2,5,6],![2,5,7],![2,6,7],   ![3,4,5],![3,4,6],![3,4,7],   ![3,5,6],![3,5,7],![3,6,7],   ![4,5,6],![4,5,7],![4,6,7],![5,6,7]]def condorcet_stationary_certificate_exists_nList : List (Fin 3 → Fin 56) :=  [![25,10,5],![29,14,5],![32,17,5],![34,19,5],![35,20,5],![35,20,4],   ![39,14,10],![42,17,10],![44,19,10],![45,20,10],![45,20,9],   ![48,17,14],![50,19,14],![51,20,14],![51,20,13],   ![53,19,17],![54,20,17],![54,20,16],   ![55,20,19],![55,20,18],![55,19,18],   ![6,1,0],![7,2,0],![8,3,0],![9,4,0],![45,35,24],   ![11,2,1],![12,3,1],![13,4,1],![51,35,28],   ![15,3,2],![16,4,2],![54,35,31],   ![18,4,3],![55,35,33],![55,34,33],   ![26,22,21],![27,23,21],![28,24,21],![29,25,21],   ![30,23,22],![31,24,22],![32,25,22],   ![33,24,23],![34,25,23],![35,25,24],   ![40,37,36],![41,38,36],![42,39,36],   ![43,38,37],![44,39,37],![45,39,38],   ![49,47,46],![50,48,46],![51,48,47],![54,53,52]]def condorcet_stationary_certificate_exists_pList : List ℕ :=  [0,6,12,20,20,20,13,18,24,24,24,28,33,33,33,44,44,44,55,55,55,29,33,37,37,28,   38,42,42,36,48,48,45,54,55,55,56,59,59,53,62,62,58,65,63,63,82,82,78,84,81,81,   105,103,103,126]def condorcet_stationary_certificate_exists_S : Fin 56 → Finset (Fin 8) :=  fun i => condorcet_stationary_certificate_exists_SList.getD i.val ∅def condorcet_stationary_certificate_exists_f : Fin 56 → Fin 8 :=  fun i => condorcet_stationary_certificate_exists_fList.getD i.val 0def condorcet_stationary_certificate_exists_d : Fin 56 → Fin 3 → Fin 8 :=  fun i => condorcet_stationary_certificate_exists_dList.getD i.val (fun _ => 0)def condorcet_stationary_certificate_exists_next : Fin 56 → Fin 3 → Fin 56 :=  fun i => condorcet_stationary_certificate_exists_nList.getD i.val (fun _ => 0)def condorcet_stationary_certificate_exists_p : Fin 56 → ℕ :=  fun i => condorcet_stationary_certificate_exists_pList.getD i.val 0def condorcet_stationary_certificate_exists_w : Fin 56 → ℕ :=  fun i => if i = 18 ∨ i = 19 ∨ i = 20 then 1 else 0def condorcet_stationary_certificate_exists_H : Finset (Fin 8) → ℕ :=  fun A => if ({5,6,7} : Finset (Fin 8)) ⊆ A then 1 else 0/-- Existence and verification of concrete 56-triple reset selector witnesses and potentials on 8 candidates. -/theorem condorcet_stationary_certificate_exists :    ∃ (S : Fin 56 → Finset (Fin 8)) (f : Fin 56 → Fin 8)      (d : Fin 56 → Fin 3 → Fin 8) (next : Fin 56 → Fin 3 → Fin 56)      (p : Fin 56 → ℕ),      (∀ i, (S i).card = 3 ∧ f i ∉ S i ∧ Function.Injective (d i) ∧        S i = Finset.univ.image (d i)) ∧      (∀ T : Finset (Fin 8), T.card = 3 → ∃ i, S i = T) ∧      (∀ i j, S (next i j) = insert (f i) ((S i).erase (d i j))) ∧      (∀ i, 70 + 3 * p i ≤ 139 * (if ∀ b ∈ S i, f i < b then 1 else 0) + ∑ k : Fin 3, p (next i k)) ∧      (∃ (w : Fin 56 → ℕ) (H : Finset (Fin 8) → ℕ),        (∀ A : Finset (Fin 8), ∀ a ∈ A,          (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) + H (A.erase a) ≤ H A) ∧        2 * H Finset.univ < ∑ i, w i) := by  refine ⟨condorcet_stationary_certificate_exists_S,          condorcet_stationary_certificate_exists_f,          condorcet_stationary_certificate_exists_d,          condorcet_stationary_certificate_exists_next,          condorcet_stationary_certificate_exists_p,          by decide, by decide, by decide, by decide, ?_⟩  exact ⟨condorcet_stationary_certificate_exists_w,         condorcet_stationary_certificate_exists_H,         by decide, by decide⟩
See it in the graphDiscuss this resultChallenge it