condorcet_minimal_predecessor_reciprocal_completion_separation
Under the preceding minimal-core and reciprocal-repair hypotheses, nonnegative real vertex weights on the larger relation put every induced acyclic subset strictly below half the total. This excludes the entire reciprocal completion construction for arbitrary core size, but does not handle arbitrary S3 relations.
Statement
theorem condorcet_minimal_predecessor_reciprocal_completion_separation (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, 0 ≤ w a) ∧ ∀ 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. 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_reciprocal_completion_exclusionLet a globally minimal finite S_k core, k positive, map by a relation-preserving function into another finite relation. If every…
- condorcet_dimension_le_three_iff_acyclic_weight_separationThe following two universal statements are equivalent. First, every finite election with a positive number of voters and strict rankings…
The proof, explained
The theorem is proved by linear programming duality and contradiction. By condorcet_half_cover_acyclic_half_cover_duality, the existence of separating weights on vertices is equivalent to the nonexistence of an acyclic half-cover (a family of acyclic subsets covering every vertex at least half the time). Assuming for contradiction that such a half-cover exists, the exclusion theorem condorcet_minimal_predecessor_reciprocal_completion_exclusion immediately derives a contradiction from the minimal predecessor core structure and reciprocal repair conditions.
By linear programming duality, it suffices to derive a contradiction from the existence of an acyclic half-cover of H.
By the duality theorem condorcet_half_cover_acyclic_half_cover_duality, finding nonnegative weights on vertices such that every acyclic subset has strictly less than half the total weight is equivalent to showing that no acyclic half-cover exists. Applying the forward implication and introducing the assumed counterexample, we suppose for contradiction that there exist a positive integer n and a collection of n acyclic vertex subsets U v of H such that every vertex belongs to at least n/2 of them.
uses
condorcet_half_cover_acyclic_half_cover_dualityclassical apply (condorcet_half_cover_acyclic_half_cover_duality q H).mp rintro ⟨n,U,hn,hU,hhalf⟩The assumed acyclic half-cover cannot exist under the given hypotheses, yielding a contradiction.
We invoke the exclusion theorem condorcet_minimal_predecessor_reciprocal_completion_exclusion. Under the hypotheses that R has the k-predecessor property and is minimal, f is a homomorphism from R to H, and all (k+1)-sets without a common predecessor in R are reciprocally repaired in H, this theorem establishes that no acyclic half-cover of H can exist, which derives False and completes the proof.
uses
condorcet_minimal_predecessor_reciprocal_completion_exclusionexact condorcet_minimal_predecessor_reciprocal_completion_exclusion m q n k hn hk R H f hroot hminimal hmap hrepair U hU hhalf
condorcet_half_cover_acyclic_half_cover_duality- A relation on a finite set admits nonnegative vertex weights where every acyclic subset has strictly less than half the total weight if and only if there is no acyclic half-cover (that is, no finite collection of n > 0 acyclic subsets covering each vertex at least n/2 times).
condorcet_minimal_predecessor_reciprocal_completion_exclusion- Under the minimal k-predecessor core and reciprocal (k+1)-repair hypotheses, no acyclic half-cover of the relation H can exist.
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_reciprocal_completion_separation (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, 0 ≤ w a) ∧ ∀ 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 apply (condorcet_half_cover_acyclic_half_cover_duality q H).mp rintro ⟨n,U,hn,hU,hhalf⟩ exact condorcet_minimal_predecessor_reciprocal_completion_exclusion m q n k hn hk R H f hroot hminimal hmap hrepair U hU hhalf