Proof of Generalized Pigeonhole Principle used in MIT OCW course 6.042 in Lecture 16.

Question

The Generalized Pigeonhole principle states that :

If |X| >= K|Y|, then for all f:X -> Y, there exists K+1 different elements of X that are mapped to the same element in Y.

Prove this.

Answer 1

The proposition is false. For example,
let Y be a singleton and |X| = k.

If |X| > k|Y| and f:X -> Y, then
exists y with k > |f$^{-1}$(x)|.

Otherwise, for all y, |f$^{-1}$(y)| <= k;
X = $\cup${ f$^{-1}$(y) : y in Y };
|X| <= k|Y|, a contradiction.