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 from a set to a set is denoted by and is nothing but a rule that assigns some element of to each element of . This element could be the same for all elements of or it can be different for each element of , and it may or may not be the case that every element of is assigned to some element of , but it must be the case that every element of has one and only one element of 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 as a way of “getting us from to ”, 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 as a way of “getting from to ”, 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 to if we’re given a function from to and a function from to ?
We can in fact denote this question purely symbolically, as in figure 1 below. In this figure we denote the functions and by having the arrows point from the domain of the function to the codomain of the function, and by putting the labels and 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!
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 and whose codomain (destination location) is , if we know that we have a function whose domain is and whose codomain is , and another function whose domain is and whose codomain is (thus making 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 and the function . We notice that this is precisely the set up for the question above. Let me then define the function that sends each element to the element . Let me explain what that means. The element is the element obtained by first sending to the element (using the function ) and then noticing that this is just some perfectly well-defined element in so that we can use our function to send this element to . 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 to elements of 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 is sent to one and only one element in (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 and are themselves functions.
To see this, let’s first check that indeed every element of is sent somewhere. This is guaranteed since is a function and therefore “picks up” every element in and sends it somewhere in , and similarly is a function and therefore “picks up” every element in and sends it somewhere in . To see that each element in goes unambiguously to one and only one element in is also clear, since again we know that both and have this quality. In other words, since sends each element in to one and only one element in , and since sends each element of to one and only one element of , we know that applying and then sends each element of to one and only one element of (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 to denote the statement “first send to and then to ”. However, this is completely ill-defined if the codomain of is different from the domain of , since in this case “wouldn’t know” how to send anywhere, since isn’t in the “domain of influence” of .
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 and be two functions, with their domains and codomains as written. The composition of and , denoted by , is the function that takes to —this last phrase is often denoted by . In other words, .
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.
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!
1) Let be the function defined as and let be the function defined as . Write down (or say out loud, or figure out in your head) the value of for each element in . In other words, calculate for all .
2) Recall that is the set of integers: . Let denote the set of even integers: . Let denote the set of multiples of 3: . Let be the function that takes each integer to 4 times that integer, so that and for example (note that is most certainly not surjective). Now let be the function that sends each element in to 3 times itself, so that and for example . Let be the composition of and . Calculate
On to Lesson 32