編集部イチオシ

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

5個の箱がある←うん 6羽の鳩がいる←うん 5個の箱に6羽の鳩が入っている←うん てことは少なくとも1つの箱には2羽以上の鳩が入っている←わかる 続きを読む
数学 鳩ノ巣原理 ペアノの公理 鳩ノ巣論法
41
鯵坂もっちょ🐟 @motcho_tw
鳩ノ巣原理って、どんな理由付けで正当化されてんだ…?
鯵坂もっちょ🐟 @motcho_tw
5個の箱に6羽の鳩が入ってたらどれか一つの箱には少なくとも2羽いるって、人間以外にとっても自明かなあ。
鯵坂もっちょ🐟 @motcho_tw
ぼく「5個の箱に6羽の鳩が入ってたらどれか一つの箱には少なくとも2羽いるじゃん」 宇宙人「え? なんで?」 って言われたらどう答えればいいの
鯵坂もっちょ🐟 @motcho_tw
ちろん実際そこまで自明じゃないと思ってるわけではなくて、鳩ノ巣論法ってどんな公理のもとに立脚されてんの?って話
鯵坂もっちょ🐟 @motcho_tw
もしかして直感にたよってるの...? そんなものを無反省に使い続けてていいの...? と思いました
tsujimotter @tsujimotter
@motcho_tw 6羽の鳩を全部の箱に1羽以下ずつ入れて、ちょうど6羽入れ切ったと仮定する。すると、5箱であれば全部で5羽以下の鳩が入っていることになるが、これは矛盾だ。よって、少なくとも2羽以上入っている。で、証明できたことになりませんか?
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された内容にありましたが、始域よりも終域の方が濃度が大きいことが帰結されるということです。
せきゅーん @integers_blog
@tsujimotter @motcho_tw 私が昔読んだ弥永昌吉著『数の体系(上)』では帰納法で証明しているのですが、厳密に証明が書いてあって、主張は自明に思えるにも関わらず、なんと丸々一ページを使っています(p109~p110)。
tsujimotter @tsujimotter
@integers_blog @motcho_tw ページ番号まで指定いただいてありがとうございます!気になるので読んでみます!
鯵坂もっちょ🐟 @motcho_tw
本当に疑問があって「どうして?」と聞くときには相手が「疑問文、否定文に聞こえる症候群」でないことを祈るばかりだ
前野[いろもの物理学者]昌弘 @irobutsu
学生さんが「よって、Aとなります」と言う。 私は「よって」の論拠が足りないと思ったので、「どうしてそうなるの?」と問う(Aに異存はない)。 すると学生さん慌てたように「違いましたBでした」と話を変える。 「『どうして?』が否定文に聞こえる問題」と名づけている。
残りを読む(19)

コメント

齊藤明紀 @a_saitoh 2016年4月19日
初等数学の範囲で証明するならば、不等式と背理法でいけるかなぁ
きゃっつ(Kats)⊿6/10日向坂ツアー広島? @grayengineer 2016年4月19日
背理法でしょ。「すべての箱に1羽以下しか入ってない」と仮定すると最大で5羽しか入らないため矛盾する。したがって仮定が誤りとわかる
空弁者 @scavenger0519 2016年4月19日
数学はさておき・・・。 前提として「全てのハコには鳩がいる」でお話していらっしゃるけれど、一個以上のハコは空きがある可能性もある、を考慮してはいけないのでしょうか? いくつかのハコに二羽以上いる・・・。3羽のオスと3羽のメスが一夫一婦制なら3箱しか使用しないかも。1羽のオスと5羽のメスなら妊娠したメスは1羽1箱になるかも。
Localio Projects @LocalioProjects 2016年4月19日
巣箱の概念と鳩の行動が基礎知識。「鳩は夜には巣に戻るため夜間には六羽の鳩は全て屋内(5個の巣箱)に居る」「巣箱は壁で区切られており、鳩は巣箱の間を移動できない」。宇宙人にはこれを伝えないとダメ。自由に出入りできるなら外に一羽いる可能性があるので成り立たいし、巣箱が内部連結なら二箱に三羽の可能性もある。
barubaru @barubaru14 2016年4月19日
1.5羽入りの巣が2つあればいいのでは?
羽倉田 @wakurata 2016年4月19日
プログラム界隈では当たり前の配列の原理って数学方面から証明するのは難しいって事なの?
羽倉田 @wakurata 2016年4月19日
巣箱を配列として二個の変数が入る配列を5個用意してそこに6個の変数をループ文で順次入れていくという単純な話に思うのだけど
想 詩拓@文芸サークル『文机』 @sou_sitaku 2016年4月20日
scavenger0519 「5個の箱に6羽の鳩が入っている」という前提がはっきり示されております。
kkitmur @kkitmur 2016年4月20日
プログラム的に表現するなら「長さ5のint型配列(中身は全て0)がある。ここからランダムに一つ要素を選んで1を足す操作を6回行ったとき、必ず2以上になる要素がある」ということですね。 むろん、そうなるのは自明ですが、何をもって必ずそうなると言い切れるか、というお話です
JojoTomochan @JojoTomochan 2016年4月20日
数学に中にはアセンブラレベルの話題もあれば高級言語でのコーディングレベルの話もある。鳩ノ巣原理の妥当性は高級言語に実装されてる配列がどう実装されてるか?ってレベルの議論なのにプログラムだと簡単なんて何言ってるの?
JojoTomochan @JojoTomochan 2016年4月20日
簡単というならアセンブラで配列を実装してから家。ペアノの公理から話をするのって正にアセンブラ、いやIC組み合わせて四則演算実装するようなレベルの話なんだけどね。
🦅あえとす⛩️ @aetos382 2016年4月20日
とあるラノベの主人公の「鳩ノ巣論」っていうキャラ名がこれ由来だと今更気が付いた #どうでもいい
のりしあん @noricyan2 2016年4月20日
1つの巣1つ入れるとき、x個の巣には最大x個しか入れられない。これも自明と言ってはいけないのかなぁ。
Kawai_Yusuke @fiddler_K 2016年4月27日
「数学モンスターズエッセイ」
黒羊はね @bsheep 2016年8月11日
数学的にはn,mだから自然数っていうのが自明なんでしょうけど、文章的には「すべての鳩は解体されていないとする」みたいな条件がいるのでは
Tsuyoshi CHO @tsuyoshi_cho 2016年12月17日
いまさらにコメント。「『どうして?』が否定文に聞こえる問題」は日本語的な問題かもしれんなぁ...主語的には「(その結論は(どういう証明の詳細で))どうして(そうなってるの)?」の略ってのは難しいし「どうして(そう(間違った)なっちゃってるの)?」に感じるのはしょうがない、「その証明の詳細は?」とかのほうがいいかも...と思ったり。
ログインして広告を非表示にする
ログインして広告を非表示にする