AFTD Auto-Formalizing Theoretical Domains

finite_endomap_missing_image_eq_nonrepresentatives

theoremverified

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

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.

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

    lines 6–7

    uses Finset.card_bij

      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)
  2. 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).

    lines 8–12

    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)
  3. 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₂.

    lines 13–17

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

    lines 18–20

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

    lines 21–22

    uses Finset.filter_not, Finset.card_sdiff_of_subset, Finset.subset_univ

      rw [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

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