condorcet_critical_rank_core_source_exchange
For positive k and n=k+q, a nonempty induced S_k subset of a rank relation whose vertices all have q active indices and satisfy the contained-signature Pareto antichain condition admits a source for each restricted activity set. For each vertex a and inactive index j there is a predecessor r of a, active at j, with signature contained in that of a plus j, also preceding every source of an index outside that union. Sources of nonempty restricted activity sets belong to those sets; all sources belong to B.
Statement
theorem condorcet_critical_rank_core_source_exchange {m n k q : ℕ} (hk : 0 < k) (hn : n = k + q) (U : Fin n → Finset (Fin m)) (p : Fin n → Fin m → ℕ) (B : Finset (Fin m)) (hBne : B.Nonempty) (hcard : ∀ a ∈ B, (univ.filter fun v => a ∈ U v).card = q) (hroot : ∀ J : Finset (Fin m), J ⊆ B → J.card ≤ k → ∃ r, r ∈ B ∧ r ∉ J ∧ ∀ c ∈ J, condorcet_cover_rank_relation U p r c) (hanti : ∀ a ∈ B, ∀ b ∈ B, a ≠ b → (∀ v, a ∈ U v → b ∈ U v) → ∃ v, a ∈ U v ∧ p v b < p v a) : ∃ s : Fin n → Fin m, (∀ v, s v ∈ B) ∧ (∀ v, (B ∩ U v).Nonempty → s v ∈ U v) ∧ (∀ v, ∀ r ∈ B, r ∈ U v → ¬condorcet_cover_rank_relation U p r (s v)) ∧ ∀ a ∈ B, ∀ j : Fin n, a ∉ U j → ∃ r, r ∈ B ∧ condorcet_cover_rank_relation U p r a ∧ r ∈ U j ∧ (∀ v, r ∈ U v → a ∈ U v ∨ v = j) ∧ (∀ v, v ≠ j → a ∉ U v → condorcet_cover_rank_relation U p r (s v))
- Source
- IN-391, OP-19 campaign session10, 2026-10-30. Supporting lemmas and precisely scoped method diagnostics for the rank-saturated acyclic-cover route. The main election theorem remains open; no new election bound or novelty is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- condorcet_cover_rank_relationThe loopless rank-compatible relation: an arrow a to b is permitted precisely when a differs from b and a has a strictly smaller…
- condorcet_minimal_rank_core_pareto_antichainIn a globally minimum induced S_k subset of a rank-compatible relation, with every vertex active somewhere, distinct vertices a and b with…
The proof, explained
The proof first constructs a source s(v) ∈ B for each index v by minimizing the rank p(v, ·) on B ∩ U(v) (or choosing an arbitrary element if empty), which guarantees that no element in B ∩ U(v) can cover s(v). To find the desired predecessor r for a given a ∈ B and inactive index j, we consider the set W of all k - 1 indices outside the signature of a and {j}, and form the test set J = {a} ∪ s(W), which has cardinality at most k. By the S_k property, some r ∈ B covers all elements of J; this r cannot be active on W (which would contradict the source property of s(v)), and cannot be inactive at j (which would contradict the Pareto antichain condition since r covers a). Hence r is active at j, has its signature contained in that of a plus j, and covers all sources s(v) for v ∈ W.
For each index v, there exists a source s(v) ∈ B which belongs to U(v) whenever B ∩ U(v) is nonempty and cannot be covered by any element of B ∩ U(v).
If B ∩ U(v) is nonempty, choose s(v) ∈ B ∩ U(v) minimizing the rank p(v, ·) via exists_min_image. If some r ∈ B ∩ U(v) were to cover s(v), then by definition of the covering relation, p(v, r) < p(v, s(v)), contradicting the minimality of p(v, s(v)). If B ∩ U(v) is empty, choose an arbitrary element b ∈ B (given by hBne), for which both conditions hold vacuously. Using choice, we obtain a function s : Fin n → B satisfying these source conditions, reducing the goal to finding the required predecessor r for any a ∈ B and inactive index j.
uses
exists_min_image,not_lt_of_geclassical obtain ⟨b,hb⟩ := hBne have hex : ∀ v : Fin n, ∃ s, s ∈ B ∧ ((B ∩ U v).Nonempty → s ∈ U v) ∧ ∀ r ∈ B, r ∈ U v → ¬condorcet_cover_rank_relation U p r s := by intro v by_cases hnon : (B ∩ U v).Nonempty · obtain ⟨s,hs,hmin⟩ := (B ∩ U v).exists_min_image (p v) hnon refine ⟨s,(mem_inter.mp hs).1,fun _ => (mem_inter.mp hs).2,?_⟩ intro r hrB hrU hrs exact (not_lt_of_ge (hmin r (mem_inter.mpr ⟨hrB,hrU⟩))) (hrs.2 v hrU (mem_inter.mp hs).2) · exact ⟨b,hb,fun h => (hnon h).elim,fun r hrB hrU _ => hnon ⟨r,mem_inter.mpr ⟨hrB,hrU⟩⟩⟩ choose s hsB hsU hs using hex refine ⟨s,hsB,hsU,hs,?_⟩
For a fixed vertex a ∈ B and inactive index j ∉ U(a), the set W of indices outside {j} ∪ {v | a ∈ U(v)} has size k - 1.
Let I be the signature of a, which has cardinality q by hypothesis hcard. Since a ∉ U(j), the index j does not belong to I, so the set {j} ∪ I has size q + 1. The complement W = Fin n \ ({j} ∪ I) in the universe of n = k + q indices therefore has cardinality (k + q) - (q + 1) = k - 1.
uses
card_sdiff,inter_univ,card_univ,Fintype.card_fin,card_insert_of_notMemintro a ha j haj let I := univ.filter fun v => a ∈ U v let W := univ \ insert j I have hI : I.card = q := hcard a ha have hjI : j ∉ I := by simpa only [I,mem_filter,mem_univ,true_and] using haj have hW : W.card = k - 1 := by dsimp only [W] rw [card_sdiff,inter_univ,card_univ,Fintype.card_fin,card_insert_of_notMem hjI,hI,hn] omega
The set J = {a} ∪ s(W) is a subset of B of cardinality at most k.
Because a ∈ B and each s(v) ∈ B, the set J = {a} ∪ s(W) is contained in B. Since |s(W)| ≤ |W| = k - 1 by card_image_le, inserting a yields |J| ≤ (k - 1) + 1 = k by card_insert_le.
uses
insert_subset,card_image_le,card_insert_lehave hJsub : insert a (W.image s) ⊆ B := by apply insert_subset ha intro x hx obtain ⟨v,_,rfl⟩ := mem_image.mp hx exact hsB v have hJcard : (insert a (W.image s)).card ≤ k := by have hle := card_image_le (f := s) (s := W) have hle' := card_insert_le a (W.image s) omega
There exists a vertex r ∈ B that covers every element of J, and in particular covers a.
Applying the S_k property hroot to the set J ⊆ B of size at most k yields an element r ∈ B that covers every element of J. Since a ∈ J, r covers a.
uses
mem_insert_selfobtain ⟨r,hrB,_,hr⟩ := hroot (insert a (W.image s)) hJsub hJcard have hra := hr a (mem_insert_self _ _)
For every index v, if r ∈ U(v) then a ∈ U(v) or v = j.
Assume for contradiction that r ∈ U(v) for some index v with a ∉ U(v) and v ≠ j. Then v belongs to the complement W, so s(v) ∈ s(W) ⊆ J. Hence r covers s(v). But r ∈ B ∩ U(v), so this directly contradicts the source property of s(v), which states that no element of B ∩ U(v) can cover s(v).
uses
mem_insert_of_memhave htype : ∀ v, r ∈ U v → a ∈ U v ∨ v = j := by intro v hrv by_contra h push_neg at h have hvW : v ∈ W := by apply mem_sdiff.mpr refine ⟨mem_univ _,?_⟩ intro hv rcases mem_insert.mp hv with hv | hv · exact h.2 hv · exact h.1 (mem_filter.mp hv).2 exact hs v r hrB hrv (hr (s v) (mem_insert_of_mem (mem_image.mpr ⟨v,hvW,rfl⟩)))
The vertex r is active at index j, that is, r ∈ U(j).
Assume for contradiction that r ∉ U(j). Combining this with the signature containment from the previous step, every index where r is active must also be active for a (∀ v, r ∈ U(v) → a ∈ U(v)). Since r covers a, r ≠ a. By the Pareto antichain condition hanti, there must be some index v where r ∈ U(v) and p(v, a) < p(v, r) (meaning a is ranked better than r at v). But since r covers a and both are active at v, we also have p(v, r) < p(v, a), which is impossible.
uses
not_lt_of_ge,le_of_lthave hrj : r ∈ U j := by by_contra hnot have hsub : ∀ v, r ∈ U v → a ∈ U v := by intro v hv rcases htype v hv with h | rfl · exact h · exact (hnot hv).elim obtain ⟨v,hrv,hlt⟩ := hanti r hrB a ha hra.1 hsub exact (not_lt_of_ge (le_of_lt hlt)) (hra.2 v hrv (hsub v hrv))
The vertex r satisfies all conditions: it belongs to B, covers a, is active at j, has signature contained in that of a plus j, and covers s(v) for all v ≠ j with a ∉ U(v).
Assembling the properties established for r: r ∈ B, r covers a, r ∈ U(j), and its signature is contained in {j} ∪ {v | a ∈ U(v)}. Finally, for any index v ≠ j where a ∉ U(v), v lies in W, which implies s(v) ∈ s(W) ⊆ J. Since r covers every element of J, r covers s(v).
uses
mem_insert_of_memrefine ⟨r,hrB,hra,hrj,htype,?_⟩ intro v hvj hva apply hr (s v) apply mem_insert_of_mem apply mem_image.mpr refine ⟨v,?_,rfl⟩ apply mem_sdiff.mpr refine ⟨mem_univ _,?_⟩ intro hv rcases mem_insert.mp hv with hv | hv · exact hvj hv · exact hva (mem_filter.mp hv).2
exists_min_image- Every nonempty finite set contains an element that minimizes a given function into a linearly ordered type.
not_lt_of_ge- If a ≤ b, then b is not strictly less than a.
card_sdiff- The cardinality of the set difference t \ s is the cardinality of t minus the cardinality of s ∩ t.
inter_univ- The intersection of a finite set with the universal set is the finite set itself.
card_univ- The cardinality of the universal finset is the cardinality of the underlying finite type.
Fintype.card_fin- The finite type Fin n has cardinality n.
card_insert_of_notMem- Inserting an element into a finite set that does not already contain it increases the cardinality by 1.
insert_subset- If a ∈ t and s ⊆ t, then {a} ∪ s ⊆ t.
card_image_le- The cardinality of the image of a finite set under a function is at most the cardinality of the domain set.
card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1.
mem_insert_self- An element belongs to the set obtained by inserting it into any set.
mem_insert_of_mem- If an element belongs to a set s, it also belongs to the set obtained by inserting another element into s.
le_of_lt- A strict inequality a < b implies the non-strict inequality a ≤ b.
- Linear arithmetic over ℕ via the omega tactic is used to verify the set cardinality equations (k + q) - (q + 1) = k - 1 on line 46 and |J| ≤ k on line 55.
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 Finsetset_option maxHeartbeats 100000000set_option maxRecDepth 30000theorem condorcet_critical_rank_core_source_exchange {m n k q : ℕ} (hk : 0 < k) (hn : n = k + q) (U : Fin n → Finset (Fin m)) (p : Fin n → Fin m → ℕ) (B : Finset (Fin m)) (hBne : B.Nonempty) (hcard : ∀ a ∈ B, (univ.filter fun v => a ∈ U v).card = q) (hroot : ∀ J : Finset (Fin m), J ⊆ B → J.card ≤ k → ∃ r, r ∈ B ∧ r ∉ J ∧ ∀ c ∈ J, condorcet_cover_rank_relation U p r c) (hanti : ∀ a ∈ B, ∀ b ∈ B, a ≠ b → (∀ v, a ∈ U v → b ∈ U v) → ∃ v, a ∈ U v ∧ p v b < p v a) : ∃ s : Fin n → Fin m, (∀ v, s v ∈ B) ∧ (∀ v, (B ∩ U v).Nonempty → s v ∈ U v) ∧ (∀ v, ∀ r ∈ B, r ∈ U v → ¬condorcet_cover_rank_relation U p r (s v)) ∧ ∀ a ∈ B, ∀ j : Fin n, a ∉ U j → ∃ r, r ∈ B ∧ condorcet_cover_rank_relation U p r a ∧ r ∈ U j ∧ (∀ v, r ∈ U v → a ∈ U v ∨ v = j) ∧ (∀ v, v ≠ j → a ∉ U v → condorcet_cover_rank_relation U p r (s v)) := by classical obtain ⟨b,hb⟩ := hBne have hex : ∀ v : Fin n, ∃ s, s ∈ B ∧ ((B ∩ U v).Nonempty → s ∈ U v) ∧ ∀ r ∈ B, r ∈ U v → ¬condorcet_cover_rank_relation U p r s := by intro v by_cases hnon : (B ∩ U v).Nonempty · obtain ⟨s,hs,hmin⟩ := (B ∩ U v).exists_min_image (p v) hnon refine ⟨s,(mem_inter.mp hs).1,fun _ => (mem_inter.mp hs).2,?_⟩ intro r hrB hrU hrs exact (not_lt_of_ge (hmin r (mem_inter.mpr ⟨hrB,hrU⟩))) (hrs.2 v hrU (mem_inter.mp hs).2) · exact ⟨b,hb,fun h => (hnon h).elim,fun r hrB hrU _ => hnon ⟨r,mem_inter.mpr ⟨hrB,hrU⟩⟩⟩ choose s hsB hsU hs using hex refine ⟨s,hsB,hsU,hs,?_⟩ intro a ha j haj let I := univ.filter fun v => a ∈ U v let W := univ \ insert j I have hI : I.card = q := hcard a ha have hjI : j ∉ I := by simpa only [I,mem_filter,mem_univ,true_and] using haj have hW : W.card = k - 1 := by dsimp only [W] rw [card_sdiff,inter_univ,card_univ,Fintype.card_fin,card_insert_of_notMem hjI,hI,hn] omega have hJsub : insert a (W.image s) ⊆ B := by apply insert_subset ha intro x hx obtain ⟨v,_,rfl⟩ := mem_image.mp hx exact hsB v have hJcard : (insert a (W.image s)).card ≤ k := by have hle := card_image_le (f := s) (s := W) have hle' := card_insert_le a (W.image s) omega obtain ⟨r,hrB,_,hr⟩ := hroot (insert a (W.image s)) hJsub hJcard have hra := hr a (mem_insert_self _ _) have htype : ∀ v, r ∈ U v → a ∈ U v ∨ v = j := by intro v hrv by_contra h push_neg at h have hvW : v ∈ W := by apply mem_sdiff.mpr refine ⟨mem_univ _,?_⟩ intro hv rcases mem_insert.mp hv with hv | hv · exact h.2 hv · exact h.1 (mem_filter.mp hv).2 exact hs v r hrB hrv (hr (s v) (mem_insert_of_mem (mem_image.mpr ⟨v,hvW,rfl⟩))) have hrj : r ∈ U j := by by_contra hnot have hsub : ∀ v, r ∈ U v → a ∈ U v := by intro v hv rcases htype v hv with h | rfl · exact h · exact (hnot hv).elim obtain ⟨v,hrv,hlt⟩ := hanti r hrB a ha hra.1 hsub exact (not_lt_of_ge (le_of_lt hlt)) (hra.2 v hrv (hsub v hrv)) refine ⟨r,hrB,hra,hrj,htype,?_⟩ intro v hvj hva apply hr (s v) apply mem_insert_of_mem apply mem_image.mpr refine ⟨v,?_,rfl⟩ apply mem_sdiff.mpr refine ⟨mem_univ _,?_⟩ intro hv rcases mem_insert.mp hv with hv | hv · exact hvj hv · exact hva (mem_filter.mp hv).2