鳩ノ巣原理を証明する方法

質問

鳩ノ巣原理は正しいことはすぐにわかると思うのですが、それ自体はどのように示せばよいのでしょうか？

回答No.3

tmpname · ベストアンサー

要は、鳩ノ巣原理というのは、
「自然数m, nに対し、Aをm元集合、Bをn元集合とする。m>nのとき、AからBへの単射は存在しない」
ということですが、公理的集合論とかその辺を議論する時は、きちんと証明しないといけない。
で、証明ですが、nに対する数学的帰納法で示します。
A n=1の時は明らか
B n=n0の時成り立つとして、n=n0+1の時成り立つ事を示す。
次の方針で示します。
『今、m' > n0+1なるある自然数m'があって、あるm'元集合A'からn0 + 1元集合B'への単射が存在すると仮定する。
この時、あるm'-1元集合からn0元集合への単射が存在することになり、数学的帰納法の仮定と矛盾する』
これを示すのがカギです。要は、A'とB' から1元ずつ取り除いてうまく単射を作ります。

（wikipediaに書いてある無限集合の場合については、そもそも「濃度」の定義から明らかです。ただし、その「濃度」の定義が凄く面倒くさいのでここでは書きません）

一度考えてみて、分からなければ質問してください。
（例えば次に載ってます
斎藤正彦「数学の基礎」（東大出版）p235）

お礼

ちゃんと証明があるのですね。ありがとうございます。

回答No.4

tmpname

一応きちんとしておく為に書いておくと、（自然数を1 startとして）集合Dがn元集合というのは、Dと集合{1, 2, 3, … , n}との間に一対一対応（全単射）があることとします。

回答No.2

noname#211431

間違えた・・

こっち・・https://ja.wikipedia.org/wiki/%E9%B3%A9%E3%81%AE%E5%B7%A3%E5%8E%9F%E7%90%86

お礼

回答ありがとうございます。wikiも見たのですが、証明が書いてないように思えたので質問しました。

回答No.1

noname#211431

証明されてるのを　更に証明するの？

http://okwave.jp/qa/q9072037.html