condorcet_minimum_s2_incidence_root_policy_obstruction
In the existing eight-vertex globally minimal S3 core, every three-vertex induced S2 core has a unique common root outside it and an acyclic pair of weight three under the incidence recipe with total weight five (one on each core vertex, two on the root). Thus choosing the best minimum-order core and root cannot extend these fixed reciprocal-completion weights to arbitrary directed repairs. This is a recipe obstruction, not a counterexample to the main conjecture.
Statement
theorem condorcet_minimum_s2_incidence_root_policy_obstruction (D : Finset (Fin 8)) (hD : D.card = 3) (hpair : ∀ a ∈ D, ∀ b ∈ D, ∃ c ∈ D, condorcet_uniform_outgoing_gap_relation c a ∧ condorcet_uniform_outgoing_gap_relation c b) : ∃ r a : Fin 8, r ∉ D ∧ a ∈ D ∧ (∀ x, (∀ b ∈ D, condorcet_uniform_outgoing_gap_relation x b) ↔ x = r) ∧ WellFounded (fun x y : {x : Fin 8 // x ∈ ({r,a} : Finset (Fin 8))} => condorcet_uniform_outgoing_gap_relation x.val y.val) ∧ (let w : Fin 8 → ℕ := fun x => (if x∈D then 1 else 0) + (if x=r then 2 else 0) (∑ x,w x) = 5 ∧ (∑ x∈({r,a} : Finset (Fin 8)),w x) = 3)
- 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- Built on 1
- condorcet_uniform_outgoing_stationary_core_obstructionAn explicit eight-vertex S3 relation is globally minimal under induced vertex restriction and every arrow has a private triple. Its…
- Used by 1
- condorcet_s2_incidence_recipe_failure_witnessThe existing eight-vertex S3 relation actually contains a three-vertex S2 core with the fixed-incidence recipe obstruction: its unique…
The proof, explained
The proof proceeds by finite exhaustive computation on the eight-vertex graph followed by explicit algebraic and relational verification. A decision procedure first certifies over all three-element subsets with the pairwise predecessor condition that there exists an external common predecessor $r \notin D$ and a core vertex $a \in D$ with no edge to $r$. Instantiating this for $D$, the restriction of the relation to $\{r, a\}$ is shown to be well-founded (acyclic) via a measure mapping $r \mapsto 0$ and $a \mapsto 1$, since irreflexivity and the absence of an edge $a \to r$ leave $r \to a$ as the only possible edge. Finally, the sum of indicator weights evaluates to 5 globally and 3 on $\{r, a\}$ by distributing sums and evaluating the indicator conditions.
For every 3-element subset satisfying the pairwise predecessor condition, there exists an external vertex $r \notin D$ that is the unique common predecessor of $D$, and a vertex $a \in D$ that does not dominate $r$. automation
Since the vertex set `Fin 8` is finite, whether all 3-element subsets with the pairwise common-predecessor property admit such an external root $r$ and non-dominating core vertex $a$ is decidable and checked exhaustively by `decide`.
have hcert : ∀ D ∈ (univ : Finset (Fin 8)).powerset, D.card = 3 → (∀ a∈D,∀ b∈D,∃ c∈D,condorcet_uniform_outgoing_gap_relation c a ∧ condorcet_uniform_outgoing_gap_relation c b) → ∃ r a : Fin 8, r∉D ∧ a∈D ∧ (∀ x, (∀ b∈D,condorcet_uniform_outgoing_gap_relation x b) ↔ x=r) ∧ ¬condorcet_uniform_outgoing_gap_relation a r := by decide
There exist vertices $r \notin D$ and $a \in D$ such that $r$ is the unique common predecessor of $D$ and there is no directed edge from $a$ to $r$.
We instantiate the certificate `hcert` with the given 3-element subset $D$, using `subset_univ` to show $D \subseteq \mathrm{univ}$, together with the hypotheses that $|D| = 3$ and that $D$ satisfies the pairwise condition.
uses
subset_univobtain ⟨r,a,hr,ha,hroot,har⟩ := hcert D (mem_powerset.mpr (subset_univ D)) hD hpairThe root $r$ and the vertex $a$ are distinct ($r \ne a$).
If $r = a$, then substituting $r$ for $a$ in $a \in D$ would imply $r \in D$, directly contradicting $r \notin D$.
have hne : r ≠ a := fun h => hr (h ▸ ha)
The relation is irreflexive (no vertex has an edge to itself). automation
The absence of self-loops ($x \not\to x$ for all $x \in \mathrm{Fin}\; 8$) is verified by exhaustive computation using `decide`.
have hloop : ∀ x, ¬condorcet_uniform_outgoing_gap_relation x x := by decide
Providing $r$ and $a$ as witnesses reduces the theorem to establishing well-foundedness on $\{r, a\}$ and the two weight identities.
We supply $r$ and $a$ together with the proofs that $r \notin D$, $a \in D$, and that $r$ is the unique common predecessor of $D$. This leaves two obligations: proving the relation on $\{r, a\}$ is well-founded, and computing the total and pair weights.
refine ⟨r,a,hr,ha,hroot,?_,?_⟩The relation restricted to the two-element set $\{r, a\}$ is well-founded (acyclic).
We define a measure on $\{r, a\}$ assigning 0 to $r$ and 1 to $a$, and use `measure` to reduce well-foundedness to showing that any edge $x \to y$ in $\{r, a\}$ strictly decreases this measure. Given $x, y \in \{r, a\}$ with $x \to y$, we check the four cases: self-loops $r \to r$ and $a \to a$ are ruled out by irreflexivity (`hloop`, via `False.elim`); the edge $a \to r$ is ruled out by choice of $a$ (`har`, via `False.elim`); and for $r \to a$, the measure strictly decreases from 0 to 1 using $r \ne a$ (via `Ne.symm`). Hence $\{r, a\}$ is acyclic.
uses
measure,False.elim,Ne.symm· refine (measure (fun x : {x : Fin 8 // x∈({r,a} : Finset (Fin 8))} => if x.val=r then 0 else 1)).wf.mono ?_ intro x y hxy have hx := x.property have hy := y.property simp only [mem_insert,mem_singleton] at hx hy rcases hx with hx|hx <;> rcases hy with hy|hy · exact False.elim (hloop r (by simpa only [hx,hy] using hxy)) · change (if x.val=r then 0 else 1) < (if y.val=r then 0 else 1) simp [hx,hy,Ne.symm hne] · exact False.elim (har (by simpa only [hx,hy] using hxy)) · exact False.elim (hloop a (by simpa only [hx,hy] using hxy))
The weight function satisfies $\sum_x w(x) = 5$ and $\sum_{x \in \{r, a\}} w(x) = 3$.
For the total weight, distributing the sum via `sum_add_distrib` gives $\sum_x [x \in D] + \sum_x 2[x = r] = |D| + 2 = 3 + 2 = 5$ using `hD`. For the pair sum, because $r \ne a$, `sum_pair` rewrites the sum over $\{r, a\}$ as $w(r) + w(a)$. Since $r \notin D$ we have $w(r) = 0 + 2 = 2$, and since $a \in D$ and $a \ne r$ (via `Ne.symm`) we have $w(a) = 1 + 0 = 1$, giving $2 + 1 = 3$.
uses
sum_add_distrib,sum_pair,Ne.symm· dsimp only constructor · simp [sum_add_distrib,hD] · rw [sum_pair hne] simp [hr,ha,hne,Ne.symm hne]
subset_univ- Every subset of a finite type is a subset of the universal set `univ`.
measure- Constructs a well-founded relation from a measure function into ℕ, relating `x` to `y` when the measure of `x` is strictly less than that of `y`.
False.elim- From a contradiction (`False`), any proposition can be derived (ex falso quodlibet).
Ne.symm- Inequality is symmetric: if `a ≠ b`, then `b ≠ a`.
sum_add_distrib- The sum of two functions over a finite set equals the sum of the individual sums: $\sum_{x \in s} (f(x) + g(x)) = \sum_{x \in s} f(x) + \sum_{x \in s} g(x)$.
sum_pair- The sum of a function over a pair of distinct elements $\{a, b\}$ with $a \ne b$ equals $f(a) + f(b)$.
- The certificate `hcert` (lines 17–22) and the irreflexivity lemma `hloop` (line 25) are established by exhaustive finite verification using Lean's `decide` tactic, searching over all vertices and 3-element subsets of `Fin 8`.
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_minimum_s2_incidence_root_policy_obstruction (D : Finset (Fin 8)) (hD : D.card = 3) (hpair : ∀ a ∈ D, ∀ b ∈ D, ∃ c ∈ D, condorcet_uniform_outgoing_gap_relation c a ∧ condorcet_uniform_outgoing_gap_relation c b) : ∃ r a : Fin 8, r ∉ D ∧ a ∈ D ∧ (∀ x, (∀ b ∈ D, condorcet_uniform_outgoing_gap_relation x b) ↔ x = r) ∧ WellFounded (fun x y : {x : Fin 8 // x ∈ ({r,a} : Finset (Fin 8))} => condorcet_uniform_outgoing_gap_relation x.val y.val) ∧ (let w : Fin 8 → ℕ := fun x => (if x∈D then 1 else 0) + (if x=r then 2 else 0) (∑ x,w x) = 5 ∧ (∑ x∈({r,a} : Finset (Fin 8)),w x) = 3) := by have hcert : ∀ D ∈ (univ : Finset (Fin 8)).powerset, D.card = 3 → (∀ a∈D,∀ b∈D,∃ c∈D,condorcet_uniform_outgoing_gap_relation c a ∧ condorcet_uniform_outgoing_gap_relation c b) → ∃ r a : Fin 8, r∉D ∧ a∈D ∧ (∀ x, (∀ b∈D,condorcet_uniform_outgoing_gap_relation x b) ↔ x=r) ∧ ¬condorcet_uniform_outgoing_gap_relation a r := by decide obtain ⟨r,a,hr,ha,hroot,har⟩ := hcert D (mem_powerset.mpr (subset_univ D)) hD hpair have hne : r ≠ a := fun h => hr (h ▸ ha) have hloop : ∀ x, ¬condorcet_uniform_outgoing_gap_relation x x := by decide refine ⟨r,a,hr,ha,hroot,?_,?_⟩ · refine (measure (fun x : {x : Fin 8 // x∈({r,a} : Finset (Fin 8))} => if x.val=r then 0 else 1)).wf.mono ?_ intro x y hxy have hx := x.property have hy := y.property simp only [mem_insert,mem_singleton] at hx hy rcases hx with hx|hx <;> rcases hy with hy|hy · exact False.elim (hloop r (by simpa only [hx,hy] using hxy)) · change (if x.val=r then 0 else 1) < (if y.val=r then 0 else 1) simp [hx,hy,Ne.symm hne] · exact False.elim (har (by simpa only [hx,hy] using hxy)) · exact False.elim (hloop a (by simpa only [hx,hy] using hxy)) · dsimp only constructor · simp [sum_add_distrib,hD] · rw [sum_pair hne] simp [hr,ha,hne,Ne.symm hne]