finite_endomap_local_degree_deficit_le_missing_image
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
- finite_endomap_missing_image_eq_nonrepresentativesFor a finite endomap with a chosen representative from each nonempty fiber, the number of elements outside its image equals the number of…
- Used by 2
- digraph_oriented_degree_deficit_overlap_budgetIn every finite loopless oriented arc-dominated digraph, twice the sum of positive outdegree-minus-indegree deficits is at most three…
- digraph_oriented_girth_degree_deficit_overlap_budgetIn a finite loopless oriented arc-dominated digraph whose directed cycles have at least g vertices, with g at least three, g−1 times the…
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.
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.
classical let N : Finset A := Finset.univ.filter fun x => r (f x) ≠ x
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.
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
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.
uses
congrArg,Finset.mem_filter.mphave 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'
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.
uses
Finset.mem_image.mp,Finset.mem_filter.mp,Finset.mem_filter.mpr,Finset.mem_univhave 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⟩
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|.
uses
Finset.card_image_of_injOn,Finset.card_le_cardhave hc : R.card ≤ I.card := by rw [← Finset.card_image_of_injOn hinj] exact Finset.card_le_card hsub
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|.
uses
Finset.card_filter_add_card_filter_not,and_commhave 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
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}|.
uses
Finset.card_eq_sum_card_fiberwise,Finset.mem_univhave 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 _)
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.
uses
Finset.sum_le_sumhave hbound := Finset.sum_le_sum (fun v (_ : v ∈ (Finset.univ : Finset V)) => hlocal v) rw [← hsum] at hbound
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.
uses
finite_endomap_missing_image_eq_nonrepresentativeshave 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}
- Subtraction on ℕ is truncated (non-negative) subtraction: a - b = 0 whenever a ≤ b. As a result, the local deficit |O_v| - |I_v| automatically represents the positive excess max(0, |O_v| - |I_v|) of outgoing edges over incoming edges.
- At line 42, the omega tactic performs linear arithmetic over ℕ with truncated subtraction to deduce |O| - |I| ≤ |N ∩ O| from |O| = |R| + |N ∩ O| and |R| ≤ |I|.
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.
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