condorcet_minimal_predecessor_reciprocal_completion_exclusion
Let a globally minimal finite S_k core, k positive, map by a relation-preserving function into another finite relation. If every undominated (k+1)-set of the core has a common reciprocal neighbor in the larger relation, the larger relation admits no positive finite acyclic half-cover. Injectivity of the map is not required.
Statement
theorem condorcet_minimal_predecessor_reciprocal_completion_exclusion (m q n k : ℕ) (hn : 0 < n) (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) (U : Fin n → Finset (Fin q)) (hU : ∀ v, WellFounded (fun a b : {a : Fin q // a ∈ U v} => H a.val b.val)) (hhalf : ∀ a, n ≤ 2*(univ.filter fun v => a∈U v).card) : False
- 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 1
- condorcet_minimal_predecessor_coalition_completion_exclusionSuch a globally minimal predecessor core cannot have an acyclic half-cover if every undominated (k+1)-set has an additional event of at…
- Used by 1
- condorcet_minimal_predecessor_reciprocal_completion_separationUnder the preceding minimal-core and reciprocal-repair hypotheses, nonnegative real vertex weights on the larger relation put every…
The proof, explained
The proof proceeds by reduction to condorcet_minimal_predecessor_coalition_completion_exclusion, which establishes that no minimal S_k core can admit an acyclic majority half-cover with majority exclusion for undominated (k+1)-sets. We pull back the assumed acyclic half-cover U of the target relation along the relation-preserving map f to obtain a candidate cover V on the core, which inherits well-foundedness on each slice. For any undominated (k+1)-element set T, the repair hypothesis provides a mutual neighbor x in the target relation whose cover indices form a majority coalition B. Finally, no element of T can belong to V(v) for v ∈ B because a 2-cycle with x would violate the asymmetry of the well-founded relation on U(v), thereby supplying the required majority exclusion and deriving a contradiction.
The problem reduces via condorcet_minimal_predecessor_coalition_completion_exclusion to showing that the preimages V(v) = f⁻¹(U(v)) form a well-founded majority cover with majority exclusion.
We enable classical reasoning and define the family V(v) = {a ∈ Fin m | f(a) ∈ U(v)} on the core as the preimage under f of each set U(v). We then apply the exclusion theorem condorcet_minimal_predecessor_coalition_completion_exclusion, which rules out the existence of such a family on a minimal S_k core. This reduces the theorem to three subgoals: well-foundedness of each V(v), the half-cover property for each vertex of the core, and majority exclusion for every undominated (k+1)-element subset.
uses
condorcet_minimal_predecessor_coalition_completion_exclusionclassical let V : Fin n → Finset (Fin m) := fun v => univ.filter fun a => f a ∈ U v apply condorcet_minimal_predecessor_coalition_completion_exclusion m n k hn hk R hroot hminimal V
For each index v, the relation R restricted to V(v) is well-founded.
The map f restricts to a function g : V(v) → U(v). Since f preserves the relation (hmap), R restricted to V(v) is a subrelation of the inverse image under g of the relation H on U(v). By assumption hU, H is well-founded on U(v), so its inverse image under g is well-founded by InvImage.wf. Because well-foundedness is preserved by passing to subrelations, R restricted to V(v) is well-founded.
uses
InvImage.wf· intro v let g : {a : Fin m // a∈V v} → {a : Fin q // a∈U v} := fun a => ⟨f a.val,(mem_filter.mp a.property).2⟩ exact (InvImage.wf g (hU v)).mono (fun a b hab => hmap a b hab)
Every vertex in the core belongs to V(v) for at least half of the indices v.
For any a ∈ Fin m, by definition a ∈ V(v) if and only if f(a) ∈ U(v). Applying the half-cover hypothesis hhalf to the image point f(a) ∈ Fin q yields n ≤ 2 |{v | f(a) ∈ U(v)}|, which directly gives n ≤ 2 |{v | a ∈ V(v)}|.
· intro a simpa [V] using hhalf (f a)
For any undominated (k+1)-set T, the repair hypothesis yields a candidate majority coalition B.
Given a subset T ⊆ Fin m of size k+1 with no common predecessor in R, the repair hypothesis hrepair provides a vertex x ∈ Fin q that is a mutual neighbor under H with f(a) for every a ∈ T (both H(x, f(a)) and H(f(a), x) hold). We define B to be the set of indices v such that x ∈ U(v). By the half-cover hypothesis hhalf applied to x, B is a majority coalition, satisfying n ≤ 2|B|.
· intro T hT hbad obtain ⟨x,hx⟩ := hrepair T hT hbad refine ⟨univ.filter (fun v => x ∈ U v),hhalf x,?_⟩
No vertex of T belongs to V(v) for any index v ∈ B.
Suppose for contradiction that some a ∈ T belongs to V(v) for an index v ∈ B. By definition of B and V, both x and f(a) belong to U(v). By construction of x, both H(x, f(a)) and H(f(a), x) hold, so x and f(a) form a 2-cycle in U(v). But H restricted to U(v) is well-founded and hence asymmetric, which rules out mutual edges and gives False.
intro v hv a ha hmem have hxU := (mem_filter.mp hv).2 have haU := (mem_filter.mp hmem).2 exact (hU v).asymmetric (a := ⟨x,hxU⟩) (b := ⟨f a,haU⟩) (hx a ha).1 (hx a ha).2
condorcet_minimal_predecessor_coalition_completion_exclusion- On a minimal S_k core, no family of subsets can simultaneously be well-founded on each slice, cover every vertex in at least half of the slices, and provide a majority coalition excluding any undominated (k+1)-element subset.
InvImage.wf- The inverse image of a well-founded relation under any function is well-founded.
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_exclusion (m q n k : ℕ) (hn : 0 < n) (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) (U : Fin n → Finset (Fin q)) (hU : ∀ v, WellFounded (fun a b : {a : Fin q // a ∈ U v} => H a.val b.val)) (hhalf : ∀ a, n ≤ 2*(univ.filter fun v => a∈U v).card) : False := by classical let V : Fin n → Finset (Fin m) := fun v => univ.filter fun a => f a ∈ U v apply condorcet_minimal_predecessor_coalition_completion_exclusion m n k hn hk R hroot hminimal V · intro v let g : {a : Fin m // a∈V v} → {a : Fin q // a∈U v} := fun a => ⟨f a.val,(mem_filter.mp a.property).2⟩ exact (InvImage.wf g (hU v)).mono (fun a b hab => hmap a b hab) · intro a simpa [V] using hhalf (f a) · intro T hT hbad obtain ⟨x,hx⟩ := hrepair T hT hbad refine ⟨univ.filter (fun v => x ∈ U v),hhalf x,?_⟩ intro v hv a ha hmem have hxU := (mem_filter.mp hv).2 have haU := (mem_filter.mp hmem).2 exact (hU v).asymmetric (a := ⟨x,hxU⟩) (b := ⟨f a,haU⟩) (hx a ha).1 (hx a ha).2