AFTD Auto-Formalizing Theoretical Domains

condorcet_s2_strict_majority_cover_obstruction

theoremverified

An explicit eighteen-vertex relation has outside common predecessors for every set of at most two vertices and has nine induced acyclic sets covering each vertex exactly five times. It explicitly fails the corresponding three-vertex predecessor property. Thus S2 and strict majority coverage alone do not yield a contradiction; this does not refute the special three-of-five auxiliary.

Statement

theorem condorcet_s2_strict_majority_cover_obstruction :
    ∃ (R : Fin 18 → Fin 18 → Prop) (U : Fin 9 → Finset (Fin 18)),
      (∀ J : Finset (Fin 18), J.card ≤ 2 →
        ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) ∧
      (∀ v, WellFounded (fun a b : {a : Fin 18 // a ∈ U v} => R a.val b.val)) ∧
      (∀ a, (univ.filter fun v => a∈U v).card = 5) ∧
      ¬(∀ J : Finset (Fin 18), J.card ≤ 3 →
        ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b)
Source
IN-383, OP-19 campaign session 9, 2026-10-30. Structural analysis of the S2-to-S3 completion route from IN-362; finite diagnostics audited in experiments9630 and9640. Supports the general campaign only; no new election bound or research novelty is claimed.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem is proved by exhibiting an explicit 18-vertex relation R and a family of 9 subsets U that serve as an obstruction. The graph consists of three blocks of 6 vertices arranged in a cyclic 3-tournament, with a directed 6-cycle inside each block. Using ranking functions into the natural numbers and finite computation (`decide`), the proof shows that each subset in U is acyclic, each vertex is covered by a strict majority (5 of 9) of the subsets, and every pair of vertices has an outside common predecessor. However, the three-element set {0, 6, 12} consisting of the first vertex of each block has no common predecessor, refuting the degree-3 predecessor property.

  1. The candidate relation R, the family of nine subsets U, and the ranking functions ord are defined on Fin 18.

    We define a directed relation R on 18 vertices partitioned into three blocks of six. Edges run in a 6-cycle within each block, and from all vertices of block k to all vertices of block (k+1) mod 3. We also register a decidability instance for R, define nine 10-element subsets U 0 through U 8, and define an explicit integer ranking function ord v for each subset to later certify acyclicity.

    lines 14–37

      let R : Fin 18 → Fin 18 → Prop := fun a b =>
        (a.val / 6 = b.val / 6 ∧ b.val % 6 = (a.val % 6 + 1) % 6) ∨
          b.val / 6 = (a.val / 6 + 1) % 3
      letI (a b : Fin 18) : Decidable (R a b) := inferInstanceAs (Decidable
        ((a.val / 6 = b.val / 6 ∧ b.val % 6 = (a.val % 6 + 1) % 6) ∨
          b.val / 6 = (a.val / 6 + 1) % 3))
      let U : Fin 9 → Finset (Fin 18) := ![{7,8,9,10,11,13,14,15,16,17},
        {6,8,9,10,11,12,14,15,16,17},
        {6,7,9,10,11,12,13,15,16,17},
        {1,2,3,4,5,12,13,14,16,17},
        {0,2,3,4,5,12,13,14,15,17},
        {0,1,3,4,5,12,13,14,15,16},
        {0,1,2,4,5,6,7,8,10,11},
        {0,1,2,3,5,6,7,8,9,11},
        {0,1,2,3,4,6,7,8,9,10}]
      let ord : Fin 9 → Fin 18 → ℕ := ![![0,0,0,0,0,0,0,0,1,2,3,4,0,5,6,7,8,9],
        ![0,0,0,0,0,0,4,0,0,1,2,3,9,0,5,6,7,8],
        ![0,0,0,0,0,0,3,4,0,0,1,2,8,9,0,5,6,7],
        ![0,5,6,7,8,9,0,0,0,0,0,0,2,3,4,0,0,1],
        ![9,0,5,6,7,8,0,0,0,0,0,0,1,2,3,4,0,0],
        ![8,9,0,5,6,7,0,0,0,0,0,0,0,1,2,3,4,0],
        ![2,3,4,0,0,1,7,8,9,0,5,6,0,0,0,0,0,0],
        ![1,2,3,4,0,0,6,7,8,9,0,5,0,0,0,0,0,0],
        ![0,1,2,3,4,0,5,6,7,8,9,0,0,0,0,0,0,0]]
  2. The relation R is irreflexive, and every pair of vertices has a common predecessor.

    Exhaustive finite evaluation (`decide`) verifies that R has no self-loops (hloop: ∀ a, ¬ R a a) and that for any two vertices a and b, there exists some vertex c such that R c a and R c b (hpair).

    lines 38–39

      have hloop : ∀ a, ¬ R a a := by decide
      have hpair : ∀ a b, ∃ c, R c a ∧ R c b := by decide
  3. Every subset of vertices J with |J| ≤ 2 has a common predecessor outside J.

    We proceed by cases on |J|. If |J| = 0, then J = ∅, and vertex 0 is trivially an outside predecessor. If |J| = 1, J = {a}; using hpair on a and a, we obtain a predecessor c of a, which must satisfy c ≠ a by irreflexivity (hloop), so c ∉ J. If |J| = 2, J = {a, b} with a ≠ b; hpair provides a common predecessor c of both a and b, and irreflexivity ensures c ∉ {a, b}.

    lines 40–64

    uses card_eq_zero, card_eq_one, card_eq_two, mem_singleton, mem_insert, not_or

      have hroot : ∀ J : Finset (Fin 18), 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
              simpa only [mem_singleton.mp hb] using 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
  4. For each v ∈ Fin 9, the induced relation on the subset U v is well-founded (acyclic).

    First, exhaustive finite check (`decide`) confirms that for every v and all a, b ∈ U v, an edge R a b implies ord v a < ord v b. Then, well-foundedness of the restriction to U v is deduced by pulling back the standard well-ordering on ℕ along the ranking function ord v using `measure`.

    lines 65–70

    uses measure

      have horder : ∀ v a b, a∈U v → b∈U v → R a b → ord v a < ord v b := by decide
      have hU : ∀ v, WellFounded (fun a b : {a : Fin 18 // a ∈ U v} => R a.val b.val) := by
        intro v
        refine (measure (fun a : {a : Fin 18 // a ∈ U v} => ord v a.val)).wf.mono ?_
        intro a b hab
        exact horder v a b a.property b.property hab
  5. Each of the 18 vertices belongs to exactly 5 of the 9 subsets U v.

    Exhaustive finite evaluation (`decide`) checks that the fiber {v | a ∈ U v} has cardinality exactly 5 for every vertex a ∈ Fin 18, establishing strict majority coverage (5 > 9/2).

    line 71

      have hcover : ∀ a, (univ.filter fun v => a∈U v).card = 5 := by decide
  6. The relation R and family U satisfy all required conditions, and the predecessor property fails for the 3-element subset {0, 6, 12}.

    We instantiate the existential claim with R and U, supplying hroot, hU, and hcover. To refute the predecessor property for subsets of size at most 3, we assume for contradiction that it holds and instantiate it with the 3-element set {0, 6, 12}. This would yield a common predecessor a to 0, 6, and 12, but finite evaluation (`decide`) proves that no vertex simultaneously precedes all three, producing a contradiction.

    lines 72–76

      refine ⟨R,U,hroot,hU,hcover,?_⟩
      intro hthree
      obtain ⟨a,_,ha⟩ := hthree {0,6,12} (by decide)
      have hbad : ∀ a, ¬(R a 0 ∧ R a 6 ∧ R a 12) := by decide
      exact hbad a ⟨ha 0 (by simp),ha 6 (by simp),ha 12 (by simp)⟩
card_eq_zero
A finite set has cardinality 0 if and only if it is the empty set.
card_eq_one
A finite set has cardinality 1 if and only if it is a singleton {a}.
card_eq_two
A finite set has cardinality 2 if and only if it is a doubleton {a, b} with a ≠ b.
mem_singleton
An element belongs to {a} if and only if it equals a.
mem_insert
An element belongs to 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 ¬p ∧ ¬q.
measure
Constructs a well-founded relation on a type from a ranking function into the natural numbers.

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 30000000set_option maxRecDepth 20000theorem condorcet_s2_strict_majority_cover_obstruction :    ∃ (R : Fin 18 → Fin 18 → Prop) (U : Fin 9 → Finset (Fin 18)),      (∀ J : Finset (Fin 18), J.card ≤ 2 →        ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) ∧      (∀ v, WellFounded (fun a b : {a : Fin 18 // a ∈ U v} => R a.val b.val)) ∧      (∀ a, (univ.filter fun v => a∈U v).card = 5) ∧      ¬(∀ J : Finset (Fin 18), J.card ≤ 3 →        ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) := by  let R : Fin 18 → Fin 18 → Prop := fun a b =>    (a.val / 6 = b.val / 6 ∧ b.val % 6 = (a.val % 6 + 1) % 6) ∨      b.val / 6 = (a.val / 6 + 1) % 3  letI (a b : Fin 18) : Decidable (R a b) := inferInstanceAs (Decidable    ((a.val / 6 = b.val / 6 ∧ b.val % 6 = (a.val % 6 + 1) % 6) ∨      b.val / 6 = (a.val / 6 + 1) % 3))  let U : Fin 9 → Finset (Fin 18) := ![{7,8,9,10,11,13,14,15,16,17},    {6,8,9,10,11,12,14,15,16,17},    {6,7,9,10,11,12,13,15,16,17},    {1,2,3,4,5,12,13,14,16,17},    {0,2,3,4,5,12,13,14,15,17},    {0,1,3,4,5,12,13,14,15,16},    {0,1,2,4,5,6,7,8,10,11},    {0,1,2,3,5,6,7,8,9,11},    {0,1,2,3,4,6,7,8,9,10}]  let ord : Fin 9 → Fin 18 → ℕ := ![![0,0,0,0,0,0,0,0,1,2,3,4,0,5,6,7,8,9],    ![0,0,0,0,0,0,4,0,0,1,2,3,9,0,5,6,7,8],    ![0,0,0,0,0,0,3,4,0,0,1,2,8,9,0,5,6,7],    ![0,5,6,7,8,9,0,0,0,0,0,0,2,3,4,0,0,1],    ![9,0,5,6,7,8,0,0,0,0,0,0,1,2,3,4,0,0],    ![8,9,0,5,6,7,0,0,0,0,0,0,0,1,2,3,4,0],    ![2,3,4,0,0,1,7,8,9,0,5,6,0,0,0,0,0,0],    ![1,2,3,4,0,0,6,7,8,9,0,5,0,0,0,0,0,0],    ![0,1,2,3,4,0,5,6,7,8,9,0,0,0,0,0,0,0]]  have hloop : ∀ a, ¬ R a a := by decide  have hpair : ∀ a b, ∃ c, R c a ∧ R c b := by decide  have hroot : ∀ J : Finset (Fin 18), 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          simpa only [mem_singleton.mp hb] using 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 horder : ∀ v a b, a∈U v → b∈U v → R a b → ord v a < ord v b := by decide  have hU : ∀ v, WellFounded (fun a b : {a : Fin 18 // a ∈ U v} => R a.val b.val) := by    intro v    refine (measure (fun a : {a : Fin 18 // a ∈ U v} => ord v a.val)).wf.mono ?_    intro a b hab    exact horder v a b a.property b.property hab  have hcover : ∀ a, (univ.filter fun v => a∈U v).card = 5 := by decide  refine ⟨R,U,hroot,hU,hcover,?_⟩  intro hthree  obtain ⟨a,_,ha⟩ := hthree {0,6,12} (by decide)  have hbad : ∀ a, ¬(R a 0 ∧ R a 6 ∧ R a 12) := by decide  exact hbad a ⟨ha 0 (by simp),ha 6 (by simp),ha 12 (by simp)⟩
See it in the graphDiscuss this resultChallenge it