全射

全射の定義

写像\(f:A\rightarrow B\)とは始集合に属するそれぞれの要素\(a\in A\)に対して、終集合に属する要素\(f\left(a\right) \in B\)を1つずつ定める規則として定義されます。

終集合に属する要素\(b\in B\)を選んだとき、それに対して\(b=f\left( a\right) \)を満たす始集合の要素\(a\in A\)は存在するとは限りません。つまり、写像\(f\)の終集合の要素は、始集合に属する何らかの要素の像であるとは限らないといことです。

その一方で、写像\(f:A\rightarrow B\)の終集合の要素\(b\in B\)を任意に選んだとき、それに対して\(b=f\left(a\right) \)を満たす始集合の要素\(a\in A\)が存在することを保証できる場合には、つまり、\begin{equation*}\forall b\in B,\ \exists a\in A:b=f\left( a\right)
\end{equation*}が成り立つ場合には、\(f\)を\(A\)から\(B\)への全射（surjection）や\(A\)から\(B\)の上への写像（onto-mapping）などと呼びます。

写像\(f:A\rightarrow B\)が全射でないこととは、上の命題の否定である、\begin{equation*}\exists b\in B,\ \forall a\in A:b\not=f\left( a\right)
\end{equation*}が成り立つことを意味します。つまり、\(f\)の終集合の要素の中に、\(f\)の始集合のいかなる要素の像でないものが存在する場合、\(f\)は全射ではありません。

例（全射）

以下の2つの集合\begin{eqnarray*}
A &=&\left\{ 1,2,3\right\} \\
B &=&\left\{ a,b,c\right\}
\end{eqnarray*}に対して、写像\(f:A\rightarrow B\)を以下の図で定義します。

図から読み取れるように、\begin{eqnarray*}
f\left( 1\right) &=&c \\
f\left( 2\right) &=&a \\
f\left( 3\right) &=&b
\end{eqnarray*}が成立しています。終集合\(B\)のそれぞれの要素に対して始集合\(A\)の要素から矢印が伸びているため、この写像\(f\)は全射です。

例（全射ではない写像）

以下の2つの集合\begin{eqnarray*}
A &=&\left\{ 1,2,3\right\} \\
B &=&\left\{ a,b,c\right\}
\end{eqnarray*}に対して、写像\(f:A\rightarrow B\)を以下の図で定義します。

図から読み取れるように、\begin{eqnarray*}
f\left( 1\right) &=&b \\
f\left( 2\right) &=&a \\
f\left( 3\right) &=&b
\end{eqnarray*}が成立しています。その一方で、終集合\(B\)の要素である\(c\)に対して、始集合\(A\)の要素から伸びる矢印は存在しません。つまり、\begin{equation*}\exists c\in B,\ \forall x\in A:c\not=f\left( x\right)
\end{equation*}が成立しているため、この写像\(f\)は全射ではありません。

全射による補集合の像

写像\(f:A\rightarrow B\)が与えられたとき、始集合の部分集合\(X\subset A\)を任意に選んだ上で、その補集合\(X^{c}=A\backslash X\)をとります。このとき、以下の2つの集合\begin{eqnarray*}f\left( X^{c}\right) &=&\left\{ f\left( x\right) \in B\ |\ x\in
X^{c}\right\} \\
f\left( X\right) ^{c} &=&B\backslash f\left( X\right)
\end{eqnarray*}の間に包含関係は成立するとは限りません。一方、\(f\)が全射である場合には、以下の関係\begin{equation*}f\left( X\right) ^{c}\subset f\left( X^{c}\right)
\end{equation*}が成立することが保証されます。

実は、上の命題の逆もまた成立します。つまり、写像\(f:A\rightarrow B\)が与えられたとき、任意の集合\(X\subset A\)について、\begin{equation*}f\left( X\right) ^{c}\subset f\left( X^{c}\right)
\end{equation*}が成り立つ場合には、\(f\)は全射であることが保証されます。

以上の2つの命題を踏まえると、写像が全射であることを以下のように表現できることが明らかになりました。

写像から生成される全射

写像\(f:A\rightarrow B\)が与えられたとき、この\(f\)が全射であるか否かを問わず、終集合を値域に制限して、\begin{equation*}f:A\rightarrow f\left( A\right)
\end{equation*}とすれば、これは必ず全射になります。\(b\in f\left( A\right) \)を任意に選んだとき、値域の定義より\(b=f\left( a\right) \)を満たす\(a\in A\)が必ず存在するからです。つまり、\begin{equation*}\forall b\in f\left( A\right) ,\ \exists a\in A:b=f\left( a\right)
\end{equation*}が成り立ちますが、これは\(f\)が全射であることを意味します。

上の命題の逆も成立します。つまり、写像が全射であるならば、その終集合が値域と一致します。

以上の命題より、写像が全射であることと、その写像の終集合と値域が一致することは必要十分であることが明らかになりました。

全射と合成写像

2つの写像\begin{eqnarray*}
f &:&A\rightarrow B \\
g &:&B\rightarrow C
\end{eqnarray*}が与えられたとき、\(f\)の終集合と\(g\)の始集合はともに\(B\)で一致するため合成写像\begin{equation*}g\circ f:A\rightarrow C
\end{equation*}が定義可能であり、これはそれぞれの\(a\in A\)に対して、\begin{equation*}\left( g\circ f\right) \left( a\right) =g\left( f\left( a\right) \right)
\end{equation*}を定めます。

写像\(f,g\)がともに全射である場合、それらの合成写像\(g\circ f\)もまた全射になることが保証されます。

逆に、合成写像\(g\circ f\)が全射であるとき、それを構成する写像\(f,g\)もまた全射であることを保証できるのでしょうか。この場合、\(g\)が全射であることは保証されます。

合成写像\(g\circ f\)が全射である場合には\(g\)もまた全射であることが明らかになりましたが、もう一方の写像\(f\)は全射であるとは限りません。以下の例より明らかです。

全射の逆写像

全射の逆写像は存在するとは限りません。実際、写像\(f:A\rightarrow B\)が全射であり、なおかつ終集合のある要素\(b\in B\)に対してその逆像\(f^{-1}\left( b\right) \subset A\)が複数の要素を持つ場合、逆写像\(f^{-1}:B\rightarrow A\)は点\(b\in B\)において定義不可能です。

例（逆写像を持たない全射）

以下の2つの集合\begin{eqnarray*}
A &=&\left\{ 1,2,3\right\} \\
B &=&\left\{ b,c\right\}
\end{eqnarray*}に対して、写像\(f:A\rightarrow B\)を以下の図で定義します。

図から読み取れるように、\begin{eqnarray*}
f\left( 1\right) &=&b \\
f\left( 2\right) &=&b \\
f\left( 3\right) &=&c
\end{eqnarray*}であるため\(f\)は全射です。逆写像\(f:B\rightarrow A\)は存在しません。実際、\(f\)による\(b\in B\)の逆像は\begin{eqnarray*}f^{-1}\left( b\right) &=&\left\{ x\in A\ |\ f\left( x\right) =b\right\} \\
&=&\left\{ 1,2\right\}
\end{eqnarray*}であるため、逆写像\(f^{-1}:B\rightarrow A\)はそもそも点\(b\in B\)において定義不可能だからです。

演習問題