m,nが自然数としてm>nと仮定すると集合｛1,2,...m｝から｛1,2,...n｝への単射は存在

m,nが自然数としてm>nと仮定すると集合｛1,2,...m｝から｛1,2,...n｝への単射は存在しない

これを証明するとどうなるのでしょうか？

質問者からの補足コメント

• できれば、m<nで全射が存在しない場合もお願いしたいです汗

    補足日時：2020/06/10 16:30

• 1
  このような全射fが存在するとして、
  m,nは自然数でm<nなのでnの集合は｛1,2,....m,m+1,..n｝と考えることができる。
  ｛1,2,3...m｝から｛1,2,3,...m,...n｝への全射を考える
  順に対応させていくとf(1)=1,f(2)=2,...f(m)=mの時点でm+1...nに対応させる元が足りなくなる。
  よって全射であることに矛盾。
  
  最初はこのように考えましたが、回答者さんのを参考にして考えたのが2です。
  集合から空集合への全射はあり得ないですよね？
  
  2
  このような全射fが存在するとして、
  f(m)=xとなる元をmだけだとすると、
  ｛1,2,...m-1｝から｛1,2,..n｝-｛f(m)｝への全射となる
  この操作をn回繰り返すと｛1,2,...m-n｝から空集合の全射となり
  空集合への全射は存在しないので矛盾

    補足日時：2020/06/10 18:11

No.1 回答者： ありものがたり 回答日時： 2020/06/10 16:02

そのような単射 f が存在すると仮定します。

f は単射なので、f(x) = f(m) となる x は m だけです。
よって、f の定義域を { 1,2,...,m-1 } に制限すると
{ 1,2,...,m-1 } から { 1,2,...,n } - { f(m) } への単射になります。
{ 1,2,...,n } - { f(m) } の元が n-1 個であることに注意しましょう。
同様の操作を計 n 回繰り返すと、f の制限写像として
{1,2,...,m-n } から空集合への単射が得られることになります。
空集合への単射はありえません。この矛盾は f を単射と仮定した
ことから生じたと考えられ、背理法によって、
そのような単射は存在しないと判ります。

この回答へのお礼

ありがとうございます。
すごく分かり易かったです。
もしよろしければm<nで全射が存在しない場合もお願いしたいです汗

お礼日時：2020/06/10 16:36

No.2 回答者： ありものがたり 回答日時： 2020/06/10 16:34

＞ できれば、m<nで全射が存在しない場合も

いや、それは No.1 の内容を理解したなら
自分で書けるはずです。
No.1 が解らなかったならば、どこが解らないか
またはどこがオカシイと思うかを書いてください。
解ったのであれば、全射については
自分で証明を作って補足に書きましょう。
書けば、添削はしますよ。

この回答へのお礼

書いてみました
添削お願いしたいです。

お礼日時：2020/06/10 18:19

No.3 回答者： ありものがたり 回答日時： 2020/06/11 00:17

←補足

1.
概ね良好だけど、ちょっと修正が必要。
f を f(1)=1,f(2)=2,...f(m)=m に限定してしまうと、
そうじゃない f で全射になる例があるかも
という疑惑が残る。
終域の元の番号を順次つけかえていけば
いいだけだけど、その手間を惜しんではいけない。

2.
これはダメ。
m と n のどちらが大きい場合の話をしている？

No.4 回答者： Tacosan 回答日時： 2020/06/11 02:55

「全射」だから「終域の任意の元に対して『写すとその元になる』ような始域の元が存在する」わけだけど, その「始域の元」は 1つとは限らないのでそこはちょっと注意しないとね. そんなのをもってくるといっそう「始域の元」が足らなくなるんだけど, 「そういうことはありえない」と a priori に仮定するのもよくない.

あと, 「空集合から空集合への写像」は全射 (かつ単射)... だけど, この問題ではな～んにも関係ない.