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

鯵坂もっちょ🐟『つれづれなる数学日記』発売中 @motcho_tw

これこれ

Md @Md66764648

@motcho_tw　n+1個の元を持つ集合Aとn個の元を持つ集合Bについてf:A→B を考え、この写像fが単射であると仮定する。 定義より(∀a1,a2∈A)a1≠a2⇒f(a1)≠f(a2) であるからAからn個の元を取り出した部分集合A’についてf:A’→B は全単射である

Md @Md66764648

@motcho_tw　ところが集合A-A’のただ一つの元aiについてf(ai)(∈B)が存在するならば あるaj(∈A’)が存在してai≠ajかつf(ai)=f(aj)である これはfが単射であることに矛盾する よってfは単射でない

Md @Md66764648

@motcho_tw どんな公理かって質問には応えれてない気もしますorz

鯵坂もっちょ🐟『つれづれなる数学日記』発売中 @motcho_tw

ほうほうほう！

鯵坂もっちょ🐟『つれづれなる数学日記』発売中 @motcho_tw

@Md66764648 いやいや、結構わかりました！ありがとです！

鯵坂もっちょ🐟『つれづれなる数学日記』発売中 @motcho_tw

やはり自明なところにこそおもしろいものが潜んでいるな

せきゅーん @integers_blog

ちなみに、f:[m]→[n]が単射ならばm≦nという定理とf:[m]→[n]が全射ならばm≧nという定理が証明されて、f:[m]→[n]が全単射ならばm=nということが従い、それで初めて「ものの個数は数え方に依らない」という経験則の証明がなされることになる。

鯵坂もっちょ🐟『つれづれなる数学日記』発売中 @motcho_tw

メタクソ面白いな

鯵坂もっちょ🐟『つれづれなる数学日記』発売中 @motcho_tw

数え方によって個数が変わってしまう世界...

せきゅーん @integers_blog

あと、証明に一ページも使っていると大層な書き方をしてしまいましたが、読み返してみるととても単純かつ簡単でした（演習問題とする）。ただ、帰納法を使っているので厳密な証明だということがポイントです。

せきゅーん @integers_blog

もう少し精密に言うと、集合Aが有限集合であるとは、ある自然数nに対して全単射f:A→[n]が存在することを言い、このとき、Aのfによる個数A(f)をnと定義する（[0]は空集合）。そうして、Aを二通りに方法で「数えるとは」全単射f:A→[n]とg:A→[m]が存在することを（続）

せきゅーん @integers_blog

@integers_blog 二通りに→二通りの

せきゅーん @integers_blog

@integers_blog 「数えるとは」→「数える」とは

せきゅーん @integers_blog

言う。このとき、[n]から[m]への全単射が合成によって得られるが、先ほどの定理によってn=mが示されるので、A(f)はfの取り方に依らずwell-definedとなって有限集合の個数という概念が初めて定義されるのである。

せきゅーん @integers_blog

@tsujimotter @motcho_tw せっかくなので、証明も書きます。まず、帰納法のスタートステップとしてのm=0またはm=1の場合は写像の定義がしっかりしていれば自明です。そこで、m≧1に対して、m-1のときは成立すると仮定して証明します。

せきゅーん @integers_blog

@tsujimotter @motcho_tw f:[m]→[n]の[m-1]への制限をgとします。このとき、g:[m-1]→[n]も単射です。さて、f(m)=n or f(m)≠nで場合分けをしましょう。f(m)=nのときは、g:[m-1]→[n-1]が単射となります。

せきゅーん @integers_blog

@tsujimotter @motcho_tw よって、帰納法の仮定により、m-1≦n-1が成り立つので、m≦nが言えました。次に、f(m)=k≠nの場合を考えます。このときは、h:[n]→[n]をkとnのみを入れ替える互換（特に全単射）とすると、h○f:[m]→[n]は単射で

せきゅーん @integers_blog

@tsujimotter @motcho_tw h○f(m)=h(k)=nが成り立つので、h○fについては場合分けの最初のケースと同じ状況になっており、従って同じ方法で帰納法の仮定からm≦nが示される。Q.E.D.