自然数 (6)鳩ノ巣原理
各$~n\in\mathbb{N}~$に対して、$n=0~$なら$~\mathbb{N}_0=\emptyset~$とし、$n\neq0~$なら$~\mathbb{N}_n=\{0,\dots,n-1\}~$と定める。
補題22
任意の$~n\in\mathbb{N}~$に対して、$\mathbb{N}_{n+1}~$から$~\mathbb{N}_n~$への単射は存在しない。
$n~$に関する数学的帰納法で証明する。
空集合への写像は存在しないので$~n=0~$に関しては主張は成立する。
任意に$~n\in\mathbb{N}~$をとり、$\mathbb{N}_{n+1}~$から$~\mathbb{N}_n~$への単射は存在しないとする。
単射$~f:\mathbb{N}_{n+2}\to\mathbb{N}_{n+1}~$がとれたと仮定して矛盾を導く。
ここで、各$~i\in\mathbb{N}_{n+2}~$に対して \[ g(i) = \left\{\begin{array}{ll} n & (i=n+1) \\ f(n+1) & (i\neq n+1, f(i)=n) \\ f(i) & (i\neq n+1, f(i)\neq n) \end{array}\right. \] となるように写像$~g:\mathbb{N}_{n+2}\to\mathbb{N}_{n+1}~$を定める。
これがまた単射になっていることは容易に確かめられる。
このとき、$g~$の$~\mathbb{N}_{n+1}~$への制限は明らかに$~\mathbb{N}_{n+1}~$から$~\mathbb{N}_n~$への単射となっている。
これは帰納法の仮定に矛盾する。
$$\square$$
空集合への写像は存在しないので$~n=0~$に関しては主張は成立する。
任意に$~n\in\mathbb{N}~$をとり、$\mathbb{N}_{n+1}~$から$~\mathbb{N}_n~$への単射は存在しないとする。
単射$~f:\mathbb{N}_{n+2}\to\mathbb{N}_{n+1}~$がとれたと仮定して矛盾を導く。
ここで、各$~i\in\mathbb{N}_{n+2}~$に対して \[ g(i) = \left\{\begin{array}{ll} n & (i=n+1) \\ f(n+1) & (i\neq n+1, f(i)=n) \\ f(i) & (i\neq n+1, f(i)\neq n) \end{array}\right. \] となるように写像$~g:\mathbb{N}_{n+2}\to\mathbb{N}_{n+1}~$を定める。
これがまた単射になっていることは容易に確かめられる。
このとき、$g~$の$~\mathbb{N}_{n+1}~$への制限は明らかに$~\mathbb{N}_{n+1}~$から$~\mathbb{N}_n~$への単射となっている。
これは帰納法の仮定に矛盾する。
定理23(鳩ノ巣原理)
$m,n\in\mathbb{N}~$とする。$m\lt n~$なら、$~\mathbb{N}_n~$から$~\mathbb{N}_m~$への単射は存在しない。
つまり$~m\lt n~$なら、任意の写像$~f:\mathbb{N}_n\to\mathbb{N}_m~$に対して$~f(i)=f(j)~$かつ$~i\neq j~$となる$~i,j\in\mathbb{N}_n~$がとれる。
$n\neq 0~$の場合のみ考えればよい。
$m\lt n~$なら$~m\le n-1~$なので、$\mathbb{N}_m\subset\mathbb{N}_{n-1}~$である。
$\mathbb{N}_n~$から$~\mathbb{N}_m~$への写像は$~\mathbb{N}_n~$から$~\mathbb{N}_{n-1}~$への写像ともみなせるので単射にはなり得ない。
$$\square$$
$m\lt n~$なら$~m\le n-1~$なので、$\mathbb{N}_m\subset\mathbb{N}_{n-1}~$である。
$\mathbb{N}_n~$から$~\mathbb{N}_m~$への写像は$~\mathbb{N}_n~$から$~\mathbb{N}_{n-1}~$への写像ともみなせるので単射にはなり得ない。