Pigeonhole Principle and Functions
While the Pigeonhole Principle is one of the main ideas in combinatorics, it has broad applications and it is surprisingly simple to understand.
Pigeonhole Principle: If n items are placed into m containers and n > m, then at least 1 container will have more than 1 item.
This post discusses how the Pigeonhole Principle can be applied to study functions. When you understand the dimensions of the domain and codomain (range) of a function, the Pigeonhole Principle can help determine properties of the function, such as if it is injective or surjective.
Functions 101
When you first learned, you probably thought about functions as f(x)=x²+5, but the idea of a function is much more general.
A function f : X → Y is a map from a set X to a set Y so that each element in X is mapped to exactly 1 element in Y.
The set X is called the domain and the set Y is called the codomain or range of f. An important property of functions is that every element in the set X can be mapped to only 1 element in the set Y.
Injective: 1–1
A function is injective when each element in Y can be mapped to by at most 1 element from X.
This is an important property because if a function is not injective, then there is no inverse.
For example, consider the function f(x)=x², which maps from the set of real numbers as the domain to the set of real numbers as the codomain. Since f(2)=2²=4=(-2)²=f(-2), there are 2 inputs to the function that produce the same output, so this function is not injective. However, the function f(x)=x is injective, since only 1 input value can produce any output value.
Surjective: On To
A function is surjective when every element in Y is mapped to by at least 1 element in X.
For example, consider again f(x)=x². Note that for any value of x, x² must be greater than zero. As a result, any value in Y < 0 can’t be mapped to by f(x), so this function is not surjective. However, the function f(x)=x is surjective, since only 1 input value can produce any output value.
When a function is both injective and surjective, we call that bijective. Bijective functions are nice since they are invertible.
Pigeonhole Principle and Functions
To apply the Pigeonhole Principle to functions, consider a function that maps “pigeons” to “pigeonholes.” In the 3 diagrams below, the set of pigeons is the domain, the arrows are the function, and the set of pigeonholes is the codomain.
In the on the left, there are fewer elements in the domain than the codomain, or said another way, the domain is smaller. From looking at the arrows, no 2 pigeons get mapped to the same pigeonhole, so the function is injective. However, there is a pigeonhole that is not assigned a pigeon, so the function is not surjective.
In the example on the right, the domain is larger than codomain. Every pigeonhole has a pigeon mapped to it, so the function is surjective. However, the bottom 2 pigeons are mapped to the same pigeonhole, so the function is not injective.
The middle example, the size of the domain and codomain are the same size. Every pigeonhole is mapped to by exactly 1 pigeon, making the function injective, and every pigeonhole is mapped to, making the function surjective. Since the function is surjective and injective, it is bijective or invertible.
The importance of it being invertible is that if you are given a specific pigeon, you know which pigeonhole it will end up in, and if you are given a specific pigeonhole, you know which pigeon will go there.
Extensions
The pigeonhole principle, functions, and thinking about sets this way is very powerful. These ideas give a powerful intuition for how other concepts in algebra, combinatorics, and set theory. It has applications in data compression, and can it is a great starting point for learning more math. If you are interested in other uses of this, check out the great article here!
If you made it this far, hit the clap button. I’m new to Medium, and trying to crank out some content about how I think about math, data science, and computers. Follow me that’s if your sort of thing.
