math.wiki
Logic, proof and discrete math › Sets › Composing functions between sets, and when an inverse exists
Open on the map
Discrete Mathematics and Proof

Composing functions between sets, and when an inverse exists

When one function is followed by another, which of one to one and onto survive the chaining, and when can a function be run backward?

You need
Combining and composing functionsGrades 10 to 11One-to-one, onto and bijective functionsDiscrete Mathematics and Proof
Where you are 15 in Sets
Logic, proof and discrete math6
Sets15
▴ 10 aboveRelations and their properties: reflexive, symmetric, antisymmetric, transitiveSet identities: distributive and De Morgan lawsVenn diagrams and counting a union
Composing functions between sets, and when an inverse exists
Relations, equivalence classes and partitions

Why this exists

A function can be fed into another: the outputs of the first become the inputs of the second. With real-number formulas this is composing algebraically, and undoing a formula is finding an inverse by swapping and solving. Between arbitrary sets (strings, subsets, finite sets of labels) there is no formula to solve, and two questions take its place. When one function follows another, does the chain keep the properties of one to one and onto? And exactly when can a function be run backward, so that a second function undoes it?

The answers are short theorems, used constantly afterward: to prove a function is a bijection by writing down its inverse, and to compare sizes of sets by chaining matchings.

Definition

Day 1: composition and identity

Let f : A \to B and g : B \to C. The composite of f and g is the function g \circ f : A \to C given by

(g \circ f)(a) = g\big(f(a)\big) \quad \text{for every } a \in A.

It is read right to left: f acts first, then g. The composite is defined only when the codomain of f is the domain of g, so that every output of f is something g accepts.

Two functions f, f' : A \to B are equal when they have the same domain, the same codomain, and f(a) = f'(a) for every a \in A. Proving two functions equal means checking every input.

For any set A, the identity function \mathrm{id}_A : A \to A is \mathrm{id}_A(a) = a. It is a bijection.

Day 2: inverses

Let f : A \to B. A function g : B \to A is an inverse of f when

g \circ f = \mathrm{id}_A \quad \text{and} \quad f \circ g = \mathrm{id}_B,

that is, g(f(a)) = a for every a \in A and f(g(b)) = b for every b \in B. When it exists it is unique (Result 6) and written f^{-1}. Here f^{-1} is a function, not the reciprocal \displaystyle \frac{1}{f}.

If only g \circ f = \mathrm{id}_A holds, g is a left inverse of f; if only f \circ g = \mathrm{id}_B, a right inverse. An inverse is both at once.

Intuition

In an arrow diagram, composing means following two arrows in a row. In Figure 1, the arrow from 1 lands on q, and the arrow from q lands on x, so (g \circ f)(1) = x. Erase the middle oval, keep one arrow from each start to each finish, and the result is the arrow diagram of g \circ f.

1 2 3 4 p q r x y f g
Figure 1The functions f and g of Example 1. Following two arrows in a row from the left oval to the right one gives g \circ f.

An inverse reverses every arrow. That reversed picture is a function exactly when each member of B has exactly one arrow arriving: at least one, so the reversed arrow has somewhere to start (onto), and at most one, so it has only one place to go (one to one). This is why the inverses of a function given by a table exist only when no output repeats and every target appears.

Results

Throughout, f : A \to B, g : B \to C and h : C \to D.

1. Associativity. h \circ (g \circ f) = (h \circ g) \circ f. So brackets may be dropped and h \circ g \circ f written. Composition is not commutative: g \circ f and f \circ g can differ, or one can be undefined.

2. Identity. f \circ \mathrm{id}_A = f and \mathrm{id}_B \circ f = f.

3. Composites keep the properties. If f and g are both injective, so is g \circ f. If both are surjective, so is g \circ f. So if both are bijections, so is g \circ f.

4. Partial converses. If g \circ f is injective, then f is injective. If g \circ f is surjective, then g is surjective. Nothing more follows: g need not be injective, nor f surjective (Example 3).

