condorcet_common_predecessor_neighborhood
In a finite relation in which every set of at most k+1 vertices has an outside common predecessor, the relation induced on the predecessors of any vertex has the analogous property for sets of at most k vertices.
Statement
theorem condorcet_common_predecessor_neighborhood {V : Type*} [Fintype V] (R : V → V → Prop) (k : ℕ) (hroot : ∀ J : Finset V, J.card ≤ k+1 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) (b : V) : ∀ J : Finset {a : V // R a b}, J.card ≤ k → ∃ a : {a : V // R a b}, a ∉ J ∧ ∀ c ∈ J, R a.val c.val
- Source
- IN-383, OP-19 campaign session 9, 2026-10-30. Structural verification of the maximum-potential neighborhood route suggested in IN-380. Generalization of the existing acyclic-cover reduction, whose strict election definition is from Condorcet winning sets, Social Choice and Welfare 44(3):493-517 (2015), https://www.lamsade.dauphine.fr/~lang/papers/els15.pdf . No new election bound or research novelty is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- condorcet_failure_iff_acyclic_half_coverFix a positive number n of voters. There exists a finite election with these n voters in which every candidate set of size at most three…
- Used by 1
- condorcet_potential_maximum_neighborhood_half_coverSuppose a finite relation has outside common predecessors for every set of at most k+1 vertices. If n induced acyclic sets and a real…
The proof, explained
To find a common predecessor for any set $J$ of at most $k$ predecessors of $b$, we consider the set $J' = \{b\} \cup \iota(J)$ in $V$, where $\iota$ is the inclusion of the predecessor neighborhood into $V$. Since $|J'| \le |J| + 1 \le k + 1$, the global hypothesis yields a vertex $a \notin J'$ that precedes every element in $J'$. Because $b \in J'$, $a$ precedes $b$ and therefore lies in the predecessor neighborhood of $b$; moreover, $a$ cannot be in $J$ and precedes every vertex in $J$.
Let $J$ be any finite set of predecessors of $b$ with $|J| \le k$.
We enable classical logic and introduce an arbitrary finite set $J$ of predecessors of $b$ along with the assumption $hJ$ that its cardinality is at most $k$.
classical intro J hJThe set $\{b\} \cup \iota(J)$ in $V$ has cardinality at most $k + 1$.
Mapping $J$ into $V$ via the subtype inclusion gives a set of size at most $|J| \le k$ by `card_image_le`. Inserting $b$ increases the cardinality by at most $1$ by `card_insert_le` and `Nat.add_le_add_right`, so the resulting set has cardinality at most $k + 1$.
uses
card_insert_le,Nat.add_le_add_right,card_image_lehave hc : (insert b (J.image Subtype.val)).card ≤ k+1 := (card_insert_le _ _).trans (Nat.add_le_add_right (card_image_le.trans hJ) 1)There exists a vertex $a \in V$ preceding $b$ and all vertices in $\iota(J)$, yielding a candidate predecessor $a'$.
Applying the hypothesis `hroot` to the set $\{b\} \cup \iota(J)$ gives a vertex $a \notin \{b\} \cup \iota(J)$ that precedes every element of that set. In particular, since $b$ is in this set by `mem_insert_self`, we have $R(a, b)$, so $a$ defines an element $a'$ of the predecessor subtype. We then propose $a'$ as the witness, reducing the goal to proving $a' \notin J$ and that $a'$ precedes each element of $J$.
uses
mem_insert_selfobtain ⟨a, ha, har⟩ := hroot (insert b (J.image Subtype.val)) hc let a' : {a : V // R a b} := ⟨a,har b (mem_insert_self _ _)⟩ refine ⟨a', ?_, ?_⟩
$a' \notin J$.
Assume for contradiction that $a' \in J$. Then its underlying vertex $a$ belongs to $\iota(J)$ by `mem_image.mpr`, and therefore belongs to $\{b\} \cup \iota(J)$ by `mem_insert_of_mem`. This contradicts the fact that $a \notin \{b\} \cup \iota(J)$.
uses
mem_insert_of_mem,mem_image.mpr· intro hmem exact ha (mem_insert_of_mem (mem_image.mpr ⟨a',hmem,rfl⟩))
For every $c \in J$, $a'$ precedes $c$.
For any $c \in J$, its underlying vertex $c.\text{val}$ belongs to $\iota(J)$ by `mem_image.mpr`, and hence to $\{b\} \cup \iota(J)$ by `mem_insert_of_mem`. Since $a$ precedes every element of $\{b\} \cup \iota(J)$, it follows that $R(a, c.\text{val})$.
uses
mem_insert_of_mem,mem_image.mpr· intro c hc exact har c.val (mem_insert_of_mem (mem_image.mpr ⟨c,hc,rfl⟩))
card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1: $|insert\ a\ s| \le |s| + 1$.
card_image_le- The image of a finite set under a function has cardinality at most that of the original set: $|image\ f\ s| \le |s|$.
Nat.add_le_add_right- Addition on the right preserves inequalities: if $n \le m$, then $n + k \le m + k$.
mem_insert_self- An element belongs to the set obtained by inserting it: $a \in insert\ a\ s$.
mem_insert_of_mem- An element of a set remains an element when another element is inserted: $a \in s \implies a \in insert\ b\ s$.
mem_image.mpr- If there is an element $a \in s$ with $f(a) = b$, then $b \in image\ f\ s$.
- Predecessors of $b$ are formalized using the subtype $\{a : V // R\ a\ b\}$, and sets of predecessors are mapped into $V$ via the subtype projection `Subtype.val`.
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 4000000set_option maxRecDepth 10000theorem condorcet_common_predecessor_neighborhood {V : Type*} [Fintype V] (R : V → V → Prop) (k : ℕ) (hroot : ∀ J : Finset V, J.card ≤ k+1 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) (b : V) : ∀ J : Finset {a : V // R a b}, J.card ≤ k → ∃ a : {a : V // R a b}, a ∉ J ∧ ∀ c ∈ J, R a.val c.val := by classical intro J hJ have hc : (insert b (J.image Subtype.val)).card ≤ k+1 := (card_insert_le _ _).trans (Nat.add_le_add_right (card_image_le.trans hJ) 1) obtain ⟨a, ha, har⟩ := hroot (insert b (J.image Subtype.val)) hc let a' : {a : V // R a b} := ⟨a,har b (mem_insert_self _ _)⟩ refine ⟨a', ?_, ?_⟩ · intro hmem exact ha (mem_insert_of_mem (mem_image.mpr ⟨a',hmem,rfl⟩)) · intro c hc exact har c.val (mem_insert_of_mem (mem_image.mpr ⟨c,hc,rfl⟩))