Lesson 31: New Functions From Old pt. 1

Before continuing the journey that we began in the previous lesson into the wonderful world of homomorphisms, we need to take a small detour and learn some new things about the wonderful world of general functions. We saw in the previous lesson that when we’re considering functions between groups, we can single out a certain special subclass of functions and call them homomorphisms. There is a very cool story about homomorphisms, and in order to properly understand this story we need to know a few more things about boring old functions, as these new facts will motivate our later, much cooler explorations.

Let’s recall that a function $f$ from a set $A$ to a set $B$ is denoted by $f:A\rightarrow B$ and is nothing but a rule that assigns some element of $B$ to each element of $A$ . This element could be the same for all elements of $A$ or it can be different for each element of $A$ , and it may or may not be the case that every element of $B$ is assigned to some element of $A$ , but it must be the case that every element of $A$ has one and only one element of $B$ assigned to it.

Now, we can (and should) view functions as genuine mathematical objects just as we do sets and groups, and accordingly we can ask the following question (just as we did with sets): given two functions, can we form a third? Namely, can we use the information of two old functions to construct some new function. We ask this question in the same spirit that we were in when we asked whether or not we could form new sets from old ones, to which the answer was indeed yes and we could construct unions, intersections, and Cartesian products (amongst other things). In this lesson we’ll see one way to construct new functions from two old ones, and in the next lesson we’ll see another completely different one.

Let’s start with what might be the more obvious of the two constructions: function composition. The idea behind this is the following. Let’s think of a function $f:A\rightarrow B$ as a way of “getting us from $A$ to $B$ ”, in a similar (but definitely not identical) way to how a metro takes us from point A to point B. Similarly, we could think of a function $g:B\rightarrow C$ as a way of “getting from $B$ to $C$ ”, in which case our metro would be (loosely speaking, of course) taking us from point B to point C. If we took our loose metro analogy seriously, then we find that we can ride our metro from point A to point C by simply “stopping at” point B (perhaps getting to the lower east side of Manhattan from the upper west side of Manhattan by switching lines at the dreaded Times Square station (avoid doing so at 2am on a Saturday night, though)). The question is then set for us: is there a way of defining a function from $A$ to $C$ if we’re given a function from $A$ to $B$ and a function from $B$ to $C$ ?

We can in fact denote this question purely symbolically, as in figure 1 below. In this figure we denote the functions $f:A\rightarrow B$ and $g:B\rightarrow C$ by having the arrows point from the domain of the function to the codomain of the function, and by putting the labels $f$ and $g$ near their corresponding arrows in the obvious way. The “?” then stands for “can we build such a function?”. This type of graphical representation of certain mathematical structures is not only extremely cool, but also extremely important for much of what is to follow in the coming lessons, so it is important to fully appreciate its coolness and to become familiar with the information that these graphical representations are trying to put forward. This is nothing but a cool new type of notation!

figure 1

To compare the more technical formulation of the problem to the more colloquial one, let me phrase the question this way: is there a way of defining a function whose domain (take off location) is $A$ and whose codomain (destination location) is $C$ , if we know that we have a function whose domain is $A$ and whose codomain is $B$ , and another function whose domain is $B$ and whose codomain is $C$ (thus making $B$ the Times Square stop on the way to City Hall from Columbia University).

The answer is of course yes (“of course” because otherwise I wouldn’t have written this lesson), so let’s see how this is done. Suppose we’re given the function $f:A\rightarrow B$ and the function $g:B\rightarrow C$ . We notice that this is precisely the set up for the question above. Let me then define the function that sends each element $a\in A$ to the element $g(f(a))\in C$ . Let me explain what that means. The element $g(f(a))\in C$ is the element obtained by first sending $a\in A$ to the element $f(a)\in B$ (using the function $f$ ) and then noticing that this is just some perfectly well-defined element in $B$ so that we can use our function $g$ to send this element to $g(f(a))\in C$ . There is an exercise about the composition of functions at the end of this lesson which may help to make this definition less abstract. If this idea is unclear at the moment, I encourage the reader to go look at exercise 1 in this lesson now and return afterwards.

One thing we need to do is make sure that this definition is indeed well-defined, meaning that we need to make sure our definition of assigning things in $C$ to elements of $A$ is indeed an actual function (because recall that functions have specific requirements that they need to satisfy!). In particular, we need to check that every element of $A$ is sent to one and only one element in $C$ (these are precisely the requirements that need to be satisfied for our rule to be a function). Luckily, these requirements are guaranteed to be satisfied since we know that $f$ and $g$ are themselves functions.

To see this, let’s first check that indeed every element of $A$ is sent somewhere. This is guaranteed since $f$ is a function and therefore “picks up” every element in $A$ and sends it somewhere in $B$ , and similarly $g$ is a function and therefore “picks up” every element in $B$ and sends it somewhere in $C$ . To see that each element in $A$ goes unambiguously to one and only one element in $C$ is also clear, since again we know that both $f$ and $g$ have this quality. In other words, since $f$ sends each element in $A$ to one and only one element in $B$ , and since $g$ sends each element of $B$ to one and only one element of $C$ , we know that applying $f$ and then $g$ sends each element of $A$ to one and only one element of $C$ (this may seem painfully obvious (and it may not), but it’s worth mentioning).