5. Inverses and bijections. f has an inverse if and only if f is a bijection. The inverse sends each b \in B to its one preimage. The inverse of a bijection is a bijection (Exercise 18).

6. Uniqueness. If g \circ f = \mathrm{id}_A and f \circ h = \mathrm{id}_B, then g = h. In particular f has at most one inverse.

7. Inverse of a composite. If f and g are bijections, then (g \circ f)^{-1} = f^{-1} \circ g^{-1}. Undo the last step first.

8. One-sided inverses. Let A be nonempty. f has a left inverse if and only if f is injective; if A is finite, f has a right inverse if and only if f is surjective. The “only if” halves are Result 4, since an identity is a bijection; the “if” halves are Exercises 21 and 22. For infinite A the right-inverse statement is still true, but its proof needs the axiom of choice and is not given here.

Why it is true

Result 1. Proof. Both sides are functions from A to D. For each a \in A,

\begin{aligned} \big(h \circ (g \circ f)\big)(a) &= h\big((g \circ f)(a)\big) \\ &= h\big(g(f(a))\big) \end{aligned}

and \big((h \circ g) \circ f\big)(a) = (h \circ g)\big(f(a)\big) = h\big(g(f(a))\big). The values agree at every input, so the functions are equal. \square

Result 2 is Exercise 8.

Result 3. Proof. Suppose f and g are injective, and let a_1, a_2 \in A with g(f(a_1)) = g(f(a_2)). Since g is injective, f(a_1) = f(a_2); since f is injective, a_1 = a_2.

Suppose f and g are surjective, and let c \in C. Since g is surjective there is b \in B with g(b) = c, and since f is surjective there is a \in A with f(a) = b. Then (g \circ f)(a) = g(b) = c. A bijection is both, so the last sentence follows. \square

Result 4. Proof. Suppose g \circ f is injective, and let f(a_1) = f(a_2). Applying g to both sides gives (g \circ f)(a_1) = (g \circ f)(a_2), so a_1 = a_2. Thus f is injective.

Suppose g \circ f is surjective, and let c \in C. Some a \in A has g(f(a)) = c, so the member b = f(a) of B has g(b) = c. Thus g is surjective. \square

Result 5. Proof. Suppose g is an inverse of f. The identity \mathrm{id}_A = g \circ f is injective, so f is injective by Result 4. The identity \mathrm{id}_B = f \circ g is surjective, so f, now the second function applied, is surjective by Result 4. So f is a bijection.

Conversely, suppose f is a bijection. Then every b \in B has exactly one preimage (One-to-one, onto and bijective functions, Exercise 23); define g(b) to be it. By construction f(g(b)) = b. For a \in A, the member a is a preimage of f(a) and the only one, so g(f(a)) = a. So g is an inverse of f. \square

Result 6. Proof. Using Results 2 and 1,

\begin{aligned} g &= g \circ \mathrm{id}_B = g \circ (f \circ h) \\ &= (g \circ f) \circ h = \mathrm{id}_A \circ h = h. \end{aligned}

Two inverses of f are in particular a left one and a right one, so they are equal. \square

Result 7. Proof. g \circ f is a bijection by Result 3, so it has exactly one inverse, and it is enough to check that f^{-1} \circ g^{-1} : C \to A satisfies both equations. Regrouping by Result 1,

\begin{aligned} &(f^{-1} \circ g^{-1}) \circ (g \circ f) \\ &\quad = f^{-1} \circ (g^{-1} \circ g) \circ f \\ &\quad = f^{-1} \circ \mathrm{id}_B \circ f = \mathrm{id}_A, \end{aligned}

and in the same way (g \circ f) \circ (f^{-1} \circ g^{-1}) = g \circ \mathrm{id}_B \circ g^{-1} = \mathrm{id}_C. \square

Worked examples

Example 1

Day 1: composing two arrow diagrams

