Pigeonhole Principle

**shilz222** · August 30th 2007, 01:43 PM

How many proofs are there for the pigeonhole principle? I know of one proof that just uses composition of functions to develop lemmas, and then ultimately come up with the Pigeonhole principle. The proof starts with the basic problem of 2 different ways of counting sets (i.e if $f: \mathbb{N}_{m} \to X$ and $f: \mathbb{N}_{n} \to X$ are bijections with the same codomain, then $m = n$ ). Namely, it says the following: Suppose that $X$ and $Y$ are finite, non-empty sets such that $|X| > |Y|$ . Then $f: X \to Y$ is not an injection.

**ThePerfectHacker** · August 30th 2007, 01:48 PM

What is a finite set? It is a set such has no proper subset has a bijection with the full set. Use that fact and prove formally the principle.

**Plato** · August 30th 2007, 03:15 PM

There are several proofs as you observe. This of is found in many discrete mathematics texts.
Given that $m = \left| X \right| > \left| Y \right| = n$ , recall that $<br /> X = \bigcup\limits_{y \in Y} {\overleftarrow f \left\{ y \right\}}$ .

Suppose that $\left( {\forall y \in Y} \right)\left[ {\left| {\overleftarrow f \left\{ y \right\}} \right| \le 1} \right]\quad$ .

Using that we have $\left| X \right| = \left| {\bigcup\limits_{y \in Y} {\overleftarrow f \left\{ y \right\}} } \right| = \bigcup\limits_{y \in Y} {\left| {\overleftarrow f \left\{ y \right\}} \right|} \le n$ that is a contradiction.
Thus $\left( {\exists z \in Y} \right)\left[ {\left| {\overleftarrow f \left\{ z \right\}} \right| > 1} \right]$ .

The value of this proof is that it also proves the generalized form. If we have m pigeons and n pigeonholes with $m > n$ the some hole contains at least $\left\lceil {\frac{m}{n}} \right\rceil$ pigeons (that is the ceiling function).

To see this proof use the assumptions above, using the supposition that $k = \left\lceil {\frac{m}{n}} \right\rceil \quad \& \quad \left( {\forall y \in Y} \right)\left[ {\left| {\overleftarrow f \left\{ y \right\}} \right| < k} \right]$ .

This time $\left| X \right| = \left| {\bigcup\limits_{y \in Y} {\overleftarrow f \left\{ y \right\}} } \right| = \bigcup\limits_{y \in Y} {\left| {\overleftarrow f \left\{ y \right\}} \right|} \le n\left( {k - 1} \right) \le m$ that is a contradiction.
Thus $\left( {\exists z \in Y} \right)\left[ {\left| {\overleftarrow f \left\{ z \right\}} \right| \ge k} \right]$ .

Thread: Pigeonhole Principle

LinkBack

Thread Tools

Display

Pigeonhole Principle

Similar Math Help Forum Discussions

help me with pigeonhole principle #2

help me with pigeonhole principle #1

Pigeonhole principle

Pigeonhole principle?

Pigeonhole Principle

Search Tags