Lesson 7: Injective, Surjective, Bijective

Before we panic about the “scariness” of the three words that title this lesson, let us remember that terminology is nothing to be scared of—all it means is that we have something new to learn! As you’ll see by the end of this lesson, these three words are in fact not scary at all. Mathematicians have a funny way of assigning very fancy words to ideas that are not very deep, and this is one such instance. Let us therefore go ahead and just learn what these words mean.

In the previous lesson we learned about functions between sets, thus giving us a mechanism for relating elements in one set to elements in another set (although this “other” set could be the set itself: for example, if , then a function f from A to A such that is a perfectly good function, as is a function g from A to A such that . We recall that a function is an incredibly general object: all that is needed is two sets and a relation between them such that one of the two sets has every one of its elements associated with exactly one element in the other set.

And that’s it. There were no other requirements on functions. In particular, if (recall that this reads “if f is a function from the set A to the set B”), then f could be such that it sends every element in A to the same element in B. There also weren’t any requirements on how many elements in B needed to be “hit” by the function. A function is simply a rule that assigns to each element in A exactly one element of B, and any other property that the function has is just a bonus.

The generality of functions comes at a price, however. The cost is that it is very difficult to prove things about a general function, simply because its generality means that we have very little structure to work with. Thus, what we want to do is focus on certain kinds of functions. I.e., we want to limit ourselves to considering functions that have specific properties so that we can use these new properties to prove things. This is in fact a very general pattern in mathematics: we define some very general object (a set, a function, or whatever) and then slowly start to “add structure” to it so that we can prove things. By “add structure” I simply mean that we give certain extra properties to the object so that even though it loses some of its generality, it gains a certain structure that allows us to ask more interesting questions about it.

So what type of “special functions” do we want to consider here? Let us consider what a function is, and ask what the “most obvious” kinds of properties we’d like some functions to have. For the rest of this lesson, let’s let (“let’s let f be a function from the set A to the set B). First, recall f can send two different elements in A to the same element in B. For example, if and , then the function defined by is a perfectly good function, despite the fact that cat and dog are both sent to cheese. Suppose, however, that f were a function that does not have this property for any elements in A. Namely, suppose that f does not send any two distinct elements in A to the same element of B. We would then call this function injective. Let us see an example.

Let A be a set of boys and B be a set of girls, and let f be the function of “a school dance”. Namely, let f be a function that assigns boys in A to dance with girls in B. If f were just any old function, then it could be the case that all the boys are dancing with the same girl (surely an uncomfortable experience), or it could be the case that five boys are dancing with one girl, and the rest of the boys are dancing with some other girl (still rather uncomfortable). But suppose it were the case that each boy was assigned a different girl, so that no girl was dancing with more than one boy. Then this function would be injective.

There is an important quality about injective functions that becomes apparent in this example, and that is important for us in defining an injective function rigorously. Suppose you told me that the function that assigns boys to girls is injective, and suppose you also told me that “boy 1” were dancing with “girl 17”, and that “boy 56” were also dancing with “girl 17”. Then I would immediately know that boy 1 and boy 56 are actually the same person (the same element of the set), because I know that no two different boys are dancing with the same girl (because you told me the function was injective). Thus, an injective function is one such that if a is an element in A, and b is an element in A, and (f sends them to the same element in B), then a=b! Let us therefore make this a definition:

Definition 7.1 Let be a function from the set A to the set B. Then f is injective if for any elements a and b in A, implies that . //

Said less formally, this definition tells us that a function is defined to be injective if any time two elements in A are sent to the same element in B, they must in fact have been the same elements in A to begin with!

Let us now reconsider the school dance. Even if the function is injective, it is not necessarily the case that every girl has a boy to dance with. Namely, there might just be more girls than boys. In this case, even if only one boy is assigned to dance with any given girl, there would still be girls left out. The situation is of course worse if several boys are allowed to dance with the same girl (i.e., if the function is not injective). But suppose that there are enough boys for each girl to have a dancing partner. This still doesn’t necessarily mean that each girl will have a dancing partner because we could, for example, assign all the boys to dance with the same girl (leaving all the rest partner-less). If, however, we assigned the boys in such a way that every girl did have a dance partner (perhaps more than one), then the function is called surjective.

Notice that surjectivity says nothing about how many boys are dancing with a certain girl, but rather only that each girl has at least one boy dancing with her. If there were 10 boys (labeled “boy 1”, “boy 2”, and so on), and 4 girls (similarly labeled), then we could assign boys 1-7 to dance with girl 1, and then boy 8 to dance with girl 2, boy 9 with girl 3, and boy 10 with girl 4. Then each girl has a partner despite the fact that they have very different numbers of them. We now have enough to make the following definition:

Definition 7.2 Let . Then f is said to be surjective if for every element b in B, there is some element a in A such that . //

More casually, this just means that we define a function to be surjective if for every element in its codomain (remember “codomain” from the previous lesson?) we can go find some element in its domain that gets sent to it. It might be the case that there are several different elements in its domain that we could go find, but as long as we can always find one, then we call the function surjective.

We end this lesson with a definition that we’ll end up exploring a lot more in the next lesson. Given what we’ve defined so far, it is in fact a very obvious definition to make.

Definition 7.3 Let . Then f is said to be bijective if it is both injective and surjective. //

Note that this definition is meaningful. In other words, we’ve seen that we can have functions that are injective and not surjective (if there are more girls than boys), and we can have functions that are surjective but not injective (if there are more boys than girls, then we had to send more than one boy to at least one of the girls). Thus, we are further limiting ourselves by considering bijective functions. I.e., the class of bijective functions is “smaller” than the class of injective functions, and it is also smaller than the class of surjective ones. Moreover, the class of injective functions and the class of surjective functions are each smaller than the class of all generic functions. In this way, we’ve lost some generality by talking about, say, injective functions, but we’ve gained the ability to describe a more detailed structure within these functions. This will prove very fruitful in the coming lessons (as we work our way up to seeing that there is more than one type of infinity).

Exercises:

1) Define two of your favorite sets (numbers, household objects, children, whatever), and define some a) injective functions between them (make sure to specify where the function goes from and where it goes to) b) surjective functions between them, and c) bijective functions between them. Is it always possible to do this for each case? If not, why not?

Solutions to Exercises

Next Lesson

Previous Lesson