condorcet_minimal_predecessor_canonical_completion
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
- condorcet_minimal_predecessor_completion_integer_certificateFor a globally minimal S_k core and a nonempty uniform family F containing every undominated (k+1)-set, the incidence weights Z*d(a) on…
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.
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.
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
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.
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
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.
uses
mem_filter,mem_univby_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
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).
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
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).
uses
mem_filter,mem_univ,mem_mapby_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
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.
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
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.
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)
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.
uses
mem_image,disjoint_left,mem_filterhave 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
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|.
uses
condorcet_minimal_predecessor_completion_integer_certificate,card_image_of_injective,Subtype.val_injectivehave 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
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|.
uses
Fintype.sum_sum_type,sum_filter,mul_sum,Nat.mul_commhave 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]
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.
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.
- The step proving disjointness between the core subset A and each adjoined set T in C relies on the fact that any mutual edge between inl a and inr T creates a 2-cycle, which contradicts well-foundedness via asymmetry (hX.asymmetric).
- The weight bound is deduced by applying the external certificate theorem condorcet_minimal_predecessor_completion_integer_certificate and algebraically matching the sums over the sum type with the terms of that certificate.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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