condorcet_minimal_predecessor_completion_integer_certificate
For 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 core vertices and (k+1)Z-1 on repair indices strictly separate every pair consisting of an acyclic core subset A and a subfamily B of repair sets disjoint from A. The theorem states the integer inequality directly, with its exact total weight.
Statement
theorem condorcet_minimal_predecessor_completion_integer_certificate (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 Z := F.card let d : Fin m → ℕ := fun a => (F.filter fun T => a∈T).card let c := (k+1)*Z-1 (∑ a,d a) = (k+1)*Z ∧ ∀ (A : Finset (Fin m)) (B : Finset (Finset (Fin m))), WellFounded (fun a b : {a : Fin m // a∈A} => R a.val b.val) → B ⊆ F → (∀ T ∈ B, Disjoint A T) → 2*(Z*(∑ a∈A,d a)+c*B.card) < Z*(∑ a,d a)+c*Z
- 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 2
- condorcet_minimal_predecessor_acyclic_cutFor k positive, a finite relation globally minimal under induced restriction among relations with the outside common predecessor property…
- condorcet_crossed_uniform_family_incidence_boundFor a nonempty r-uniform family F, a set A that is empty or crosses a member of F, and a subfamily B disjoint from A, let Z be the number…
- Used by 2
- condorcet_minimal_predecessor_integer_reciprocal_separatorGiven the same minimal core and uniform complete repair family, let the core map into any finite relation and choose a reciprocal common…
- condorcet_minimal_predecessor_canonical_completionFor a globally minimal S_k core, k positive, take a nonempty family of (k+1)-sets containing every set with no outside common predecessor.…
The proof, explained
The theorem proves that incidence weights on vertices and repair sets strictly separate any acyclic core subset A from a disjoint subfamily B of (k+1)-sets. First, a double-counting argument shows that the sum of all vertex degrees equals (k+1)|F|. Next, the minimality of the S_k core guarantees that any nonempty acyclic set A is crossed by an undominated (k+1)-set, which belongs to F by completeness. Finally, an incidence bound for crossed uniform families gives Z * ∑_{a ∈ A} d(a) + c * |B| ≤ c * Z, which strictly separates after multiplying by 2 because c * Z < Z * (k+1)Z when |F| > 0.
The total degree of all vertices in F satisfies ∑_a d(a) = (k+1)|F|.
By swapping the order of summation in the double sum representing total vertex incidences, ∑_a d(a) = ∑_a ∑_{T ∈ F} [a ∈ T] = ∑_{T ∈ F} |T|. Since every hyperedge T ∈ F has size k+1, this sum equals (k+1)|F|. Line 36 splits the conjunction, discharging the first conjunct with this equality and leaving the separation inequality.
uses
card_eq_sum_ones,sum_filter,sum_comm,sum_congr,Nat.mul_commclassical dsimp only have hdegree : (∑ a : Fin m, (F.filter fun T => a∈T).card) = (k+1)*F.card := by calc (∑ a : Fin m, (F.filter fun T => a∈T).card) = ∑ a : Fin m, ∑ T∈F, if a∈T then 1 else 0 := by simp only [card_eq_sum_ones,sum_filter] _ = ∑ T∈F, ∑ a : Fin m, if a∈T then 1 else 0 := sum_comm _ = ∑ T∈F, T.card := by simp _ = ∑ T∈F, (k+1) := sum_congr rfl (fun T hT => hcard T hT) _ = (k+1)*F.card := by simp [Nat.mul_comm] refine ⟨hdegree,?_⟩
Either A is empty, or some repair set T ∈ F crosses A (meaning A ∩ T is nonempty and T is not a subset of A).
We split into cases on whether A = ∅. If A is empty, the cut condition holds trivially. If A is nonempty, the lemma condorcet_minimal_predecessor_acyclic_cut provides a (k+1)-element set T crossing A that has no external predecessor dominating all its elements. By completeness of F on undominated (k+1)-sets, T belongs to F, witnessing that F contains a set crossing A.
uses
Or.inl,condorcet_minimal_predecessor_acyclic_cut,nonempty_iff_ne_empty.mpr,Or.inr,mem_inter.mprintro A B hA hBF hB have hcut : A=∅ ∨ ∃ T∈F, (A∩T).Nonempty ∧ ¬T⊆A := by by_cases hempty : A=∅ · exact Or.inl hempty · obtain ⟨T,hTc,hTb,⟨a,haT,haA⟩,⟨b,hbT,hbA⟩⟩ := condorcet_minimal_predecessor_acyclic_cut m k hk R hroot hminimal A (nonempty_iff_ne_empty.mpr hempty) hA exact Or.inr ⟨T,hcomplete T hTc hTb,⟨a,mem_inter.mpr ⟨haA,haT⟩⟩, fun h => hbA (h hbT)⟩
The weighted incidence bound Z * ∑_{a ∈ A} d(a) + c * |B| ≤ c * Z holds, where Z = |F| and c = (k+1)Z - 1.
Applying the project lemma condorcet_crossed_uniform_family_incidence_bound with uniformity r = k+1 to the cut property of A and disjoint subfamily B gives the upper bound c * Z. We also establish that Z > 0 (as F is nonempty) and c + 1 = (k+1)Z for later arithmetic.
uses
condorcet_crossed_uniform_family_incidence_bound,card_pos.mpr,Nat.mul_pos,Nat.sub_add_cancelhave hbound := condorcet_crossed_uniform_family_incidence_bound m (k+1) (by omega) F hF hcard A hcut B hBF hB have hz : 0<F.card := card_pos.mpr hF have hprod : 0<(k+1)*F.card := Nat.mul_pos (by omega) hz have hc : ((k+1)*F.card-1)+1 = (k+1)*F.card := Nat.sub_add_cancel (by omega)
The strict separation inequality 2 * (Z * ∑_{a ∈ A} d(a) + c * |B|) < Z * ∑_a d(a) + c * Z holds.
Rewriting the total degree sum on the right-hand side using the first claim gives Z * (k+1)Z + c * Z. Multiplying the incidence bound by 2 yields 2 * (Z * ∑_{a ∈ A} d(a) + c * |B|) ≤ 2 * c * Z. Because Z > 0, we have c * Z = ((k+1)Z - 1)Z < ((k+1)Z)Z = Z * (k+1)Z, which implies 2 * c * Z < Z * (k+1)Z + c * Z, completing the strict inequality.
uses
Nat.mul_le_mul_left,congrArgrw [hdegree] calc 2*(F.card*(∑ a∈A,(F.filter fun T => a∈T).card)+((k+1)*F.card-1)*B.card) ≤ 2*(((k+1)*F.card-1)*F.card) := Nat.mul_le_mul_left 2 hbound _ < F.card*((k+1)*F.card)+((k+1)*F.card-1)*F.card := by have heq : F.card*((k+1)*F.card) = ((k+1)*F.card-1)*F.card+F.card := by calc F.card*((k+1)*F.card) = F.card*(((k+1)*F.card-1)+1) := congrArg (fun x => F.card*x) hc.symm _ = ((k+1)*F.card-1)*F.card+F.card := by ring omega
card_eq_sum_ones- The cardinality of a finite set equals the sum of 1 over all its elements.
sum_filter- Summing a function over a filtered set equals summing the if-then-else indicator over the entire set.
sum_comm- The order of summation in a finite double sum can be swapped.
sum_congr- Two finite sums are equal if their index sets match and their summands are equal on that set.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
Or.inl- A disjunction P ∨ Q holds if the left disjunct P holds.
condorcet_minimal_predecessor_acyclic_cut- For a minimal S_k core and any nonempty acyclic subset A, there exists an undominated (k+1)-set with elements both inside and outside A.
nonempty_iff_ne_empty.mpr- If a finite set is not equal to the empty set, then it is nonempty.
Or.inr- A disjunction P ∨ Q holds if the right disjunct Q holds.
mem_inter.mpr- An element belongs to the intersection of two sets if it belongs to both sets.
condorcet_crossed_uniform_family_incidence_bound- For an r-uniform family F and a cut A crossed by some member of F (or empty), any subfamily B ⊆ F disjoint from A satisfies |F| * ∑_{a ∈ A} d(a) + (r|F|-1)|B| ≤ (r|F|-1)|F|.
card_pos.mpr- A finite set has strictly positive cardinality if and only if it is nonempty.
Nat.mul_pos- The product of two strictly positive natural numbers is strictly positive.
Nat.sub_add_cancel- If m ≤ n, then (n - m) + m = n.
Nat.mul_le_mul_left- Multiplying both sides of an inequality of natural numbers by a factor preserves the inequality.
congrArg- Applying a function to equal arguments yields equal values: if a = b then f a = f b.
- The proof relies on two external project lemmas: `condorcet_minimal_predecessor_acyclic_cut`, which produces a crossing undominated set from the core minimality assumption, and `condorcet_crossed_uniform_family_incidence_bound`, which provides the non-strict incidence inequality for crossed uniform hypergraphs.
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 30000000set_option maxRecDepth 20000theorem condorcet_minimal_predecessor_completion_integer_certificate (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 Z := F.card let d : Fin m → ℕ := fun a => (F.filter fun T => a∈T).card let c := (k+1)*Z-1 (∑ a,d a) = (k+1)*Z ∧ ∀ (A : Finset (Fin m)) (B : Finset (Finset (Fin m))), WellFounded (fun a b : {a : Fin m // a∈A} => R a.val b.val) → B ⊆ F → (∀ T ∈ B, Disjoint A T) → 2*(Z*(∑ a∈A,d a)+c*B.card) < Z*(∑ a,d a)+c*Z := by classical dsimp only have hdegree : (∑ a : Fin m, (F.filter fun T => a∈T).card) = (k+1)*F.card := by calc (∑ a : Fin m, (F.filter fun T => a∈T).card) = ∑ a : Fin m, ∑ T∈F, if a∈T then 1 else 0 := by simp only [card_eq_sum_ones,sum_filter] _ = ∑ T∈F, ∑ a : Fin m, if a∈T then 1 else 0 := sum_comm _ = ∑ T∈F, T.card := by simp _ = ∑ T∈F, (k+1) := sum_congr rfl (fun T hT => hcard T hT) _ = (k+1)*F.card := by simp [Nat.mul_comm] refine ⟨hdegree,?_⟩ intro A B hA hBF hB have hcut : A=∅ ∨ ∃ T∈F, (A∩T).Nonempty ∧ ¬T⊆A := by by_cases hempty : A=∅ · exact Or.inl hempty · obtain ⟨T,hTc,hTb,⟨a,haT,haA⟩,⟨b,hbT,hbA⟩⟩ := condorcet_minimal_predecessor_acyclic_cut m k hk R hroot hminimal A (nonempty_iff_ne_empty.mpr hempty) hA exact Or.inr ⟨T,hcomplete T hTc hTb,⟨a,mem_inter.mpr ⟨haA,haT⟩⟩, fun h => hbA (h hbT)⟩ have hbound := condorcet_crossed_uniform_family_incidence_bound m (k+1) (by omega) F hF hcard A hcut B hBF hB have hz : 0<F.card := card_pos.mpr hF have hprod : 0<(k+1)*F.card := Nat.mul_pos (by omega) hz have hc : ((k+1)*F.card-1)+1 = (k+1)*F.card := Nat.sub_add_cancel (by omega) rw [hdegree] calc 2*(F.card*(∑ a∈A,(F.filter fun T => a∈T).card)+((k+1)*F.card-1)*B.card) ≤ 2*(((k+1)*F.card-1)*F.card) := Nat.mul_le_mul_left 2 hbound _ < F.card*((k+1)*F.card)+((k+1)*F.card-1)*F.card := by have heq : F.card*((k+1)*F.card) = ((k+1)*F.card-1)*F.card+F.card := by calc F.card*((k+1)*F.card) = F.card*(((k+1)*F.card-1)+1) := congrArg (fun x => F.card*x) hc.symm _ = ((k+1)*F.card-1)*F.card+F.card := by ring omega