Numbers: Their Tales, Types, and Treasures.

Chapter 1: Numbers and Counting

1.6.THE BIJECTION PRINCIPLE AND THE COMPARISON OF SETS

A bijection is a one-to-one correspondence that describes a perfect match between two sets. Figure 1.6 shows flies sitting on the pebbles. There is no pebble without a fly, no two flies sit on the same pebble, and no fly is without a place to sit. Hence there is a one-to-one correspondence—a pairing—between pebbles and flies. In mathematical terminology: There is a bijection between the set of pebbles and the set of flies in this image.

Figure 1.6: Counting via one-to-one correspondence (bijection principle).

As a consequence, we can say immediately and without counting that there are as many flies as there are pebbles. Whenever there is a bijection between two finite sets, we know that they contain the same number of elements.

We can also use the bijection principle to find out whether one set is bigger than another. Obviously, the set of flies is bigger than the set of pebbles if, after pairing the flies with pebbles, all the pebbles get used and some flies are still left over. Or we could also draw the oppositeconclusion: When there are more flies than pebbles, then either some flies are without a pebble or there must be at least one pebble with two or more flies on it. In mathematics, this observation is called the pigeonhole principle. It states that when we put n objects (pigeons) into m holes, andn is bigger than m, then at least one hole will contain two or more objects (pigeons). We can use this simple observation to answer the following question: Are there two people in New York City who have exactly the same number of hairs? The answer is yes. There are more than eight million people in New York City, and even the hairiest among them will have fewer than a million hairs. Hence, the possible hair numbers range from zero to fewer than a million, and there are more people than there are possible hair numbers. By the pigeonhole principle, when we attempt to assign to each person a hair number, at least one of the hair numbers will have to be assigned to two or more persons.