condorcet_minimal_predecessor_integer_reciprocal_separator
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
- 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…
- Used by 1
- condorcet_minimal_predecessor_reciprocal_completion_integer_weightsIf 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…
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.
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.
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)
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).
uses
sum_comm,sum_filterhave 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]
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)|.
uses
sum_add_distrib,mul_sum,Nat.mul_commhave 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]
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.
uses
condorcet_minimal_predecessor_completion_integer_certificatehave 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
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|.
uses
mem_univ,filter_true,card_univ,Fintype.card_coehave 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
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.
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
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).
uses
mem_filter,InvImage.wfhave 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)
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.
uses
mem_imagehave hCF : C ⊆ F := by intro T hT obtain ⟨T,_,rfl⟩ := mem_image.mp hT exact T.property
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.
uses
mem_image,disjoint_left,mem_filterhave 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
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.
uses
card_image_of_injective,Subtype.val_injectivehave 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).
- Neither the core mapping f nor the repair mapping g is required to be injective: the weight on each target vertex is defined by summing the weights of all preimages in the core and in the repair family.
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_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