AFTD Auto-Formalizing Theoretical Domains

condorcet_source_anchored_exchange_obstruction

theoremverified

There is a forty-vertex rank-compatible S2 relation with injective rankings with six acyclic sets and exactly three memberships per vertex, realizing every three-element activity signature. Same-signature vertices are Pareto incomparable. Chosen activity-set sources satisfy every source-anchored single-index exchange condition, yet the relation fails S3. This refutes sufficiency of that exchange package, not its necessity for an S3 minimum core and not the main conjecture.

Statement

theorem condorcet_source_anchored_exchange_obstruction :
    ∃ (R : Fin 40 → Fin 40 → Prop) (U : Fin 6 → Finset (Fin 40))
      (p : Fin 6 → Fin 40 → ℕ) (s : Fin 6 → Fin 40),
      (∀ a b, R a b ↔ a ≠ b ∧ ∀ v, a ∈ U v → b ∈ U v → p v a < p v b) ∧
      (∀ v, Function.Injective (p v)) ∧
      (∀ J : Finset (Fin 40), J.card ≤ 2 →
        ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) ∧
      (∀ v, WellFounded (fun a b : {a : Fin 40 // a ∈ U v} => R a.val b.val)) ∧
      (∀ a, (univ.filter fun v => a ∈ U v).card = 3) ∧
      (∀ T : Finset (Fin 6), T.card = 3 → ∃ a : Fin 40, ∀ v, a ∈ U v ↔ v ∈ T) ∧
      (∀ a b : Fin 40, a ≠ b → (∀ v, a ∈ U v ↔ b ∈ U v) →
        ∃ v, a ∈ U v ∧ p v b < p v a) ∧
      (∀ v, s v ∈ U v ∧ ∀ a, a ∈ U v → ¬R a (s v)) ∧
      (∀ a : Fin 40, ∀ j : Fin 6, a ∉ U j →
        ∃ r : Fin 40, R r a ∧ r ∈ U j ∧
          (∀ v, r ∈ U v → a ∈ U v ∨ v = j) ∧
          (∀ v, v ≠ j → a ∉ U v → R r (s v))) ∧
      ¬(∀ J : Finset (Fin 40), J.card ≤ 3 →
        ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b)
Source
IN-391, OP-19 campaign session10, 2026-10-30. Supporting lemmas and precisely scoped method diagnostics for the rank-saturated acyclic-cover route. The main election theorem remains open; no new election bound or novelty is claimed.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • condorcet_cover_rank_relationThe loopless rank-compatible relation: an arrow a to b is permitted precisely when a differs from b and a has a strictly smaller…

The proof, explained

The theorem establishes an obstruction to S3 sufficiency by explicitly constructing a 40-vertex relation together with 6 acyclic subsets, injective rankings, and source vertices. Rank compatibility, injectivity, uniform 3-element activity signatures, Pareto incomparability of identical signatures, undominated sources, and the source-anchored exchange condition are all verified by finite decidability computations. The S2 property is proven by case analysis on subsets of size at most 2, showing that pairwise predecessors guaranteed by computation are strictly external via irreflexivity. Well-foundedness on each acyclic set is established by viewing the rank-compatible relation as a subrelation of the well-founded natural order induced by the rankings. Finally, S3 is refuted by pointing to the 3-element subset {0, 1, 16} and computationally confirming that no vertex in the domain simultaneously dominates all three.

  1. The relation defined by bitmask testing matches the Pareto dominance relation of the rankings on common active sets. automation

    The auxiliary lemma `condorcet_anchor_gap_rank_exact` verifies by finite evaluation (`decide`) that `condorcet_anchor_gap_relation a b` holds if and only if a ≠ b and for every profile v where both a and b are active, a has a strictly lower (better) rank than b.

    lines 13–16

    theorem condorcet_anchor_gap_rank_exact : ∀ a b : Fin 40,
        condorcet_anchor_gap_relation a b ↔ a ≠ b ∧
          ∀ v, a ∈ condorcet_anchor_gap_sets v → b ∈ condorcet_anchor_gap_sets v →
            condorcet_anchor_gap_rank v a < condorcet_anchor_gap_rank v b := by decide
  2. The relation is irreflexive and every pair of vertices shares a common predecessor. automation

    The auxiliary lemma `condorcet_anchor_gap_pair_check` is proved by exhaustive finite computation (`decide`), verifying that no vertex dominates itself and that for any two vertices a, b, there exists a common predecessor c dominating both.

    lines 18–21

    theorem condorcet_anchor_gap_pair_check :
        (∀ a : Fin 40, ¬condorcet_anchor_gap_relation a a) ∧
        (∀ a b : Fin 40, ∃ c, condorcet_anchor_gap_relation c a ∧
          condorcet_anchor_gap_relation c b) := by decide
  3. Introduce the witness definitions and extract irreflexivity and pairwise common predecessor properties.

    Local definitions are introduced for the relation R, the six active sets U, the rankings p, and the sources s. Irreflexivity (`hloop`) and the pairwise predecessor property (`hpair`) are extracted from the auxiliary lemma `condorcet_anchor_gap_pair_check`.

    lines 42–47

    uses condorcet_anchor_gap_pair_check

      let R := condorcet_anchor_gap_relation
      let U := condorcet_anchor_gap_sets
      let p := condorcet_anchor_gap_rank
      let s := condorcet_anchor_gap_source
      have hloop : ∀ a, ¬R a a := condorcet_anchor_gap_pair_check.1
      have hpair : ∀ a b, ∃ c, R c a ∧ R c b := condorcet_anchor_gap_pair_check.2
  4. The relation satisfies S2: every subset of at most two vertices has an external common predecessor.

    By case analysis on the cardinality of J ⊆ Fin 40: if |J| = 0, J is empty and vertex 0 is trivially an external predecessor; if |J| = 1, J = {a}, and a common predecessor c of a with itself satisfies R c a, so c ≠ a by irreflexivity (`hloop`); if |J| = 2, J = {a, b} with a ≠ b, and a common predecessor c of a and b satisfies R c a and R c b, so c ∉ {a, b} by irreflexivity. In all cases, c is strictly outside J and dominates every element of J.

    lines 48–74

    uses mem_singleton, mem_insert, not_or

      have hroot : ∀ J : Finset (Fin 40), J.card ≤ 2 →
          ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b := by
        intro J hJ
        by_cases h0 : J.card = 0
        · have hJ0 : J = ∅ := card_eq_zero.mp h0
          subst J
          exact ⟨0,by simp,by simp⟩
        · by_cases h1 : J.card = 1
          · obtain ⟨a,rfl⟩ := card_eq_one.mp h1
            obtain ⟨c,hca,_⟩ := hpair a a
            refine ⟨c,?_,?_⟩
            · simpa only [mem_singleton] using (fun heq : c = a => hloop a (heq ▸ hca))
            · intro b hb
              have heq : b = a := mem_singleton.mp hb
              subst b
              exact hca
          · have h2 : J.card = 2 := by omega
            obtain ⟨a,b,hab,rfl⟩ := card_eq_two.mp h2
            obtain ⟨c,hca,hcb⟩ := hpair a b
            refine ⟨c,?_,?_⟩
            · simp only [mem_insert,mem_singleton,not_or]
              exact ⟨fun heq => hloop a (heq ▸ hca),fun heq => hloop b (heq ▸ hcb)⟩
            · intro d hd
              simp only [mem_insert,mem_singleton] at hd
              rcases hd with rfl | rfl
              · exact hca
              · exact hcb
  5. The restriction of the relation to each active set is well-founded.

    For each profile v, well-foundedness is shown by measuring vertices in U v with the natural-number ranking p v. By `condorcet_anchor_gap_rank_exact`, if R a b holds for a, b ∈ U v, then p v a < p v b, so R is a subrelation of the well-founded standard order on ℕ pulled back by p v.

    lines 75–79

    uses measure, condorcet_anchor_gap_rank_exact

      have hU : ∀ v, WellFounded (fun a b : {a : Fin 40 // a ∈ U v} => R a.val b.val) := by
        intro v
        refine (measure (fun a : {a : Fin 40 // a ∈ U v} => p v a.val)).wf.mono ?_
        intro a b hab
        exact ((condorcet_anchor_gap_rank_exact a b).mp hab).2 v a.property b.property
  6. Instantiate the existential witnesses and computationally verify rank compatibility, injectivity, signature regularities, source conditions, and the exchange condition. automation

    The existential goal is supplied with R, U, p, s, along with the proofs of rank compatibility (`condorcet_anchor_gap_rank_exact`), S2 (`hroot`), and well-foundedness (`hU`). The remaining structural conditions—injectivity of p v (line 81), 3-regularity of set memberships (line 82), realization of every 3-element signature (line 83), Pareto incomparability of same-signature vertices (line 84), undominated status of sources (line 85), and the single-index exchange property (line 86)—are all finite checks discharged by `decide`.

    lines 80–86

    uses condorcet_anchor_gap_rank_exact

      refine ⟨R,U,p,s,condorcet_anchor_gap_rank_exact,?_,hroot,hU,?_,?_,?_,?_,?_,?_⟩
      · decide
      · decide
      · decide
      · decide
      · decide
      · decide
  7. The relation fails S3, completing the refutation.

    Assuming for contradiction that S3 holds (`intro hthree`), specializing to the 3-element set {0, 1, 16} yields a vertex a dominating all three elements. However, exhaustive evaluation (`hbad : ∀ a, ¬(R a 0 ∧ R a 1 ∧ R a 16) := by decide`) proves that no such vertex exists, producing a contradiction.

    lines 87–90

      · intro hthree
        obtain ⟨a,_,ha⟩ := hthree {0,1,16} (by decide)
        have hbad : ∀ a : Fin 40, ¬(R a 0 ∧ R a 1 ∧ R a 16) := by decide
        exact hbad a ⟨ha 0 (by simp),ha 1 (by simp),ha 16 (by simp)⟩
condorcet_anchor_gap_rank_exact
The bit-tested relation holds between a and b if and only if a ≠ b and a has strictly lower rank than b in all active profiles containing both.
condorcet_anchor_gap_pair_check
The bit-tested relation on 40 vertices is irreflexive, and every pair of vertices has a common predecessor.
mem_singleton
An element belongs to a singleton set {a} if and only if it equals a.
mem_insert
An element belongs to the set insert b s if and only if it equals b or belongs to s.
not_or
The negation of a disjunction ¬(p ∨ q) is equivalent to the conjunction of the negations ¬p ∧ ¬q.
measure
The pullback of the well-founded standard strict order on ℕ along a function f : α → ℕ produces a well-founded relation on α.

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 Finsetset_option maxHeartbeats 100000000set_option maxRecDepth 30000def condorcet_anchor_gap_sets : Fin 6 → Finset (Fin 40) := ![{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19},{0,1,2,3,4,5,6,7,20,21,22,23,24,25,26,27,28,29,30,31},{0,1,8,9,10,11,12,13,20,21,22,23,24,25,32,33,34,35,36,37},{2,3,8,9,14,15,16,17,20,21,26,27,28,29,32,33,34,35,38,39},{4,5,10,11,14,15,18,19,22,23,26,27,30,31,32,33,36,37,38,39},{6,7,12,13,16,17,18,19,24,25,28,29,30,31,34,35,36,37,38,39}]def condorcet_anchor_gap_rank : Fin 6 → Fin 40 → ℕ := ![![0,14,5,6,1,13,17,19,8,12,10,11,2,18,4,9,15,16,3,7,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79],![16,6,13,11,18,1,3,2,48,49,50,51,52,53,54,55,56,57,58,59,9,15,8,14,4,19,7,17,10,12,0,5,72,73,74,75,76,77,78,79],![13,10,42,43,44,45,46,47,16,7,1,17,15,14,54,55,56,57,58,59,12,3,4,2,9,0,66,67,68,69,70,71,11,19,6,8,5,18,78,79],![40,41,17,5,44,45,46,47,2,9,50,51,52,53,1,11,16,6,58,59,3,7,62,63,64,65,13,15,4,14,70,71,12,0,8,10,76,77,18,19],![40,41,42,43,7,11,46,47,48,49,12,4,52,53,18,9,56,57,17,8,60,61,13,15,64,65,10,1,68,69,19,6,2,16,74,75,14,5,3,0],![40,41,42,43,44,45,8,17,48,49,50,51,6,19,54,55,0,1,7,11,60,61,62,63,9,18,66,67,15,2,14,13,72,73,12,5,4,10,3,16]]def condorcet_anchor_gap_pred : Fin 40 → ℕ := ![953313918976,948131644960,274698883072,218260328448,1021014179841,1017907813120,390842539808,1096291442464,72004423697,89438045208,827821948956,881461301517,383006015505,953482724991,216959029265,191448486169,13102010171,8603585851,391595954193,451662581789,71962477794,3498984680,826849068256,827654374636,377957631584,828862611708,195438492610,52364981195,217992420706,12957437738,545461886720,468168416064,51860603594,208369368307,68735091832,68734305848,275622626364,314223827791,4969399055,52365038415]def condorcet_anchor_gap_source : Fin 6 → Fin 40 := ![0,30,25,33,39,16]def condorcet_anchor_gap_relation (a b : Fin 40) : Prop :=  (condorcet_anchor_gap_pred b).testBit a.val = trueinstance : DecidableRel condorcet_anchor_gap_relation := fun a b =>  inferInstanceAs (Decidable ((condorcet_anchor_gap_pred b).testBit a.val = true))theorem condorcet_anchor_gap_rank_exact : ∀ a b : Fin 40,    condorcet_anchor_gap_relation a b ↔ a ≠ b ∧      ∀ v, a ∈ condorcet_anchor_gap_sets v → b ∈ condorcet_anchor_gap_sets v →        condorcet_anchor_gap_rank v a < condorcet_anchor_gap_rank v b := by decidetheorem condorcet_anchor_gap_pair_check :    (∀ a : Fin 40, ¬condorcet_anchor_gap_relation a a) ∧    (∀ a b : Fin 40, ∃ c, condorcet_anchor_gap_relation c a ∧      condorcet_anchor_gap_relation c b) := by decidetheorem condorcet_source_anchored_exchange_obstruction :    ∃ (R : Fin 40 → Fin 40 → Prop) (U : Fin 6 → Finset (Fin 40))      (p : Fin 6 → Fin 40 → ℕ) (s : Fin 6 → Fin 40),      (∀ a b, R a b ↔ a ≠ b ∧ ∀ v, a ∈ U v → b ∈ U v → p v a < p v b) ∧      (∀ v, Function.Injective (p v)) ∧      (∀ J : Finset (Fin 40), J.card ≤ 2 →        ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) ∧      (∀ v, WellFounded (fun a b : {a : Fin 40 // a ∈ U v} => R a.val b.val)) ∧      (∀ a, (univ.filter fun v => a ∈ U v).card = 3) ∧      (∀ T : Finset (Fin 6), T.card = 3 → ∃ a : Fin 40, ∀ v, a ∈ U v ↔ v ∈ T) ∧      (∀ a b : Fin 40, a ≠ b → (∀ v, a ∈ U v ↔ b ∈ U v) →        ∃ v, a ∈ U v ∧ p v b < p v a) ∧      (∀ v, s v ∈ U v ∧ ∀ a, a ∈ U v → ¬R a (s v)) ∧      (∀ a : Fin 40, ∀ j : Fin 6, a ∉ U j →        ∃ r : Fin 40, R r a ∧ r ∈ U j ∧          (∀ v, r ∈ U v → a ∈ U v ∨ v = j) ∧          (∀ v, v ≠ j → a ∉ U v → R r (s v))) ∧      ¬(∀ J : Finset (Fin 40), J.card ≤ 3 →        ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) := by  let R := condorcet_anchor_gap_relation  let U := condorcet_anchor_gap_sets  let p := condorcet_anchor_gap_rank  let s := condorcet_anchor_gap_source  have hloop : ∀ a, ¬R a a := condorcet_anchor_gap_pair_check.1  have hpair : ∀ a b, ∃ c, R c a ∧ R c b := condorcet_anchor_gap_pair_check.2  have hroot : ∀ J : Finset (Fin 40), J.card ≤ 2 →      ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b := by    intro J hJ    by_cases h0 : J.card = 0    · have hJ0 : J = ∅ := card_eq_zero.mp h0      subst J      exact ⟨0,by simp,by simp⟩    · by_cases h1 : J.card = 1      · obtain ⟨a,rfl⟩ := card_eq_one.mp h1        obtain ⟨c,hca,_⟩ := hpair a a        refine ⟨c,?_,?_⟩        · simpa only [mem_singleton] using (fun heq : c = a => hloop a (heq ▸ hca))        · intro b hb          have heq : b = a := mem_singleton.mp hb          subst b          exact hca      · have h2 : J.card = 2 := by omega        obtain ⟨a,b,hab,rfl⟩ := card_eq_two.mp h2        obtain ⟨c,hca,hcb⟩ := hpair a b        refine ⟨c,?_,?_⟩        · simp only [mem_insert,mem_singleton,not_or]          exact ⟨fun heq => hloop a (heq ▸ hca),fun heq => hloop b (heq ▸ hcb)⟩        · intro d hd          simp only [mem_insert,mem_singleton] at hd          rcases hd with rfl | rfl          · exact hca          · exact hcb  have hU : ∀ v, WellFounded (fun a b : {a : Fin 40 // a ∈ U v} => R a.val b.val) := by    intro v    refine (measure (fun a : {a : Fin 40 // a ∈ U v} => p v a.val)).wf.mono ?_    intro a b hab    exact ((condorcet_anchor_gap_rank_exact a b).mp hab).2 v a.property b.property  refine ⟨R,U,p,s,condorcet_anchor_gap_rank_exact,?_,hroot,hU,?_,?_,?_,?_,?_,?_⟩  · decide  · decide  · decide  · decide  · decide  · decide  · intro hthree    obtain ⟨a,_,ha⟩ := hthree {0,1,16} (by decide)    have hbad : ∀ a : Fin 40, ¬(R a 0 ∧ R a 1 ∧ R a 16) := by decide    exact hbad a ⟨ha 0 (by simp),ha 1 (by simp),ha 16 (by simp)⟩
See it in the graphDiscuss this resultChallenge it