可算集合の像の濃度
写像\(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) \)は高々可算集合です。つまり、\(f\left( A\right) \)は有限集合または可算集合です。
先の命題を制限写像に適用すると、定義域全体だけでなく、その任意の可算部分集合についても同様の結果が得られます。
写像による可算集合の像は高々可算集合であることが明らかになりました。以下は可算集合の像が可算集合である例です。
\end{equation*}を定めるものとします。\(\mathbb{Z} \)は可算集合です。また、\begin{eqnarray*}f\left( \mathbb{Z} \right) &=&\left\{ f\left( n\right) \in \mathbb{Z} \ |\ n\in \mathbb{Z} \right\} \\
&=&\left\{ n^{2}\in \mathbb{Z} \ |\ n\in \mathbb{Z} \right\} \\
&=&\left\{ 0,1,4,9,16,\cdots \right\}
\end{eqnarray*}ですが、これは可算集合です。
続いて、可算集合の像が有限集合である例です。
\begin{array}{cl}
0 & \left( if\ n\text{が偶数}\right) \\
1 & \left( if\ n\text{が奇数}\right)
\end{array}\right.
\end{equation*}を定めるものとします。\(\mathbb{Z} \)は可算集合です。また、\begin{eqnarray*}f\left( \mathbb{Z} \right) &=&\left\{ f\left( n\right) \in \mathbb{R} \ |\ n\in \mathbb{Z} \right\} \\
&=&\left\{ 0,1\right\}
\end{eqnarray*}ですが、これは有限集合です。
単射による像の濃度の保存
写像\(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\)が単射である場合には、\begin{equation*}\left\vert f\left( A\right) \right\vert =\left\vert A\right\vert
\end{equation*}が成り立ちます。つまり、\(f\left( A\right) \)は可算集合です。
\end{equation*}が成り立つ。したがって\(f\left( A\right) \)は可算集合である。
先の命題の逆は成り立つとは限りません。つまり、\(A\)と\(f\left( A\right) \)がともに可算集合であったとしても\(f\)は単射であるとは限りません。以下の例より明らかです。
\end{equation*}を定めるものとします。ただし、\(\left\lceil \cdot\right\rceil \)は天井関数であり、\(\left\lceil x\right\rceil \)は\(x\)以上の最小の整数を表します。具体的には、\begin{eqnarray*}f\left( 1\right) &=&\left\lceil \frac{1}{2}\right\rceil =1 \\
f\left( 2\right) &=&\left\lceil 1\right\rceil =1 \\
f\left( 3\right) &=&\left\lceil \frac{3}{2}\right\rceil =2 \\
f\left( 4\right) &=&\left\lceil 2\right\rceil =2 \\
&&\vdots
\end{eqnarray*}などとなります。\(f\left(1\right) =f\left( 2\right) \)であるため\(f\)は単射ではありません。\(f\)の定義域\(\mathbb{N} \)は可算集合です。値域は、\begin{equation*}f\left( \mathbb{N} \right) =\mathbb{N} \end{equation*}ですが、これもまた可算集合です。
先の命題を制限写像に適用すると、定義域全体だけでなく、その任意の可算部分集合についても同様の結果が得られます。
\end{equation*}が成り立つ。したがって\(f\left( C\right) \)は可算集合である。
可算集合上に定義された写像による逆像
写像\(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) \)は高々可算集合になります。
先の命題では写像\(f\)の定義域\(A\)が可算集合である状況を想定しています。\(A\)が可算集合であれば、\(D\)は可算集合である必要はありません。
\end{equation*}を定めるものとします。定義域\(\mathbb{N} \)は可算集合であるため、先の命題が要求する条件を満たしています。以下の集合\begin{equation*}D=\left( \mathbb{R} \backslash \mathbb{Q} \right) \cup 2\mathbb{N} \end{equation*}に注目します。ただし、\begin{equation*}
2\mathbb{N} =\left\{ 2,4,6,\cdots \right\}
\end{equation*}です。つまり、\(D\)は無理数と正の偶数からなる集合であり、これは非可算集合です。\(D\subset \mathbb{R} \)ゆえに\(f\)による逆像をとることができますが、\begin{eqnarray*}f^{-1}\left( D\right) &=&\left\{ n\in \mathbb{N} \ |\ f\left( n\right) \in D\right\} \\
&=&\left\{ n\in \mathbb{N} \ |\ n\in \left( \mathbb{R} \backslash \mathbb{Q} \right) \cup 2\mathbb{N} \right\} \\
&=&\left\{ n\in \mathbb{N} \ |\ n\in 2\mathbb{N} \right\} \\
&=&2\mathbb{N} \end{eqnarray*}であり、これは可算集合です。
逆に、\(A\)が可算集合でない場合には、先の命題の主張は成り立つとは限りません。以下の例より明らかです。
\end{equation*}と定義します。\(f\)の定義域\(\mathbb{R} \)は可算集合ではないため、先の命題が要求する条件を満たしません。集合\(\left\{ 0\right\} \subset \mathbb{R} \)は有限集合である一方で、\begin{eqnarray*}f^{-1}\left( \left\{ 0\right\} \right) &=&\left\{ x\in \mathbb{R} \ |\ f\left( x\right) \in \left\{ 0\right\} \right\} \\
&=&\mathbb{R} \end{eqnarray*}は可算集合ではありません。
写像\(f:A\rightarrow B\)の定義域\(A\)が可算集合である場合には、集合\(D\subset B\)を任意に選んだとき、\(f\)による逆像\(f^{-1}\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*}が成り立つ。
一般の写像\(f:A\rightarrow B\)については、\(A\)が可算集合の場合には、任意の\(D\subset B\)について逆像\(f^{-1}\left(D\right) \)は高々可算集合です。一方、\(f\)が単射である場合には、\(A\)が可算集合であるかどうかとは関係なく、逆像\(f^{-1}\left( D\right) \)の濃度は集合\(D\cap f\left( A\right) \)の濃度と一致することを先の命題は主張しています。ちなみに、\(f\)が単射でない場合には、\(D\cap f\left( A\right) \)だけでは逆像\(f^{-1}\left( D\right) \)の濃度を特定できません。以下の例より明らかです。
\end{equation*}と定義されているものとします。\(f\)は単射ではありません。集合\(D=\left\{ 0\right\} \subset \mathbb{R} \)については、\begin{eqnarray*}\left\vert D\cap f\left( \mathbb{N} \right) \right\vert &=&\left\vert \left\{ 0\right\} \cap \left\{ 0\right\}
\right\vert \\
&=&\left\vert \left\{ 0\right\} \right\vert \\
&=&1
\end{eqnarray*}である一方で、\begin{eqnarray*}
\left\vert f^{-1}\left( D\right) \right\vert &=&\left\vert f^{-1}\left(
\left\{ 0\right\} \right) \right\vert \\
&=&\left\vert \mathbb{N} \right\vert
\end{eqnarray*}であるため、\begin{equation*}
\left\vert D\cap f\left( \mathbb{N} \right) \right\vert \not=\left\vert f^{-1}\left( D\right) \right\vert
\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\)と終集合の部分集合\(D\subset B\)が与えられたとき、集合族\begin{equation*}\left\{ f^{-1}\left( b\right) \right\} _{b\in D\cap f\left( A\right) }
\end{equation*}は逆像\(f^{-1}\left( D\right) \)の分割です。つまり、\begin{equation*}f^{-1}\left( D\right) =\bigcup_{b\in D\cap f\left( A\right) }f^{-1}\left(
b\right)
\end{equation*}であるとともに、\begin{equation*}
\forall b\in D\cap f\left( A\right) :f^{-1}\left( b\right) \not=\phi
\end{equation*}および、\begin{equation*}
\forall b,b^{\prime }\in D\cap 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*}は\(f^{-1}\left( D\right) \)の分割である。
写像\(f:A\rightarrow B\)と集合\(D\subset B\)について、以下の関係\begin{equation*}f^{-1}\left( D\right) =\bigcup_{b\in D\cap f\left( A\right) }f^{-1}\left(
b\right)
\end{equation*}が成り立つことが明らかになりました。ただし、\(\left\{ f^{-1}\left( b\right) \right\}_{b\in D\cap f\left( A\right) }\)の要素は互いに素です。
以上の関係を用いて逆像\(f^{-1}\left( D\right) \)の濃度を判定する際には次の2つを調べる必要があります。1つ目は添字集合\(D\cap f\left( A\right) \)の濃度です。2つ目はそれぞれの\(b\in D\cap f\left( A\right) \)に対する逆像\(f^{-1}\left( b\right) \)の濃度です。以下が具体例です。
\end{equation*}が成り立つ場合、\begin{eqnarray*}
f^{-1}\left( D\right) &=&\bigcup_{b\in D\cap f\left( A\right) }f^{-1}\left(
b\right) \\
&=&\bigcup_{b\in \phi }f^{-1}\left( b\right) \\
&=&\phi
\end{eqnarray*}であるため、\begin{equation*}
\left\vert f^{-1}\left( D\right) \right\vert =0
\end{equation*}を得ます。
\end{equation*}が有限集合である場合、\begin{equation*}
f^{-1}\left( D\right) =\bigcup_{b\in D\cap f\left( A\right) }f^{-1}\left(
b\right)
\end{equation*}は有限個の互いに素な集合\(f^{-1}\left( b\right) \)の和集合です。したがって、すべての\(f^{-1}\left( b\right) \)が有限集合であれば、有限個の有限集合の和集合は有限集合であるため\(f^{-1}\left( D\right) \)も有限集合であるとともに、\begin{equation*}\left\vert f^{-1}\left( D\right) \right\vert =\sum_{b\in D\cap f\left(
A\right) }\left\vert f^{-1}\left( b\right) \right\vert
\end{equation*}が成り立ちます。また、すべての\(f^{-1}\left( b\right) \)が高々可算集合であれば、有限個の高々可算集合の和集合は高々可算集合であるため、\(f^{-1}\left( D\right) \)も高々可算集合です。
\end{equation*}が可算集合である場合、\begin{equation*}
f^{-1}\left( D\right) =\bigcup_{b\in D\cap f\left( A\right) }f^{-1}\left(
b\right)
\end{equation*}は可算個の互いに素な集合\(f^{-1}\left( b\right) \)の和集合です。したがって、すべての\(f^{-1}\left( b\right) \)が高々可算集合であれば、選択公理のもとでは、可算個の高々可算集合の和集合は可算集合であるため、\(f^{-1}\left( D\right) \)も可算集合です。
\end{equation*}は非空であるとともに、少なくとも1つの\(b\in D\cap f\left( A\right) \)について\(f^{-1}\left(b\right) \)が非可算集合であるものとします。逆像の定義より、\begin{equation*}f^{-1}\left( b\right) \subset f^{-1}\left( D\right)
\end{equation*}が成り立つため\(f^{-1}\left(D\right) \)は非可算集合です。
演習問題
\end{equation*}を定めるものとします。この例を用いることにより、写像による可算集合の像が可算集合である場合に、その写像は単射であるとは限らないことを示してください。
\end{equation*}を定めるものとします。本文中で示した以下の関係\begin{equation*}
f^{-1}\left( D\right) =\bigcup_{b\in D\cap f\left( A\right) }f^{-1}\left(
b\right)
\end{equation*}を用いることにより、以下の集合\begin{equation*}
D=\left\{ 0,1,2,3\right\} \subset \mathbb{R} \end{equation*}の逆像\(f^{-1}\left( D\right) \)を求めてください。
\begin{array}{cl}
0 & \left( if\ n\text{が偶数}\right) \\
1 & \left( if\ n\text{が奇数}\right)
\end{array}\right.
\end{equation*}を定めるものとします。以下の逆像を求めた上で、その濃度を判定してください。
- \(f^{-1}\left( \left\{ 0\right\} \right) \)
- \(f^{-1}\left( \left\{ 1\right\} \right) \)
- \(f^{-1}\left( \left\{ 0,1\right\} \right) \)
\end{equation*}を定めるものとします。\(f\)による以下の集合\begin{equation*}D=[-2,+\infty )\subset \mathbb{R} \end{equation*}の逆像\(f^{-1}\left( D\right) \)を特定した上で、その濃度を求めてください。さらに、写像\(f:A\rightarrow B\)が単射であるならば、集合\(D\subset B\)を任意に選んだとき、\begin{equation*}\left\vert f^{-1}\left( D\right) \right\vert =\left\vert D\cap f\left(
A\right) \right\vert
\end{equation*}が成り立つという事実を利用して\(f^{-1}\left( D\right) \)の濃度を求め、先と同じ結果が得られることを確認してください。
