【数学】鳩ノ巣原理って言うほど自明か？

鯵坂もっちょ🐟 @motcho_tw

鳩ノ巣原理って、どんな理由付けで正当化されてんだ…？

鯵坂もっちょ🐟 @motcho_tw

5個の箱に6羽の鳩が入ってたらどれか一つの箱には少なくとも2羽いるって、人間以外にとっても自明かなあ。

鯵坂もっちょ🐟 @motcho_tw

ぼく「5個の箱に6羽の鳩が入ってたらどれか一つの箱には少なくとも2羽いるじゃん」 宇宙人「え？　なんで？」 って言われたらどう答えればいいの

鯵坂もっちょ🐟 @motcho_tw

もちろん実際そこまで自明じゃないと思ってるわけではなくて、鳩ノ巣論法ってどんな公理のもとに立脚されてんの？って話

鯵坂もっちょ🐟 @motcho_tw

もしかして直感にたよってるの...？　そんなものを無反省に使い続けてていいの...？　と思いました

tsujimotter ロマ数本好評発売中!! @tsujimotter

@motcho_tw ６羽の鳩を全部の箱に１羽以下ずつ入れて、ちょうど６羽入れ切ったと仮定する。すると、５箱であれば全部で５羽以下の鳩が入っていることになるが、これは矛盾だ。よって、少なくとも２羽以上入っている。で、証明できたことになりませんか？

koromon @yamadian

@motcho_tw 有限個だからひとつひとつ確かめるだけで証明できるのでは

鯵坂もっちょ🐟 @motcho_tw

@yamadian ええと、有限個なのはなんですか？

koromon @yamadian

または全部の箱に1羽以下しかいなかったら全部合わせても箱の数より少ないと

サクラ @1997_takahashi

鳩ノ巣原理の話、全射でありかつ単射でないならば逆写像が存在しないということで良いのでは、ということを云いたかった。日本語がアレだったので訂正。

鯵坂もっちょ🐟 @motcho_tw

@tsujimotter 「単純に言って、どういう数学的事実が鳩ノ巣原理を成り立たせているか？」というのが気になってるのかもしれません。1=/=2、とかそんなかんじでしょうか。言い換えれば「鳩ノ巣原理を成り立たなくするにはどういう数学的事実を取り去ればよいか？」

せきゅーん @integers_blog

@tsujimotter @motcho_tw ペアノの公理から厳密に証明出来る定理として、{1,2,…,n}を[n]と表すとき、自然数m, nに対して写像f:[m]→[n]が単射ならばm≦nであるというものがありますが、これの対偶が鳩ノ巣原理だったりしません？

tsujimotter ロマ数本好評発売中!! @tsujimotter

@integers_blog @motcho_tw その定理は知りませんでした！たしかに対偶とれば鳩ノ巣原理ですね。どうやって証明するのでしょうか？

鯵坂もっちょ🐟 @motcho_tw

あー一番納得できそうなやつかもこれ

tsujimotter ロマ数本好評発売中!! @tsujimotter

どうやって示すのだろう・・・？

がーすー @sg_tk

数学モンスターズエッセイ、鳩の巣原理の回だ…!!

サクラ @1997_takahashi

@motcho_tw 単射が構成されれば鳩ノ巣原理は成り立たなさそうです。

鯵坂もっちょ🐟 @motcho_tw

@1997_takahashi 単射が構成されれば、ってつまりどういうことですか？

サクラ @1997_takahashi

@motcho_tw 既にもっちょ氏がRTされた内容にありましたが、始域よりも終域の方が濃度が大きいことが帰結されるということです。

鯵坂もっちょ🐟 @motcho_tw

@1997_takahashi はーなるほど...

せきゅーん @integers_blog

@tsujimotter @motcho_tw 私が昔読んだ弥永昌吉著『数の体系（上）』では帰納法で証明しているのですが、厳密に証明が書いてあって、主張は自明に思えるにも関わらず、なんと丸々一ページを使っています（p109~p110）。

tsujimotter ロマ数本好評発売中!! @tsujimotter

@integers_blog @motcho_tw ページ番号まで指定いただいてありがとうございます！気になるので読んでみます！

tsujimotter ロマ数本好評発売中!! @tsujimotter

収穫があった

鯵坂もっちょ🐟 @motcho_tw

本当に疑問があって「どうして？」と聞くときには相手が「疑問文、否定文に聞こえる症候群」でないことを祈るばかりだ

前野［いろもの物理学者］昌弘 @irobutsu

学生さんが「よって、Aとなります」と言う。 私は「よって」の論拠が足りないと思ったので、「どうしてそうなるの？」と問う（Aに異存はない）。 すると学生さん慌てたように「違いましたBでした」と話を変える。 「『どうして？』が否定文に聞こえる問題」と名づけている。