PigeonholePrinciple 2001-10-25 12:01:30 2003-04-03 12:18:45 Theorem \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{graphicx} \usepackage{xypic} For any natural number $n$, there does not exist a bijection between $n$ and a proper subset of $n$. The name of the theorem is based upon the observation that pigeons will not occupy a pigeonhole that already contains a pigeon, so there is no way to fit $n$ pigeons in fewer than $n$ pigeonholes.