condorcet_s2_strict_majority_cover_obstruction
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.
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.
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]]
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).
have hloop : ∀ a, ¬ R a a := by decide have hpair : ∀ a b, ∃ c, R c a ∧ R c b := by decide
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}.
uses
card_eq_zero,card_eq_one,card_eq_two,mem_singleton,mem_insert,not_orhave 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
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`.
uses
measurehave 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
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).
have hcover : ∀ a, (univ.filter fun v => a∈U v).card = 5 := by decide
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.
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.
- Several key properties—namely the irreflexivity of R (hloop), the existence of common predecessors for every pair (hpair), the order-preservation of ord on each U v (horder), the 5-fold coverage of each vertex (hcover), and the absence of a common predecessor for {0, 6, 12} (hbad)—are verified purely by finite computation using Lean's `decide` tactic.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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)⟩