AFTD Auto-Formalizing Theoretical Domains

condorcet_integer_neighbor_mass_clone_permutation

theoremverified

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

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.

  1. 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.

    lines 11–12

      classical
      let V := Σ a : Fin m, Fin (w a)
  2. 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.

    lines 13–21

    uses card_eq_sum_ones, sum_filter, Fintype.sum_sigma, Fintype.sum_ite_mem, sum_congr

      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]
  3. 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.

    line 22

      let neighbors : V → Finset V := fun x => univ.filter (fun y => R x.1 y.1)
  4. 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)|.

    lines 23–42

    uses card_le_card, mem_univ, mem_image, mem_filter, mem_biUnion, true_and

      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]
  5. 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.

    line 43

    uses all_card_le_biUnion_card_iff_existsInjective'

      obtain ⟨g,hginj,hg⟩ := (all_card_le_biUnion_card_iff_existsInjective' neighbors).mp hclones
  6. The 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.

    lines 44–46

    uses Equiv.ofBijective

      have hgbij : Function.Bijective g := hginj.bijective_of_finite
      let e : V ≃ V := Equiv.ofBijective g hgbij
      refine ⟨e,?_⟩
  7. 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.

    lines 47–48

    uses mem_filter

      intro 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

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
See it in the graphDiscuss this resultChallenge it