finite_endomap_missing_image_eq_nonrepresentatives
For a finite endomap with a chosen representative from each nonempty fiber, the number of elements outside its image equals the number of nonrepresentatives.
Statement
theorem finite_endomap_missing_image_eq_nonrepresentatives (α : Type) [Fintype α] [DecidableEq α] (f r : α → α) (hr : ∀ x, f (r (f x)) = f x) : ((Finset.univ : Finset α) \ Finset.univ.image f).card = ((Finset.univ : Finset α).filter (fun x => r (f x) ≠ x)).card
- Source
- Collision counting for the small-overlap route to OP-110.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 7
- digraph_oriented_arc_map_missing_dirty_budgetFor a finite loopless oriented digraph and a chosen common predecessor for each arc, the number of dirty parents plus the number of arcs…
- finite_endomap_collision_charge_identityFor a finite endomap whose fibers share a tail and whose elements are determined by tail and head, the number of missing image elements is…
- digraph_oriented_arc_map_twice_missing_budgetIn a finite loopless oriented digraph with a chosen common predecessor for every arc, twice the number of arcs missing from the resulting…
- digraph_trianglefree_arc_map_weighted_budgetFor a loopless oriented digraph of directed girth at least four with chosen common predecessors for its arcs, three times the number of…
- digraph_girth_arc_map_weighted_budgetFor a loopless oriented digraph of directed girth at least g, with g at least three and chosen common predecessors for its arcs, g−1 times…
- finite_endomap_local_degree_deficit_le_missing_imageFor a finite endomap whose image heads equal the original tails, the sum of positive local tail-count minus head-count deficits is at most…
- digraph_girth_arc_map_missing_budgetFor a loopless oriented digraph of directed girth at least g, g−1 times the number of missing predecessor arc-map images is at most g…
The proof, explained
The proof shows that the missing image elements and the nonrepresentatives are complements of equinumerous subsets of α. Specifically, the representative map r restricts to a bijection between the image of f and the set of representatives {x | r (f x) = x}, where injectivity and surjectivity follow from the fiber-representative property f (r (f x)) = f x. Subtracting these equal cardinalities from the total cardinality of α yields the desired equality.
To show that the image of f and the set of fiber representatives have the same cardinality, it suffices to show that r restricts to a bijection between them.
We introduce the intermediate claim that the image of f and the set of representatives {x | r (f x) = x} have equal cardinality. By Finset.card_bij, this reduces to showing that the representative map r is well-defined into the set of representatives, injective on the image of f, and surjective onto the representatives.
uses
Finset.card_bijhave h_bij : (Finset.univ.image f).card = (Finset.univ.filter (fun x => r (f x) = x)).card := by apply Finset.card_bij (fun y _ => r y)
The map r sends every element of the image of f to a representative.
Let y be in the image of f, so y = f x for some x. To show that r y = r (f x) satisfies r (f (r y)) = r y, we apply r to both sides of the hypothesis f (r (f x)) = f x, obtaining r (f (r (f x))) = r (f x).
uses
Finset.mem_image,Finset.mem_univ,true_and,Finset.mem_filter,congr_arg· intro y hy simp only [Finset.mem_image, Finset.mem_univ, true_and] at hy rcases hy with ⟨x, rfl⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact congr_arg r (hr x)
The map r is injective on the image of f.
Suppose y₁, y₂ are in the image of f with r y₁ = r y₂. Writing y₁ = f x₁ and y₂ = f x₂, the equation r (f x₁) = r (f x₂) implies f x₁ = f (r (f x₁)) = f (r (f x₂)) = f x₂ by applying the hypothesis f (r (f x)) = f x to both sides, so y₁ = y₂.
uses
Finset.mem_image,Finset.mem_univ,true_and· intro y₁ hy₁ y₂ hy₂ h_eq simp only [Finset.mem_image, Finset.mem_univ, true_and] at hy₁ hy₂ rcases hy₁ with ⟨x₁, rfl⟩ rcases hy₂ with ⟨x₂, rfl⟩ rw [← hr x₁, ← hr x₂, h_eq]
The map r is surjective onto the set of representatives, completing the proof of the bijection.
Given any representative x satisfying r (f x) = x, the element f x lies in the image of f and satisfies r (f x) = x, providing the required preimage. This establishes the cardinality equality between the image and the representatives.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_image_of_mem· intro x hx simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx exact ⟨f x, Finset.mem_image_of_mem f (Finset.mem_univ x), hx⟩
The number of elements outside the image of f equals the number of nonrepresentatives.
The set of nonrepresentatives {x | r (f x) ≠ x} is the complement in α of the representatives {x | r (f x) = x}, so its cardinality is |α| minus the number of representatives. Similarly, the number of elements outside the image of f is |α| minus the cardinality of the image. Since the representatives and the image have the same size, their complements in the finite universe α have equal cardinality.
uses
Finset.filter_not,Finset.card_sdiff_of_subset,Finset.subset_univrw [Finset.filter_not, Finset.card_sdiff_of_subset (Finset.subset_univ _), Finset.card_sdiff_of_subset (Finset.subset_univ _), h_bij]
Finset.card_bij- Two finite sets have equal cardinality if there exists a function between them that maps into the codomain, is injective, and is surjective.
Finset.mem_image- An element b belongs to the image of a set s under f if and only if b = f a for some a ∈ s.
Finset.mem_univ- Every element of a finite type belongs to the universal set Finset.univ.
true_and- The proposition True ∧ p is equivalent to p.
Finset.mem_filter- An element a belongs to {x ∈ s | p x} if and only if a ∈ s and p a holds.
congr_arg- If a₁ = a₂, then f a₁ = f a₂ for any function f.
Finset.mem_image_of_mem- If a ∈ s, then f a belongs to the image of s under f.
Finset.filter_not- The set of elements not satisfying p is the set difference between the whole set and the subset of elements satisfying p.
Finset.card_sdiff_of_subset- If s ⊆ t, then the cardinality of t \ s is the cardinality of t minus the cardinality of s.
Finset.subset_univ- Any finite set of elements of type α is a subset of Finset.univ.
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_missing_image_eq_nonrepresentatives (α : Type) [Fintype α] [DecidableEq α] (f r : α → α) (hr : ∀ x, f (r (f x)) = f x) : ((Finset.univ : Finset α) \ Finset.univ.image f).card = ((Finset.univ : Finset α).filter (fun x => r (f x) ≠ x)).card := by have h_bij : (Finset.univ.image f).card = (Finset.univ.filter (fun x => r (f x) = x)).card := by apply Finset.card_bij (fun y _ => r y) · intro y hy simp only [Finset.mem_image, Finset.mem_univ, true_and] at hy rcases hy with ⟨x, rfl⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact congr_arg r (hr x) · intro y₁ hy₁ y₂ hy₂ h_eq simp only [Finset.mem_image, Finset.mem_univ, true_and] at hy₁ hy₂ rcases hy₁ with ⟨x₁, rfl⟩ rcases hy₂ with ⟨x₂, rfl⟩ rw [← hr x₁, ← hr x₂, h_eq] · intro x hx simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx exact ⟨f x, Finset.mem_image_of_mem f (Finset.mem_univ x), hx⟩ rw [Finset.filter_not, Finset.card_sdiff_of_subset (Finset.subset_univ _), Finset.card_sdiff_of_subset (Finset.subset_univ _), h_bij]