condorcet_source_anchored_exchange_obstruction
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.
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.
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
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.
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
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`.
uses
condorcet_anchor_gap_pair_checklet 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
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.
uses
mem_singleton,mem_insert,not_orhave 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
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.
uses
measure,condorcet_anchor_gap_rank_exacthave 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
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`.
uses
condorcet_anchor_gap_rank_exactrefine ⟨R,U,p,s,condorcet_anchor_gap_rank_exact,?_,hroot,hU,?_,?_,?_,?_,?_,?_⟩ · decide · decide · decide · decide · decide · decide
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.
· 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 α.
- Most structural properties of the relation (rank compatibility, injectivity, signature realization, Pareto incomparability, source properties, exchange conditions, and the failure of S3 on {0, 1, 16}) are discharged by `decide`, which carries out exhaustive Boolean evaluation over the finite set of 40 vertices.
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 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)⟩