Lesson 8: Bijectivity and Counting

You might be surprised to see that the word “counting” doesn’t show up until the 8th lesson of this series, seeing as this is a series of lessons on mathematics—and what could mathematics be about if not counting?  Recall, however, that this is a completely new mathematics that we’re learning.  And by “new” I mean “real”.  In other words, this is the kind of math the real mathematicians think about and have thought about for a while now.  We’ll see in this lesson that the type of abstractions that we’ve been dealing with actually lend themselves very nicely for defining a notion of counting—in an abstract way—the number of elements in a set.  Beginning with the next lesson, we’ll go on to use this new technique of counting to prove some truly remarkable things about “infinity”.  In particular, the reader will find that infinity is infinitely more complex than he or she could have imagined!

For now, let us begin at the beginning.  Recall that in the last couple of lessons we’ve developed the machinery of functions between sets.  These were associations which “mapped” each element in one set to some element in another.  For precision, let’s recall that a function f from A to B, written , sends each element in A to some element in B.  Additionally, we recall that an injective function is a function that maps elements in its domain to elements in its codomain in such a way that no two distinct elements in the domain get sent to the same element in the codomain.  Recall that in our school dance analogy (see Lesson 7), this occurs when there are never two boys dancing with the same girl.  A surjective function is a function that “hits” every element in its codomain with at least one element in its domain.  In our analogy, this occurred when every girl had at least one boy to dance with.  A bijective function is simply a function which is both injective and surjective.  We’ll explore this concept more now.

What does bijectivity have to do with counting?  Well, let us first see what injectivity and surjectivity have to do with counting, since if we can understand those cases we’ll certainly be able to understand the bijective case (which is just both at once).  Let’s continue on with the school dance analogy.  We saw before that if we wanted to define a surjective function from the boys to the girls, we need at least as many boys as there are girls.  This should be obvious, since the definition of a function forces us to only assign one girl to each boy, and not more.  Thus, if there are more girls than boys, even if we assign a different girl to each boy, we’d still have girls left over.  Therefore if there is some set of boys and some set of girls, and someone tells you that they’ve successfully defined a surjective function from the boys to the girls, then you automatically know that there are at least as many boys as there are girls.  I.e., the number of boys is greater than or equal to the number of girls.

What if someone were to tell us that they successfully defined an injective function from the boys to the girls?  What does this say about how many boys and girls there are?  Well, we know that an injective function sends each boy to a different girl. I.e., once one boy is assigned a girl, then no other boys get assigned to that girl.  If it is possible to assign all the boys to girls in this way, then clearly it must be the case that there are at least as many girls as there are boys.  For suppose there are less girls than boys.  As we start to assign boys to girls, we’ll “run out” of girls before we do boys, since we can never assign two boys to the same girl (by definition of injectivity).  However, we must send every boy to some girl, by definition of a function (remember, boys are the domain of this function).  Thus it must be the case that being able to successfully define an injective function from boys to girls is equivalent to having at least as many girls as there are boys.  I.e., the number of girls is greater than or equal to the number of boys.

It should now be clear what a bijective function between boys and girls means: there are just as many boys as there are girls.  For if the function is bijective, then it is surjective so that the number of boys is greater than or equal to the number of girls.  But we also know that the function is injective, and therefore the number of girls is greater than or equal to the number of boys.  There is only one way for two numbers to be mutually “greater than or equal to” each other, and that is only if they are the same number!  Thus, we know that if we’re given a set of boys and a set of girls and someone tells us that they’ve managed to successfully define a bijective function from the boys to the girls, then we immediately know that there are exactly as many boys as there are girls!

So what does this have to do with counting?  Suppose I hand you a set of apples and I ask you how many apples are in the set. What would you do?  Naturally, you would count them of course!  But what are you “really” doing when you’re counting them? Remember, this is what we’re after in math—what we’re “really” doing when we’re doing something that seems trivial (this is an example of abstract thought).  In other words, how can we rigorously define the notion of “how many are there”?  Now that we have the notion of bijectivity in our heads, we can rather easily define the very act of counting in a completely rigorous way.

Consider the set where N is some positive whole number, and where the “…” means that all the positive whole numbers between 4 and N are also included in the set.  For concreteness, consider the set .  Clearly, if I have a set of 5 apples, then you can define a bijective function from A to my apples.  More clearly, you most certainly could not define a bijective function from to my set of apples, nor could you define one from to my set of apples.  It has to be .  Well, this seems obvious, because I told you that my set of apples has 5 elements in it.  After all, I said it was “a set of 5 apples”.  But let us suppose that we naively didn’t know how to count.  We could define counting—we could define what it means for a set to have N elements—by saying that a set has N elements when it can be put into bijection with the set (of course, if the set has 1 or 2 or 3 elements, then we would adjust the notation of the previous set accordingly).

We could have chosen some other set with N elements in it when defining what it means for a set to have N elements in it.  I.e., we could say, “a set has 3 elements when it can be put into bijection with the set ,” or we could say “a set has 4 elements when it can be put into bijection with the set ”.  It is simply a convention (and a smart one), to use the set for some N. Thus, if I want to decide how many elements are in my set, I simply start with the set and ask if there can be a bijective function from to my set.  If there can’t, then I move on to and ask the same question.  If the answer is no, I move on to , and so on, until I finally get a yes.  I then know that no other set of this form will do it, so I simply look at which “N” I’ve stopped at and that’s how many elements are in my set!

Of course, this is not how we count in real life, but we can use this method to define “counting” rigorously.  Its power and beauty will become evident in the coming couple of lessons as we begin to see how perfect of a tool this method is for analyzing all the different types of infinity.  And yes, there is more than one type of infinity!

Next Lesson

Previous Lesson