For f and g in Figure 1, find g \circ f as a table and decide whether it is injective and whether it is surjective. Is f \circ g defined?

Solution

Follow each member of A = \{1, 2, 3, 4\} along two arrows: (g \circ f)(1) = g(q) = x, (g \circ f)(2) = g(p) = y, (g \circ f)(3) = g(r) = y and (g \circ f)(4) = g(q) = x.

a1234
(g \circ f)(a)xyyx

Both x and y are reached, so g \circ f is surjective; 1 and 4 share the output x, so it is not injective. Result 3 predicted the first: f reaches p, q, r and g reaches x, y, so both factors are surjective.

f \circ g is not defined. It would need f to accept the outputs x and y of g, but the domain of f is \{1, 2, 3, 4\}.

Example 2

Day 1: composing across different sets

Let S be the set of bit strings of length 3. Let k : S \to S flip every bit, so k(110) = 001, and let w : S \to \{0, 1, 2, 3\} count the 1s in a string. Describe w \circ k, and show that (w \circ k) \circ k = w.

Solution

The 1s of k(s) sit exactly where s has 0s, and a string of length 3 has 3 - w(s) of those. So

(w \circ k)(s) = 3 - w(s) \quad \text{for every } s \in S.

For instance (w \circ k)(110) = w(001) = 1 = 3 - 2. The other order, k \circ w, is not defined: w produces numbers and k accepts only strings.

Flipping twice restores every bit, so k \circ k = \mathrm{id}_S. Then by Result 1 and Result 2,

(w \circ k) \circ k = w \circ (k \circ k) = w \circ \mathrm{id}_S = w.
Example 3

Day 1: the converses go one way only

In Figure 2, f : \{1, 2\} \to \{a, b, c\} and g : \{a, b, c\} \to \{x, y\}. Show that g \circ f is a bijection although neither f nor g is.

1 2 a b c x y f g
Figure 2The functions of Example 3. The composite pairs 1 with x and 2 with y perfectly, although f misses c and g sends two inputs to y.
Solution

(g \circ f)(1) = g(a) = x and (g \circ f)(2) = g(b) = y. The two outputs differ and cover \{x, y\}, so g \circ f is a bijection. But f misses c, so it is not surjective, and g(b) = g(c) = y, so g is not injective.

Result 4 still holds, as it must: f is injective and g is surjective. What fails is the other half. The composite never visits c, so whatever g does to c, including a collision, cannot spoil it. One pair of functions thus refutes both “g \circ f injective forces g injective” and “g \circ f surjective forces f surjective” (Counterexample).

Example 4

Day 1: a left inverse that is not an inverse

Let f : \mathbb{Z} \to \mathbb{Z}, f(n) = 3n, and let g : \mathbb{Z} \to \mathbb{Z} send n to its quotient on division by 3: write n = 3q + r with q \in \mathbb{Z} and r \in \{0, 1, 2\}, and put g(n) = q. Show that g \circ f = \mathrm{id}_{\mathbb{Z}} but f \circ g \neq \mathrm{id}_{\mathbb{Z}}, and decide which of f, g are injective or surjective.

Solution

For n \in \mathbb{Z}, 3n = 3 \cdot n + 0, so the quotient of 3n is n and g(f(n)) = n. Thus g \circ f = \mathrm{id}_{\mathbb{Z}}. The identity is a bijection, so Result 4 gives that f is injective and g is surjective.

In the other order, 7 = 3 \cdot 2 + 1, so f(g(7)) = f(2) = 6 \neq 7, and f \circ g \neq \mathrm{id}_{\mathbb{Z}}. In general (f \circ g)(n) = 3q = n - r, the largest multiple of 3 not above n.

Neither function is a bijection. f is not surjective, since 3n = 1 has no integer solution, and g is not injective, since g(6) = g(7) = g(8) = 2. So g is a left inverse of f and not an inverse, and both equations in the definition are needed.

Example 5

Day 2: reversing the arrows

