WIIS

写像

全射

目次

前のページ:

単射と左逆写像の関係

次のページ:

全射と右逆写像の関係

Mailで保存
Xで共有

全射の定義

写像\(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\)は全射ではありません。

例(全射)
入り口を集めることにより得られる集合\(A\)と、出口を集めることにより得られる集合\(B\)が与えられているものとします。それぞれの入り口\(a\in A\)に対して、その入り口を選んだ場合に到達する出口\(f\left( a\right) \in B\)が1つずつだけ存在するのであれば、\begin{equation*}f:A\rightarrow B
\end{equation*}は写像になります。\(f\)が全射である場合には、\begin{equation*}\forall b\in B,\ \exists a\in A:b=f\left( a\right)
\end{equation*}が成り立ちますが、これは、すべての出口が何らかの入り口から繋がっていることを意味します。つまり、入り口を適切に選べば、どの出口へも到達可能であるということです。

例(全射)
以下の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:\mathbb{N} \rightarrow E_{++}\)はそれぞれの\(x\in \mathbb{N} \)に対して、\begin{equation*}f\left( x\right) =2x
\end{equation*}を定めるものとします。ただし、\(\mathbb{N} \)はすべての自然数からなる集合であり、\(E_{++}\)はすべての正の偶数からなる集合です。終集合の要素である正の偶数\(y\in E_{++}\)を任意に選ぶと、それは自然数\(x\in \mathbb{N} \)を用いて\(y=2x\)という形で表すことができますが、\(f\)の定義より、これは\(f\left( x\right) =y\)であることを意味します。つまり、\begin{equation*}\forall y\in E_{++},\ \exists x\in \mathbb{N} :y=f\left( x\right)
\end{equation*}が成り立つため、\(f\)が全射であることが示されました。
例(全射ではない写像)
写像\(f:\mathbb{N} \rightarrow \mathbb{N} \)はそれぞれの\(x\in \mathbb{N} \)に対して、\begin{equation*}f\left( x\right) =2x
\end{equation*}を像として定めるものとします。ただし、\(\mathbb{N} \)はすべての自然数からなる集合です。先の例とは異なり、終集合はすべての正の偶数からなる集合\(E_{++}\)ではなく、すべての自然数からなる集合\(\mathbb{N} \)であることに注意してください。この写像\(f\)は全射ではありません。実際、終集合の要素\(3\in \mathbb{N} \)に注目すると、これに対して\(3=2x\)すなわち\(3=f\left( x\right) \)を満たす自然数\(x\in \mathbb{N} \)は存在しません。つまり、\begin{equation*}\exists 3\in \mathbb{N} ,\ \forall x\in \mathbb{N} :3\not=f\left( x\right)
\end{equation*}が成り立つため、この\(f\)が全射ではないことが示されました。
例(包含写像)
写像\(f:A\rightarrow B\)は包含写像であるものとします。つまり、定義域と終集合の間に\(A\subset B\)という関係が成り立つとともに、\(f\)がそれぞれの\(a\in A\)に対して定める像が、\begin{equation*}f\left( a\right) =a
\end{equation*}であるということです。以前に示したように包含写像は単射です。その一方で、包含写像は全射であるとは限りません。実際、\(f\)の定義域\(A\)が終集合\(B\)の真部分集合であるとき、\begin{equation*}\exists b\in B\backslash A,\ \forall a\in A:b\not=a
\end{equation*}が成り立ちますが、これは、\begin{equation*}
\exists b\in B,\ \forall a\in A:b\not=f\left( a\right)
\end{equation*}を意味するからです。

例(恒等写像)
写像\(f:A\rightarrow A\)が恒等写像であるものとします。つまり、\(f\)がそれぞれの\(a\in A\)に対して定める像が、\begin{equation*}f\left( a\right) =a
\end{equation*}であるということです。以前に示したように恒等写像は単射です。加えて、恒等写像は全射でもあります。実際、\begin{equation*}
\forall a\in A,\ \exists a\in A:a=f\left( a\right)
\end{equation*}すなわち、\begin{equation*}
\forall a\in A,\ \exists a\in A:a=a
\end{equation*}が成り立つからです。

 

