In the previous lesson we explored one possible way of taking two functions (that are assumed to somehow already be “given” to us, so to speak) and forming a third (new) function from them. We noted that this is very similar in spirit to our definitions of unions, intersections, and Cartesian products of two sets, each giving a way to form a third set from the information of two initially given sets. And just as there is more than one to form a third set from two old ones, there is more than one way to do the same for functions. This lesson explores a second way of doing so.
Before making our definitions, let us make a little more contact with the likely more familiar story of sets. As mentioned above, we have three different ways of forming a new set from two old ones: 1) we can form the union of the two old ones, 2) we can form the intersection of the two old ones, and 3) we can form the Cartesian product of the two old ones. These three different constructions can then be classified into two different classes: one type of construction leaves the underlying elements of the two old sets alone, and the other type of construction creates a set whose underlying elements are different than those of both of the original sets. In particular, the process of forming the union or intersection of two sets is to simply form a third set whose elements are taken from the two original sets in precisely the same form. For example, if one of our old sets is a set of basketballs and dinosaurs and the other old set is a set of basketballs and dinosaurs, then the union (and intersection) of these two sets is a set of basketballs and dinosaurs just the same (just possibly a different collection of basketballs and dinosaurs). The Cartesian product construction, however, differs in the sense that the underlying elements are changed. Namely, in the above case of sets of basketballs and dinosaurs, the individual elements of the Cartesian product of the two old sets are neither basketballs nor dinosaurs, but rather a collection of abstract pairs of basketballs and dinosaurs.
Let us quickly note that this is all entirely okay! A set is just a collection of elements. If we want to build a new set from two old ones, all we need to do is create a collection of elements—there is no requirement that these elements must be the same as the elements in the old sets.
We now turn our attention to how this all relates to creating new functions from old ones. Our discussion in the previous lesson introduced the construction of the composition of two functions. In this construction we were able to define a third function from two old ones without changing the underlying domains and codomains. Namely, we saw that if we have a function and another function then we can define a third function . In other words, if the codomain of is the same as the domain of then we can define a third function whose domain is that of and whose codomain is that of . We are reminded therefore that we can’t “willy nilly” define a third function from two old ones—the two old functions must satisfy certain requirements on their domains and codomains. Moreover, and more interestingly, we can ask the question of whether or not we can define a third function from two old ones in such a way that the underlying domains and codomains are changed (analogous to the changing of the underlying elements in the Cartesian product construction). Indeed we can, and in exploring one particular way we will also find a way to define a third function from two old ones even if the constraints on the respective domains and codomains needed for composition are not satisfied. Let us see how this goes.
Suppose we’re given (by some enemy or divine creature or math teacher or what have you) two functions and . We note immediately that unless (or ) as sets, we cannot define the composition (or ) of and because in neither case does the domain of one equal the codomain of the other. This doesn’t mean that we can pack up and go home, though, for there are other interesting things that we can do.
The way out of our “oh-no-we-can’t-form-a-composition-function” conundrum is to change the underlying domains and codomains. The essence of this idea is that even though we can’t (in general) define a function from, say, to using the information of and we can define a function from the Cartesian product to the Cartesian product . In other words, as we’ll soon see, we can define a new function from the Cartesian product of the domains of and to the Cartesian product of the codomains of and . Despite this possibly confusing wording, the math is actually quite straightforward.
Consider the set . We remind the reader that this is nothing but the set of pairs with and . For each though, assigns a particular element since we know that is a function from to . Similarly, for each assigns the particular element to it. Thus, to each we can assign the element .
Before defining our function, we need to first check that this method of assigning elements in to elements in is in fact in line with the definition of a function. In particular, we need to ensure that each element in is sent somewhere in and we need to make sure that each element in is sent to only one element in . This property of the assignment procedure indeed follows straightforwardly from the fact that we already know that and are functions and therefore have the “function properties” required of them for their respective domains and codomains. We leave the explicit proof—which is highly recommended to the reader to at least read through, as it nicely illustrates how to succinctly use the formalism that we’ve built up to prove new things within the formalsim—to the exercises. For now, we assume that this method of assigning elements of to elements of indeed forms a function.
Let us give this function some nice notation. Namely, we denote the function that sends each to by the symbol . Thus, analogous to the notation we have the notation . The expression gives us a symbolic “name” for the function, is the domain of the function, and is the codomain of the function. Additionally, analogous to the statement that is an element of (namely, that element of that is sent to by ), we now have the statement that is an element of where in the symbolic expression we simply have that replaces as the name of the function and replaces as the element in the domain that is getting sent to the codomain. Explicitly, we have that since the right hand side is the element in that is, by definition, the image of the element under the function .
Let’s now take a look at a concrete example so that we can get a feel for how these abstract ideas can actually be used to do some mathematical things. Let us suppose that that that and that let us suppose that is a function such that and and finally let us suppose that is a function such that and Phew! That was a lot of “supposing”, but this is all that is meant by the phrase “suppose we’re given a function and a function ”. Namely, to be “given” some mathematical structure, we must either construct it explicitly ourselves (which we’ve just done, by “supposing” that we have them), or we acquire them from some other mathematical problem or proof—either way, though, once we have them, we can do with them what we want. In particular, let us now examine the function that we now know about, namely .
We have already explicitly constructed both the functions and and therefore the action of the function is completely fixed for us. In other words, we had the freedom to choose and as we desired (so long as what we chose was indeed mathematically well-defined, i.e. satisfying the requirements of what a function is, etc.), but once we’ve chosen these functions we are stuck with the resulting . This is part of the beauty of math: we can define certain structures quite freely, and then we are forced to deal with their eternal, objective, indisputable consequences. The art of mathematics then is, in part, the act of figuring out which objects to define in order to get the most interesting and/or beautiful and/or useful (unavoidable) consequences.
Enough philosophizing, let us just go on and see what the function with and defined above, looks like. First let’s examine the domain of . This is and writing out all of the elements explicitly we have
Let’s now look at the codomain, . We have
We then have that the image of, for example, under the action of the function is . In symbols, we have . In the same way, we can see where the other five elements in are mapped under and we leave the explicit results for the exercises (see Exercise 2). We also leave one other full example—a slightly more open ended example—to Exercise 3.
In the next lesson we return to the world of groups and homomorphisms, and we use the construction of to give a more abstract view of homomorphisms. This will have important uses for us in the (very) far future when we discuss the mathematical structure known as categories, but for now it will simply give us a (very) cool pictorial representation of homomorphisms. Here’s to plowing further into the true beauty of math!
1) Prove that if and are both functions, then as defined in this lesson, is also a function.
2) Explicitly write where the remaining five elements (i.e., those that are not ) in go under the action of in the example discussed at the end of this lesson.
3) Define four sets and of your choosing, and define two functions and also of your choosing (but make sure they’re well-defined!). As explicitly as possible*, write out the action of i.e., write out where each element in the domain of goes in the codomain.
*It may not be possible to explicitly list where each individual element in the domain goes, as may be the case if you define sets with infinitely many elements. Nonetheless, express the action of as concretely as possible.