If the set A has a finite number of elements, prove that if f maps A onto A, then f is one-to-one.
GATE 1988 · Discrete Mathematics · Functions · medium
Answer: For a finite set A, an onto map f: A -> A cannot collapse two inputs without losing a value, so f is necessarily one-to-one.
Use surjectivity to fix the image size: Since f maps A onto A, every element of A is an image, so f(A) = A and |f(A)| = n. The domain A also has n elements.
Rule out collisions by counting: Suppose f were not one-to-one: then some x != y have f(x) = f(y), so the n inputs produce at most n-1 distinct outputs, giving |f(A)| <= n-1. But Step 1 needs |f(A)| = n, a contradiction. Therefore no collision occurs and f is one-to-one.