condorcet_minimal_predecessor_coalition_completion_exclusion
Such a globally minimal predecessor core cannot have an acyclic half-cover if every undominated (k+1)-set has an additional event of at least half the voters avoiding every member of that set. The extra event hypothesis is essential.
Statement
theorem condorcet_minimal_predecessor_coalition_completion_exclusion (m n k : ℕ) (hn : 0 < n) (hk : 0 < k) (R : Fin m → Fin m → Prop) (hroot : ∀ J : Finset (Fin m), J.card ≤ k → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) (hminimal : ∀ S : Finset (Fin m), (∀ J : Finset (Fin m), J ⊆ S → J.card ≤ k → ∃ a ∈ S, a ∉ J ∧ ∀ b ∈ J, R a b) → S = univ) (U : Fin n → Finset (Fin m)) (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) (hhalf : ∀ a, n ≤ 2*(univ.filter fun v => a∈U v).card) (hextra : ∀ T : Finset (Fin m), T.card = k+1 → (¬∃ a, a ∉ T ∧ ∀ b ∈ T, R a b) → ∃ B : Finset (Fin n), n ≤ 2*B.card ∧ ∀ v ∈ B, ∀ a ∈ T, a ∉ U v) : False
- 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 2
- condorcet_minimal_predecessor_acyclic_cutFor k positive, a finite relation globally minimal under induced restriction among relations with the outside common predecessor property…
- condorcet_half_coalitions_partition_of_incompatibleFor two incompatible voter events in a finite electorate, if each has at least half of the voter support, the electorate size is even, the…
- Used by 1
- condorcet_minimal_predecessor_reciprocal_completion_exclusionLet a globally minimal finite S_k core, k positive, map by a relation-preserving function into another finite relation. If every…
The proof, explained
The proof proceeds by contradiction. Choosing a voter v whose set U(v) is nonempty, the acyclic cut lemma provides a set T of size k+1 with no external common predecessor that crosses the boundary of U(v), containing an alternative a ∈ U(v) and an alternative b ∉ U(v). By the coalition completion hypothesis, at least half the voters avoid T entirely, forming a coalition B. Because the coalition approving a and the coalition B are disjoint and both contain at least half the voters, they partition the electorate, meaning that approving a is equivalent to not being in B; the same holds for b. This implies that voter v approves b if and only if they approve a, contradicting the fact that v approves a but not b.
There exists an alternative r and a voter v who approves r, showing that U(v) is nonempty.
Applying `hroot` to the empty set (which has size 0 ≤ k) produces an alternative r. By `hhalf`, at least half of the voters approve r. Because the total number of voters n is strictly positive, the coalition of voters approving r has strictly positive cardinality (verified by `omega`). Using `card_pos.mp`, we extract a voter v such that r ∈ U(v).
uses
card_pos.mpclassical obtain ⟨r,_,_⟩ := hroot ∅ (by simp) have hpos : 0 < (univ.filter fun v => r ∈ U v).card := by have h := hhalf r omega obtain ⟨v,hv⟩ := card_pos.mp hpos
There exists a set T of k+1 alternatives with no external common predecessor that contains an alternative inside U(v) and an alternative outside U(v).
Because U(v) is nonempty (containing r, unpacked with `mem_filter.mp`) and the restriction of R to U(v) is well-founded (`hU v`), the cut lemma `condorcet_minimal_predecessor_acyclic_cut` yields a subset T of size k+1 with no external common predecessor, containing some a ∈ U(v) and some b ∉ U(v).
uses
condorcet_minimal_predecessor_acyclic_cut,mem_filter.mpobtain ⟨T,hTcard,hTbad,⟨a,haT,haU⟩,⟨b,hbT,hbU⟩⟩ := condorcet_minimal_predecessor_acyclic_cut m k hk R hroot hminimal (U v) ⟨r,(mem_filter.mp hv).2⟩ (hU v)There is a coalition B of at least half the voters that avoids all alternatives in T.
Applying hypothesis `hextra` to T (which has cardinality k+1 and no external common predecessor) gives a coalition B of voters with n ≤ 2|B| such that no voter in B approves any member of T. Line 29 rewrites this size bound in terms of filtering the universal set of voters.
obtain ⟨B,hB,havoid⟩ := hextra T hTcard hTbad have hB' : n ≤ 2*(univ.filter fun v => v ∈ B).card := by simpa using hB
For every voter, approving a is equivalent to not belonging to B, and approving b is also equivalent to not belonging to B.
The coalition of voters approving a has size at least n/2 (by `hhalf a`), and coalition B also has size at least n/2. Since a ∈ T, voters in B avoid a, making the two coalitions disjoint. By `condorcet_half_coalitions_partition_of_incompatible`, two disjoint coalitions each of size at least n/2 form a partition, so a voter approves a if and only if they are not in B. The identical argument applies to b ∈ T, showing that a voter approves b if and only if they are not in B.
uses
condorcet_half_coalitions_partition_of_incompatiblehave ha := (condorcet_half_coalitions_partition_of_incompatible n (fun v => a ∈ U v) (fun v => v ∈ B) (hhalf a) hB' (fun v hv => havoid v hv.2 a haT hv.1)).2.2 have hb := (condorcet_half_coalitions_partition_of_incompatible n (fun v => b ∈ U v) (fun v => v ∈ B) (hhalf b) hB' (fun v hv => havoid v hv.2 b hbT hv.1)).2.2
A contradiction is reached, completing the proof.
For the specific voter v chosen in the first step, we have a ∈ U(v). By the equivalence for a, v ∉ B. Then by the equivalence for b, this implies b ∈ U(v). But b was constructed specifically so that b ∉ U(v), yielding a contradiction.
exact hbU ((hb v).mpr ((ha v).mp haU))
card_pos.mp- A finite set with strictly positive cardinality is nonempty.
condorcet_minimal_predecessor_acyclic_cut- In a minimal k-predecessor system, any nonempty subset on which the dominance relation is well-founded admits a (k+1)-element subset with no external common predecessor that contains at least one element inside the subset and at least one element outside it.
mem_filter.mp- If an element belongs to a filtered finite set, then it belongs to the original set and satisfies the filtering predicate.
condorcet_half_coalitions_partition_of_incompatible- Two disjoint voter coalitions each containing at least half of all voters must partition the electorate, so that each is the exact complement of the other.
- Line 29 uses `simpa` to formally convert the coalition size |B| into the cardinality of a filtered universal set #{v | v ∈ B} to match the hypothesis shape of `condorcet_half_coalitions_partition_of_incompatible`.
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_minimal_predecessor_coalition_completion_exclusion (m n k : ℕ) (hn : 0 < n) (hk : 0 < k) (R : Fin m → Fin m → Prop) (hroot : ∀ J : Finset (Fin m), J.card ≤ k → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) (hminimal : ∀ S : Finset (Fin m), (∀ J : Finset (Fin m), J ⊆ S → J.card ≤ k → ∃ a ∈ S, a ∉ J ∧ ∀ b ∈ J, R a b) → S = univ) (U : Fin n → Finset (Fin m)) (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) (hhalf : ∀ a, n ≤ 2*(univ.filter fun v => a∈U v).card) (hextra : ∀ T : Finset (Fin m), T.card = k+1 → (¬∃ a, a ∉ T ∧ ∀ b ∈ T, R a b) → ∃ B : Finset (Fin n), n ≤ 2*B.card ∧ ∀ v ∈ B, ∀ a ∈ T, a ∉ U v) : False := by classical obtain ⟨r,_,_⟩ := hroot ∅ (by simp) have hpos : 0 < (univ.filter fun v => r ∈ U v).card := by have h := hhalf r omega obtain ⟨v,hv⟩ := card_pos.mp hpos obtain ⟨T,hTcard,hTbad,⟨a,haT,haU⟩,⟨b,hbT,hbU⟩⟩ := condorcet_minimal_predecessor_acyclic_cut m k hk R hroot hminimal (U v) ⟨r,(mem_filter.mp hv).2⟩ (hU v) obtain ⟨B,hB,havoid⟩ := hextra T hTcard hTbad have hB' : n ≤ 2*(univ.filter fun v => v ∈ B).card := by simpa using hB have ha := (condorcet_half_coalitions_partition_of_incompatible n (fun v => a ∈ U v) (fun v => v ∈ B) (hhalf a) hB' (fun v hv => havoid v hv.2 a haT hv.1)).2.2 have hb := (condorcet_half_coalitions_partition_of_incompatible n (fun v => b ∈ U v) (fun v => v ∈ B) (hhalf b) hB' (fun v hv => havoid v hv.2 b hbT hv.1)).2.2 exact hbU ((hb v).mpr ((ha v).mp haU))