= Infinite pigeonhole principle
The <infinite pigeonhole principle> says that if an <infinite set> has a <partition of a set> into finitely many parts, at least one part is an <infinite set>. Equivalently, assigning infinitely many objects to a finite number of boxes forces some box to contain infinitely many objects. For example, separating the <natural numbers> into their two <residue classes> modulo $2$ forces at least one class to be an <infinite set>; here both are, as the lists $0,2,4,\ldots$ and $1,3,5,\ldots$ show.
\b[Proof outline.] A <union> of finitely many <finite sets> is a <finite set>. If all the parts were <finite sets>, their <union> could not be the original <infinite set>.
The assumption of finitely many parts is essential. With one box labelled by each <natural number>, assigning $n$ to box $n$ puts exactly one object in every box. Infinitely many objects and infinitely many boxes therefore need not produce even a shared box. The <infinite pigeonhole principle> is useful whenever finitely many labels organize an endless collection: one label must keep occurring infinitely often, providing an <infinite set> on which that label is constant.
Back to article page
