有限集合の像の濃度
写像\(f:A\rightarrow B\)による定義域\(A\)の像、すなわち\(f\)の値域は、\begin{equation*}f\left( A\right) =\left\{ f\left( a\right) \in B\ |\ a\in A\right\}
\end{equation*}と定義されます。定義域\(A\)が有限集合である場合、値域\(f\left( A\right) \)もまた有限集合です。また、異なる要素が同じ像を持つ可能性があるため、値域の濃度は定義域の濃度以下になります。
\end{equation*}が成り立つ。
先の命題を制限写像に適用すると、定義域全体だけでなく、その任意の有限部分集合についても同様の結果が得られます。
\end{equation*}が成り立つ。
像の濃度の等号条件
写像\(f:A\rightarrow B\)について\(A\)が有限集合である場合には、値域\(f\left( A\right) \)も有限集合であるとともに、\begin{equation*}\left\vert f\left( A\right) \right\vert \leq \left\vert A\right\vert
\end{equation*}が成り立つことが明らかになりました。特に、この不等式が等号で成立することと、\(f\)が単射であることは必要十分です。
A\right\vert \\
&&\left( b\right) \ f\text{は単射ではない}\Leftrightarrow \left\vert f\left( A\right) \right\vert <\left\vert
A\right\vert
\end{eqnarray*}が成り立つ。
有限な逆像の濃度
写像\(f:A\rightarrow B\)による集合\(D\subset B\)の逆像は、\begin{equation*}f^{-1}\left( D\right) =\left\{ a\in A\ |\ f\left( a\right) \in D\right\}
\end{equation*}として定義されます。定義より、\begin{equation*}
f^{-1}\left( D\right) \subset A
\end{equation*}であるため、定義域\(A\)が有限集合である場合には\(f^{-1}\left( D\right) \)もまた有限集合になります。
\end{equation*}が成り立つ。
先の命題では写像\(f\)の定義域\(A\)が有限集合である状況を想定しています。\(A\)が有限集合であれば、\(D\)は有限集合である必要はありません。
f\left( 2\right) &=&4 \\
f\left( 3\right) &=&6 \\
f\left( 4\right) &=&7
\end{eqnarray*}と定義します。\(f\)の定義域\(\left\{ 1,2,3,4\right\} \)は有限集合であるため、先の命題が要求する条件を満たしています。すべての偶数からなる集合\begin{equation*}E=\left\{ 2n\ |\ n\in \mathbb{Z} \right\}
\end{equation*}に注目します。\(E\subset \mathbb{Z} \)であるとともに\(E\)は有限集合ではありません。しかし、\(f\)による逆像は、\begin{eqnarray*}f^{-1}\left( E\right) &=&\left\{ x\in \left\{ 1,2,3,4\right\} \ |\ f\left(
x\right) \in E\right\} \\
&=&\left\{ 1,2,3\right\}
\end{eqnarray*}であり、これは有限集合です。さらに、\begin{equation*}
\left\vert f^{-1}\left( E\right) \right\vert =3\leq 4=\left\vert \left\{
1,2,3,4\right\} \right\vert
\end{equation*}が成立しています。
逆に、\(A\)が有限集合でない場合には、先の命題の主張は成り立つとは限りません。以下の例より明らかです。
\end{equation*}と定義します。\(f\)の定義域\(\mathbb{Z} \)は有限集合ではないため、先の命題が要求する条件を満たしません。集合\(\left\{ 0\right\} \subset \mathbb{Z} \)は有限集合である一方で、\begin{eqnarray*}f^{-1}\left( \left\{ 0\right\} \right) &=&\left\{ z\in \mathbb{Z} \ |\ f\left( z\right) \in \left\{ 0\right\} \right\} \\
&=&\mathbb{Z} \end{eqnarray*}は有限集合ではありません。
写像\(f:A\rightarrow B\)の定義域\(A\)が有限集合である場合には、集合\(D\subset B\)を任意に選んだとき、\(f\)による逆像\(f\left( D\right) \)は有限集合であるとともに、\begin{equation*}\left\vert f^{-1}\left( D\right) \right\vert \leq \left\vert A\right\vert
\end{equation*}が成り立つことが明らかになりました。逆像\(f^{-1}\left( D\right) \)の濃度をより正確に評価するために、まずは以下の命題を示します。
\end{equation*}が成り立つ。
以上の命題を踏まえると以下を得ます。
D\right) \right\vert \leq \left\vert A\right\vert
\end{equation*}が成り立つ。
単射・全射の場合の逆像の濃度
写像が単射または全射である場合、逆像の濃度についてさらに強い結果が得られます。
A\right) \right\vert
\end{equation*}が成り立つ。
全射による逆像の濃度については以下が成り立ちます。
\end{equation*}が成り立つ。
全単射の場合には以下が成り立ちます。
\end{equation*}が成り立つ。
要素の逆像の濃度の和
写像\(f:A\rightarrow B\)が与えられたとき、終集合の要素\(b\in B\)の逆像は、\begin{equation*}f^{-1}\left( b\right) =\left\{ a\in A\ |\ f\left( a\right) =b\right\}
\end{equation*}と定義されます。ちなみにこれは、\(f\)による1点集合\(\left\{ b\right\} \subset B\)の逆像\begin{eqnarray*}f^{-1}\left( \left\{ b\right\} \right) &=&\left\{ a\in A\ |\ f\left(
a\right) \in \left\{ b\right\} \right\} \\
&=&\left\{ a\in A\ |\ f\left( a\right) =b\right\}
\end{eqnarray*}と一致しますが、以降では\(f^{-1}\left( b\right) \)を用いて議論します。
写像\(f:A\rightarrow B\)の値域\(f\left( A\right) \)に属するそれぞれの要素の逆像からなる集合族\begin{equation*}\left\{ f^{-1}\left( b\right) \right\} _{b\in f\left( A\right) }
\end{equation*}は\(f\)の定義域\(A\)の分割です。つまり、\begin{equation*}A=\bigcup_{b\in f\left( A\right) }f^{-1}\left( b\right)
\end{equation*}であるとともに、\begin{equation*}
\forall b,b^{\prime }\in f\left( A\right) :\left[ b\not=b^{\prime
}\Rightarrow f^{-1}\left( b\right) \cap f^{-1}\left( b^{\prime }\right)
=\phi \right]
\end{equation*}が成り立ちます。
\end{equation*}は\(A\)の分割である。
写像の定義域が有限集合である場合、その濃度は値域の要素の逆像の濃度の和として表されます。
f^{-1}\left( b\right) \right\vert
\end{equation*}が成り立つ。
先の命題は、終集合の部分集合の逆像についても一般化できます。
A\right) }\left\vert f^{-1}\left( b\right) \right\vert
\end{equation*}が成り立つ。
演習問題
A &=&\left\{ 1,2,3,4,5,6\right\} \\
B &=&\left\{ a,b,c,d\right\}
\end{eqnarray*}に対して、写像\(f:A\rightarrow B\)を、\begin{eqnarray*}f\left( 1\right) &=&f\left( 2\right) =a \\
f\left( 3\right) &=&b \\
f\left( 4\right) &=&f\left( 5\right) =f\left( 6\right) =c
\end{eqnarray*}と定義します。以下の集合を特定した上で、その濃度を求めてください。
- \(f\left( A\right) \)
- \(f^{-1}\left( a\right) \)
- \(f^{-1}\left( \left\{ a,c\right\} \right) \)
\end{equation*}が成り立つものとします。このとき、\begin{equation*}
2\left\vert B\right\vert \leq \left\vert A\right\vert
\end{equation*}が成り立つことを証明してください。
\end{equation*}が成り立つものとします。さらに、\begin{equation*}
\left\vert A\right\vert =30
\end{equation*}であるとき、\(\left\vert B\right\vert \)を求めてください。
