One-to-one, onto and bijective functions
A rule sends every member of one set to a member of another. Does it ever send two members to the same place, and does it reach every member of the target?
Where you are 15 in Sets
Why this exists
A function from one set to another can fail to be a perfect matching in two separate ways. It can send two different inputs to the same output, so the output no longer tells you which input it came from. Or it can leave some members of the target set unreached, so some outputs are never produced.
These are the two questions behind almost everything done with functions between sets. Undoing a function needs the first to never happen and the second to never happen. Comparing the sizes of two sets, including infinite ones, is done by finding a function that avoids both. This lesson names the two properties, states each with quantifiers, and proves and disproves them.
Definition
Day 1: functions between sets, and injective
A function f : A \to B assigns to every member a of A exactly one member f(a) of B (recap of Definition of a function; as a set of pairs it is a relation in which every member of A is a first coordinate exactly once). A is the domain and B the codomain. Both are part of the function: the same rule with a different domain or codomain is a different function.
The image of f is the set of outputs actually produced,
It is always a subset of B, and it may be a proper one. Many books call f(A) the range; since others use “range” for the codomain, this lesson says image. Here \mathbb{N} = \{0, 1, 2, 3, \dots\}; some books start the natural numbers at 1.
f is injective (one to one) when different inputs always give different outputs. With quantifiers, the usual form to prove is
which is the contrapositive of “a_1 \neq a_2 \to f(a_1) \neq f(a_2)” and so says the same thing (Proof by contraposition). Negating it (Negating a quantified statement), f is not injective when
So a disproof is one pair of different inputs with the same output: a Counterexample.
Day 2: surjective and bijective
f is surjective (onto) when every member of the codomain is an output:
An a with f(a) = b is a preimage of b. Negated, f is not surjective when
that is, some single member of B is never reached.
f is bijective, or a bijection, when it is both injective and surjective.
Intuition
Draw the domain on the left, the codomain on the right, and one arrow from each member of A to its output. Being a function is a condition on arrows leaving A: exactly one from each. The three new words are conditions on arrows arriving in B.
Injective means no member of B receives two arrows. Surjective means no member of B receives none. Bijective means every member of B receives exactly one, so the arrows pair the two sets off with nothing left over on either side. The two properties are independent: Figure 1 shows all four combinations.
Results
1. Onto means the image is everything. f : A \to B is surjective if and only if f(A) = B.
2. Sizes of finite sets. Let A and B be finite. If there is an injection A \to B, then \lvert A \rvert \le \lvert B \rvert. If there is a surjection A \to B, then \lvert A \rvert \ge \lvert B \rvert. So if there is a bijection, \lvert A \rvert = \lvert B \rvert.
3. Equal finite sizes. If A and B are finite with \lvert A \rvert = \lvert B \rvert, then for f : A \to B the three conditions injective, surjective and bijective are equivalent: any one of the first two gives the other.
Read backward, the first half of Result 2 says that when \lvert A \rvert > \lvert B \rvert some two members of A must share an output, which is the pigeonhole principle (The pigeonhole principle). Result 3 lets you check one property and get the other free. For instance, take d : \{0, 1, \dots, 6\} \to \{0, 1, \dots, 6\}, where d(n) is the remainder when 2n is divided by 7. The outputs for n = 0, 1, \dots, 6 are 0, 2, 4, 6, 1, 3, 5, all different, so d is injective and therefore a bijection.
Why it is true
Result 1. Every output lies in B, so f(A) \subseteq B always. Surjective says exactly that every b \in B is some f(a), that is B \subseteq f(A). Two inclusions give equality, and equality gives back B \subseteq f(A). \square
Result 2, the injective half. Proof. List A = \{a_1, \dots, a_m\} with no repeats, so \lvert A \rvert = m. The image is f(A) = \{f(a_1), \dots, f(a_m)\}. Since f is injective, these m outputs are all different, so \lvert f(A) \rvert = m. A subset of a finite set has at most as many members as the set (Cardinality of a finite set), and f(A) \subseteq B, so m \le \lvert B \rvert. \square
The surjective half is Exercise 21.
Result 3. Proof. Let \lvert A \rvert = \lvert B \rvert = n and list A = \{a_1, \dots, a_n\} with no repeats.
Suppose f is injective. As above, f(A) has n members and f(A) \subseteq B. If some b \in B were missing from f(A), then f(A) would sit inside B with b removed, a set of n - 1 members, which cannot hold n different members. So f(A) = B and f is surjective.
Suppose f is surjective but, for contradiction, not injective: some a_i \neq a_j have f(a_i) = f(a_j). Then the list f(a_1), \dots, f(a_n) has a repeat, so f(A) has at most n - 1 members. But f(A) = B by Result 1, and B has n members. This contradiction shows f is injective. \square
Worked examples
Day 1: reading two arrow diagrams
For g : \{1, 2, 3, 4\} \to \{w, x, y, z\} and h : \{1, 2, 3\} \to \{w, x, y, z\} in Figure 2, find each image and decide whether each function is injective and whether it is surjective.
For g, the outputs are g(1) = x, g(2) = z, g(3) = x, g(4) = w, so the image is g(\{1, 2, 3, 4\}) = \{w, x, z\}. Two different inputs share an output, g(1) = g(3) = x, so g is not injective. The member y receives no arrow, so g is not surjective. The image is a proper subset of the codomain, which is Result 1 seen from the other side.
For h, the image is \{w, y, z\}. Each of w, y, z receives one arrow and x receives none, so h is injective and not surjective. No function from a 3-member set onto a 4-member set exists at all: three arrows reach at most three places (Result 2).
Day 1: proving and disproving injective on the integers
Show that f : \mathbb{Z} \to \mathbb{Z}, f(n) = 8n - 3, is injective, and that q : \mathbb{Z} \to \mathbb{Z}, q(n) = n^2 + n, is not.
SolutionProof. Let a, b \in \mathbb{Z} with f(a) = f(b). Then 8a - 3 = 8b - 3. Adding 3 to both sides gives 8a = 8b, and dividing by 8 gives a = b. So f is injective. \square
The proof starts from two inputs with the same output and is forced to the conclusion that the inputs are equal. It never assumes they are different.
For q, one pair is enough. Since q(n) = n(n + 1), the output is 0 whenever n = 0 or n + 1 = 0, so q(0) = 0 and q(-1) = (-1)(0) = 0. The inputs 0 and -1 are different and share an output, so q is not injective.
Day 1: functions on strings and on subsets
Let S be the set of bit strings of length 4, and let r : S \to S write a string backward, so r(0111) = 1110. Let \sigma : \mathcal{P}(\{1, 2, 3, 4\}) \to \mathbb{Z} send each subset to the sum of its members, with \sigma(\varnothing) = 0. Is r injective? Is \sigma? Find the image of \sigma.
SolutionWriting a string backward twice puts every bit back in its place, so r(r(s)) = s for every s \in S.
Proof that r is injective. Let s, t \in S with r(s) = r(t). Apply r to both sides: r(r(s)) = r(r(t)), that is s = t. \square
The same fact shows r is surjective, since each t \in S is the output r(r(t)) of the input r(t). So r is a bijection of S with itself.
\sigma is not injective: \sigma(\{1, 4\}) = 5 = \sigma(\{2, 3\}), two different subsets with the same sum. The largest sum is 1 + 2 + 3 + 4 = 10, and every whole number from 0 to 10 occurs: \varnothing, \{1\}, \{2\}, \{3\}, \{4\} give 0 to 4, and \{1,4\}, \{2,4\}, \{3,4\}, \{1,3,4\}, \{2,3,4\}, \{1,2,3,4\} give 5 to 10. The image is \{0, 1, 2, \dots, 10\}, a proper subset of the codomain \mathbb{Z}, so \sigma is not surjective either.
Day 1: counting the injections from a 3-set to a 5-set
Itzayana hangs three photos u, v, w on a wall of five empty frames numbered 1 to 5, one photo to a frame. How many ways can she do it? How many functions are there from \{u, v, w\} to \{1, 2, 3, 4, 5\} altogether, and how many of those are surjective?
SolutionA hanging is a function from the photos to the frames, and “one photo to a frame” says no two photos share a frame: the hangings are exactly the injections. Choose the frame for u (5 ways), then for v, any frame but u’s (4 ways), then for w, any of the 3 left. By the fundamental counting principle there are
injections. Without the restriction each photo has 5 frames, so there are 5^3 = 125 functions, and 125 - 60 = 65 of them put two or three photos in one frame. None is surjective: three outputs cannot cover five frames, by Result 2. In general, a set of m members has n(n - 1) \cdots (n - m + 1) injections into a set of n members when m \le n, the permutation count, and none when m > n.
Day 2: proving surjective by solving for the preimage
Show that G : \mathbb{R} \to \mathbb{R}, G(x) = 8x - 3, is surjective, and that the function f : \mathbb{Z} \to \mathbb{Z} of Example 2, with the same rule, is not. Find the image of f.
SolutionA surjectivity proof starts from an arbitrary member y of the codomain and has to produce an input. Scratch work finds a candidate by solving 8x - 3 = y, which gives \displaystyle x = \frac{y + 3}{8}. The proof then checks that the candidate lies in the domain and really works.
Proof. Let y \in \mathbb{R}, and put \displaystyle x = \frac{y + 3}{8}. This is a real number, since real numbers are closed under addition and under division by a nonzero number. Then
So every real y has a preimage, and G is surjective. \square
With Example 2’s argument, G is also injective, so G is a bijection.
For f on \mathbb{Z} the same candidate fails the domain check. Take y = 0. If 8n - 3 = 0 then \displaystyle n = \frac{3}{8}, which is not an integer, so no integer n has f(n) = 0, and f is not surjective. The image is the set of integers 8n - 3, that is \{\dots, -11, -3, 5, 13, \dots\}: the integers that leave remainder 5 when divided by 8.
Day 2: a bijection built from two cases
Prove that f : \mathbb{Z} \to \mathbb{Z} is a bijection, where
The key fact is what f does to parity. If n = 2k then f(n) = 2k + 3 = 2(k + 1) + 1 is odd, and if n = 2k + 1 then f(n) = 2k - 4 = 2(k - 2) is even, for some integer k in each case. So f sends even integers to odd ones and odd integers to even ones.
Proof that f is injective. Let a, b \in \mathbb{Z} with f(a) = f(b). Equal outputs have the same parity, so by the fact above a and b have the same parity, and there are two cases. If both are even, a + 3 = b + 3, so a = b. If both are odd, a - 5 = b - 5, so a = b. \square
Proof that f is surjective. Let m \in \mathbb{Z}. If m is odd, put n = m - 3, which is even as an odd number minus an odd number; then f(n) = (m - 3) + 3 = m. If m is even, put n = m + 5, which is odd; then f(n) = (m + 5) - 5 = m. Either way m has a preimage. \square
Each candidate came from solving the matching branch for n, and the parity check is what confirms that the branch used is the one f actually applies to that n.
Day 2: one rule, four verdicts
The rule n \mapsto \lvert n \rvert is used with four choices of domain and codomain. Decide in each case whether the function is injective and whether it is surjective.
(a) \mathbb{Z} \to \mathbb{Z} \quad (b) \mathbb{Z} \to \mathbb{N} \quad (c) \mathbb{N} \to \mathbb{N} \quad (d) \mathbb{N} \to \mathbb{Z}
SolutionEvery \lvert n \rvert is a natural number, so all four are functions.
(a) Not injective, since \lvert -2 \rvert = 2 = \lvert 2 \rvert. Not surjective, since an absolute value is never negative, so -1 has no preimage. Neither.
(b) Same domain, so still not injective. Now surjective: for m \in \mathbb{N}, the input m itself is in \mathbb{Z} and \lvert m \rvert = m. Surjective only.
(c) On \mathbb{N} every input is at least 0, so \lvert n \rvert = n. If \lvert a \rvert = \lvert b \rvert then a = b, so it is injective, and each m \in \mathbb{N} is \lvert m \rvert, so it is surjective. Bijective.
(d) Injective as in (c), since injectivity depends only on the rule and the domain. Not surjective, since -1 is in the codomain and is never an output. Injective only.
Shrinking the domain can only help injectivity; shrinking the codomain can only help surjectivity, but a codomain must still contain every output. With codomain the negative integers there is no function at all, since \lvert 3 \rvert = 3 has nowhere to go.
Boundaries
No codomain, no question. “Is n \mapsto \lvert n \rvert onto?” has no answer until a domain and a codomain are named, as Example 7 shows.
Results 2 and 3 are about finite sets. On \mathbb{N}, the function n \mapsto n + 1 is injective but not surjective (0 is missed), even though domain and codomain are the same set. Infinite sets can be matched with parts of themselves, which is the subject of Matching two sets one to one.
The empty domain. A function \varnothing \to B has no inputs, so it is injective with nothing to check (the universal statement is vacuously true). It is surjective only when B = \varnothing.
Injective is not the function condition. “Each input has exactly one output” is what makes f a function at all. Injective is the separate condition that each output has at most one input.
Where this goes next
A bijection can be run backward: the inverse sends each b to its one preimage, and a function has an inverse exactly when it is a bijection, which is proved in Composing functions between sets, and when an inverse exists together with how the properties behave under composition.
Result 2 is the start of measuring size by matching. For infinite sets there is nothing to count, so “same size” is defined as “there is a bijection”, in Matching two sets one to one, leading to Countable sets. Its finite form, read backward, is the pigeonhole principle, one of the most used tools in counting proofs.
Exercises
Day 1: arrow diagrams and images
For each function in Figure 3, give the image, and say whether it is injective and whether it is surjective.
- P
- Q
- R
- Let A = \{1, 2, 3\} and B = \{x, y\}. Write down a surjection A \to B, and explain why no function A \to B is injective.
Day 1: proving and disproving injective
- Prove that f : \mathbb{Z} \to \mathbb{Z}, f(n) = 11n - 6, is injective.
- Show that g : \mathbb{Z} \to \mathbb{Z}, g(n) = n^2 - 4n + 1, is not injective.
- Prove that k : \mathbb{N} \to \mathbb{N}, k(n) = n^2 + 2n, is injective, and show that the same rule as a function \mathbb{Z} \to \mathbb{Z} is not.
- Let T be the set of bit strings of length 5, and let \rho : T \to T move the first bit to the end, so \rho(10010) = 00101. Prove that \rho is injective.
- Define e : \mathcal{P}(\{1, 2, 3\}) \to \mathcal{P}(\{1, 2, 3, 4\}) by e(X) = X \cup \{4\}. Prove that e is injective. Is it surjective?
- How many injections are there from a 4-member set to a 6-member set? How many functions?
Day 2: proving and disproving surjective
- Prove that F : \mathbb{Q} \to \mathbb{Q}, \displaystyle F(x) = 3x + \frac{1}{2}, is a bijection.
- Prove that g : \mathbb{Z} \to \mathbb{Z}, g(n) = 10 - n, is a bijection.
- Decide whether h : \mathbb{Z} \to \mathbb{Z} is injective and whether it is surjective, where h(n) = n - 4 if n is even and h(n) = n + 1 if n is odd.
- Let L be the set of nonempty subsets of \{1, 2, 3, 4\}, and let \mu : L \to \{1, 2, 3, 4\} send each subset to its largest member. Is \mu injective? Surjective?
- Define d : \mathbb{N} \to \mathbb{N} by d(0) = 0 and d(n) = n - 1 for n \ge 1. Show that d is surjective but not injective.
Day 2: changing the domain or the codomain
- The rule X \mapsto X \cap \{1, 2\} is used with four choices of domain and codomain. Decide injective and surjective for each: (a) \mathcal{P}(\{1,2,3\}) \to \mathcal{P}(\{1,2,3\}), (b) \mathcal{P}(\{1,2,3\}) \to \mathcal{P}(\{1,2\}), (c) \mathcal{P}(\{1,2\}) \to \mathcal{P}(\{1,2\}), (d) \mathcal{P}(\{1,2\}) \to \mathcal{P}(\{1,2,3\}).
- Find a codomain C for the rule n \mapsto 8n - 3 on \mathbb{Z} that makes f : \mathbb{Z} \to C a bijection, and prove that it does.
Day 2: finite sets
- On \{0, 1, \dots, 8\}, let r(n) be the remainder when 4n is divided by 9, and t(n) the remainder when 3n is divided by 9. Use Result 3 to decide which of r, t is a bijection of \{0, 1, \dots, 8\} with itself, and give the image of the other.
- How many bijections are there from \{1, 2, 3, 4\} to \{a, b, c, d\}? Explain why counting injections gives the answer.
- How many functions are there from a 4-member set to a 2-member set, and how many of them are surjective? How many are injective?
Day 2: reasoning
- Prove the surjective half of Result 2: if A and B are finite and f : A \to B is surjective, then \lvert A \rvert \ge \lvert B \rvert.
- Prove that if f : A \to B is injective, then the same rule with codomain f(A) is a bijection A \to f(A).
- Prove that f : A \to B is a bijection if and only if every b \in B has exactly one preimage.
- For a subset X of \{1, 2, 3\}, let \beta(X) be the sum of 2^{x - 1} over the members x of X, with \beta(\varnothing) = 0. Prove that \beta : \mathcal{P}(\{1, 2, 3\}) \to \{0, 1, \dots, 7\} is a bijection.
Answers
- Image \{a, b, c, d\}. Injective and surjective, so bijective: each of a, b, c, d receives exactly one arrow.
- Image \{b, d\}. Not injective, since Q(1) = Q(3) = d. Not surjective, since a and c receive no arrow.
- Image \{a, b, c\}. Surjective. Not injective, since R(1) = R(3) = c.
- For example 1 \mapsto x, 2 \mapsto y, 3 \mapsto y; both x and y are reached. An injection would give three different outputs, but B has only two members (Result 2: 3 > 2).
- Proof. If 11a - 6 = 11b - 6 for integers a, b, then 11a = 11b and a = b. \square
- g(0) = 1 and g(4) = 16 - 16 + 1 = 1, with 0 \neq 4.
- Proof. If a^2 + 2a = b^2 + 2b for a, b \in \mathbb{N}, then a^2 - b^2 + 2a - 2b = (a - b)(a + b + 2) = 0. Since a + b + 2 \ge 2, the first factor is 0, so a = b. \square On \mathbb{Z}, k(0) = 0 = k(-2), since 4 - 4 = 0.
- Proof. Write s = s_1 s_2 s_3 s_4 s_5 and t = t_1 t_2 t_3 t_4 t_5. If \rho(s) = \rho(t), the strings s_2 s_3 s_4 s_5 s_1 and t_2 t_3 t_4 t_5 t_1 agree position by position, so s_i = t_i for every i and s = t. \square
- Proof. Neither X nor Y contains 4, so removing 4 gives it back: X = (X \cup \{4\}) \setminus \{4\}. If e(X) = e(Y), removing 4 from both gives X = Y. \square Not surjective: every output contains 4, so \varnothing has no preimage. The image is the 8 subsets that contain 4.
- 6 \cdot 5 \cdot 4 \cdot 3 = 360 injections, out of 6^4 = 1296 functions.
- Proof. Injective: \displaystyle 3a + \frac{1}{2} = 3b + \frac{1}{2} gives 3a = 3b, so a = b. Surjective: for y \in \mathbb{Q} put \displaystyle x = \frac{2y - 1}{6}, a rational number since y is; then \displaystyle F(x) = \frac{2y - 1}{2} + \frac{1}{2} = y. \square
- Proof. Injective: 10 - a = 10 - b gives a = b. Surjective: for m \in \mathbb{Z}, the integer n = 10 - m has g(n) = 10 - (10 - m) = m. \square
- Neither. For n even, n - 4 is even; for n odd, n + 1 is even. So every output is even and 1 has no preimage. Not injective: h(5) = 6 = h(10).
- Surjective, since \mu(\{k\}) = k for each k. Not injective: \mu(\{2\}) = 2 = \mu(\{1, 2\}).
- For m \in \mathbb{N}, the input m + 1 \ge 1 gives d(m + 1) = m, so d is surjective. d(0) = 0 = d(1), so it is not injective.
- (a) Neither: \{3\} and \varnothing both go to \varnothing, and \{3\} is never an output. (b) Surjective only: each Y \subseteq \{1, 2\} is its own output. (c) Bijective: every X here already lies in \{1, 2\}, so X \cap \{1, 2\} = X. (d) Injective only: \{3\} is missed.
- C = \{8k - 3 : k \in \mathbb{Z}\}. Proof. Every output lies in C, so f is a function. Injective as in Example 2. Each member of C is 8k - 3 = f(k) for some integer k, so f is surjective. \square
- r has outputs 0, 4, 8, 3, 7, 2, 6, 1, 5, all different, so it is injective, hence a bijection by Result 3. t has t(0) = t(3) = 0, so it is not injective, hence by Result 3 not surjective; its image is \{0, 3, 6\}.
- 24. The sets have the same size, so by Result 3 the injections are exactly the bijections, and there are 4 \cdot 3 \cdot 2 \cdot 1 = 24 injections.
- 2^4 = 16 functions. Only the two constant functions miss a member of the codomain, so 14 are surjective. None is injective, since 4 > 2.
- Proof. List A = \{a_1, \dots, a_m\}. Then f(A) = \{f(a_1), \dots, f(a_m)\} has at most m members, fewer if the list repeats. Since f is surjective, f(A) = B by Result 1, so \lvert B \rvert \le m = \lvert A \rvert. \square
- Proof. Each f(a) lies in f(A), so f : A \to f(A) is a function. Same rule and domain, so still injective. Each member of f(A) is f(a) for some a \in A by the definition of the image, so it is surjective. \square
- Proof. Suppose f is a bijection and b \in B. Surjective gives a preimage. If a_1 and a_2 are both preimages, then f(a_1) = b = f(a_2), so a_1 = a_2 by injectivity. Conversely, suppose each b has exactly one preimage. Having one makes f surjective. If f(a_1) = f(a_2), then a_1 and a_2 are preimages of the same b, so a_1 = a_2, and f is injective. \square
- Proof. Every output is at most 1 + 2 + 4 = 7, so \beta is a function into \{0, \dots, 7\}. Surjective: write k in base 2 as k = c_1 + 2c_2 + 4c_3 with each c_i equal to 0 or 1, and take X = \{i : c_i = 1\}; then \beta(X) = k. Both sets have 8 members, so by Result 3 \beta is also injective, hence a bijection. \square