【写像】全射、単射、全単射の性質と例題

写像とは

２つの集合X、Y内にあるそれぞれの要素(x,y)の対応関係を決める規則を言います。

規則は、関数で表されることが多いです。$f=2x$とすると、集合X：$X:(1,2,3,4)$に対する写像は、$Y:(2,4,6,8)$のようになります。

このため、下記のような例は写像になりません。

一方で、下記の組み合わせでも写像として成立します。

全射とは

集合Xから集合Yへの写像に対し、Yの内部要素全てに遷移元の要素が存在する場合の組み合わせを言います。

数学的に述べると、下記の説明になります。

$$\begin{array}{}\text{(1)}& \begin{array}{r}\mathrm{集}\mathrm{合}Y\mathrm{を}\mathrm{構}\mathrm{成}\mathrm{す}\mathrm{る}\mathrm{任}\mathrm{意}\mathrm{の}y\mathrm{に}\mathrm{対}\mathrm{し}、y=f(x)\mathrm{を}\mathrm{満}\mathrm{た}\mathrm{す}\mathrm{要}\mathrm{素}x\mathrm{が}\mathrm{集}\mathrm{合}X\mathrm{内}\mathrm{に}\mathrm{存}\mathrm{在}\mathrm{す}\mathrm{る}。\end{array}\end{array}$$

単射とは

集合Xから集合Yに対応する写像が存在し、遷移元の要素の重複が無いことを言います。

前章「写像として存在する例」２．に該当しない写像が単射になります。

数学的には、下記の説明になります。

任意の$x_0,x_1\in X$に対し、

$$\begin{array}{}\text{(2)}& \begin{array}{r}{x}_0\ne x_1\mathrm{な}\mathrm{ら}\mathrm{ば}f(x_0)\ne f_{(}{x}_1)\end{array}\end{array}$$

なお、下記は全て同値になります。

厳密な説明は省きますが、

遷移元の要素が2つの集合に属するならば、遷移先の要素も2つの集合に対する写像に属すること。(１．の説明)
遷移元の要素が1つの集合にしか属さない場合は、遷移先も1つの集合にのみ属すること。(２．の説明)

以上2点を意味しています。

全単射とは

全射かつ単射である写像を言います。

下記のように、像の衝突は発生せず、集合Y内部の要素yそれぞれに対応する要素xも存在します。

合成関数における写像(全射、単射、全単射)

合成関数とは

合成関数とは、2つ以上の関数を写像として組み合わせ、1つの関数として見たものになります。

合成関数の記号は$\circ$を用います。

$$\begin{array}{}\text{(3)}& \begin{array}{r}g\circ f=g(f(x))\end{array}\end{array}$$

と表され、g(x)の引数xの部分にf(x)を丸々代入すると、合成関数になります。

合成関数の注意点

定義可能条件

$g\circ f$について、遷移元の集合X内の要素$x$に対応する像$f(x)$が$g$の定義範囲に属することです。

$x=1$のとき、$f(1)=-2$ですが、これを関数$g$に代入しようとすると、$g(-2)$のため定義範囲外です。

このように、合成写像$g\circ f$は定義できないことが分かりました。

合成の順番と一致性

合成関数$g\circ f$と$f\circ g$が両方定義可能であったとしても、結果が一致するとは限らないです。

$$\begin{array}{}\text{(4)}& \{\begin{array}{l}g\circ f=x^2+1+2=x^2+3\\ f\circ g=(x+2{)}^2+1=x^2+4x+5\end{array}\end{array}$$

より、両者は一致しない。

合成関数の結合即

定義可能な3つ以上の関数を合成するとき、下記の関係が成立します。

$$\begin{array}{}\text{(5)}& \begin{array}{r}h\circ g\circ f=(h\circ g)\circ f=h\circ (g\circ f)\end{array}\end{array}$$

※$h\circ g$、$g\circ f$が定義可能であることが前提です。

前節では、$g\circ f$、$f\circ g$のように合成する順番を変更すると結果が変わるとお話ししました。一方で、全体としての順番が変わらなければ、括弧()付きで合成しやすい関数から計算しても結果が変わらないことを表しています。

試験では、計算しやすい関数から順に攻めていく方針が良いと思います。

合成関数を用いた写像の性質

全射の証明

$g\circ f$の出力$z\in Z$を考える。

$g$は全射だから、ある$y\in Y$が存在して$z=g(y)$が成立する。
$f$も全射だから、ある$x\in X$が存在して$y=f(x)$が成立する。

二つを合わせて、

$$\begin{array}{}\text{(6)}& \begin{array}{r}z=g(y)=g(f(x))=g\circ f(x)\end{array}\end{array}$$

なる全射の写像$g\circ f$が存在する。

単射の証明

集合X内の異なる要素：$x_0,x_1\in X$を考える。

$x_0,x_1$は異なる要素のため、$f(x_0)\ne f(x_1)$

$f(x_0)\ne f(x_1)$のため、$g(f(x_0))\ne g(f(x_1))$

$g(f(x_0))\ne g(f(x_1))$なので、定義より、$g\circ f$は単射である。

全単射の証明

全射かつ単射であることが全単射の定義である。

よって、前節、前々節の証明を合わせると、$f$と$g$が共に全単射のとき、$g\circ f$も全単射であることが分かる。

解答例

(1)全射写像の個数

集合AからBへ遷移するとき、遷移先の要素が重複しても良い。ただし、Bの要素でAからの遷移元が無いパターンは除外することに注目する。

考えられる例を書き下していくと下記の6通り考えられる。

補足

集合Aの要素数をn、集合Bの要素数をm (ただし、n≧m)としたとき、全射の個数は

$$\begin{array}{}\text{(7)}& \begin{array}{r}\sum _{k=1}^m(-1{)}^{m-k}{}_m{C}_k\ast k^n\end{array}\end{array}$$

個存在します。

証明は、要望が多ければ追記します。

(2)単射写像の個数

Cの要素4つの中から異なる3つを選ぶ順列のため

$$\begin{array}{}\text{(8)}& \begin{array}{r}{}_4{P}_3=4\ast 3\ast 2=24\mathrm{通}\mathrm{り}\end{array}\end{array}$$

補足

上記の式でピンとくるかもしれませんが、集合Aの要素数をn、集合Bの要素数をm (ただし、n≦m)としたとき、単射の個数は

$$\begin{array}{}\text{(9)}& \begin{array}{r}{}_n{P}_m\mathrm{個}\end{array}\end{array}$$

(3)全単射の個数

集合AとDの個数はお互いに同じ。重複を許さず、一対一でマッチングさせていくので

$$\begin{array}{}\text{(10)}& \begin{array}{r}4!=4\ast 3\ast 2\ast 1=24\mathrm{通}\mathrm{り}\end{array}\end{array}$$

(鳩ノ巣原理と言います。)

最後に

本問は、電通大の院試でよく出てきます。

同大学を志望される方は、是非隅々まで理解しましょう。