差集合
2つの集合\(A,B\)に集合演算子\(\backslash \)を作用することで得られる、\begin{equation*}A\backslash B
\end{equation*}もまた集合です。\(\backslash \)は差集合(difference)と呼ばれる集合演算子であり、集合\(A\backslash B\)を\(A\)と\(B\)の差集合(difference of \(A\ \)and \(B\))と呼びます。
差集合を表す集合演算子として\(\backslash \)の代わりに\(-\)を利用する流儀もあります。つまり、2つの集合\(A,B\)の差集合を、\begin{equation*}A-B
\end{equation*}と表現する場合もあるということです。ただし、この記号\(-\)は差集合とは異なる集合演算子を表す記号としても利用されるため(ミンコフスキー差)、どちらの意味で使われているか文脈から判断する必要があります。本稿では差集合を\(\backslash \)で表記します。
全体集合が\(U\)であるものとします。集合\(A,B\)が与えられたとき、それらの差集合\(A\backslash B\)とは、\(U\)の要素の中でも\(A\)の要素である一方で\(B\)の要素ではないものからなる集合\begin{equation*}A\backslash B=\left\{ x\in U\ |\ x\in A\wedge x\not\in B\right\}
\end{equation*}として定義されます。定義より、以下の関係\begin{equation*}
\forall x\in U:\left[ x\in A\backslash B\Leftrightarrow \left( x\in A\wedge
x\not\in B\right) \right]
\end{equation*}が成り立ちます。つまり、\(x\)が差集合\(A\backslash B\)の要素であることと、\(x\)が\(A\)の要素である一方で\(B\)の要素ではないことは必要十分です。このとき、\begin{equation*}\forall x\in U:\left[ x\not\in A\backslash B\Leftrightarrow \left( x\not\in
A\vee x\in B\right) \right]
\end{equation*}もまた成り立ちます。つまり、\(x\)が差集合\(A\backslash B\)の要素ではないことは、\(x\)が\(A\)の要素ではないか、\(x\)が\(B\)の要素であるか、その少なくとも一方が成り立つことと必要十分です。
A &=&\left\{ 1,2,3\right\} \\
B &=&\left\{ 2,3,4\right\}
\end{eqnarray*}の差集合は、\(A\)の要素である一方で\(B\)の要素ではないものからなる集合であるため、\begin{equation*}A\backslash B=\left\{ 1\right\}
\end{equation*}となります。
A &=&\left\{ 1,2,3,a\right\} \\
B &=&\left\{ 3,a,b,c\right\}
\end{eqnarray*}の差集合は、\(A\)の要素である一方で\(B\)の要素ではないものからなる集合であるため、\begin{equation*}A\backslash B=\left\{ 1,2\right\}
\end{equation*}となります。
A &=&\left\{ 1,2,3\right\} \\
B &=&\left\{ 1,2,3,4,5,6\right\}
\end{eqnarray*}の差集合は、\(A\)の要素である一方で\(B\)の要素ではないものからなる集合ですが、そのような要素は存在しないため、\begin{equation*}A\backslash B=\phi
\end{equation*}となります。
A &=&\left[ 0,2\right] \\
B &=&\left[ 1,3\right] \end{eqnarray*}に注目します。つまり、\(A\)は\(0\)以上\(2\)以下のすべての実数からなる集合であり、\(B\)は\(1\)以上\(3\)以下のすべての実数からなる集合です。これらの集合の差集合は、\begin{equation*}A\backslash B=\left[ 0,1\right)
\end{equation*}です。つまり、\(A\backslash B\)は\(0\)以上かつ\(1\)より小さいすべての実数からなる集合です。\(1\)は\(A\)の要素ですが\(B\)の要素でもあるため\(A\backslash B\)の要素ではありません。
A &=&\left[ 0,2\right] \\
B &=&\left( 1,3\right] \end{eqnarray*}に注目します。つまり、\(A\)は\(0\)以上\(2\)以下のすべての実数からなる集合であり、\(B\)は\(1\)より大きく\(3\)以下であるようなすべての実数からなる集合です。これらの集合の差集合は、\begin{equation*}A\backslash B=\left[ 0,1\right] \end{equation*}です。つまり、\(A\backslash B\)は\(0\)以上\(1\)以下のすべての実数からなる集合です。\(1\)は\(A\)の要素ですが\(B\)の要素ではないため\(A\backslash B\)の要素です。
\end{equation*}となります。ちなみに、茨城、千葉、東京、神奈川は関東地方にありますが海に面しているため\(A\)と\(B\)双方の要素であるため\(A\backslash B\)の要素ではありません。
差集合をとる順番
全体集合が\(U\)であるものとします。2つの集合\(A,B\)が与えられたとき、差集合は、\begin{equation*}A\backslash B=\left\{ x\in U\ |\ x\in A\wedge x\not\in B\right\}
\end{equation*}と定義されますが、\(A\)と\(B\)の立場を変えることにより、以下の形の差集合\begin{equation*}B\backslash A=\left\{ x\in U\ |\ x\in B\wedge x\not\in A\right\}
\end{equation*}も定義可能です。これらは区別する必要があります。つまり、\(A\backslash B\)は\(A\)の要素である一方で\(B\)の要素ではない要素からなる集合であり、\(B\backslash A\)は\(B\)の要素である一方で\(A\)の要素ではない要素からなる集合です。
A &=&\left\{ 1,2,3\right\} \\
B &=&\left\{ 2,3,4\right\}
\end{eqnarray*}が与えられたとき、差集合の定義より、\begin{eqnarray*}
A\backslash B &=&\left\{ 1\right\} \\
B\backslash A &=&\left\{ 4\right\}
\end{eqnarray*}となるため、\begin{equation*}
A\backslash B\not=B\backslash A
\end{equation*}を得ます。
上の例から明らかなったように、集合\(A,B\)が与えられたとき、\(A\backslash B\)と\(B\backslash A\)は一致するとは限りません。では、\(A\backslash B\)と\(B\backslash A\)が一致する事態は起こり得るのでしょうか。実は、\(A\)と\(B\)が一致する場合、そしてその場合にのみ\(A\backslash B\)と\(B\backslash A\)は一致します。
\end{equation*}が成り立つ。
差集合の内包的表現
全体集合が\(U\)である状況を想定します。集合\(A\)は以下の条件\begin{equation*}\forall x\in U:\left[ x\in A\Leftrightarrow P\left( x\right) \right]
\end{equation*}を満たす命題関数\(P\left(x\right) \)の真理集合として表現可能です。つまり、全体集合\(U\)に属する要素の中でも命題\(P\left( x\right) \)が真になるような要素\(x\)からなる集合が\(A\)であり、\begin{equation*}A=\left\{ x\in U\ |\ P\left( x\right) \right\}
\end{equation*}と表現できるということです。
2つの集合\(A,B\)がそれぞれ命題関数\(P\left( x\right) ,Q\left( x\right) \)を用いて内包的に定義されている場合、それらの差集合\(A\backslash B\)はどのような命題関数を用いて内包的に表現されるでしょうか。集合\(A,B\)がそれぞれ、\begin{eqnarray}A &=&\left\{ x\in U\ |\ P\left( x\right) \right\} \quad \cdots (1) \\
B &=&\left\{ x\in U\ |\ Q\left( x\right) \right\} \quad \cdots (2)
\end{eqnarray}と定義されているものとします。差集合の定義より、任意の\(x\in U\)について、\begin{equation}x\in A\backslash B\Leftrightarrow x\in A\wedge x\not\in B \quad \cdots (3)
\end{equation}が成り立ちます。以上を踏まえると、任意の\(x\in U\)について、\begin{eqnarray*}x\in A\backslash B &\Leftrightarrow &x\in A\wedge x\not\in B\quad \because
\left( 3\right) \\
&\Leftrightarrow &P\left( x\right) \wedge \lnot Q\left( x\right) \quad
\because \left( 1\right) ,\left( 2\right)
\end{eqnarray*}となるため、以下の命題\begin{equation*}
\forall x\in U:\left[ x\in A\backslash B\Leftrightarrow P\left( x\right)
\wedge \lnot Q\left( x\right) \right]
\end{equation*}が成り立つことが明らかになりました。したがって、差集合\(A\backslash B\)は命題関数\(P\left( x\right)\wedge \lnot Q\left( x\right) \)の真理集合として表現されるため、\begin{equation*}A\backslash B=\left\{ x\in U\ |\ P\left( x\right) \wedge \lnot Q\left(
x\right) \right\}
\end{equation*}となります。全体集合\(U\)に属する要素の中でも命題\(P\left( x\right) \wedge \lnot Q\left(x\right) \)が真、すなわち命題\(P\left( x\right) \)が真である一方で命題\(Q\left( x\right) \)が偽になるような要素\(x\)からなる集合が\(A\backslash B\)です。差集合\(\backslash \)という集合演算は否定\(\lnot \)と論理積\(\wedge \)から間接的に定義可能であるということです。
B &=&\left\{ x\in U\ |\ Q\left( x\right) \right\}
\end{eqnarray*}とそれぞれ表現されている場合、差集合\(A\backslash B\)は、\begin{equation*}A\backslash B=\left\{ x\in U\ |\ P\left( x\right) \wedge \lnot Q\left(
x\right) \right\}
\end{equation*}と定まる。
つまり、集合\(A,B\)が命題関数\(P\left( x\right) ,Q\left( x\right) \)を用いてそれぞれ表現されている場合、命題関数\(P\left( x\right) \wedge \lnot Q\left( x\right) \)を特定すれば、差集合\(A\backslash B\)を特定できるということです。
上の命題の主張を視覚的に表現したものが以下の図です。
全体集合\(U\)が上の長方形の領域として描かれているものとします。集合\(A\)が命題関数\(P\left( x\right) \)から内包的に定義されているとき、\(A\)は命題\(P\left( x\right) \)が真になるような値\(x\in U\)からなる集合、すなわち\(P\left(x\right) \)の真理集合\(\phi \left( P\right) \)と一致します。同様に、集合\(B\)が命題関数\(Q\left( x\right) \)から内包的に定義されているとき、\(B\)は\(Q\left( x\right) \)の真理集合\(\phi\left( Q\right) \)と一致します。一方、差集合\(A\backslash B\)は命題関数\(P\left( x\right) \wedge \lnot Q\left(x\right) \)の真理集合\(\phi \left( P\wedge \lnot Q\right) \)と一致し、これは上図においてグレーの領域として描かれています。
B& =\left\{ x\in \mathbb{Z} \ |\ x\text{は}3\text{の倍数}\right\}
\end{align*}と内包的に定義されているものとします。差集合は、\begin{eqnarray*}
A\backslash B &=&\left\{ x\in \mathbb{Z} \ |\ 1<x<10\wedge x\text{は}3\text{の倍数ではない}\right\} \\
&=&\left\{ 2,4,5,7,8\right\}
\end{eqnarray*}となります。
B& =\left\{ x\in \mathbb{R} \ |\ 4\leq x\leq 15\right\}
\end{align*}と内包的に定義されてるとき、任意の\(x\in \mathbb{R} \)に対して、\begin{eqnarray*}x\in A\backslash B &\Leftrightarrow &x\in A\wedge x\not\in B\quad \because
\text{差集合の定義} \\
&\Leftrightarrow &1<x<10\wedge \lnot \left( 4\leq x\leq 15\right) \quad
\because A,B\text{の定義} \\
&\Leftrightarrow &1<x<10\wedge \lnot \left( 4\leq x\wedge x\leq 15\right) \\
&\Leftrightarrow &1<x<10\wedge \left[ \lnot \left( 4\leq x\right) \vee \lnot
\left( x\leq 15\right) \right] \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &1<x<10\wedge \left( 4>x\vee x>15\right) \\
&\Leftrightarrow &\left( 1<x<10\wedge 4>x\right) \vee \left( 1<x<10\wedge
x>15\right) \quad \because \text{分配律} \\
&\Leftrightarrow &1<x<4\vee \bot \quad \because \bot \text{は恒偽式} \\
&\Leftrightarrow &1<x<4\quad \because \text{恒等律}
\end{eqnarray*}となるため、\begin{equation*}
A\backslash B=\left\{ x\in \mathbb{R} \ |\ 1<x<4\right\}
\end{equation*}となります。他方で、任意の\(x\in \mathbb{R} \)に対して、\begin{eqnarray*}x\in B\backslash A &\Leftrightarrow &x\in B\wedge x\not\in A\quad \because
\text{差集合の定義} \\
&\Leftrightarrow &4\leq x\leq 15\wedge \lnot \left( 1<x<10\right) \quad
\because A,B\text{の定義} \\
&\Leftrightarrow &4\leq x\leq 15\wedge \lnot \left( 1<x\wedge x<10\right) \\
&\Leftrightarrow &4\leq x\leq 15\wedge \left[ \lnot \left( 1<x\right) \vee
\lnot \left( x<10\right) \right] \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &4\leq x\leq 15\wedge \left( 1\geq x\vee x\geq 10\right) \\
&\Leftrightarrow &\left( 4\leq x\leq 15\wedge 1\geq x\right) \vee \left(
4\leq x\leq 15\wedge x\geq 10\right) \quad \because \text{分配律} \\
&\Leftrightarrow &\bot \vee 10\leq x\leq 15\quad \because \bot \text{は恒偽式} \\
&\Leftrightarrow &10\leq x\leq 15\quad \because \text{恒等律}
\end{eqnarray*}となるため、\begin{equation*}
B\backslash A=\left\{ x\in \mathbb{R} \ |\ 10\leq x\leq 15\right\}
\end{equation*}となります。
空集合や全体集合との差集合
全体集合\(U\)は恒真式\(\top \)を用いて内包的に表現され、空集合\(\phi \)は恒偽式\(\bot \)を用いて内包的に表現されます。つまり、\begin{eqnarray*}U &=&\left\{ x\in U\ |\ \top \right\} \\
\phi &=&\left\{ x\in U\ |\ \bot \right\}
\end{eqnarray*}です。以上の事実を用いると、全体集合や空集合との差集合に関する以下の命題が導かれます。
&&\left( b\right) \ \phi \backslash A=\phi \\
&&\left( c\right) \ A\backslash U=\phi \\
&&\left( d\right) \ U\backslash A=A^{c}
\end{eqnarray*}が成り立つ。
補集合と共通部分を用いた差集合の定義
全体集合が\(U\)であるものとします。集合\(A,B\)が任意に与えられたとき、以下の関係\begin{equation*}A\backslash B=A\cap B^{c}
\end{equation*}が成り立つことが保証されます。つまり、\(A\)と\(B\)の差集合は、\(A\)と\(B\)の補集合の共通部分と一致します。
\end{equation*}が成り立つ。
上の命題は、差集合\(\backslash \)という概念が補集合\(c\)と共通部分\(\cap \)という集合演算から間接的に定義可能であることを示唆します。つまり、\(c\)と\(\cap \)が与えられたとき、任意の集合\(A,B\)に対して、\begin{equation*}A\backslash B=A\cap B^{c}
\end{equation*}を満たすものとして差集合\(\backslash \)を定義できるということです。したがって、補集合と共通部分さえ定義されていれば差集合を新たな集合演算として定義する必要はありません。とは言え、差集合を独立した集合演算として定義しておくと便利であるため引き続き差集合を利用します。
差集合を用いた包含関係の定義
全体集合を\(U\)とします。集合\(A,B\)を任意に選んだとき、以下の関係\begin{equation*}A\subset B\Leftrightarrow A\backslash B=\phi
\end{equation*}が成り立つことが保証されます。つまり、\(A\)が\(B\)の部分集合であることと、\(A\)と\(B\)の差集合が空集合であることは必要十分です。
\end{equation*}という関係が成り立つ。
上の命題は、包含関係\(\subset \)という概念が差集合\(\backslash \)という集合演算から間接的に定義可能であることを示唆します。つまり、\(\backslash \)が与えられたとき、任意の集合\(A,B\)に対して、\begin{equation*}A\subset B\Leftrightarrow A\backslash B=\phi
\end{equation*}を満たすものとして\(\subset \)を定義できるということです。
B &=&\left\{ x\in U\ |\ x\text{は低学年}\right\}
\end{eqnarray*}とおくと、\(A\subset B\)が成り立ちます。このとき、\begin{equation*}A\backslash B=\left\{ x\in U\ |\ x\text{は1年生だが低学年ではない}\right\}
\end{equation*}となりますが、明らかに\(A\backslash B=\phi \)です。この結果は上の命題と整合的です。
演習問題
B &=&\left\{ d,e,f\right\} \\
C &=&\left\{ 1,2,3\right\}
\end{eqnarray*}で与えられているとき、以下のそれぞれの集合を外延的に表記してください。
- \(A\backslash B\)
- \(B\backslash A\)
- \(\left( A\backslash B\right) \cup \left( B\backslash A\right) \)
- \(A\backslash C\)
- \(\left( A\cap C\right) \cup \left( A\backslash C\right) \)
\end{equation*}という関係が成り立つことを証明してください。
\end{equation*}が成り立つことを証明してください。
\\
&&\left( b\right) \ A\cup B=\left( A\backslash B\right) \cup B \\
&&\left( c\right) \ B\cap \left( A\backslash B\right) =\phi
\end{eqnarray*}が成り立つことをそれぞれ証明してください。
\\
\left( b\right) \ A &\subset &B\Rightarrow C\backslash B\subset C\backslash A
\end{eqnarray*}が成り立つことをそれぞれ証明してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】