PineWikiThe pigeonhole principle says that if you put m pigeons in n < m holes, some hole gets more than one pigeon. Stated more formally, there is an injection from m = { 0, 1, 2, ..., m-1 } to n = { 0, 1, 2, ..., n-1 } if and only if m ≤ n. (Note that we are using the definition of natural numbers from SetTheory, where a natural number is represented by the set of all smaller natural numbers.)
1. Proof
The if part is easy: when m ≤ n, let f:m→n be given by f(x) = x. It is trivial to verify that this is indeed an injection.
For the only if part, we proceed by induction on n. When n = 0 = { }, there is no function from m to n at all unless m is also 0. This gives us our base case.
For larger n, we have from the induction hypothesis that there is an injection from m' to n-1 if and only if m' ≤ n-1.
Now consider some m, and suppose that there is an injection f from m to n. Because f is an injection, it maps at most one element x of m to the last element n-1 of n. Define a new function f':(m-1) → (n-1) by f'(y) = f(y) if y < x and f'(y) = f(y+1) if y ≥ x. The range of f' includes the entire range of f except f(x) = n-1, so f' is indeed a function from (m-1) to (n-1). To show that f' is an injection, suppose for some y and z that f'(y) = f'(z). If y and z are both less than x, we have f(y) = f'(y) = f'(z) = f(z) and so y = z (since f is an injection). If y and z are both greater than or equal to x, we similarly have that f(y+1) = f'(y) = f'(z) = f(z+1) and y+1 = z+1, implying y = z. If y is less than x and z greater than or equal to x, we have f(y) = f'(y) = f'(z) = f(z+1), so y = z+1; but this contradicts the assumption that y < z. The remaining case is symmetric. In each case it follows that f':(m-1)→(n-1) is an injection, so m-1 ≤ n-1. But then m ≤ n.
2. Applications
|S| is well-defined (for finite S). Suppose that there are bijections f:S↔m and g:S↔n. Then fg-1:n→m is an injection as is gf-1:m→n. From the pigeonhole principle we have that n ≤ m and m ≤ n and thus n = m.
Any function f:S→T, where |T| < |S|, is not an injection. For example, the undergraduate population of Yale College consists of approximately 4000 students none of whom stand more than 3000 millimeters tall. We can immediately conclude that at any given time there is at least one pair of Yale undergraduates who are equal in height when rounded to the nearest millimeter. Note that this is a pure existence proof: it provides no guidance for finding this pair, and indeed the winning pair or pairs may change from moment to moment as students grow, shrink, slouch, get haircuts, etc.