Find the inverse of m : \{1, 2, 3, 4\} \to \{p, q, r, s\} with m(1) = r, m(2) = p, m(3) = s, m(4) = q, and check both equations. Explain why f of Example 1 and f of Example 3 have no inverse.

Solution

Each of p, q, r, s receives exactly one arrow, so m is a bijection, and reversing the arrows (Figure 3) gives m^{-1}(p) = 2, m^{-1}(q) = 4, m^{-1}(r) = 1, m^{-1}(s) = 3.

1 2 3 4 p q r s m p q r s 1 2 3 4
m^{-1}
Figure 3Reversing every arrow of a bijection gives its inverse (Example 5).

Check m^{-1} \circ m = \mathrm{id} at every input: m^{-1}(m(1)) = m^{-1}(r) = 1, m^{-1}(m(2)) = m^{-1}(p) = 2, m^{-1}(m(3)) = m^{-1}(s) = 3, m^{-1}(m(4)) = m^{-1}(q) = 4. And m \circ m^{-1} = \mathrm{id}: m(2) = p, m(4) = q, m(1) = r, m(3) = s.

Reversing f of Example 1 sends q back to both 1 and 4, which is not a function: f is not injective. Reversing f of Example 3 leaves c with no arrow at all: f is not surjective. Each failure alone rules out an inverse, by Result 5.

Example 6

Day 2: proving a bijection by exhibiting its inverse

Define T : \mathbb{Z} \to \mathbb{Z} by T(n) = n + 1 if n leaves remainder 0 or 1 on division by 3, and T(n) = n - 2 if it leaves remainder 2. Show that T is a bijection and find T^{-1}.

Solution

Write n = 3q + r. T moves around the block \{3q, 3q + 1, 3q + 2\} in a cycle: 3q \mapsto 3q + 1 \mapsto 3q + 2 \mapsto 3q. Three steps from any starting point return to it, so T \circ T \circ T = \mathrm{id}_{\mathbb{Z}}. By Result 1 this holds bracketed either way, so T \circ (T \circ T) and (T \circ T) \circ T are both \mathrm{id}_{\mathbb{Z}}, and T \circ T is an inverse of T. By Result 5, T is a bijection, and by Result 6, T^{-1} = T \circ T, which steps back once around each block:

T^{-1}(m) = \begin{cases} m + 2 & \text{if } 3 \mid m, \\ m - 1 & \text{otherwise.} \end{cases}

Check: T(T^{-1}(3q)) = T(3q + 2) = 3q. No injectivity or surjectivity proof was needed; any F : A \to A with F \circ F \circ F = \mathrm{id}_A is a bijection in the same way.

Example 7

Day 2: undoing a composite in the right order

Let S be the bit strings of length 3, let v : S \to \{0, 1, \dots, 7\} read a string as a base-2 numeral, so v(110) = 6, and let a : \{0, 1, \dots, 7\} \to \{0, 1, \dots, 7\} send k to the remainder of k + 3 on division by 8. Find (a \circ v)^{-1}(2) and (a \circ v)^{-1}(0).

Solution

v is a bijection, with v^{-1} writing a number in base 2 with three digits, and a is a bijection, with a^{-1}(k) the remainder of k + 5 on division by 8 (adding 5 undoes adding 3, since 3 + 5 = 8). By Result 7, (a \circ v)^{-1} = v^{-1} \circ a^{-1}: first undo a, then undo v. So

(a \circ v)^{-1}(2) = v^{-1}(a^{-1}(2)) = v^{-1}(7) = 111.

Check: v(111) = 7 and a(7) = 2, the remainder of 10. Likewise (a \circ v)^{-1}(0) = v^{-1}(5) = 101, and a(v(101)) = a(5) = 0.

The other order, a^{-1} \circ v^{-1}, is not even defined: v^{-1} produces strings and a^{-1} accepts numbers. Socks go on before shoes, and come off after them.

Boundaries

