Example 15: Computing $g\circ f$ on finite sets

Basics you need

Solution

1. Check that $gof$ is defined

   $f$ goes from $A = \{2,3,4,5\}$ into $B = \{3,4,5,9\}$⁠, and $g$ starts from the same set $B$⁠. So every output $f(x)$ is an element of $B$⁠, and $g$ can be applied to it. Hence $gof$ is a function from $A$ to $C = \{7,11,15\}$⁠:

   $$A \xrightarrow{\ f\ } B \xrightarrow{\ g\ } C, \qquad gof : A \to C.$$
   Composition only makes sense when the second function can accept every output of the first. If $f$ could produce a value outside the domain of $g$⁠, then $g(f(x))$ would have no meaning for that $x$⁠. Here $f$'s codomain and $g$'s domain are the same set, so there is nothing to worry about. This is exactly the setting of Definition 8.
   Definition 8: for $f : A \to B$ and $g : B \to C$⁠, $gof : A \to C$ is given by $gof(x) = g(f(x))$ for all $x\in A$⁠. Lesson: composition of functions

2. Compute $gof(2)$ and $gof(3)$

   Work from the inside out: first the inner value $f(x)$⁠, then $g$ of it.

   $$\begin{aligned} gof(2) &= g(f(2)) = g(3) = 7,\\ gof(3) &= g(f(3)) = g(4) = 7. \end{aligned}$$
   The bracket $g(f(2))$ tells us the order. We cannot evaluate $g$ until we know what it is being applied to, and that is $f(2)$⁠. From the list, $f(2) = 3$⁠; then from $g$'s list, $g(3) = 7$⁠. The same two look-ups give $f(3) = 4$ and $g(4) = 7$⁠.
   Inner function first: in $g(f(x))$⁠, $f$ acts on $x$ and $g$ acts on the result. This is the usual rule for nested brackets, the same as working out $\sqrt{(2+7)}$ by adding first.

3. Compute $gof(4)$ and $gof(5)$

   $$\begin{aligned} gof(4) &= g(f(4)) = g(5) = 11,\\ gof(5) &= g(f(5)) = g(5) = 11. \end{aligned}$$

   (The textbook shortens the last line to $gof(5) = g(5) = 11$⁠, because $f(5) = 5$⁠.)

   The question gives $f(4) = f(5) = 5$⁠: two inputs share the output 5. Whatever $g$ does to 5, it does once, so $gof(4)$ and $gof(5)$ must be equal. Note that the value $g(9) = 11$ is never used, because no element of $A$ is sent to 9 by $f$⁠.
   A function may send different inputs to the same output (here $f(4)=f(5)$⁠). It may not send one input to two outputs. That is why $f(5)$ has the single value 5 and the look-up is unambiguous. Basics: what a function is

4. Collect the answer

   Putting the four values together:

   $x$	2	3	4	5
   $f(x)$	3	4	5	5
   $gof(x) = g(f(x))$	7	7	11	11

   So $gof(2) = 7$⁠, $gof(3) = 7$⁠, $gof(4) = 11$⁠, $gof(5) = 11$. As a set of ordered pairs,

   $$gof = \{(2,7),\ (3,7),\ (4,11),\ (5,11)\}.$$
   A function on a finite set is completely known once its value at every element of the domain is known (Basic 1). We have all four values, so $gof$ has been found in full. The middle set $B$ is only a stopping point; it does not appear in the answer.
   A function $h : A \to C$ can be written as the set of pairs $\{(x, h(x)) : x\in A\}$⁠. Basics: ordered pairs

5. What kind of function is $gof$⁠? (an extra look)

   The book does not ask this, but it is worth seeing what the composite inherits.

   • $gof$ is not one-one: $gof(2) = gof(3) = 7$ with $2 \ne 3$⁠.
   • $gof$ is not onto $C$⁠: the range of $gof$ is $\{7, 11\}$⁠, and $15 \in C$ is not an output.
   • Neither is $f$ one-one ($f(4)=f(5)$⁠) or onto $B$ (nothing goes to 9), and $g$ is neither one-one ($g(3)=g(4)$⁠) nor onto $C$ (nothing goes to 15).

   Also, the other order $fog$ is not defined here: $g$ outputs 7 or 11, and these are not in the domain $\{2,3,4,5\}$ of $f$⁠, so $f(g(3)) = f(7)$ has no meaning.

   Each claim is settled by the lists themselves. "Not one-one" needs one pair of different inputs with equal outputs, and $2, 3$ is such a pair. "Not onto" needs one element of the codomain that is never hit; since $gof$ only ever produces 7 and 11, the element 15 is never hit. The remark about $fog$ shows that composition depends on order: one order can be defined while the other is not.
   To disprove "one-one" or "onto", one explicit counterexample is enough. Basics: proving and disproving

Every fact used, and where it comes from