Proposition 4.1. Pigeon Hole Principle.
If \(f:X\longrightarrow Y\) is a function and \(|X|>|Y|\text{,}\) then there exists an element \(y\in Y\) and distinct elements \(x,x'\in X\) so that \(f(x)=f(x')=y\text{.}\)
Section 4.1 The Pigeon Hole Principle
A function \(f:X\longrightarrow Y\) is said to be \(1\)–\(1\) (read one-to-one) when \(f(x)\neq f(x')\) for all \(x,x'\in X\) with \(x\neq x'\text{.}\) A \(1\)–\(1\) function is also called an injection or we say that \(f\) is injective. When \(f:X\longrightarrow Y\) is \(1\)–\(1\text{,}\) we note that \(|X|\le |Y|\text{.}\) Conversely, we have the following self-evident statement, which is popularly called the “Pigeon Hole” principle.
In more casual language, if you must put \(n+1\) pigeons into \(n\) holes, then you must put two pigeons into the same hole.
Here is a classic result, whose proof follows immediately from the Pigeon Hole Principle.
Theorem 4.2. Erdős/Szekeres Theorem.
If \(m\) and \(n\) are non-negative integers, then any sequence of \(mn+1\) distinct real numbers either has an increasing subsequence of \(m+1\) terms, or it has a decreasing subsequence of \(n+1\) terms.
Proof.
Let \(\sigma=(x_1,x_2,x_3,\dots,x_{mn+1})\) be a sequence of \(mn+1\) distinct real numbers. For each \(i=1,2,\dots,mn+1\text{,}\) let \(a_i\) be the maximum number of terms in a increasing subsequence of \(\sigma\) with \(x_i\) the first term. Also, let \(b_i\) be the maximum number of terms in a decreasing subsequence of \(\sigma\) with \(x_i\) the last term. If there is some \(i\) for which \(a_i\ge m+1\text{,}\) then \(\sigma\) has an increasing subsequence of \(m+1\) terms. Conversely, if for some \(i\text{,}\) we have \(b_i\ge n+1\text{,}\) then we conclude that \(\sigma\) has a decreasing subsequence of \(n+1\) terms.
It remains to consider the case where \(a_i\le m\) and \(b_i\le n\) for all \(i=1,2,\dots,mn+1\text{.}\) Since there are \(mn\) ordered pairs of the form \((a,b)\) where \(1\le a\le m\) and \(1\le b\le n\text{,}\) we conclude from the Pigeon Hole principle that there must be integers \(i_1\) and \(i_2\) with \(1\le i_1\lt i_2\le mn+1\) for which \((a_{i_1},b_{i_1})=(a_{i_2},b_{i_2})\text{.}\) Since \(x_{i_1}\) and \(x_{i_2}\) are distinct, we either have \(x_{i_1}\lt x_{i_2}\) or \(x_{i_1}>x_{i_2}\text{.}\) In the first case, any increasing subsequence with \(x_{i_2}\) as its first term can be extended by prepending \(x_{i_1}\) at the start. This shows that \(a_{i_1}>a_{i_2}\text{.}\) In the second case, any decreasing sequence of with \(x_{i_1}\) as its last element can be extended by adding \(x_{i_2}\) at the very end. This shows \(b_{i_2}>b_{i_1}\text{.}\)
In Chapter 11, we will explore some powerful generalizations of the Pigeon Hole Principle. All these results have the flavor of the general assertion that total disarray is impossible.