The middle sets must match. g \circ f needs the codomain of f to be the domain of g. Some books allow the image of f to merely lie inside the domain of g; here one first shrinks the codomain of f to make the sets match.

Order matters. g \circ f and f \circ g may both exist and differ (Exercise 6), or only one may exist (Examples 1 and 2).

One equation is not enough. Example 4 has g \circ f = \mathrm{id}_{\mathbb{Z}} with no inverse in sight. The exception is finite sets of equal size: there g \circ f = \mathrm{id}_A makes f injective, hence bijective (One-to-one, onto and bijective functions, Result 3), and then g = f^{-1} (Exercise 19).

f^{-1} is only for bijections. For a function that is not a bijection there is no inverse function, though one may still speak of the set of preimages of a subset of B.

Where this goes next

Results 3 and 5 are what make “has the same size as” behave like equality in Matching two sets one to one: a bijection A \to B reverses to one B \to A, and two bijections chain into one. That is the ground under Countable sets and Cantor's theorem: no set matches its power set. The bijections of a set with itself, under composition, satisfy associativity (Result 1), have an identity (Result 2) and have inverses (Result 5), the first example of a group in abstract algebra. The real-number versions, with graphs reflected in y = x, are in Inverse functions.

Exercises

Day 1: composing

Exercises 1 to 3 use u and v in Figure 4.

1 2 3 a b c d x y z u v
Figure 4The functions u and v for Exercises 1 to 3.
  1. Give v \circ u as a table, and its image.
  2. Is u \circ v defined? Explain.
  3. Decide whether each of u, v and v \circ u is injective and whether it is surjective.
  4. Let a, b : \mathbb{Z} \to \mathbb{Z}, a(n) = 2n - 1 and b(n) = n^2. Find a \circ b and b \circ a, and every integer n with (a \circ b)(n) = (b \circ a)(n).
  5. Let S_4 be the bit strings of length 4, let c : S_4 \to \{0, 1, 2, 3, 4\} count the 1s, and let e : \{0, 1, 2, 3, 4\} \to \{0, 1\} send k to its remainder on division by 2. Describe e \circ c in words, and decide which of c, e, e \circ c are injective or surjective.
  6. Find f, g : \{1, 2\} \to \{1, 2\} with g \circ f \neq f \circ g.
  7. Let s : \mathcal{P}(\{1, 2, 3\}) \to \{0, 1, 2, 3\}, s(X) = \lvert X \rvert, and let t : \{0, 1, 2, 3\} \to \mathcal{P}(\{1, 2, 3\}), t(0) = \varnothing and t(k) = \{1, \dots, k\} for k \ge 1. Show that s \circ t is an identity, compute (t \circ s)(\{2, 3\}), and say what Result 4 gives.

Day 1: reasoning

  1. Prove Result 2: f \circ \mathrm{id}_A = f and \mathrm{id}_B \circ f = f for f : A \to B.
  2. Prove that if g \circ f is injective and f is surjective, then g is injective.
  3. Prove that if g \circ f is surjective and g is injective, then f is surjective.
  4. Suppose g \circ f is a bijection. Which of f, g must be injective, and which surjective? With A = C = \{0\} and B = \{0, 1\}, give f and g showing neither need be a bijection.