全射による補集合の像

写像\(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\)を任意に選んだ上で、その補集合\(X^{c}=A\backslash X\)をとる。\(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\)は全射であることが保証されます。

命題(補集合の像を用いた全射の特徴づけ)
写像\(f:A\rightarrow B\)が与えられたとき、\begin{equation*}\forall X\subset A:f\left( X\right) ^{c}\subset f\left( X^{c}\right)
\end{equation*}が成り立つならば、\(f\)は全射である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

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

命題(補集合の像を用いた全射の特徴づけ)
写像\(f:A\rightarrow B\)が与えられたとき、\begin{equation*}\forall X\subset A:f\left( X\right) ^{c}\subset f\left( X^{c}\right)
\end{equation*}が成り立つことは、\(f\)が全射であるための必要十分条件である。

 

写像から生成される全射

写像\(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\)が全射であることを意味します。

命題(写像から生成される全射)
写像\(f:A\rightarrow B\)が任意に与えられたとき、\(f:A\rightarrow f\left( A\right) \)は全射である。ただし、\(f\left( A\right) \)は\(f\)の値域である。

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

命題(全射の終集合と値域は一致する)
写像\(f:A\rightarrow B\)が全射であるならば、\(B=f\left( A\right) \)が成り立つ。ただし、\(f\left(A\right) \)は\(f\)の値域である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

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

命題(全射の特徴づけ)

写像\(f:A\rightarrow B\)について\(B=f\left(A\right) \)が成り立つことは、\(f\)が全射であるための必要十分条件である。

例(写像から生成される全射)
写像\(f:\mathbb{R} \supset \left[ 1,2\right] \rightarrow \mathbb{R} \)はそれぞれの\(x\in \left[ 1,2\right] \)に対して、\begin{equation*}f\left( x\right) =2x
\end{equation*}を定めるものとします。\(f\)の値域は、\begin{eqnarray*}f\left( \left[ 1,2\right] \right) &=&\left\{ f\left( x\right) \in \mathbb{R} \ |\ x\in \left[ 1,2\right] \right\} \\
&=&\left\{ 2x\in \mathbb{R} \ |\ x\in \left[ 1,2\right] \right\} \\
&=&\left[ 2,4\right] \end{eqnarray*}ですが、これは\(f\)の終集合\(\mathbb{R} \)と一致しないため、先の命題より\(f\)は全射ではありません。一方、\(f\)の終集合を値域に制限して\(f:\mathbb{R} \supset \left[ 1,2\right] \rightarrow \left[ 2,4\right] \)とすれば、先の命題より\(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\)もまた全射になることが保証されます。

命題(全射の合成は全射)
2つの写像\(f:A\rightarrow B\)と\(g:B\rightarrow C\)が任意に与えられたとき、これらがともに全射であるならば、合成写像\(g\circ f:A\rightarrow C\)もまた全射である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

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

命題(全射である合成写像を構成する全射)
2つの写像\(f:A\rightarrow B\)と\(g:B\rightarrow C\)が任意に与えられたとき、合成写像\(g\circ f:A\rightarrow C\)が全射であるならば、写像\(g\)もまた全射である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

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