Let me note that this is a pattern we’ll see over and over again in mathematics. Namely, we’ve seen that we can construct some new object from two old ones, and we prove that the new object indeed has the required properties to be such an object solely because the old objects used to construct it had those properties. Namely, we’ll see that we can construct new groups from old ones, and the way that we prove that the new thing we create is indeed a group is by relying heavily on the assumption that the two things we started with were indeed groups. We’re seeing now that we can construct new functions from old ones, and the fact that the new thing is indeed a function comes from the fact that the two old things were functions as well. In this case the “proof” of the “function-ness” of the thing that we created is a bit trivial (or perhaps not), but the thought process is an extremely important one!

Before setting up the notation for function compositions, let me emphasize how important it is that the codomain (“end”) of one function is the domain (“beginning”) of the next. We used the notation $g(f(a))$ to denote the statement “first send $a$ to $f(a)$ and then to $g(f(a))$ ”. However, this is completely ill-defined if the codomain of $f$ is different from the domain of $g$ , since in this case $g$ “wouldn’t know” how to send $f(a)$ anywhere, since $f(a)$ isn’t in the “domain of influence” of $g$ .

Let me further expand on this absolutely essential point using the following basketball analogy. In basketball, every pass needs to go from some player to some other player. In this way a pass is kind of like a function, with a domain and a codomain. In order for a play involving more than one pass to be well-defined, it must be the case that the codomain of one pass is always the domain of the next pass. Namely, “Johnny passes to Billy, then Billy passes to Eric, then Eric passes to Timmy” is a well-defined play, whereas the play “Johnny passes to Eric and then Timmy passes to Billy” is completely ill-defined, since Timmy never gets the ball and therefore can’t ever pass it to Billy! This is exactly the kind of “ill-defined-ness” that we’re avoiding above by forcing the two functions that we want to compose to be such that the codomain of the initial function (the recipient of the first pass) is the same as the domain of the second function (the starting point of the next pass).

We’re now ready to define the compostion of functions, and in doing so we’ll set up some notation for this idea as well.

Defintion 31.1 Let $f:A\rightarrow B$ and $g:B\rightarrow C$ be two functions, with their domains and codomains as written. The composition of $f$ and $g$ , denoted by $g\circ f$ , is the function $g\circ f: A\rightarrow C$ that takes $a\in A$ to $g(f(a))\in C$ —this last phrase is often denoted by $a\mapsto g(f(a))$ . In other words, $g\circ f(a)=g(f(a))$ .

We’ve therefore answered the question that we posed ourselves above, and the answer is to use the composition of the two given functions. Graphically, the answer can be seen in figure 2.

figure 2

In order to get fully acquainted with this definition one should really do (or at least look at) the following exercises. In the next lesson we’ll see another construction of a new function from two old ones which differs from this construction quite drastically. Enjoy!

Exercises:

1) Let $f:\{1, 2, 3, 4\}\rightarrow \{a, b, c\}$ be the function defined as $f(1)=b, f(2)=b, f(3)=c, f(4)=a$ and let $g:\{a,b,c\}\rightarrow \{apple, Kobe, Donkey, fruitcake\}$ be the function defined as $g(a)=Kobe, g(b)=fruitcake, g(c)=Donkey$ . Write down (or say out loud, or figure out in your head) the value of $g\circ f: \{1, 2, 3, 4\}\rightarrow \{apple, Kobe, Donkey, fruitcake\}$ for each element in $\{1, 2, 3, 4\}$ . In other words, calculate $g(f(a))$ for all $a\in A$ .

2) Recall that $\mathbb{Z}$ is the set of integers: $\mathbb{Z}=\{..., -3, -2, -1, 0, 1, 2, 3, ...\}$ . Let $\mathbb{E}$ denote the set of even integers: $\mathbb{E}=\{..., -6, -4, -2, 0, 2, 4, 6, ...\}$ . Let $\mathbb{T}$ denote the set of multiples of 3: $\mathbb{T}=\{..., -9, -6, -3, 0, 3, 6, 12, ...\}$ . Let $f:\mathbb{Z}\rightarrow \mathbb{E}$ be the function that takes each integer to 4 times that integer, so that $f(a)=4\times a$ and for example $f(-5)=-20\in \mathbb{E}$ (note that $f$ is most certainly not surjective). Now let $g:\mathbb{E}\rightarrow \mathbb{T}$ be the function that sends each element in $\mathbb{E}$ to 3 times itself, so that $g(a)=3\times a$ and for example $g(6)=18$ . Let $g\circ f:\mathbb{Z}\rightarrow \mathbb{T}$ be the composition of $f$ and $g$ . Calculate