共通部分の有限性と濃度の上限
前節では、有限集合の和集合もまた有限集合であり、その濃度を包除原理によって求められることを示しました。本節では、有限集合の共通部分の濃度について考えます。
集合\(A,B\)の共通部分\(A\cap B\)とは、\(A\)と\(B\)の両方に属する要素からなる集合です。共通部分については、\begin{eqnarray*}A\cap B &\subset &A \\
A\cap B &\subset &B
\end{eqnarray*}がともに成り立ちます。したがって、\(A\)や\(B\)が有限集合である場合、有限集合の部分集合の濃度に関する性質を利用することにより、共通部分\(A\cap B\)の有限性と濃度の上限を明らかにできます。
命題（共通部分の有限性と濃度の上限）
集合\(A\)が有限集合であるならば、任意の集合\(B\)について、共通部分\(A\cap B\)も有限集合であるとともに、\begin{equation*}\left\vert A\cap B\right\vert \leq \left\vert A\right\vert
\end{equation*}が成り立つ。
\end{equation*}が成り立つ。
先の命題では\(B\)は有限集合であることを仮定する必要はありません。\(A,B\)の少なくとも一方が有限集合であれば、その共通部分は有限集合です。ちなみに、\(A,B\)の双方が有限集合である場合には以下が成り立ちます。
命題（2つの有限集合の共通部分の濃度の上限）
集合\(A,B\)がともに有限集合であるならば、共通部分\(A\cap B\)も有限集合であるとともに、\begin{equation*}\left\vert A\cap B\right\vert \leq \min \left\{ \left\vert A\right\vert
,\left\vert B\right\vert \right\}
\end{equation*}が成り立つ。
,\left\vert B\right\vert \right\}
\end{equation*}が成り立つ。
例（共通部分の濃度の上限）
以下の有限集合\begin{eqnarray*}
A &=&\left\{ 1,2,3,4,5,6\right\} \\
B &=&\left\{ 4,5,6,7,8\right\}
\end{eqnarray*}について、\begin{eqnarray*}
\left\vert A\right\vert &=&6 \\
\left\vert B\right\vert &=&5
\end{eqnarray*}です。また、\begin{equation*}
A\cap B=\left\{ 4,5,6\right\}
\end{equation*}であるため、\begin{equation*}
\left\vert A\cap B\right\vert =3
\end{equation*}です。したがって、\begin{equation*}
\left\vert A\cap B\right\vert =3\leq 5=\min \left\{ \left\vert A\right\vert
,\left\vert B\right\vert \right\}
\end{equation*}が成り立ちますが、この結果は先の命題の主張と整合的です。
A &=&\left\{ 1,2,3,4,5,6\right\} \\
B &=&\left\{ 4,5,6,7,8\right\}
\end{eqnarray*}について、\begin{eqnarray*}
\left\vert A\right\vert &=&6 \\
\left\vert B\right\vert &=&5
\end{eqnarray*}です。また、\begin{equation*}
A\cap B=\left\{ 4,5,6\right\}
\end{equation*}であるため、\begin{equation*}
\left\vert A\cap B\right\vert =3
\end{equation*}です。したがって、\begin{equation*}
\left\vert A\cap B\right\vert =3\leq 5=\min \left\{ \left\vert A\right\vert
,\left\vert B\right\vert \right\}
\end{equation*}が成り立ちますが、この結果は先の命題の主張と整合的です。
2つの集合に関する先の結果は、有限個の集合の共通部分にも拡張できます。
命題（共通部分の有限性と濃度の上限）
自然数\(n\in \mathbb{N} \)と\(n\)個の集合\(A_{1},\cdots ,A_{n}\)が与えられているものとする。その中の少なくとも1つ\(A_{k}\)が有限集合であるならば、共通部分\begin{equation*}\bigcap\limits_{i=1}^{n}A_{i}
\end{equation*}も有限集合であるとともに、\begin{equation*}
\left\vert \bigcap\limits_{i=1}^{n}A_{i}\right\vert \leq \left\vert
A_{k}\right\vert
\end{equation*}が成り立つ。特に、\(A_{1},\cdots ,A_{n}\)がいずれも有限集合であるならば、\begin{equation*}\left\vert \bigcap\limits_{i=1}^{n}A_{i}\right\vert \leq \min_{1\leq i\leq
n}\left\vert A_{i}\right\vert
\end{equation*}が成り立つ。
\end{equation*}も有限集合であるとともに、\begin{equation*}
\left\vert \bigcap\limits_{i=1}^{n}A_{i}\right\vert \leq \left\vert
A_{k}\right\vert
\end{equation*}が成り立つ。特に、\(A_{1},\cdots ,A_{n}\)がいずれも有限集合であるならば、\begin{equation*}\left\vert \bigcap\limits_{i=1}^{n}A_{i}\right\vert \leq \min_{1\leq i\leq
n}\left\vert A_{i}\right\vert
\end{equation*}が成り立つ。
包除原理による共通部分の濃度
2つの有限集合\(A,B\)に関する包除原理より、\begin{equation*}\left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert
B\right\vert -\left\vert A\cap B\right\vert
\end{equation*}が成り立ちます。この等式を\(\left\vert A\cap B\right\vert \)について解くことにより、共通部分の濃度を求める公式が得られます。
命題（2つの有限集合の共通部分の濃度）
集合\(A,B\)がともに有限集合であるならば、共通部分\(A\cap B\)も有限集合であるとともに、\begin{equation*}\left\vert A\cap B\right\vert =\left\vert A\right\vert +\left\vert
B\right\vert -\left\vert A\cup B\right\vert
\end{equation*}が成り立つ。
B\right\vert -\left\vert A\cup B\right\vert
\end{equation*}が成り立つ。
共通部分の濃度の上限に関する命題\begin{equation*}
\left\vert A\cap B\right\vert \leq \left\vert A\right\vert
\end{equation*}では\(A\)が有限であれば\(B\)は必ずしも有限である必要はありません。また、\(A\cap B\)の濃度の上限を知る上で\(A\)の濃度さえあれば十分です。一方、共通部分の濃度を特定する命題\begin{equation*}\left\vert A\cap B\right\vert =\left\vert A\right\vert +\left\vert
B\right\vert -\left\vert A\cup B\right\vert
\end{equation*}では\(A,B\)がともに有限濃度であることを想定しています。また、こちらの命題では\(A\cap B\)の濃度を知る上で\(A\)の濃度に加えて\(B\)や\(A\cup B\)の濃度も必要になります。以上が両者の違いです。
例（共通部分の濃度の計算）
有限集合\(A,B\)について、\begin{eqnarray*}\left\vert A\right\vert &=&40 \\
\left\vert B\right\vert &=&35 \\
\left\vert A\cup B\right\vert &=&60
\end{eqnarray*}が成り立つ場合、先の命題より、\begin{eqnarray*}
\left\vert A\cap B\right\vert &=&\left\vert A\right\vert +\left\vert
B\right\vert -\left\vert A\cup B\right\vert \\
&=&40+35-60 \\
&=&15
\end{eqnarray*}が得られます。
\left\vert B\right\vert &=&35 \\
\left\vert A\cup B\right\vert &=&60
\end{eqnarray*}が成り立つ場合、先の命題より、\begin{eqnarray*}
\left\vert A\cap B\right\vert &=&\left\vert A\right\vert +\left\vert
B\right\vert -\left\vert A\cup B\right\vert \\
&=&40+35-60 \\
&=&15
\end{eqnarray*}が得られます。
2つの集合に関する先の結果は、有限個の集合の共通部分にも拡張できます。
命題（有限個の有限集合の共通部分の濃度）
\(n\geq 2\)を満たす\(n\in \mathbb{N} \)と\(n\)個の集合\(A_{1},\cdots ,A_{n}\)が与えられているものとする。これらがいずれも有限集合であるならば、共通部分\begin{equation*}\bigcap\limits_{i=1}^{n}A_{i}
\end{equation*}も有限集合であるとともに、\begin{equation*}
\left\vert \bigcap\limits_{i=1}^{n}A_{i}\right\vert =\left( -1\right) ^{n+1}
\left[ \left\vert \bigcup\limits_{i=1}^{n}A_{i}\right\vert -\sum_{\phi
\not=I\varsubsetneq \left\{ 1,\cdots ,n\right\} }\left( -1\right)
^{\left\vert I\right\vert +1}\left\vert \bigcap\limits_{i\in
I}A_{i}\right\vert \right] \end{equation*}が成り立つ。
\end{equation*}も有限集合であるとともに、\begin{equation*}
\left\vert \bigcap\limits_{i=1}^{n}A_{i}\right\vert =\left( -1\right) ^{n+1}
\left[ \left\vert \bigcup\limits_{i=1}^{n}A_{i}\right\vert -\sum_{\phi
\not=I\varsubsetneq \left\{ 1,\cdots ,n\right\} }\left( -1\right)
^{\left\vert I\right\vert +1}\left\vert \bigcap\limits_{i\in
I}A_{i}\right\vert \right] \end{equation*}が成り立つ。
例（3個の有限集合の共通部分の濃度）
3個の集合\(A_{1},A_{2},A_{3}\)がいずれも有限集合であるならば、先の命題より共通部分\(A_{1}\cap A_{2}\cap A_{3}\)もまた有限集合であるとともに、\begin{eqnarray*}\left\vert A_{1}\cap A_{2}\cap A_{3}\right\vert &=&\left( -1\right) ^{3+1}
\left[ \left\vert A_{1}\cup A_{2}\cup A_{3}\right\vert -\sum_{\phi
\not=I\varsubsetneq \left\{ 1,2,3\right\} }\left( -1\right) ^{\left\vert
I\right\vert +1}\left\vert \bigcap\limits_{i\in I}A_{i}\right\vert \right] \\
&=&\left\vert A_{1}\cup A_{2}\cup A_{3}\right\vert -\sum_{\phi
\not=I\varsubsetneq \left\{ 1,2,3\right\} }\left( -1\right) ^{\left\vert
I\right\vert +1}\left\vert \bigcap\limits_{i\in I}A_{i}\right\vert \\
&=&\left\vert A_{1}\cup A_{2}\cup A_{3}\right\vert \\
&&+\left\vert A_{1}\cap A_{2}\right\vert +\left\vert A_{1}\cap
A_{3}\right\vert +\left\vert A_{2}\cap A_{3}\right\vert \\
&&-\left\vert A_{1}\right\vert -\left\vert A_{2}\right\vert -\left\vert
A_{3}\right\vert
\end{eqnarray*}が成り立ちます。
\left[ \left\vert A_{1}\cup A_{2}\cup A_{3}\right\vert -\sum_{\phi
\not=I\varsubsetneq \left\{ 1,2,3\right\} }\left( -1\right) ^{\left\vert
I\right\vert +1}\left\vert \bigcap\limits_{i\in I}A_{i}\right\vert \right] \\
&=&\left\vert A_{1}\cup A_{2}\cup A_{3}\right\vert -\sum_{\phi
\not=I\varsubsetneq \left\{ 1,2,3\right\} }\left( -1\right) ^{\left\vert
I\right\vert +1}\left\vert \bigcap\limits_{i\in I}A_{i}\right\vert \\
&=&\left\vert A_{1}\cup A_{2}\cup A_{3}\right\vert \\
&&+\left\vert A_{1}\cap A_{2}\right\vert +\left\vert A_{1}\cap
A_{3}\right\vert +\left\vert A_{2}\cap A_{3}\right\vert \\
&&-\left\vert A_{1}\right\vert -\left\vert A_{2}\right\vert -\left\vert
A_{3}\right\vert
\end{eqnarray*}が成り立ちます。
例（4個の有限集合の共通部分の濃度）
4個の集合\(A_{1},A_{2},A_{3},A_{4}\)がいずれも有限集合であるならば、先の命題より共通部分\(A_{1}\cap A_{2}\cap A_{3}\cap A_{4}\)もまた有限集合であるとともに、\begin{eqnarray*}\left\vert A_{1}\cap A_{2}\cap A_{3}\cap A_{4}\right\vert &=&\left(
-1\right) ^{4+1}\left[ \left\vert A_{1}\cup A_{2}\cup A_{3}\cup
A_{4}\right\vert -\sum_{\phi \not=I\varsubsetneq \left\{ 1,2,3,4\right\}
}\left( -1\right) ^{\left\vert I\right\vert +1}\left\vert
\bigcap\limits_{i\in I}A_{i}\right\vert \right] \\
&=&-\left\vert A_{1}\cup A_{2}\cup A_{3}\cup A_{4}\right\vert +\sum_{\phi
\not=I\varsubsetneq \left\{ 1,2,3,4\right\} }\left( -1\right) ^{\left\vert
I\right\vert +1}\left\vert \bigcap\limits_{i\in I}A_{i}\right\vert \\
&=&-\left\vert A_{1}\cup A_{2}\cup A_{3}\cup A_{4}\right\vert \\
&&+\left\vert A_{1}\cap A_{2}\cap A_{3}\right\vert +\left\vert A_{1}\cap
A_{2}\cap A_{4}\right\vert +\left\vert A_{1}\cap A_{3}\cap A_{4}\right\vert
+\left\vert A_{2}\cap A_{3}\cap A_{4}\right\vert \\
&&-\left\vert A_{1}\cap A_{2}\right\vert -\left\vert A_{1}\cap
A_{3}\right\vert -\left\vert A_{1}\cap A_{4}\right\vert -\left\vert
A_{2}\cap A_{3}\right\vert -\left\vert A_{2}\cap A_{4}\right\vert
-\left\vert A_{3}\cap A_{4}\right\vert \\
&&+\left\vert A_{1}\right\vert +\left\vert A_{2}\right\vert +\left\vert
A_{3}\right\vert +\left\vert A_{4}\right\vert
\end{eqnarray*}が成り立ちます。
-1\right) ^{4+1}\left[ \left\vert A_{1}\cup A_{2}\cup A_{3}\cup
A_{4}\right\vert -\sum_{\phi \not=I\varsubsetneq \left\{ 1,2,3,4\right\}
}\left( -1\right) ^{\left\vert I\right\vert +1}\left\vert
\bigcap\limits_{i\in I}A_{i}\right\vert \right] \\
&=&-\left\vert A_{1}\cup A_{2}\cup A_{3}\cup A_{4}\right\vert +\sum_{\phi
\not=I\varsubsetneq \left\{ 1,2,3,4\right\} }\left( -1\right) ^{\left\vert
I\right\vert +1}\left\vert \bigcap\limits_{i\in I}A_{i}\right\vert \\
&=&-\left\vert A_{1}\cup A_{2}\cup A_{3}\cup A_{4}\right\vert \\
&&+\left\vert A_{1}\cap A_{2}\cap A_{3}\right\vert +\left\vert A_{1}\cap
A_{2}\cap A_{4}\right\vert +\left\vert A_{1}\cap A_{3}\cap A_{4}\right\vert
+\left\vert A_{2}\cap A_{3}\cap A_{4}\right\vert \\
&&-\left\vert A_{1}\cap A_{2}\right\vert -\left\vert A_{1}\cap
A_{3}\right\vert -\left\vert A_{1}\cap A_{4}\right\vert -\left\vert
A_{2}\cap A_{3}\right\vert -\left\vert A_{2}\cap A_{4}\right\vert
-\left\vert A_{3}\cap A_{4}\right\vert \\
&&+\left\vert A_{1}\right\vert +\left\vert A_{2}\right\vert +\left\vert
A_{3}\right\vert +\left\vert A_{4}\right\vert
\end{eqnarray*}が成り立ちます。
演習問題
問題（共通部分の濃度）
有限集合\(A,B\)について、\begin{eqnarray*}\left\vert A\right\vert &=&42 \\
\left\vert B\right\vert &=&31 \\
\left\vert A\cup B\right\vert &=&58
\end{eqnarray*}が成り立つものとします。\begin{equation*}
\left\vert A\cap B\right\vert
\end{equation*}を求めてください。
\left\vert B\right\vert &=&31 \\
\left\vert A\cup B\right\vert &=&58
\end{eqnarray*}が成り立つものとします。\begin{equation*}
\left\vert A\cap B\right\vert
\end{equation*}を求めてください。
問題（互いに素であることの濃度による特徴づけ）
任意の有限集合\(A,B\)について、\begin{equation*}A\cap B=\phi \Leftrightarrow \left\vert A\cap B\right\vert =0
\end{equation*}が成り立つことを証明してください。
\end{equation*}が成り立つことを証明してください。
問題（共通部分の濃度による包含関係の特徴づけ）
任意の集合\(A,B\)について、\(A\)が有限集合である場合には、\begin{equation*}A\subset B\Leftrightarrow \left\vert A\cap B\right\vert =\left\vert
A\right\vert
\end{equation*}が成り立つことを証明してください。
A\right\vert
\end{equation*}が成り立つことを証明してください。
問題（共通部分と集合の相等）
任意の有限集合\(A,B\)について、\begin{equation*}\left\vert A\cap B\right\vert =\left\vert A\right\vert =\left\vert
B\right\vert \Rightarrow A=B
\end{equation*}が成り立つことを証明してください。
B\right\vert \Rightarrow A=B
\end{equation*}が成り立つことを証明してください。
問題（共通部分の濃度が上限に達するための条件）
任意の有限集合\(A,B\)について、\begin{equation*}\left\vert A\cap B\right\vert =\min \left\{ \left\vert A\right\vert
,\left\vert B\right\vert \right\} \Leftrightarrow A\subset B\vee B\subset A
\end{equation*}が成り立つことを証明してください。
,\left\vert B\right\vert \right\} \Leftrightarrow A\subset B\vee B\subset A
\end{equation*}が成り立つことを証明してください。
問題（共通部分として実現できる濃度）
\(m,n\in \mathbb{Z} _{+}\)が与えられたとき、\(k\in \mathbb{Z} _{+}=\left\{ 0,1,2,\cdots \right\} \)が、\begin{equation*}0\leq k\leq \min \left\{ m,n\right\}
\end{equation*}を満たす場合には、それに対して、\begin{eqnarray*}
\left\vert A\right\vert &=&m \\
\left\vert B\right\vert &=&n \\
\left\vert A\cap B\right\vert &=&k
\end{eqnarray*}をすべて満たす有限集合\(A,B\)が存在することを証明してください。
\end{equation*}を満たす場合には、それに対して、\begin{eqnarray*}
\left\vert A\right\vert &=&m \\
\left\vert B\right\vert &=&n \\
\left\vert A\cap B\right\vert &=&k
\end{eqnarray*}をすべて満たす有限集合\(A,B\)が存在することを証明してください。
問題（共通部分の濃度が取り得る範囲）
有限集合\(A,B\)について、\begin{eqnarray*}\left\vert A\right\vert &=&20 \\
\left\vert B\right\vert &=&15
\end{eqnarray*}が成り立つものとします。\(\left\vert A\cap B\right\vert \)が取り得る最小値と最大値を求めてください。また、その間のすべての整数が実現可能であることを示してください。
\left\vert B\right\vert &=&15
\end{eqnarray*}が成り立つものとします。\(\left\vert A\cap B\right\vert \)が取り得る最小値と最大値を求めてください。また、その間のすべての整数が実現可能であることを示してください。
問題（3つの集合の共通部分の濃度）
有限集合\(A,B,C\)について、\begin{eqnarray*}\left\vert A\right\vert &=&70 \\
\left\vert B\right\vert &=&65 \\
\left\vert C\right\vert &=&55 \\
\left\vert A\cap B\right\vert &=&40 \\
\left\vert A\cap C\right\vert &=&30 \\
\left\vert B\cap C\right\vert &=&25 \\
\left\vert A\cup B\cup C\right\vert &=&100
\end{eqnarray*}が成り立つものとします。\begin{equation*}
\left\vert A\cap B\cap C\right\vert
\end{equation*}を求めてください。
\left\vert B\right\vert &=&65 \\
\left\vert C\right\vert &=&55 \\
\left\vert A\cap B\right\vert &=&40 \\
\left\vert A\cap C\right\vert &=&30 \\
\left\vert B\cap C\right\vert &=&25 \\
\left\vert A\cup B\cup C\right\vert &=&100
\end{eqnarray*}が成り立つものとします。\begin{equation*}
\left\vert A\cap B\cap C\right\vert
\end{equation*}を求めてください。
