AFTD Auto-Formalizing Theoretical Domains

condorcet_minimal_predecessor_coalition_completion_exclusion

theoremverified

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

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.

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

    lines 19–24

    uses card_pos.mp

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

    lines 25–27

    uses condorcet_minimal_predecessor_acyclic_cut, mem_filter.mp

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

    lines 28–29

      obtain ⟨B,hB,havoid⟩ := hextra T hTcard hTbad
      have hB' : n ≤ 2*(univ.filter fun v => v ∈ B).card := by simpa using hB
  4. 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.

    lines 30–35

    uses condorcet_half_coalitions_partition_of_incompatible

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

    line 36

      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.

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