condorcet_integer_neighbor_mass_clone_permutation
Finite weighted neighborhood inequalities imply an arrow-supported permutation on the finite set containing w(a) clones of every vertex a. This exposes the same matching construction used to build the integer circulation.
Statement
theorem condorcet_integer_neighbor_mass_clone_permutation (m : ℕ) (R : Fin m → Fin m → Prop) [DecidableRel R] (w : Fin m → ℕ) (hHall : ∀ S : Finset (Fin m), (∑ a ∈ S, w a) ≤ ∑ b ∈ univ.filter (fun b => ∃ a ∈ S, R a b), w b) : ∃ e : Equiv.Perm (Σ a : Fin m, Fin (w a)), ∀ x, R x.1 (e x).1
- Source
- IN-380, OP-19 campaign session8, 2026-10-30. Supporting reduction from the proved strict-half circulation bridge. Scratch ClosedWalk.lean passed trusted-axiom checking. Standard finite matching and orbit averaging; no research novelty or new election bound is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- condorcet_strict_half_separator_acyclic_cover_closed_walkIf a finite relation has a nonnegative real strict-half acyclic separator, then every positive finite family of induced acyclic sets…
The proof, explained
The proof constructs an arrow-supported permutation on the cloned vertex set V = Σ a, Fin (w a) by applying Hall's Marriage Theorem. It first establishes that the number of clones over any vertex subset S is exactly the sum of the weights in S. Using this identity, Hall's condition on any subset of clones B reduces directly to the given weighted Hall hypothesis on its projection S. Finally, Hall's Marriage Theorem produces an injective system of distinct representatives from V to itself, which, by finiteness of V, is automatically a permutation respecting the relation R.
Introduce the cloned vertex set V = Σ a : Fin m, Fin (w a).
We enable classical reasoning and define V as the disjoint union of w(a) clones for each base vertex a in Fin m.
classical let V := Σ a : Fin m, Fin (w a)For any subset S of base vertices, the number of clone vertices projecting to S equals the sum of weights ∑ a ∈ S, w a.
We express the cardinality of the clones projecting to S as a sum of 1s, convert the filter condition to an if-then-else indicator, and decompose the sum over the sigma type into an outer sum over base vertices a and an inner sum over clones of a. For each a, the inner sum is w(a) when a ∈ S and 0 otherwise. Summing over all a gives ∑ a ∈ S, w a.
uses
card_eq_sum_ones,sum_filter,Fintype.sum_sigma,Fintype.sum_ite_mem,sum_congrhave hcard (S : Finset (Fin m)) : (univ.filter (fun x : V => x.1 ∈ S)).card = ∑ a ∈ S, w a := by rw [card_eq_sum_ones,sum_filter] change (∑ x : (Σ a : Fin m, Fin (w a)), if x.1 ∈ S then 1 else 0) = _ rw [Fintype.sum_sigma] rw [← Fintype.sum_ite_mem S w] apply sum_congr rfl intro a ha by_cases h : a ∈ S <;> simp [h]
Define the neighborhood of a clone vertex x as all clone vertices whose base vertex is related to that of x by R.
The neighborhood function lifts the relation R from the base vertices to V: a clone y is a neighbor of x whenever R x.1 y.1 holds.
let neighbors : V → Finset V := fun x => univ.filter (fun y => R x.1 y.1)
Every subset B of clone vertices satisfies Hall's condition: |B| ≤ |⋃_{x ∈ B} neighbors(x)|.
Let S be the image of B under projection to the base vertices, and let N be the R-neighborhood of S. Then B is contained in the set of all clones over S, so |B| ≤ ∑ a ∈ S, w a. Furthermore, the union of neighborhoods of elements of B is precisely the set of all clones over N, which has size ∑ b ∈ N, w b. By the weighted Hall hypothesis hHall on S, ∑ a ∈ S, w a ≤ ∑ b ∈ N, w b, establishing |B| ≤ |⋃_{x ∈ B} neighbors(x)|.
uses
card_le_card,mem_univ,mem_image,mem_filter,mem_biUnion,true_andhave hclones : ∀ B : Finset V, B.card ≤ (B.biUnion neighbors).card := by intro B let S := B.image Sigma.fst let N := univ.filter (fun b => ∃ a ∈ S, R a b) have hB : B ⊆ univ.filter (fun x : V => x.1 ∈ S) := by intro x hx exact mem_filter.mpr ⟨mem_univ _,mem_image.mpr ⟨x,hx,rfl⟩⟩ have hN : B.biUnion neighbors = univ.filter (fun y : V => y.1 ∈ N) := by ext y simp only [mem_biUnion,neighbors,mem_filter,mem_univ,true_and,N,S,mem_image] constructor · rintro ⟨x,hx,hxy⟩ exact ⟨x.1,⟨x,hx,rfl⟩,hxy⟩ · rintro ⟨a,⟨x,hx,rfl⟩,hay⟩ exact ⟨x,hx,hay⟩ calc B.card ≤ (univ.filter (fun x : V => x.1 ∈ S)).card := card_le_card hB _ = ∑ a ∈ S, w a := hcard S _ ≤ ∑ a ∈ N, w a := hHall S _ = (B.biUnion neighbors).card := by rw [hN,hcard]
There exists an injective function g : V → V selecting for each clone vertex x a neighbor g(x) ∈ neighbors(x).
Because Hall's condition holds for all subsets of the finite set V, Hall's Marriage Theorem (the forward direction of all_card_le_biUnion_card_iff_existsInjective') provides an injective matching g : V → V with g(x) ∈ neighbors(x) for all x.
uses
all_card_le_biUnion_card_iff_existsInjective'obtain ⟨g,hginj,hg⟩ := (all_card_le_biUnion_card_iff_existsInjective' neighbors).mp hclonesThe injective map g is a bijection, yielding a permutation e of the clone vertices V.
Because V is a finite type, any injective map from V to itself is automatically surjective and therefore bijective. Converting this bijection into an equivalence gives a permutation e of V.
uses
Equiv.ofBijectivehave hgbij : Function.Bijective g := hginj.bijective_of_finite let e : V ≃ V := Equiv.ofBijective g hgbij refine ⟨e,?_⟩
The permutation e satisfies R x.1 (e x).1 for all clone vertices x.
For each clone vertex x, e(x) belongs to neighbors(x) by construction. Unfolding the definition of neighbors confirms that R x.1 (e x).1 holds.
uses
mem_filterintro x exact (mem_filter.mp (hg x)).2
card_eq_sum_ones- The cardinality of a finite set equals the sum of 1 over all its elements.
sum_filter- Summing over elements satisfying a predicate is equivalent to summing an if-then-else indicator over the whole set.
Fintype.sum_sigma- A sum over a sigma type (dependent sum) equals the iterated sum over the index type and each fiber.
Fintype.sum_ite_mem- Summing an indicator function (if i ∈ s then f i else 0) over a finite type equals the sum of f over s.
sum_congr- Two sums over the same finset are equal if their summands agree on every element.
card_le_card- If a finite set s is a subset of t, then the cardinality of s is at most that of t.
mem_filter- An element belongs to the filtered finset if and only if it belongs to the base finset and satisfies the predicate.
mem_univ- Every element of a finite type belongs to the universal finset univ.
mem_image- An element b is in the image of s under f if and only if b = f a for some a in s.
mem_biUnion- An element belongs to a finset biUnion if and only if it belongs to the set associated to some element in the index set.
true_and- The logical conjunction True ∧ p is equivalent to p.
all_card_le_biUnion_card_iff_existsInjective'- Hall's Marriage Theorem for finite types: every subset s satisfies |s| ≤ |⋃_{x ∈ s} t(x)| if and only if there exists an injective system of distinct representatives f with f(x) ∈ t(x) for all x.
Equiv.ofBijective- A bijective function between two types gives an equivalence (bijection) between them.
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_integer_neighbor_mass_clone_permutation (m : ℕ) (R : Fin m → Fin m → Prop) [DecidableRel R] (w : Fin m → ℕ) (hHall : ∀ S : Finset (Fin m), (∑ a ∈ S, w a) ≤ ∑ b ∈ univ.filter (fun b => ∃ a ∈ S, R a b), w b) : ∃ e : Equiv.Perm (Σ a : Fin m, Fin (w a)), ∀ x, R x.1 (e x).1 := by classical let V := Σ a : Fin m, Fin (w a) have hcard (S : Finset (Fin m)) : (univ.filter (fun x : V => x.1 ∈ S)).card = ∑ a ∈ S, w a := by rw [card_eq_sum_ones,sum_filter] change (∑ x : (Σ a : Fin m, Fin (w a)), if x.1 ∈ S then 1 else 0) = _ rw [Fintype.sum_sigma] rw [← Fintype.sum_ite_mem S w] apply sum_congr rfl intro a ha by_cases h : a ∈ S <;> simp [h] let neighbors : V → Finset V := fun x => univ.filter (fun y => R x.1 y.1) have hclones : ∀ B : Finset V, B.card ≤ (B.biUnion neighbors).card := by intro B let S := B.image Sigma.fst let N := univ.filter (fun b => ∃ a ∈ S, R a b) have hB : B ⊆ univ.filter (fun x : V => x.1 ∈ S) := by intro x hx exact mem_filter.mpr ⟨mem_univ _,mem_image.mpr ⟨x,hx,rfl⟩⟩ have hN : B.biUnion neighbors = univ.filter (fun y : V => y.1 ∈ N) := by ext y simp only [mem_biUnion,neighbors,mem_filter,mem_univ,true_and,N,S,mem_image] constructor · rintro ⟨x,hx,hxy⟩ exact ⟨x.1,⟨x,hx,rfl⟩,hxy⟩ · rintro ⟨a,⟨x,hx,rfl⟩,hay⟩ exact ⟨x,hx,hay⟩ calc B.card ≤ (univ.filter (fun x : V => x.1 ∈ S)).card := card_le_card hB _ = ∑ a ∈ S, w a := hcard S _ ≤ ∑ a ∈ N, w a := hHall S _ = (B.biUnion neighbors).card := by rw [hN,hcard] obtain ⟨g,hginj,hg⟩ := (all_card_le_biUnion_card_iff_existsInjective' neighbors).mp hclones have hgbij : Function.Bijective g := hginj.bijective_of_finite let e : V ≃ V := Equiv.ofBijective g hgbij refine ⟨e,?_⟩ intro x exact (mem_filter.mp (hg x)).2