2.6Functions: one-to-one, onto, bijective
The idea
A function f : A → B sends each element of A to exactly one element of B. It is injective when different inputs give different outputs, surjective when every element of B is hit, and bijective when both.
Think of it like this: Seats and guests: injective means nobody shares a seat, surjective means every seat is taken, bijective means a perfect one-to-one pairing.
Why it exists
Counting functions of each kind and testing a given formula are a steady source of marks, and the onto-function count needs inclusion–exclusion.
How it works
- All functions A → B: nᵐ (each of the m inputs picks any of n outputs).
- Injective: n·(n−1)·…·(n−m+1) = n!/(n−m)!, zero if m > n.
- Surjective: Σ(−1)ᵏ C(n,k)(n−k)ᵐ = n!·S(m,n); zero if m < n.
- Bijective: n! when m = n. For equal finite sets, injective ⇔ surjective.
Worked example: Onto functions from a 4-set to a 3-set
3⁴ − 3·2⁴ + 3·1⁴ = 81 − 48 + 3 = 36 (equals 3!·S(4,3) = 6·6).
Now play with it
- →Load "surjective, not injective" and watch the injective flag fail.
- →Set |A| = 4, |B| = 3 and read the onto count.
| Function | Injective | Surjective | Bijective |
|---|---|---|---|
| f(x) = x + 1 on ℤ | ✓ | ✓ | ✓ |
| f(x) = 2x on ℤ | ✓ | ✗ | ✗ |
| f(x) = x² on ℤ | ✗ | ✗ | ✗ |
| f(x) = x² on ℝ → [0, ∞) | ✗ | ✓ | ✗ |
| f(x) = x³ on ℝ | ✓ | ✓ | ✓ |
| f(x) = ⌊x/2⌋ on ℤ | ✗ | ✓ | ✗ |
| f(n) = n mod 5 on ℕ → {0..4} | ✗ | ✓ | ✗ |
Check injective with f(a) = f(b) ⇒ a = b; check surjective by solving f(x) = y for any y in the codomain.
Check yourself
How many one-to-one functions are there from a 3-set to a 5-set?
Exam notes (the dense version)
f : A → B. Injective: different inputs give different outputs. Surjective: every element of B is hit. Bijective = both. Counts with |A| = m, |B| = n: all functions nᵐ; injective n!/(n−m)!; bijective n! (m = n); surjective Σ(−1)ᵏ C(n,k)(n−k)ᵐ = n!·S(m,n). For finite sets of equal size, injective ⇔ surjective.
Previous year questions: Sets, Relations & Functions (20)
PYQs are grouped by topic, so this is the full set for Sets, Relations & Functions; try the ones that match this subtopic. Open all 20 on the topic page.