AFTD Auto-Formalizing Theoretical Domains

condorcet_minimal_predecessor_integer_reciprocal_separator

theoremverified

Given the same minimal core and uniform complete repair family, let the core map into any finite relation and choose a reciprocal common neighbor for each repair set. There are natural-number weights on the target, with explicit total Z*((k+1)*Z)+((k+1)*Z-1)*Z, strictly separating every induced acyclic subset below half. Neither the core map nor the chosen repair map needs to be injective.

Statement

theorem condorcet_minimal_predecessor_integer_reciprocal_separator
    (m q k : ℕ) (hk : 0 < k)
    (R : Fin m → Fin m → Prop) (H : Fin q → Fin q → 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)
    (F : Finset (Finset (Fin m))) (hF : F.Nonempty)
    (hcard : ∀ T ∈ F, T.card = k+1)
    (hcomplete : ∀ T : Finset (Fin m), T.card = k+1 →
      (¬∃ a, a ∉ T ∧ ∀ b ∈ T, R a b) → T ∈ F)
    (f : Fin m → Fin q) (g : {T : Finset (Fin m) // T∈F} → Fin q)
    (hmap : ∀ a b, R a b → H (f a) (f b))
    (hrepair : ∀ T, ∀ a∈T.val, H (f a) (g T) ∧ H (g T) (f a)) :
    ∃ w : Fin q → ℕ,
      (∑ x,w x) = F.card*((k+1)*F.card)+((k+1)*F.card-1)*F.card ∧
      ∀ X : Finset (Fin q),
        WellFounded (fun a b : {a : Fin q // a∈X} => H a.val b.val) →
        2*(∑ x∈X,w x)<∑ x,w x
Source
IN-383, OP-19 campaign session 9, 2026-10-30. Constructive completion of the minimal-core incidence argument developed in this session; all four proofs were scratch-checked together in CanonicalAndTransport3.log. General supporting route lemmas, not a new election bound or a research novelty claim.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The proof transfers an integer certificate from the core digraph (Fin m, R) and repair family F to the target digraph (Fin q, H) via pushforward weights. Each core vertex a has weight |F|*d(a) pushed forward along f, and each repair set T ∈ F has weight c = (k+1)*|F|-1 pushed forward along g. For any acyclic subset X ⊆ Fin q, its core preimage f⁻¹(X) is acyclic in R, while the reciprocal repair edges force f⁻¹(X) to be disjoint from every repair set T with g(T) ∈ X (as any intersection would produce a 2-cycle in X). The strict majority separation then follows directly by applying the core integer certificate theorem to these preimages.

  1. Define the hypergraph degree d on core vertices, the constant c, and the pushforward weight function w on the target relation.

    For each core vertex a, let d(a) be the number of repair sets in F containing a. Let c = (k+1)*|F| - 1. The target weight function w assigns to each vertex x ∈ Fin q the sum of |F|*d(a) over all core vertices a with f(a) = x, plus c for every repair set T ∈ F with g(T) = x.

    lines 26–31

      classical
      let d : Fin m → ℕ := fun a => (F.filter fun T => a∈T).card
      let c := (k+1)*F.card-1
      let w : Fin q → ℕ := fun x =>
        (∑ a : Fin m,if f a=x then F.card*d a else 0)+
        (∑ T : {T : Finset (Fin m) // T∈F},if g T=x then c else 0)
  2. Establish the pushforward summation formula `hpush`.

    For any function j : α → Fin q on a finite type and weight function v : α → ℕ, summing the fiber indicators over x ∈ X swaps with the inner sum via `sum_comm`, and simplifies via `sum_filter` to the sum of v(a) over the preimage j⁻¹(X).

    lines 32–37

    uses sum_comm, sum_filter

      have hpush {α : Type} [Fintype α] (j : α → Fin q) (v : α → ℕ)
          (X : Finset (Fin q)) :
          (∑ x∈X, ∑ a,if j a=x then v a else 0) =
            ∑ a∈univ.filter (fun a => j a∈X),v a := by
        rw [sum_comm]
        simp [sum_filter]
  3. Express the total weight of any subset X ⊆ Fin q in terms of the preimages under f and g (`hmass`).

    Expanding the definition of w on X, distributing the summation over addition with `sum_add_distrib`, and applying `hpush` to both the vertex pushforward and the repair pushforward yields |F| * ∑_{a ∈ f⁻¹(X)} d(a) + c * |g⁻¹(X)|.

    lines 38–43

    uses sum_add_distrib, mul_sum, Nat.mul_comm

      have hmass (X : Finset (Fin q)) :
          (∑ x∈X,w x) = F.card*(∑ a∈univ.filter (fun a => f a∈X),d a)+
            c*(univ.filter fun T => g T∈X).card := by
        dsimp only [w]
        rw [sum_add_distrib,hpush,hpush,← mul_sum]
        simp [Nat.mul_comm]
  4. Obtain the total core degree sum and the separation bound from the core certificate theorem.

    Applying `condorcet_minimal_predecessor_completion_integer_certificate` to the core relation and repair family F yields two conclusions: the total core degree ∑_a d(a) = (k+1)*|F|, and a strict upper bound on 2*(|F|*∑_{a∈A} d(a) + c*|C|) for any well-founded A and disjoint subfamily C ⊆ F.

    lines 44–46

    uses condorcet_minimal_predecessor_completion_integer_certificate

      have hcert := condorcet_minimal_predecessor_completion_integer_certificate
        m k hk R hroot hminimal F hF hcard hcomplete
      have hdegree : (∑ a,d a) = (k+1)*F.card := hcert.1
  5. Compute the total weight of the target space (`htotal`).

    Applying `hmass` to the universal set univ on Fin q and substituting the total degree sum ∑_a d(a) = (k+1)*|F| gives the exact total weight |F|*((k+1)*|F|) + c*|F|.

    lines 47–49

    uses mem_univ, filter_true, card_univ, Fintype.card_coe

      have htotal : (∑ x,w x) = F.card*((k+1)*F.card)+c*F.card := by
        have h := hmass univ
        simpa only [mem_univ,filter_true,card_univ,Fintype.card_coe,hdegree] using h
  6. Provide w and its total sum, and define the preimages A = f⁻¹(X) and C ⊆ F for an assumed acyclic set X.

    Witness the weight function w and the total weight `htotal`. Assume X ⊆ Fin q is well-founded under H. Let A ⊆ Fin m be the preimage f⁻¹(X), B be the set of repair sets T ∈ F with g(T) ∈ X, and C ⊆ Finset (Fin m) be the image of B under subtype valuation.

    lines 50–54

      refine ⟨w,htotal,?_⟩
      intro X hX
      let A : Finset (Fin m) := univ.filter fun a => f a∈X
      let B : Finset {T : Finset (Fin m) // T∈F} := univ.filter fun T => g T∈X
      let C : Finset (Finset (Fin m)) := B.image Subtype.val
  7. The preimage A is well-founded under the core relation R.

    The mapping f maps R-edges to H-edges. Since H on X is well-founded, the inverse image relation under f is well-founded by `InvImage.wf`, which pulls well-foundedness back to (A, R).

    lines 55–58

    uses mem_filter, InvImage.wf

      have hA : WellFounded (fun a b : {a : Fin m // a∈A} => R a.val b.val) := by
        let j : {a : Fin m // a∈A} → {a : Fin q // a∈X} :=
          fun a => ⟨f a.val,(mem_filter.mp a.property).2⟩
        exact (InvImage.wf j hX).mono (fun a b hab => hmap a b hab)
  8. The family C is a subset of F.

    Every element of C is the underlying set of some subtype element in B ⊆ {T // T ∈ F}, and thus belongs to F.

    lines 59–62

    uses mem_image

      have hCF : C ⊆ F := by
        intro T hT
        obtain ⟨T,_,rfl⟩ := mem_image.mp hT
        exact T.property
  9. Every repair set T ∈ C is disjoint from A.

    If some a ∈ T were also in A, then f(a) ∈ X and g(T) ∈ X. By the repair property `hrepair`, H(f(a), g(T)) and H(g(T), f(a)), forming a 2-cycle in X. This contradicts the asymmetry of the well-founded relation H on X.

    lines 63–70

    uses mem_image, disjoint_left, mem_filter

      have hCA : ∀ T∈C,Disjoint A T := by
        intro T hT
        obtain ⟨T,hTB,rfl⟩ := mem_image.mp hT
        apply disjoint_left.mpr
        intro a haA haT
        exact hX.asymmetric
          (a := ⟨f a,(mem_filter.mp haA).2⟩)
          (b := ⟨g T,(mem_filter.mp hTB).2⟩) (hrepair T a haT).1 (hrepair T a haT).2
  10. Conclude that 2 * ∑_{x∈X} w(x) < ∑_x w(x).

    Because subtype valuation is injective, |C| = |B| by `card_image_of_injective` and `Subtype.val_injective`. The certificate bound applies to A and C, and rewriting by `hmass` and `htotal` shows that the weight of X is strictly less than half of the total weight.

    lines 71–74

    uses card_image_of_injective, Subtype.val_injective

      have hCcard : C.card = B.card := card_image_of_injective _ Subtype.val_injective
      have hbound := hcert.2 A C hA hCF hCA
      rw [hmass,htotal]
      simpa only [hCcard,hcert.1] using hbound
Subtype.val_injective
The projection mapping a subtype element to its underlying value is injective.
card_image_of_injective
The image of a finite set under an injective function has the same cardinality as the original set.
Fintype.card_coe
The cardinality of a Finset viewed as a coerced subtype equals the cardinality of the Finset itself.
card_univ
The cardinality of the universal Finset of a finite type is the cardinality of the type.
condorcet_minimal_predecessor_completion_integer_certificate
For a minimal predecessor core relation and complete repair family F of (k+1)-sets, the hypergraph degree sum is (k+1)|F|, and for any well-founded subset A of the core and any subfamily B ⊆ F disjoint from A, 2*(|F|*∑_{a∈A} d(a) + c*|B|) < |F|*∑_a d(a) + c*|F| where c = (k+1)|F|-1.
disjoint_left
Two sets are disjoint if and only if no element of the first belongs to the second.
filter_true
Filtering a Finset by an identically true predicate leaves the Finset unchanged.
InvImage.wf
The inverse image of a well-founded relation under any function is well-founded.
mem_filter
An element belongs to the filtered Finset {x ∈ s | p x} if and only if it belongs to s and satisfies p.
mem_image
An element belongs to the image of a Finset under a function if and only if it is the image of some element of the set.
mem_univ
Every element of a finite type belongs to the universal Finset univ.
mul_sum
Multiplication by a scalar distributes over finite sums: a * ∑_{i∈s} f(i) = ∑_{i∈s} a * f(i).
Nat.mul_comm
Multiplication of natural numbers is commutative: n * m = m * n.
sum_add_distrib
Finite sums distribute over addition: ∑_{x∈s} (f(x) + g(x)) = ∑_{x∈s} f(x) + ∑_{x∈s} g(x).
sum_comm
The order of two finite summations can be swapped: ∑_{x∈s} ∑_{y∈t} f(x, y) = ∑_{y∈t} ∑_{x∈s} f(x, y).
sum_filter
The sum of a function over a filtered Finset equals the sum over the whole Finset of the function guarded by the filtering condition (or zero if false).

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 4000000set_option maxRecDepth 10000theorem condorcet_minimal_predecessor_integer_reciprocal_separator    (m q k : ℕ) (hk : 0 < k)    (R : Fin m → Fin m → Prop) (H : Fin q → Fin q → 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)    (F : Finset (Finset (Fin m))) (hF : F.Nonempty)    (hcard : ∀ T ∈ F, T.card = k+1)    (hcomplete : ∀ T : Finset (Fin m), T.card = k+1 →      (¬∃ a, a ∉ T ∧ ∀ b ∈ T, R a b) → T ∈ F)    (f : Fin m → Fin q) (g : {T : Finset (Fin m) // T∈F} → Fin q)    (hmap : ∀ a b, R a b → H (f a) (f b))    (hrepair : ∀ T, ∀ a∈T.val, H (f a) (g T) ∧ H (g T) (f a)) :    ∃ w : Fin q → ℕ,      (∑ x,w x) = F.card*((k+1)*F.card)+((k+1)*F.card-1)*F.card ∧      ∀ X : Finset (Fin q),        WellFounded (fun a b : {a : Fin q // a∈X} => H a.val b.val) →        2*(∑ x∈X,w x)<∑ x,w x := by  classical  let d : Fin m → ℕ := fun a => (F.filter fun T => a∈T).card  let c := (k+1)*F.card-1  let w : Fin q → ℕ := fun x =>    (∑ a : Fin m,if f a=x then F.card*d a else 0)+    (∑ T : {T : Finset (Fin m) // T∈F},if g T=x then c else 0)  have hpush {α : Type} [Fintype α] (j : α → Fin q) (v : α → ℕ)      (X : Finset (Fin q)) :      (∑ x∈X, ∑ a,if j a=x then v a else 0) =        ∑ a∈univ.filter (fun a => j a∈X),v a := by    rw [sum_comm]    simp [sum_filter]  have hmass (X : Finset (Fin q)) :      (∑ x∈X,w x) = F.card*(∑ a∈univ.filter (fun a => f a∈X),d a)+        c*(univ.filter fun T => g T∈X).card := by    dsimp only [w]    rw [sum_add_distrib,hpush,hpush,← mul_sum]    simp [Nat.mul_comm]  have hcert := condorcet_minimal_predecessor_completion_integer_certificate    m k hk R hroot hminimal F hF hcard hcomplete  have hdegree : (∑ a,d a) = (k+1)*F.card := hcert.1  have htotal : (∑ x,w x) = F.card*((k+1)*F.card)+c*F.card := by    have h := hmass univ    simpa only [mem_univ,filter_true,card_univ,Fintype.card_coe,hdegree] using h  refine ⟨w,htotal,?_⟩  intro X hX  let A : Finset (Fin m) := univ.filter fun a => f a∈X  let B : Finset {T : Finset (Fin m) // T∈F} := univ.filter fun T => g T∈X  let C : Finset (Finset (Fin m)) := B.image Subtype.val  have hA : WellFounded (fun a b : {a : Fin m // a∈A} => R a.val b.val) := by    let j : {a : Fin m // a∈A} → {a : Fin q // a∈X} :=      fun a => ⟨f a.val,(mem_filter.mp a.property).2⟩    exact (InvImage.wf j hX).mono (fun a b hab => hmap a b hab)  have hCF : C ⊆ F := by    intro T hT    obtain ⟨T,_,rfl⟩ := mem_image.mp hT    exact T.property  have hCA : ∀ T∈C,Disjoint A T := by    intro T hT    obtain ⟨T,hTB,rfl⟩ := mem_image.mp hT    apply disjoint_left.mpr    intro a haA haT    exact hX.asymmetric      (a := ⟨f a,(mem_filter.mp haA).2⟩)      (b := ⟨g T,(mem_filter.mp hTB).2⟩) (hrepair T a haT).1 (hrepair T a haT).2  have hCcard : C.card = B.card := card_image_of_injective _ Subtype.val_injective  have hbound := hcert.2 A C hA hCF hCA  rw [hmass,htotal]  simpa only [hCcard,hcert.1] using hbound
See it in the graphDiscuss this resultChallenge it