AFTD Auto-Formalizing Theoretical Domains

condorcet_minimum_s2_incidence_root_policy_obstruction

theoremverified

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
Used by 1

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.

  1. 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`.

    lines 17–22

      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
  2. 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.

    line 23

    uses subset_univ

      obtain ⟨r,a,hr,ha,hroot,har⟩ := hcert D (mem_powerset.mpr (subset_univ D)) hD hpair
  3. The 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$.

    line 24

      have hne : r ≠ a := fun h => hr (h ▸ ha)
  4. 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`.

    line 25

      have hloop : ∀ x, ¬condorcet_uniform_outgoing_gap_relation x x := by decide
  5. 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.

    line 26

      refine ⟨r,a,hr,ha,hroot,?_,?_⟩
  6. 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.

    lines 27–38

    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))
  7. 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$.

    lines 39–43

    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)$.

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_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]
See it in the graphDiscuss this resultChallenge it