Day 2: finding and using inverses

  1. Let \omega : \{1, 2, 3, 4, 5\} \to \{a, b, c, d, e\} have \omega(1) = c, \omega(2) = e, \omega(3) = a, \omega(4) = b, \omega(5) = d. Give \omega^{-1} as a table and evaluate \omega^{-1}(\omega(2)) and \omega(\omega^{-1}(a)).
  2. Let h : \mathbb{Z} \to \mathbb{Z}, h(n) = n + 1 for even n and h(n) = n - 1 for odd n. Show that h \circ h = \mathrm{id}_{\mathbb{Z}}, and conclude that h is a bijection with h^{-1} = h.
  3. On bit strings of length 5, let \phi(s) be the complement of s (every bit flipped) written backward. Find \phi(10110) and \phi(\phi(10110)), and prove \phi \circ \phi = \mathrm{id}.
  4. Let f, g : \mathbb{Z} \to \mathbb{Z}, f(n) = n - 8 and g(n) = 3 - n. Find g \circ f, f^{-1} \circ g^{-1} and g^{-1} \circ f^{-1}. Which of the last two is (g \circ f)^{-1}?
  5. Decide which have an inverse; give it, or name the property that fails. (a) n \mapsto n + 1, \mathbb{N} \to \mathbb{N}, where \mathbb{N} = \{0, 1, 2, \dots\}. (b) n \mapsto n + 1, \mathbb{Z} \to \mathbb{Z}. (c) X \mapsto X \cup \{1\}, \mathcal{P}(\{1, 2\}) \to \mathcal{P}(\{1, 2\}). (d) X \mapsto \{1, 2\} \setminus X, \mathcal{P}(\{1, 2\}) \to \mathcal{P}(\{1, 2\}).
  6. How many functions \{1, 2, 3\} \to \{1, 2, 3\} have an inverse? How many satisfy f \circ f = \mathrm{id}?

Day 2: reasoning

  1. Prove that if f is a bijection, then f^{-1} is a bijection and (f^{-1})^{-1} = f.
  2. Let f : A \to B be a bijection and g : B \to A with g \circ f = \mathrm{id}_A. Prove that g = f^{-1}.
  3. Prove that if f : A \to A is injective and f \circ f = f, then f = \mathrm{id}_A.
  4. Let A be nonempty and f : A \to B injective. Construct a left inverse of f and prove it is one. Where is “nonempty” used?
  5. Let A be finite and f : A \to B surjective. Construct a right inverse of f and prove it is one.
