鳩の巣原理
濃度に関する一般化を述べる為にまず鳩の巣原理を集合の言葉で言い換える。
A を鳩の集合とし、B を巣の集合とする。すると、鳩に巣を対応させる行為は A の元に B の元を対応させる写像f とみなせる。
鳩の巣原理は、A 、B が有限集合で、 A の元の数が B の元の数より大きいとき、2羽の鳩が同じ巣に入ることを意味しており、これはすなわち、f が単射でない事と同値である。
より一般に(有限とは限らない)集合A、Bについて、fをAからBへの関数とする。 このときAの濃度がBの濃度より大きければ、fは単射ではありえない(このことは濃度の大小の定義から直ちに出る)。
鳩の巣原理(はとのすげんり、英: Pigeonhole principle)、またはディリクレの箱入れ原理(ディリクレのはこいれげんり、英: Dirichlet's box principle, Dirichlet's drawer principle)、あるいは部屋割り論法とは、n 個の物を m 個の箱に入れるとき、n > m であれば、少なくとも1個の箱には1個より多い物が中にある、という原理である。別の言い方をすれば、1つの箱に1つの物を入れるとき、m 個の箱には最大 m 個の物しか入れることができない(もう1つ物を入れたいなら、箱の1つを再利用しないといけないから)、ということである。
鳩の巣原理は数え上げ問題の例の一つで、一対一対応ができない無限集合など、多くの形式的問題に適用できる。
この原理に関する最初の記述は、ペーター・グスタフ・ディリクレが1834年に "Schubfachprinzip"(「引き出し原理」)の名前で書いたものであると信じられている。また、ディリクレが発見したためディリクレの原理と呼ばれることもある(同名の、調和関数における最小原理と混同してはいけない)。日本語では、以上の「—原理」はすべて「—論法」と訳されることもある。
この原理は、ディオファントス近似において、小さな係数を持ち、なおかつ指定された解をもつ線形方程式系の存在を示すために応用される。この方法は、「ジーゲルの補題」という名前で知られる。発見者であるディリクレ自身、そのような高度な技巧を経由するものではないがディオファントス近似に関する彼の定理を証明するためにこの原理を用いている。また、さらに一般的な数学的構造においても類似の定理が数多く存在することが知られている。