 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.
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{.}$$