AFTD Auto-Formalizing Theoretical Domains

finite_endomap_local_degree_deficit_le_missing_image

theoremverified

For a finite endomap whose image heads equal the original tails, the sum of positive local tail-count minus head-count deficits is at most the number of elements missing from the image.

Statement

theorem finite_endomap_local_degree_deficit_le_missing_image
    (A V : Type) [Fintype A] [DecidableEq A] [Fintype V] [DecidableEq V]
    (f r : A → A) (tail head : A → V)
    (hr : ∀ x, f (r (f x)) = f x)
    (hf : ∀ x, head (f x) = tail x) :
    (∑ v : V, ((Finset.univ.filter fun x : A => tail x = v).card -
      (Finset.univ.filter fun x : A => head x = v).card)) ≤
      ((Finset.univ : Finset A) \ Finset.univ.image f).card
Source
Arc-map counting for the four-cycle campaign.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 2

The proof, explained

The theorem bounds the total positive local degree deficit ∑_{v ∈ V} (|O_v| - |I_v|) by the number of elements missing from the image of f, where O_v and I_v are the edges with tail and head at v. The key move is that f is injective on the subset R_v ⊆ O_v of canonical representatives (where r(f(x)) = x) and maps R_v into I_v, which forces |R_v| ≤ |I_v|. Consequently, the local deficit |O_v| - |I_v| is bounded by the number of non-representatives in O_v, and summing these bounds across all vertices yields at most |N|, which matches the missing image size |A \ f(A)| by an established identity.

  1. Let N be the finset of non-representative elements of A.

    Under classical logic, define N ⊆ A to be the set of elements x ∈ A that differ from their canonical fiber representative, meaning r(f(x)) ≠ x.

    lines 9–10

      classical
      let N : Finset A := Finset.univ.filter fun x => r (f x) ≠ x
  2. For a fixed vertex v ∈ V, set up the local edge sets O, R, and I.

    We begin proving that for each vertex v ∈ V, the local deficit is bounded by the number of non-representatives in its outgoing fiber. For a fixed v, define O = {x ∈ A | tail x = v} as the outgoing edges, R = {x ∈ O | r(f(x)) = x} as the subset of representative outgoing edges, and I = {x ∈ A | head x = v} as the incoming edges.

    lines 11–18

      have hlocal : ∀ v : V,
          (Finset.univ.filter fun x : A => tail x = v).card -
            (Finset.univ.filter fun x : A => head x = v).card ≤
              (N.filter fun x => tail x = v).card := by
        intro v
        let O : Finset A := Finset.univ.filter fun x => tail x = v
        let R : Finset A := O.filter fun x => r (f x) = x
        let I : Finset A := Finset.univ.filter fun x => head x = v
  3. The map f is injective when restricted to the representative set R.

    If x, y ∈ R satisfy f(x) = f(y), applying r gives r(f(x)) = r(f(y)) via congrArg. Since x and y belong to R, their defining property extracted via Finset.mem_filter.mp gives x = r(f(x)) and r(f(y)) = y, so x = y.

    lines 19–26

    uses congrArg, Finset.mem_filter.mp

        have hinj : Set.InjOn f (↑R : Set A) := by
          intro x hx y hy hxy
          have hx' := (Finset.mem_filter.mp hx).2
          have hy' := (Finset.mem_filter.mp hy).2
          calc
            x = r (f x) := hx'.symm
            _ = r (f y) := congrArg r hxy
            _ = y := hy'
  4. The image f(R) is contained in I.

    For any y ∈ f(R), Finset.mem_image.mp provides x ∈ R such that y = f(x). Since x ∈ R ⊆ O, its tail is v by Finset.mem_filter.mp. By the hypothesis hf, head(f(x)) = tail x = v, which places f(x) in I by Finset.mem_filter.mpr.

    lines 27–31

    uses Finset.mem_image.mp, Finset.mem_filter.mp, Finset.mem_filter.mpr, Finset.mem_univ

        have hsub : R.image f ⊆ I := by
          intro y hy
          obtain ⟨x,hx,rfl⟩ := Finset.mem_image.mp hy
          have hv : tail x = v := (Finset.mem_filter.mp (Finset.mem_filter.mp hx).1).2
          exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, (hf x).trans hv⟩
  5. The cardinality of R is at most the cardinality of I.

    Since f is injective on R, |f(R)| = |R| by Finset.card_image_of_injOn. Because f(R) ⊆ I, Finset.card_le_card gives |f(R)| ≤ |I|, so |R| ≤ |I|.

    lines 32–34

    uses Finset.card_image_of_injOn, Finset.card_le_card

        have hc : R.card ≤ I.card := by
          rw [← Finset.card_image_of_injOn hinj]
          exact Finset.card_le_card hsub
  6. For every vertex v, the local degree deficit |O| - |I| is at most |{x ∈ N | tail x = v}|.

    By Finset.card_filter_add_card_filter_not, O partitions into R (where r(f(x)) = x) and its negation (where r(f(x)) ≠ x). Commuting the conjunction with and_comm identifies the negation with N ∩ O = {x ∈ N | tail x = v}, giving |R| + |N ∩ O| = |O|. Together with |R| ≤ |I|, linear natural arithmetic (omega) implies |O| - |I| ≤ |N ∩ O|.

    lines 35–42

    uses Finset.card_filter_add_card_filter_not, and_comm

        have hp := Finset.card_filter_add_card_filter_not (s := O) (fun x => r (f x) = x)
        have hneg : O.filter (fun x => ¬ r (f x) = x) = N.filter (fun x => tail x = v) := by
          ext x
          simp [O,N, and_comm]
        rw [hneg] at hp
        change R.card + (N.filter fun x => tail x = v).card = O.card at hp
        change O.card - I.card ≤ (N.filter fun x => tail x = v).card
        omega
  7. The total size |N| decomposes into the sum of the sizes of its tail fibers.

    Applying Finset.card_eq_sum_card_fiberwise to the tail map partitions N by vertex, showing that |N| = ∑_{v ∈ V} |{x ∈ N | tail x = v}|.

    lines 43–44

    uses Finset.card_eq_sum_card_fiberwise, Finset.mem_univ

      have hsum : N.card = ∑ v : V, (N.filter fun x => tail x = v).card := by
        exact Finset.card_eq_sum_card_fiberwise (t := Finset.univ) (fun x hx => Finset.mem_univ _)
  8. The sum of local degree deficits over all vertices is at most |N|.

    Summing the local deficit bound over all v ∈ V using Finset.sum_le_sum bounds the total deficit by ∑_{v ∈ V} |{x ∈ N | tail x = v}|, which equals |N| by the fiberwise sum decomposition.

    lines 45–46

    uses Finset.sum_le_sum

      have hbound := Finset.sum_le_sum (fun v (_ : v ∈ (Finset.univ : Finset V)) => hlocal v)
      rw [← hsum] at hbound
  9. The sum of local deficits is at most the number of missing elements in the image of f.

    By finite_endomap_missing_image_eq_nonrepresentatives, the size of the complement of the image of f, |Finset.univ \ f(Finset.univ)|, is equal to |N|. Rewriting with this identity concludes the inequality.

    lines 47–50

    uses finite_endomap_missing_image_eq_nonrepresentatives

      have hidentity := finite_endomap_missing_image_eq_nonrepresentatives A f r hr
      change ((Finset.univ : Finset A) \ Finset.univ.image f).card = N.card at hidentity
      rw [hidentity]
      exact hbound
