condorcet_minimal_predecessor_reciprocal_completion_integer_weights
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
- 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_undominated_extensionFor every natural k, a finite relation globally minimal under induced restriction among S_k relations has an undominated set of exactly…
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.
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.
classical let F : Finset (Finset (Fin m)) := univ.filter fun T => T.card = k+1 ∧ ¬∃ a,a∉T ∧ ∀ b∈T,R a b
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.
uses
condorcet_minimal_predecessor_undominated_extension,mem_univhave 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⟩⟩
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).
uses
mem_univhave 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⟩
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.
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
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.
uses
condorcet_minimal_predecessor_integer_reciprocal_separatorobtain ⟨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⟩)
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.
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
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_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⟩