Lesson 7 of 10 · 9 min
Finite sets and counting
NCERT §1.3
Eight runners, eight lanes. The starter can allot them in many ways, but every allotment that gives each runner a lane of their own also fills every lane. On a finite track, one-one and onto come together.
The lesson in notes
In short
When X is finite, a map from X to itself is one-one exactly when it is onto. This equivalence is what sets finite sets apart from infinite ones.
Why: if f on {1, 2, 3} is one-one, its three images are three different elements of {1, 2, 3}, so all of them are hit. If it is not one-one, two elements share an image and the range has at most two elements, so it cannot be onto.
The property fails for infinite sets: f(x) = 2x on N is one-one but not onto, and f(1) = f(2) = 1, f(x) = x − 1 (x > 2) on N is onto but not one-one.
Each one-one map of {1, 2, 3} onto itself just rearranges the symbols 1, 2, 3, so there are 3! = 6 of them. By the finite-set property, the onto functions from {1, 2, …, n} to itself also number n!.
Between finite sets with n(X) = m and n(Y) = n, a one-one map needs m ≤ n (m different images), an onto map needs m ≥ n (n elements to cover), and a bijection needs m = n.
There are nᵐ functions in all from X to Y, because each of the m elements picks one of n images.