AFTD Auto-Formalizing Theoretical Domains

condorcet_minimal_predecessor_canonical_completion

theoremverified

For a globally minimal S_k core, k positive, take a nonempty family of (k+1)-sets containing every set with no outside common predecessor. Adjoin one vertex per family member, put arrows from every core vertex to every new vertex, and from each new vertex to the members of its set. The resulting relation has S_(k+1), and the explicit integer incidence weights put every induced acyclic subset strictly below half the total.

Statement

theorem condorcet_minimal_predecessor_canonical_completion
    (m k : ℕ) (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)
    (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) :
    let Q := Fin m ⊕ {T : Finset (Fin m) // T ∈ F}
    let H : Q → Q → Prop := fun a b => match a,b with
      | .inl a,.inl b => R a b
      | .inl _,.inr _ => True
      | .inr T,.inl a => a ∈ T.val
      | .inr _,.inr _ => False
    let w : Q → ℕ := fun a => match a with
      | .inl a => F.card * (F.filter fun T => a∈T).card
      | .inr _ => (k+1)*F.card-1
    (∀ J : Finset Q, J.card ≤ k+1 →
      ∃ a, a ∉ J ∧ ∀ b ∈ J, H a b) ∧
    (∀ A : Finset Q,
      WellFounded (fun a b : {a : 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 1

The proof, explained

The proof establishes the canonical completion of a minimal S_k tournament core R by adjoining one vertex for each hyperedge in a complete (k+1)-family F. To verify property S_(k+1), any test set J of size at most k+1 either has at most k core vertices—where an outside core predecessor exists by S_k—or consists of k+1 core vertices with no outside core root, in which case the adjoined vertex representing that set dominates all of J. For the weight bound, any acyclic subset X decomposes into core vertices and adjoined vertices that cannot intersect without creating 2-cycles; applying an integer certificate theorem then proves that X carries strictly less than half the total weight.

  1. Set up definitions and split the goal into the S_(k+1) property and the acyclic weight bound.

    We define the extended vertex set Q = Fin m ⊕ {T // T ∈ F}, the relation H extending R, and the weight function w. Using constructor, the theorem is split into two independent goals: showing that H satisfies property S_(k+1), and showing that every acyclic subset has weight strictly less than half the total.

    lines 31–44

      classical
      let Q := Fin m ⊕ {T : Finset (Fin m) // T ∈ F}
      let H : Q → Q → Prop := fun a b => match a,b with
        | .inl a,.inl b => R a b
        | .inl _,.inr _ => True
        | .inr T,.inl a => a ∈ T.val
        | .inr _,.inr _ => False
      let w : Q → ℕ := fun a => match a with
        | .inl a => F.card * (F.filter fun T => a∈T).card
        | .inr _ => (k+1)*F.card-1
      change (∀ J : Finset Q, J.card ≤ k+1 → ∃ a, a∉J ∧ ∀ b∈J,H a b) ∧
        (∀ A : Finset Q, WellFounded (fun a b : {a : Q // a∈A} => H a.val b.val) →
          2*(∑ a∈A,w a)<∑ a,w a)
      constructor
  2. Project J onto the core vertices A, giving |A| ≤ k + 1.

    Given a subset J ⊆ Q with |J| ≤ k + 1, we define A to be the set of core vertices whose canonical embedding lies in J. Since the image inl(A) is a subset of J, its cardinality |A| is bounded by |J| ≤ k + 1.

    lines 45–53

    uses mem_map, mem_filter, card_le_card

      · intro J hJ
        let A : Finset (Fin m) := univ.filter fun a => (Sum.inl a : Q)∈J
        have hAJ : A.map (Function.Embedding.inl) ⊆ J := by
          intro x hx
          obtain ⟨a,ha,rfl⟩ := mem_map.mp hx
          exact (mem_filter.mp ha).2
        have hAle : A.card ≤ k+1 := by
          have h := card_le_card hAJ
          simpa using h.trans hJ
  3. If |A| ≤ k, an outside common predecessor for J exists in the core.

    By the S_k property of the core (hroot), there is a core vertex a ∉ A that dominates all of A under R. The corresponding extended vertex inl a is not in J, dominates all core vertices in J via R, and dominates all new vertices in J by definition of H.

    lines 54–61

    uses mem_filter, mem_univ

        by_cases hAk : A.card ≤ k
        · obtain ⟨a,ha,har⟩ := hroot A hAk
          refine ⟨Sum.inl a,?_,?_⟩
          · exact fun h => ha (mem_filter.mpr ⟨mem_univ _,h⟩)
          · intro b hb
            cases b with
            | inl b => exact har b (mem_filter.mpr ⟨mem_univ _,hb⟩)
            | inr b => trivial
  4. If |A| > k, then |A| = k + 1 and J consists solely of core vertices: J = inl(A). automation

    Because |A| ≤ k + 1 and ¬(|A| ≤ k), linear arithmetic gives |A| = k + 1. Since inl(A) ⊆ J and |J| ≤ k + 1, the subset inclusion must be an equality: J = inl(A).

    lines 62–66

    uses eq_of_subset_of_card_le

        · have hAc : A.card = k+1 := by omega
          have hEq : J = A.map Function.Embedding.inl := by
            symm
            apply eq_of_subset_of_card_le hAJ
            simpa [hAc] using hJ
  5. If A has an outside common predecessor in the core, it serves as a common predecessor for J.

    If there is some a ∉ A dominating all of A under R, then inl a ∉ J dominates every element of J = inl(A).

    lines 67–74

    uses mem_filter, mem_univ, mem_map

          by_cases hAroot : ∃ a, a∉A ∧ ∀ b∈A,R a b
          · obtain ⟨a,ha,har⟩ := hAroot
            refine ⟨Sum.inl a,?_,?_⟩
            · exact fun h => ha (mem_filter.mpr ⟨mem_univ _,h⟩)
            · intro b hb
              rw [hEq] at hb
              obtain ⟨b,hbin,rfl⟩ := mem_map.mp hb
              exact har b hbin
  6. If A has no outside predecessor in the core, the adjoined vertex corresponding to A dominates all of J.

    By completeness of F (hcomplete), since |A| = k + 1 and A has no outside predecessor, A belongs to F. The adjoined vertex inr ⟨A, ...⟩ does not belong to J (since J contains only core vertices) and dominates every inl b ∈ J = inl(A) because b ∈ A. This completes the S_(k+1) branch.

    lines 75–82

    uses mem_map

          · let T : {T : Finset (Fin m) // T∈F} := ⟨A,hcomplete A hAc hAroot⟩
            refine ⟨Sum.inr T,?_,?_⟩
            · rw [hEq]
              simp [Function.Embedding.inl]
            · intro b hb
              rw [hEq] at hb
              obtain ⟨b,hbin,rfl⟩ := mem_map.mp hb
              exact hbin
  7. Decompose an acyclic subset X ⊆ Q and deduce well-foundedness on its core vertices A.

    Let X ⊆ Q be an acyclic subset. Decompose X into its core vertices A = {a | inl a ∈ X}, its adjoined vertices B = {T | inr T ∈ X}, and their underlying sets C = {T.val | T ∈ B}. The relation R restricted to A is well-founded because it is a subrelation of the pullback of the well-founded relation H on X along the embedding inl.

    lines 83–91

    uses mem_filter, InvImage.wf, WellFounded.mono

      · intro X hX
        let A : Finset (Fin m) := univ.filter fun a => (Sum.inl a : Q)∈X
        let B : Finset {T : Finset (Fin m) // T∈F} :=
          univ.filter fun T => (Sum.inr T : Q)∈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 f : {a : Fin m // a∈A} → {a : Q // a∈X} :=
            fun a => ⟨Sum.inl a.val,(mem_filter.mp a.property).2⟩
          exact (InvImage.wf f hX).mono (fun _ _ h => h)
  8. The core subset A is disjoint from every adjoined set T in C.

    If some vertex a ∈ A were also in T ∈ C, then both inl a and inr T would belong to X. Under H, inl a dominates inr T (all core vertices dominate adjoined vertices) and inr T dominates inl a (since a ∈ T), producing a 2-cycle. This contradicts the asymmetry of the well-founded relation H on X, so A and T must be disjoint.

    lines 92–103

    uses mem_image, disjoint_left, mem_filter

        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 := ⟨Sum.inl a,(mem_filter.mp haA).2⟩)
            (b := ⟨Sum.inr T,(mem_filter.mp hTB).2⟩) (by trivial) haT
  9. Apply the integer certificate inequality to A and C.

    Since A is well-founded under R, C ⊆ F, and A is disjoint from every T ∈ C, the second conclusion of condorcet_minimal_predecessor_completion_integer_certificate applies to A and C. Injectivity of the subtype coercion ensures |C| = |B|.

    lines 104–106

    uses condorcet_minimal_predecessor_completion_integer_certificate, card_image_of_injective, Subtype.val_injective

        have hbound := (condorcet_minimal_predecessor_completion_integer_certificate
          m k hk R hroot hminimal F hF hcard hcomplete).2 A C hA hCF hCA
        have hCcard : C.card = B.card := card_image_of_injective _ Subtype.val_injective
  10. Express the sum of weights over X and Q in terms of the certificate quantities.

    Summing w over X splits into the sum over inl(A), which equals |F| ∑_{a ∈ A} d(a), and the sum over inr(B), which equals ((k+1)|F| - 1) |C|. Similarly, the sum over all of Q equals |F| ∑_{a} d(a) + ((k+1)|F| - 1) |F|.

    lines 107–125

    uses Fintype.sum_sum_type, sum_filter, mul_sum, Nat.mul_comm

        have hsumX : (∑ x∈X,w x) =
            F.card*(∑ a∈A,(F.filter fun T => a∈T).card)+((k+1)*F.card-1)*C.card := by
          have hXu : (∑ x∈X,w x) = ∑ x : Q, if x∈X then w x else 0 := by
            simp
          rw [hXu,Fintype.sum_sum_type]
          change (∑ a : Fin m, if (Sum.inl a : Q)∈X then
              F.card*(F.filter fun T => a∈T).card else 0) +
            (∑ T : {T : Finset (Fin m) // T∈F}, if (Sum.inr T : Q)∈X then
              (k+1)*F.card-1 else 0) = _
          rw [← sum_filter,← sum_filter]
          change (∑ a∈A,F.card*(F.filter fun T => a∈T).card)+
            (∑ _T∈B,((k+1)*F.card-1)) = _
          rw [mul_sum, hCcard]
          simp [Nat.mul_comm]
        have hsum : (∑ x : Q,w x) =
            F.card*(∑ a : Fin m,(F.filter fun T => a∈T).card)+
              ((k+1)*F.card-1)*F.card := by
          rw [Fintype.sum_sum_type]
          simp [w,mul_sum,Nat.mul_comm]
  11. Conclude that 2 ∑_{x ∈ X} w(x) < ∑_{x ∈ Q} w(x).

    Rewriting the sums using the explicit formulas derived in the previous step transforms the goal into the certificate inequality obtained earlier, completing the proof.

    lines 126–127

        rw [hsumX,hsum]
        exact hbound
mem_map
An element belongs to the image under an embedding if and only if it is the image of an element in the source finset.
mem_filter
An element belongs to a filtered finset if and only if it is in the finset and satisfies the predicate.
mem_univ
Every element of a finite type belongs to the universal finset univ.
card_le_card
A subset has cardinality at most that of its superset.
eq_of_subset_of_card_le
If s is a subset of t and t has cardinality at most that of s, then s = t.
InvImage.wf
The inverse image of a well-founded relation under any function is well-founded.
WellFounded.mono
A subrelation of a well-founded relation is well-founded.
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 in the finset.
disjoint_left
Two finsets are disjoint if and only if no element of the first belongs to the second.
condorcet_minimal_predecessor_completion_integer_certificate
For a minimal S_k tournament core and complete (k+1)-hypergraph F, any well-founded core subset A and subcollection B ⊆ F mutually disjoint from A satisfy the certificate inequality 2(|F| ∑_{a ∈ A} d(a) + c|B|) < |F| ∑_a d(a) + c|F|.
card_image_of_injective
The image of a finset under an injective function has the same cardinality as the finset.
Subtype.val_injective
The coercion from a subtype to the underlying type is injective.
Fintype.sum_sum_type
The sum of a function over a sum type α ⊕ β equals the sum over α plus the sum over β.
sum_filter
Summing over the elements satisfying a predicate equals summing the conditional expression (if p x then f x else 0).
mul_sum
Multiplication distributes over a finite sum from the left: a * ∑ x, f x = ∑ x, a * f x.
Nat.mul_comm
Multiplication of natural numbers is commutative.

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_canonical_completion    (m k : ℕ) (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)    (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) :    let Q := Fin m ⊕ {T : Finset (Fin m) // T ∈ F}    let H : Q → Q → Prop := fun a b => match a,b with      | .inl a,.inl b => R a b      | .inl _,.inr _ => True      | .inr T,.inl a => a ∈ T.val      | .inr _,.inr _ => False    let w : Q → ℕ := fun a => match a with      | .inl a => F.card * (F.filter fun T => a∈T).card      | .inr _ => (k+1)*F.card-1    (∀ J : Finset Q, J.card ≤ k+1 →      ∃ a, a ∉ J ∧ ∀ b ∈ J, H a b) ∧    (∀ A : Finset Q,      WellFounded (fun a b : {a : Q // a∈A} => H a.val b.val) →      2*(∑ a∈A,w a) < ∑ a,w a) := by  classical  let Q := Fin m ⊕ {T : Finset (Fin m) // T ∈ F}  let H : Q → Q → Prop := fun a b => match a,b with    | .inl a,.inl b => R a b    | .inl _,.inr _ => True    | .inr T,.inl a => a ∈ T.val    | .inr _,.inr _ => False  let w : Q → ℕ := fun a => match a with    | .inl a => F.card * (F.filter fun T => a∈T).card    | .inr _ => (k+1)*F.card-1  change (∀ J : Finset Q, J.card ≤ k+1 → ∃ a, a∉J ∧ ∀ b∈J,H a b) ∧    (∀ A : Finset Q, WellFounded (fun a b : {a : Q // a∈A} => H a.val b.val) →      2*(∑ a∈A,w a)<∑ a,w a)  constructor  · intro J hJ    let A : Finset (Fin m) := univ.filter fun a => (Sum.inl a : Q)∈J    have hAJ : A.map (Function.Embedding.inl) ⊆ J := by      intro x hx      obtain ⟨a,ha,rfl⟩ := mem_map.mp hx      exact (mem_filter.mp ha).2    have hAle : A.card ≤ k+1 := by      have h := card_le_card hAJ      simpa using h.trans hJ    by_cases hAk : A.card ≤ k    · obtain ⟨a,ha,har⟩ := hroot A hAk      refine ⟨Sum.inl a,?_,?_⟩      · exact fun h => ha (mem_filter.mpr ⟨mem_univ _,h⟩)      · intro b hb        cases b with        | inl b => exact har b (mem_filter.mpr ⟨mem_univ _,hb⟩)        | inr b => trivial    · have hAc : A.card = k+1 := by omega      have hEq : J = A.map Function.Embedding.inl := by        symm        apply eq_of_subset_of_card_le hAJ        simpa [hAc] using hJ      by_cases hAroot : ∃ a, a∉A ∧ ∀ b∈A,R a b      · obtain ⟨a,ha,har⟩ := hAroot        refine ⟨Sum.inl a,?_,?_⟩        · exact fun h => ha (mem_filter.mpr ⟨mem_univ _,h⟩)        · intro b hb          rw [hEq] at hb          obtain ⟨b,hbin,rfl⟩ := mem_map.mp hb          exact har b hbin      · let T : {T : Finset (Fin m) // T∈F} := ⟨A,hcomplete A hAc hAroot⟩        refine ⟨Sum.inr T,?_,?_⟩        · rw [hEq]          simp [Function.Embedding.inl]        · intro b hb          rw [hEq] at hb          obtain ⟨b,hbin,rfl⟩ := mem_map.mp hb          exact hbin  · intro X hX    let A : Finset (Fin m) := univ.filter fun a => (Sum.inl a : Q)∈X    let B : Finset {T : Finset (Fin m) // T∈F} :=      univ.filter fun T => (Sum.inr T : Q)∈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 f : {a : Fin m // a∈A} → {a : Q // a∈X} :=        fun a => ⟨Sum.inl a.val,(mem_filter.mp a.property).2⟩      exact (InvImage.wf f hX).mono (fun _ _ h => h)    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 := ⟨Sum.inl a,(mem_filter.mp haA).2⟩)        (b := ⟨Sum.inr T,(mem_filter.mp hTB).2⟩) (by trivial) haT    have hbound := (condorcet_minimal_predecessor_completion_integer_certificate      m k hk R hroot hminimal F hF hcard hcomplete).2 A C hA hCF hCA    have hCcard : C.card = B.card := card_image_of_injective _ Subtype.val_injective    have hsumX : (∑ x∈X,w x) =        F.card*(∑ a∈A,(F.filter fun T => a∈T).card)+((k+1)*F.card-1)*C.card := by      have hXu : (∑ x∈X,w x) = ∑ x : Q, if x∈X then w x else 0 := by        simp      rw [hXu,Fintype.sum_sum_type]      change (∑ a : Fin m, if (Sum.inl a : Q)∈X then          F.card*(F.filter fun T => a∈T).card else 0) +        (∑ T : {T : Finset (Fin m) // T∈F}, if (Sum.inr T : Q)∈X then          (k+1)*F.card-1 else 0) = _      rw [← sum_filter,← sum_filter]      change (∑ a∈A,F.card*(F.filter fun T => a∈T).card)+        (∑ _T∈B,((k+1)*F.card-1)) = _      rw [mul_sum, hCcard]      simp [Nat.mul_comm]    have hsum : (∑ x : Q,w x) =        F.card*(∑ a : Fin m,(F.filter fun T => a∈T).card)+          ((k+1)*F.card-1)*F.card := by      rw [Fintype.sum_sum_type]      simp [w,mul_sum,Nat.mul_comm]    rw [hsumX,hsum]    exact hbound
See it in the graphDiscuss this resultChallenge it