AFTD Auto-Formalizing Theoretical Domains

condorcet_minimal_predecessor_reciprocal_completion_integer_weights

theoremverified

If a globally minimal finite S_k core with k positive maps into a finite relation, preserving arrows, and every missing (k+1)-set has a common reciprocal neighbor there, then natural-number vertex weights put every induced acyclic subset strictly below half the total. This strengthens the earlier real-weight existence result to a direct integer construction for the same structural family; arbitrary one-way repairs remain outside its hypotheses.

Statement

theorem condorcet_minimal_predecessor_reciprocal_completion_integer_weights
    (m q k : ℕ) (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) :
    ∃ w : Fin q → ℕ, ∀ A : Finset (Fin q),
      WellFounded (fun a b : {a : Fin q // a∈A} => H a.val b.val) →
      2*(∑ a∈A,w a) < ∑ a,w a
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 2

The proof, explained

The proof reduces the theorem to the master separation result condorcet_minimal_predecessor_integer_reciprocal_separator by explicitly packaging the missing (k+1)-subsets. It defines F to be the collection of all (k+1)-subsets of Fin m that have no common external predecessor under R, and proves F is nonempty using the global minimality of the S_k core. Applying the reciprocal completion hypothesis along with the axiom of choice produces a function g selecting a reciprocal neighbor in Fin q for each member of F. Finally, applying the integer reciprocal separator theorem with F and g yields the desired integer weighting separating all induced acyclic subsets below half of the total weight.

  1. Enable classical reasoning and define the family F of (k+1)-subsets of Fin m lacking an external common predecessor under R.

    Working classically, the family F is defined by filtering the universal finset of subsets of Fin m to those T of size k + 1 for which there is no vertex a ∉ T that is an R-predecessor to every element of T.

    lines 21–23

      classical
      let F : Finset (Finset (Fin m)) := univ.filter fun T =>
        T.card = k+1 ∧ ¬∃ a,a∉T ∧ ∀ b∈T,R a b
  2. The family F is nonempty.

    By condorcet_minimal_predecessor_undominated_extension, the global minimality of the S_k core guarantees the existence of a subset T of cardinality k + 1 with no external common predecessor. Since T satisfies the filtering predicate and belongs to the universal set by mem_univ, T is an element of F.

    lines 24–27

    uses condorcet_minimal_predecessor_undominated_extension, mem_univ

      have hF : F.Nonempty := by
        obtain ⟨T,hTc,hTb⟩ := condorcet_minimal_predecessor_undominated_extension
          m k R hroot hminimal
        exact ⟨T,mem_filter.mpr ⟨mem_univ _,hTc,hTb⟩⟩
  3. Every subset in F has cardinality k + 1, and conversely every size-(k+1) subset without an external predecessor belongs to F.

    Unpacking membership in F confirms that every T ∈ F has cardinality k + 1 (hcard). Conversely, any subset T of size k + 1 lacking an external common predecessor satisfies the membership conditions for the filter and Finset.univ (via mem_univ), and thus belongs to F (hcomplete).

    lines 28–31

    uses mem_univ

      have hcard : ∀ T∈F,T.card=k+1 := fun T hT => (mem_filter.mp hT).2.1
      have hcomplete : ∀ T : Finset (Fin m), T.card=k+1 →
          (¬∃ a,a∉T ∧ ∀ b∈T,R a b) → T∈F :=
        fun T hc hb => mem_filter.mpr ⟨mem_univ _,hc,hb⟩
  4. There exists a choice function g : F → Fin q associating each T ∈ F with a reciprocal neighbor to f(T).

    For each T ∈ F, its cardinality is k + 1 and it lacks an external predecessor, so the hypothesis hrepair provides an element x ∈ Fin q that is reciprocally connected to every vertex in f(T). Applying the axiom of choice (choose) to this existential property yields a function g : F → Fin q witnessing the reciprocal neighbor property for each T ∈ F.

    lines 32–36

      have hex : ∀ T : {T : Finset (Fin m) // T∈F},
          ∃ x : Fin q, ∀ a∈T.val,H x (f a) ∧ H (f a) x := by
        intro T
        exact hrepair T.val (mem_filter.mp T.property).2.1 (mem_filter.mp T.property).2.2
      choose g hg using hex
  5. There exists an integer weight function w : Fin q → ℕ strictly separating all induced acyclic subsets below half of the total weight.

    We invoke condorcet_minimal_predecessor_integer_reciprocal_separator with the relation R, the target relation H, the homomorphism f, the family F, its nonemptiness hF, its cardinality and completeness properties, and the choice function g. This provides an integer weighting w : Fin q → ℕ such that every subset whose induced subrelation under H is well-founded has total weight strictly less than half the total sum of weights.

    lines 37–39

    uses condorcet_minimal_predecessor_integer_reciprocal_separator

      obtain ⟨w,_,hw⟩ := condorcet_minimal_predecessor_integer_reciprocal_separator
        m q k hk R H hroot hminimal F hF hcard hcomplete f g hmap
        (fun T a ha => ⟨(hg T a ha).2,(hg T a ha).1⟩)
  6. The weight function w witnesses the theorem.

    We package the constructed integer weight function w together with its separation property hw to conclude the existential goal.

    line 40

      exact ⟨w,hw⟩
condorcet_minimal_predecessor_undominated_extension
In a globally minimal finite relation satisfying the S_k property, there exists a subset of cardinality k + 1 that has no common predecessor outside itself.
mem_univ
Every element of a finite type is an element of its universal finset Finset.univ.
condorcet_minimal_predecessor_integer_reciprocal_separator
Given a globally minimal S_k core mapping into a finite relation with a non-empty family of missing (k+1)-sets equipped with reciprocal neighbors, there exists an integer weighting such that every induced acyclic subset has weight strictly less than half the total.

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_reciprocal_completion_integer_weights    (m q k : ℕ) (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) :    ∃ w : Fin q → ℕ, ∀ A : Finset (Fin q),      WellFounded (fun a b : {a : Fin q // a∈A} => H a.val b.val) →      2*(∑ a∈A,w a) < ∑ a,w a := by  classical  let F : Finset (Finset (Fin m)) := univ.filter fun T =>    T.card = k+1 ∧ ¬∃ a,a∉T ∧ ∀ b∈T,R a b  have hF : F.Nonempty := by    obtain ⟨T,hTc,hTb⟩ := condorcet_minimal_predecessor_undominated_extension      m k R hroot hminimal    exact ⟨T,mem_filter.mpr ⟨mem_univ _,hTc,hTb⟩⟩  have hcard : ∀ T∈F,T.card=k+1 := fun T hT => (mem_filter.mp hT).2.1  have hcomplete : ∀ T : Finset (Fin m), T.card=k+1 →      (¬∃ a,a∉T ∧ ∀ b∈T,R a b) → T∈F :=    fun T hc hb => mem_filter.mpr ⟨mem_univ _,hc,hb⟩  have hex : ∀ T : {T : Finset (Fin m) // T∈F},      ∃ x : Fin q, ∀ a∈T.val,H x (f a) ∧ H (f a) x := by    intro T    exact hrepair T.val (mem_filter.mp T.property).2.1 (mem_filter.mp T.property).2.2  choose g hg using hex  obtain ⟨w,_,hw⟩ := condorcet_minimal_predecessor_integer_reciprocal_separator    m q k hk R H hroot hminimal F hF hcard hcomplete f g hmap    (fun T a ha => ⟨(hg T a ha).2,(hg T a ha).1⟩)  exact ⟨w,hw⟩
See it in the graphDiscuss this resultChallenge it