離散数学の証明

1.関数f:A->Bが可逆であるのは、fが全射でかつ単射な関数であるときに限ること。
2.有限集合A上の関数f:A->Aに関して、fが単射であるための必要十分条件はfが全射であること。
の、どちらかの証明を教えてください。
全射とは、上への関数
単射とは、１対１関数のことです。

No.3 回答者： stomachman 回答日時： 2001/02/20 00:25

全射・単射・可逆の概念は決して難しくない。

これらをよく理解するために是非、絵を描いてみると良いと思います。Aの要素aからBの要素bへ矢印を描いて、これがf(a)=bを表す、と考える。

あるいはイメージしやすい文章題にしてみるのはいかがでしょう。
1.の方は、Aをひとの集まり、Bを番号札だと思って、f(a)=bはaさんがb番の札を持っている、という意味。f:A->Bなので全員が札を持っています。
番号をどれでもひとつ呼んだとき、必ず丁度一人のひとが「ハーイ」と返事するようにするには？
人数が無限の場合はどうでしょうか。

2. 沢山のひとAが自分のパンツ（名前入り）を脱いで、パンツを混ぜ合わせます。このパンツの山は集合Aと同一視できますね。さて、みんなかってにパンツを取って穿きます。誰aのパンツを誰bが穿いているか、がf(a)=bです。これが単射であるとは、誰もパンツを二枚以上重ねて穿いていない、ということ。全射であるとは、全員にパンツが行き渡ったということ。
人数が無限の場合、a番目のひとが2a番目のひとのパンツを穿くことにすると、パンツが大量に余りますから、無限集合では成り立たないですね。

あんまりリアリティがない？すいません。

No.2 回答者： oodaiko 回答日時： 2001/02/19 18:59

2.有限集合A上の関数f:A->Aに関して、fが単射であるための必要十分条件はfが全射で

あること。

全射→単射：A={a_1,a_2,…,a_n}(Aの要素数はn）とする。
fは全射だから f(A)={f(a_1),f(a_2),…,f(a_n)} = A
すなわち f(a_1),f(a_2),…,f(a_n)がそれぞれ a_1,a_2,…,a_n のどれかに
対応している。{f(a_1),f(a_2),…,f(a_n)}も{ a_1,a_2,…,a_n}も要素数は
同じだからその対応は１対１でなくてはならない。

単射→全射： fは単射だからa_i≠a_jならf(a_i)≠f(a_j)。
そこでf(A)はAのn個の異なる要素からなる集合である。そのようなものはA自身しかない。


なおこの問題はAが有限集合であることが本質で、無限集合ではどちらも正しくない。
証明のどこに有限性が効いているのか、また無限集合の場合に成立しない例を
挙げておけばポイントが高いかも知れません。

No.1 回答者： oodaiko 回答日時： 2001/02/19 18:28

時節がらレポートのようなので完全回答はしません。

残りは自分で補って
数学的にきちんとした証明を仕上げて下さい。

1.関数f:A->Bが可逆であるのは、fが全射でかつ単射な関数であるときに限ること。

fに対する逆写像 f^{-1}:B->A が作れることを示せば良い。
fは全射だから任意のy ∈ Bに対して f^{-1}(y) の候補となるx∈A が少なくとも１つはある。
さらにfが単射であることを使って、このxが一意的であることが示せる。