congrArg
applying a function to both sides of an equality yields an equality: if a₁ = a₂, then g(a₁) = g(a₂)
Finset.mem_filter.mp
an element in a filtered finset belongs to the underlying finset and satisfies the filter predicate
Finset.mem_filter.mpr
an element in the underlying finset satisfying the predicate belongs to the filtered finset
Finset.mem_image.mp
an element in the image f(s) is of the form f(x) for some x ∈ s
Finset.mem_univ
every element of a finite type belongs to its universal finset
Finset.card_image_of_injOn
if a function is injective on a finset s, the image f(s) has the same cardinality as s
Finset.card_le_card
if s ⊆ t for finsets s and t, then |s| ≤ |t|
Finset.card_filter_add_card_filter_not
the size of a finset is the sum of the sizes of the elements satisfying a predicate and those satisfying its negation
and_comm
propositional conjunction is commutative: a ∧ b ↔ b ∧ a
Finset.card_eq_sum_card_fiberwise
the cardinality of a finset equals the sum of the cardinalities of its fibers under a map, summed over a finset containing the image
Finset.sum_le_sum
if f(i) ≤ g(i) for all elements i of a finset, then the sum of f over that finset is at most the sum of g
finite_endomap_missing_image_eq_nonrepresentatives
for an endomap f on a finite type with pseudo-inverse section r satisfying f(r(f(x))) = f(x), the number of elements missing from the image of f equals the number of non-representatives {x | r(f(x)) ≠ x}

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