例(全射である合成写像を構成する非全射)
集合\(A,B,C\)がそれぞれ、\begin{eqnarray*}A &=&\left\{ a_{1},a_{2}\right\} \\
B &=&\left\{ b_{1},b_{2},b_{3}\right\} \\
C &=&\left\{ c_{1},c_{2}\right\}
\end{eqnarray*}が与えられているものとします。写像\(f:A\rightarrow B\)は、\begin{eqnarray*}f\left( a_{1}\right) &=&b_{1} \\
f\left( a_{2}\right) &=&b_{2}
\end{eqnarray*}を満たし、写像\(g:B\rightarrow C\)は、\begin{eqnarray*}g\left( b_{1}\right) &=&c_{1} \\
g\left( b_{2}\right) &=&c_{2} \\
g\left( b_{3}\right) &=&c_{2}
\end{eqnarray*}を満たすとき、合成写像\(g\circ f:A\rightarrow C\)は、\begin{eqnarray*}\left( g\circ f\right) \left( a_{1}\right) &=&g\left( f\left( a_{1}\right)
\right) =g\left( b_{1}\right) =c_{1} \\
\left( g\circ f\right) \left( a_{2}\right) &=&g\left( f\left( a_{2}\right)
\right) =g\left( b_{2}\right) =c_{2}
\end{eqnarray*}を満たします。\(g\)と\(g\circ f\)はともに全射である一方、\(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\)において定義不可能だからです。

 

演習問題

問題(全射)
写像\(f:\mathbb{N} \rightarrow \mathbb{N} \)はそれぞれの\(x\in \mathbb{N} \)に対して、\begin{equation*}f\left( x\right) =2x^{2}-1
\end{equation*}を定めるものとします。\(f\)は全射でしょうか。議論してください。ただし、\(\mathbb{N} \)はすべての自然数からなる集合です。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(全射)
写像\(f:\mathbb{R} \rightarrow \mathbb{R} _{+}\)はそれぞれの\(x\in \mathbb{R} \)に対して、\begin{equation*}f\left( x\right) =\left\vert x\right\vert
\end{equation*}を定めるものとします。\(f\)は全射でしょうか。議論してください。ただし、\(\mathbb{R} _{+}\)はすべての非負の実数からなる集合です。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(全射)
写像\(f:\mathbb{N} \rightarrow \mathbb{Q} \)はそれぞれの\(x\in \mathbb{N} \)に対して、\begin{equation*}f\left( x\right) =\frac{x}{x+1}
\end{equation*}を定めるものとします。\(f\)は全射でしょうか。議論してください。ただし、\(\mathbb{N} \)はすべての自然数からなる集合であり、\(\mathbb{Q} \)はすべての有理数からなる集合です。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(全射)
写像\(f:\mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z} \)はそれぞれの\(\left( x,y\right) \in \mathbb{Z} \times \mathbb{Z} \)に対して、\begin{equation*}f\left( x,y\right) =x+y
\end{equation*}を定めるものとします。\(f\)は全射でしょうか。議論してください。ただし、\(\mathbb{Z} \)はすべての整数からなる集合です。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(全射)
写像\(f:\mathbb{R} \rightarrow \mathbb{R} \)はそれぞれの\(x\in \mathbb{R} \)に対して、\begin{equation*}f\left( x\right) =1
\end{equation*}を定めるものとします。\(f\)は全射ですか。議論してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(全射)
集合\(A,B\)がそれぞれ、\begin{eqnarray*}A &=&\left\{ a,b,c,d\right\} \\
B &=&\left\{ 0,1,2,3\right\}
\end{eqnarray*}と定義されているものとします。以下の\(A\times B\)の部分集合\begin{eqnarray*}f &=&\left\{ \left( a,2\right) ,\left( b,0\right) ,\left( c,0\right) ,\left(
d,1\right) \right\} \\
g &=&\left\{ \left( a,1\right) ,\left( b,3\right) ,\left( c,0\right) ,\left(
d,2\right) \right\} \\
h &=&\left\{ \left( a,3\right) ,\left( b,1\right) ,\left( d,2\right) ,\left(
d,3\right) \right\} \\
i &=&\left\{ \left( a,1\right) ,\left( c,2\right) ,\left( d,3\right)
\right\}
\end{eqnarray*}はそれぞれ全射でしょうか。議論してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(単射と全射が一致するための条件)
集合\(A\)が有限集合である場合には、写像\(A\rightarrow A\)が単射であることと、その写像\(f:A\rightarrow A\)が全射であることは必要十分であることを証明してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

関連知識

前のページ:

単射と左逆写像の関係

次のページ:

全射と右逆写像の関係

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

プレミアム会員専用コンテンツです
ログイン】【会員登録