AFTD Auto-Formalizing Theoretical Domains

condorcet_minimal_predecessor_reciprocal_completion_exclusion

theoremverified

Let a globally minimal finite S_k core, k positive, map by a relation-preserving function into another finite relation. If every undominated (k+1)-set of the core has a common reciprocal neighbor in the larger relation, the larger relation admits no positive finite acyclic half-cover. Injectivity of the map is not required.

Statement

theorem condorcet_minimal_predecessor_reciprocal_completion_exclusion
    (m q n k : ℕ) (hn : 0 < n) (hk : 0 < k)
    (R : Fin m → Fin m → Prop) (H : Fin q → Fin q → Prop) (f : Fin m → Fin q)
    (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)
    (hmap : ∀ a b, R a b → H (f a) (f b))
    (hrepair : ∀ T : Finset (Fin m), T.card = k+1 →
      (¬∃ a, a ∉ T ∧ ∀ b ∈ T, R a b) →
      ∃ x : Fin q, ∀ a ∈ T, H x (f a) ∧ H (f a) x)
    (U : Fin n → Finset (Fin q))
    (hU : ∀ v, WellFounded (fun a b : {a : Fin q // a ∈ U v} => H a.val b.val))
    (hhalf : ∀ a, n ≤ 2*(univ.filter fun v => a∈U v).card) : 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 1
Used by 1

The proof, explained

The proof proceeds by reduction to condorcet_minimal_predecessor_coalition_completion_exclusion, which establishes that no minimal S_k core can admit an acyclic majority half-cover with majority exclusion for undominated (k+1)-sets. We pull back the assumed acyclic half-cover U of the target relation along the relation-preserving map f to obtain a candidate cover V on the core, which inherits well-foundedness on each slice. For any undominated (k+1)-element set T, the repair hypothesis provides a mutual neighbor x in the target relation whose cover indices form a majority coalition B. Finally, no element of T can belong to V(v) for v ∈ B because a 2-cycle with x would violate the asymmetry of the well-founded relation on U(v), thereby supplying the required majority exclusion and deriving a contradiction.

  1. The problem reduces via condorcet_minimal_predecessor_coalition_completion_exclusion to showing that the preimages V(v) = f⁻¹(U(v)) form a well-founded majority cover with majority exclusion.

    We enable classical reasoning and define the family V(v) = {a ∈ Fin m | f(a) ∈ U(v)} on the core as the preimage under f of each set U(v). We then apply the exclusion theorem condorcet_minimal_predecessor_coalition_completion_exclusion, which rules out the existence of such a family on a minimal S_k core. This reduces the theorem to three subgoals: well-foundedness of each V(v), the half-cover property for each vertex of the core, and majority exclusion for every undominated (k+1)-element subset.

    lines 21–24

    uses condorcet_minimal_predecessor_coalition_completion_exclusion

      classical
      let V : Fin n → Finset (Fin m) := fun v => univ.filter fun a => f a ∈ U v
      apply condorcet_minimal_predecessor_coalition_completion_exclusion m n k hn hk R
        hroot hminimal V
  2. For each index v, the relation R restricted to V(v) is well-founded.

    The map f restricts to a function g : V(v) → U(v). Since f preserves the relation (hmap), R restricted to V(v) is a subrelation of the inverse image under g of the relation H on U(v). By assumption hU, H is well-founded on U(v), so its inverse image under g is well-founded by InvImage.wf. Because well-foundedness is preserved by passing to subrelations, R restricted to V(v) is well-founded.

    lines 25–28

    uses InvImage.wf

      · intro v
        let g : {a : Fin m // a∈V v} → {a : Fin q // a∈U v} :=
          fun a => ⟨f a.val,(mem_filter.mp a.property).2⟩
        exact (InvImage.wf g (hU v)).mono (fun a b hab => hmap a b hab)
  3. Every vertex in the core belongs to V(v) for at least half of the indices v.

    For any a ∈ Fin m, by definition a ∈ V(v) if and only if f(a) ∈ U(v). Applying the half-cover hypothesis hhalf to the image point f(a) ∈ Fin q yields n ≤ 2 |{v | f(a) ∈ U(v)}|, which directly gives n ≤ 2 |{v | a ∈ V(v)}|.

    lines 29–30

      · intro a
        simpa [V] using hhalf (f a)
  4. For any undominated (k+1)-set T, the repair hypothesis yields a candidate majority coalition B.

    Given a subset T ⊆ Fin m of size k+1 with no common predecessor in R, the repair hypothesis hrepair provides a vertex x ∈ Fin q that is a mutual neighbor under H with f(a) for every a ∈ T (both H(x, f(a)) and H(f(a), x) hold). We define B to be the set of indices v such that x ∈ U(v). By the half-cover hypothesis hhalf applied to x, B is a majority coalition, satisfying n ≤ 2|B|.

    lines 31–33

      · intro T hT hbad
        obtain ⟨x,hx⟩ := hrepair T hT hbad
        refine ⟨univ.filter (fun v => x ∈ U v),hhalf x,?_⟩
  5. No vertex of T belongs to V(v) for any index v ∈ B.

    Suppose for contradiction that some a ∈ T belongs to V(v) for an index v ∈ B. By definition of B and V, both x and f(a) belong to U(v). By construction of x, both H(x, f(a)) and H(f(a), x) hold, so x and f(a) form a 2-cycle in U(v). But H restricted to U(v) is well-founded and hence asymmetric, which rules out mutual edges and gives False.

    lines 34–37

        intro v hv a ha hmem
        have hxU := (mem_filter.mp hv).2
        have haU := (mem_filter.mp hmem).2
        exact (hU v).asymmetric (a := ⟨x,hxU⟩) (b := ⟨f a,haU⟩) (hx a ha).1 (hx a ha).2
condorcet_minimal_predecessor_coalition_completion_exclusion
On a minimal S_k core, no family of subsets can simultaneously be well-founded on each slice, cover every vertex in at least half of the slices, and provide a majority coalition excluding any undominated (k+1)-element subset.
InvImage.wf
The inverse image of a well-founded relation under any function is well-founded.

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_reciprocal_completion_exclusion    (m q n k : ℕ) (hn : 0 < n) (hk : 0 < k)    (R : Fin m → Fin m → Prop) (H : Fin q → Fin q → Prop) (f : Fin m → Fin q)    (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)    (hmap : ∀ a b, R a b → H (f a) (f b))    (hrepair : ∀ T : Finset (Fin m), T.card = k+1 →      (¬∃ a, a ∉ T ∧ ∀ b ∈ T, R a b) →      ∃ x : Fin q, ∀ a ∈ T, H x (f a) ∧ H (f a) x)    (U : Fin n → Finset (Fin q))    (hU : ∀ v, WellFounded (fun a b : {a : Fin q // a ∈ U v} => H a.val b.val))    (hhalf : ∀ a, n ≤ 2*(univ.filter fun v => a∈U v).card) : False := by  classical  let V : Fin n → Finset (Fin m) := fun v => univ.filter fun a => f a ∈ U v  apply condorcet_minimal_predecessor_coalition_completion_exclusion m n k hn hk R    hroot hminimal V  · intro v    let g : {a : Fin m // a∈V v} → {a : Fin q // a∈U v} :=      fun a => ⟨f a.val,(mem_filter.mp a.property).2⟩    exact (InvImage.wf g (hU v)).mono (fun a b hab => hmap a b hab)  · intro a    simpa [V] using hhalf (f a)  · intro T hT hbad    obtain ⟨x,hx⟩ := hrepair T hT hbad    refine ⟨univ.filter (fun v => x ∈ U v),hhalf x,?_⟩    intro v hv a ha hmem    have hxU := (mem_filter.mp hv).2    have haU := (mem_filter.mp hmem).2    exact (hU v).asymmetric (a := ⟨x,hxU⟩) (b := ⟨f a,haU⟩) (hx a ha).1 (hx a ha).2
See it in the graphDiscuss this resultChallenge it