AとBを2つの有限集合とし,AとBの要素の個数をそ れぞれ mとnとする。 1. Aから Bへの写像

AとBを2つの有限集合とし,AとBの要素の個数をそ
れぞれ mとnとする。
1. Aから Bへの写像は全部でいくつあるか?
2. A とBの間の関係は全部でいくつあるか?
3.(挑戦問題)AからBへの部分写像は全部でいくつあるか?

一番は分かるのですが2、3が分かりません。教えていただきたいです。

No.1 回答者： ありものがたり 回答日時： 2020/05/13 20:41

2.

「関係」は、A の要素の何個が B の要素の何個と関係しようがokです。
A の要素と B の要素の対 mn 個のうちどれが「関係」に入っても入らなくてもいいので、
その総数は 2^(mn) になります。
mn 対のそれぞれについて「入る」「入らない」が二択できるからです。

3.
「A から B への部分写像」とは、A の部分集合から B への写像のことです。
A の全ての要素に対して写像の値が定義されているわけではありません。
何か B の要素ではない、「写像の値が定義されていない」ことを表す記号(例えば φ)
を用意して、A から B∪{φ} への写像を考えると、それがA から B への部分写像と
一対一に対応しています。つまり、求める個数は、 (n+1)^m 個です。