theorem finite_endomap_local_degree_deficit_le_missing_image    (A V : Type) [Fintype A] [DecidableEq A] [Fintype V] [DecidableEq V]    (f r : A → A) (tail head : A → V)    (hr : ∀ x, f (r (f x)) = f x)    (hf : ∀ x, head (f x) = tail x) :    (∑ v : V, ((Finset.univ.filter fun x : A => tail x = v).card -      (Finset.univ.filter fun x : A => head x = v).card)) ≤      ((Finset.univ : Finset A) \ Finset.univ.image f).card := by  classical  let N : Finset A := Finset.univ.filter fun x => r (f x) ≠ x  have hlocal : ∀ v : V,      (Finset.univ.filter fun x : A => tail x = v).card -        (Finset.univ.filter fun x : A => head x = v).card ≤          (N.filter fun x => tail x = v).card := by    intro v    let O : Finset A := Finset.univ.filter fun x => tail x = v    let R : Finset A := O.filter fun x => r (f x) = x    let I : Finset A := Finset.univ.filter fun x => head x = v    have hinj : Set.InjOn f (↑R : Set A) := by      intro x hx y hy hxy      have hx' := (Finset.mem_filter.mp hx).2      have hy' := (Finset.mem_filter.mp hy).2      calc        x = r (f x) := hx'.symm        _ = r (f y) := congrArg r hxy        _ = y := hy'    have hsub : R.image f ⊆ I := by      intro y hy      obtain ⟨x,hx,rfl⟩ := Finset.mem_image.mp hy      have hv : tail x = v := (Finset.mem_filter.mp (Finset.mem_filter.mp hx).1).2      exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, (hf x).trans hv⟩    have hc : R.card ≤ I.card := by      rw [← Finset.card_image_of_injOn hinj]      exact Finset.card_le_card hsub    have hp := Finset.card_filter_add_card_filter_not (s := O) (fun x => r (f x) = x)    have hneg : O.filter (fun x => ¬ r (f x) = x) = N.filter (fun x => tail x = v) := by      ext x      simp [O,N, and_comm]    rw [hneg] at hp    change R.card + (N.filter fun x => tail x = v).card = O.card at hp    change O.card - I.card ≤ (N.filter fun x => tail x = v).card    omega  have hsum : N.card = ∑ v : V, (N.filter fun x => tail x = v).card := by    exact Finset.card_eq_sum_card_fiberwise (t := Finset.univ) (fun x hx => Finset.mem_univ _)  have hbound := Finset.sum_le_sum (fun v (_ : v ∈ (Finset.univ : Finset V)) => hlocal v)  rw [← hsum] at hbound  have hidentity := finite_endomap_missing_image_eq_nonrepresentatives A f r hr  change ((Finset.univ : Finset A) \ Finset.univ.image f).card = N.card at hidentity  rw [hidentity]  exact hbound
See it in the graphDiscuss this resultChallenge it