Answers
  1. 1 \mapsto x, 2 \mapsto x, 3 \mapsto z, since v(b) = x, v(d) = x, v(a) = z. Image \{x, z\}.
  2. No. v outputs x, y, z, which are not in the domain \{1, 2, 3\} of u.
  3. u is injective, not surjective (c is missed). v is surjective, not injective (v(b) = v(d) = x). v \circ u is neither: (v \circ u)(1) = (v \circ u)(2) = x, and y is missed. Result 3 needs both factors to share a property.
  4. (a \circ b)(n) = 2n^2 - 1 and (b \circ a)(n) = (2n - 1)^2 = 4n^2 - 4n + 1. Equal when 2n^2 - 4n + 2 = 2(n - 1)^2 = 0, so only n = 1, where both are 1.
  5. e \circ c sends a string to 0 if it has an even number of 1s and to 1 if odd. All three are surjective and none is injective: c(0000) = 0, c(1000) = 1, c(1100) = 2, c(1110) = 3, c(1111) = 4, but c(1000) = c(0100); e(0) = e(2); (e \circ c)(0000) = (e \circ c)(1100) = 0. That e is surjective also follows from Result 4.
  6. For example f(1) = f(2) = 1 and g the swap g(1) = 2, g(2) = 1. Then g \circ f sends both inputs to 2 and f \circ g sends both to 1.
  7. s(t(k)) = \lvert \{1, \dots, k\} \rvert = k, and s(\varnothing) = 0, so s \circ t = \mathrm{id}_{\{0, 1, 2, 3\}}. (t \circ s)(\{2, 3\}) = t(2) = \{1, 2\} \neq \{2, 3\}. Result 4 gives t injective and s surjective; t \circ s is not an identity.
  8. Proof. All three functions go from A to B. For a \in A, (f \circ \mathrm{id}_A)(a) = f(\mathrm{id}_A(a)) = f(a) and (\mathrm{id}_B \circ f)(a) = \mathrm{id}_B(f(a)) = f(a). \square
  9. Proof. Let g(b_1) = g(b_2). Since f is surjective, b_1 = f(a_1) and b_2 = f(a_2) for some a_1, a_2 \in A. Then (g \circ f)(a_1) = (g \circ f)(a_2), so a_1 = a_2, and b_1 = f(a_1) = f(a_2) = b_2. \square
  10. Proof. Let b \in B. Since g(b) \in C and g \circ f is surjective, some a has g(f(a)) = g(b). Since g is injective, f(a) = b. \square
  11. f must be injective and g surjective (Result 4). Take f(0) = 0 and g(0) = g(1) = 0. Then g \circ f = \mathrm{id}_{\{0\}} is a bijection, but f misses 1 and g is not injective.
  12. \omega^{-1}: a \mapsto 3, b \mapsto 4, c \mapsto 1, d \mapsto 5, e \mapsto 2. Then \omega^{-1}(\omega(2)) = \omega^{-1}(e) = 2 and \omega(\omega^{-1}(a)) = \omega(3) = a.
  13. For even n, n + 1 is odd, so h(h(n)) = (n + 1) - 1 = n. For odd n, n - 1 is even, so h(h(n)) = (n - 1) + 1 = n. So h is an inverse of itself; Result 5 makes it a bijection and Result 6 gives h^{-1} = h.
  14. \phi(10110): complement 01001, backward 10010. Then \phi(10010): complement 01101, backward 10110. Proof. Write \phi = r \circ k, with k the complement and r the reversal. Flipping then reversing equals reversing then flipping, so k \circ r = r \circ k, and k \circ k = r \circ r = \mathrm{id}. By Result 1, \phi \circ \phi = r \circ (k \circ r) \circ k = r \circ r \circ k \circ k = \mathrm{id}. \square
  15. (g \circ f)(n) = 3 - (n - 8) = 11 - n. With f^{-1}(m) = m + 8 and g^{-1} = g, (f^{-1} \circ g^{-1})(m) = (3 - m) + 8 = 11 - m and (g^{-1} \circ f^{-1})(m) = 3 - (m + 8) = -5 - m. The inverse is f^{-1} \circ g^{-1}: (g \circ f)(11 - m) = m, while (g \circ f)(-5 - m) = 16 + m.
  16. (a) No: not surjective, 0 is missed. (b) Yes: m \mapsto m - 1. (c) No: not injective, \varnothing and \{1\} both go to \{1\}. (d) Yes, itself, since \{1, 2\} \setminus (\{1, 2\} \setminus X) = X.
  17. 6: by Result 5 these are the bijections, 3 \cdot 2 \cdot 1 = 6. For f \circ f = \mathrm{id}: 4, the identity and the three swaps of two members.
  18. Proof. The equations f^{-1} \circ f = \mathrm{id}_A and f \circ f^{-1} = \mathrm{id}_B say that f is an inverse of f^{-1}. By Result 5, f^{-1} is a bijection, and by Result 6 its inverse is f. \square
  19. Proof. By Results 2 and 1, g = g \circ \mathrm{id}_B = g \circ (f \circ f^{-1}), and this equals (g \circ f) \circ f^{-1} = \mathrm{id}_A \circ f^{-1} = f^{-1}. \square
  20. Proof. For a \in A, f(f(a)) = f(a). Since f is injective, the inputs f(a) and a are equal. So f(a) = a for every a. \square
  21. Proof. Fix some a_0 \in A. For b \in f(A) let g(b) be the one a with f(a) = b (one only, since f is injective); for b \notin f(A) let g(b) = a_0. Then for a \in A, f(a) \in f(A) and a is its preimage, so g(f(a)) = a. \square Nonempty supplies a_0: with A = \varnothing and B \neq \varnothing there is no function B \to A at all.
  22. Proof. List A = \{a_1, \dots, a_n\}. For b \in B, surjectivity gives at least one i with f(a_i) = b; let g(b) = a_i for the smallest such i. Then f(g(b)) = b for every b, so f \circ g = \mathrm{id}_B. \square
kg1128 · updated 2026-10-22 · CC-BY-SA-4.0