差集合(set difference)とは、集合 $A$ の元のうち集合 $B$ に属さないもの全体からなる集合 $A\setminus B$ である。全体集合の中では $A\setminus B=A\cap B^c$ と書け、補集合は差集合の特別な場合である。差集合は交換法則も結合法則も満たさず、逆像はこれを保つが、像がこれを保つのは写像が単射のときに限る。重なりのある集合の列を、和集合を変えずに互いに素な列 $A_n\setminus(A_1\cup\cdots\cup A_{n-1})$ に取り替える操作は、確率や測度の計算の基本である。
差集合は第一の集合に属し、第二の集合には属さない元を残す操作である。順序に依存するため、和集合や共通部分と異なり一般には交換法則を満たさない。
集合 $A,B$ の差集合(set difference)とは、$A$ に属するが $B$ には属さない元全体の集合
$$
A\setminus B:=\{x\mid x\in A\text{ かつ }x\notin B\}
$$
である。$A-B$ とも書くが、数の減法との混同を避けるため $A\setminus B$ を用いる。全体集合 $U$ を固定すれば $A\setminus B=A\cap B^c$ である。
$A=\{1,2,3\}$、$B=\{2,3,4\}$ なら
$$
A\setminus B=\{1\},\qquad B\setminus A=\{4\}
$$
である。また $A\setminus A=\emptyset$、$A\setminus\emptyset=A$ である。差集合は第一の集合から元を取り除く操作なので、二つの引数の役割は対称でない。
実数の区間 $A=[0,3]$、$B=(1,2]$ に対して
$$
A\setminus B=[0,1]\cup(2,3]
$$
である。端点 $1$ は $B$ に属さないので残り、端点 $2$ は $B$ に属するので取り除かれる。区間の差を求めるときは、図の見た目だけでなく各端点の所属を個別に確認する必要がある。
$A=\{1,2\}$、$B=\{2,3\}$ に対して $A\setminus B=\{1\}$ である。元 $1,2$ から数として $2,3$ を引く操作ではない。また、$A\setminus B$ の濃度について $|A\setminus B|=|A|-|B|$ は一般に成り立たない。この例では左辺は $1$、右辺は $0$ である。有限集合について正しい式は
$$
|A\setminus B|=|A|-|A\cap B|
$$
である。
次の三つは同値である。
(1 ⇒ 2)$A\cap B\subseteq A$ は定義から明らかである。$x\in A$ とすると、$A\subseteq B$ より $x\in B$ でもあるので $x\in A\cap B$ である。よって $A\subseteq A\cap B$ であり、$A\cap B=A$ を得る。
(2 ⇒ 1)$x\in A$ とすると $x\in A\cap B$ なので $x\in B$ である。よって $A\subseteq B$ である。
(1 ⇒ 3)$B\subseteq A\cup B$ は定義から明らかである。$x\in A\cup B$ とすると、$x\in A$ の場合は $A\subseteq B$ より $x\in B$、$x\in B$ の場合はそのまま $x\in B$ である。よって $A\cup B\subseteq B$ であり、$A\cup B=B$ を得る。
(3 ⇒ 1)$x\in A$ とすると $x\in A\cup B=B$ である。よって $A\subseteq B$ である。$\square$
任意の集合 $A,B,C$ について
$$
(A\setminus B)\setminus C=A\setminus(B\cup C),\qquad
A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C)
$$
が成り立つ。
任意の $x$ について、
$$
x\in(A\setminus B)\setminus C
\Longleftrightarrow x\in A, x\notin B, x\notin C
\Longleftrightarrow x\in A\setminus(B\cup C)
$$
である。また
$$
x\in A\setminus(B\cap C)
\Longleftrightarrow x\in A, (x\notin B\text{ または }x\notin C)
\Longleftrightarrow x\in(A\setminus B)\cup(A\setminus C)
$$
である。外延性により二つの等式を得る。$\square$
同じ方法で、次の公式も得られる。
$$
A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C),
$$
$$
(A\cup B)\setminus C=(A\setminus C)\cup(B\setminus C),
$$
$$
(A\cap B)\setminus C=(A\setminus C)\cap(B\setminus C).
$$
第1式と、命題で証明した $A\setminus(B\cap C)$ の式は、補集合に関するDe Morganの法則の相対版である。
$A\subseteq A'$ かつ $B'\subseteq B$ なら
$$
A\setminus B\subseteq A'\setminus B'
$$
である。従って差集合は第1引数について単調、第2引数について反単調である。
$x\in A\setminus B$ とする。すると $x\in A$ かつ $x\notin B$ である。$A\subseteq A'$ から $x\in A'$ を得る。また $B'\subseteq B$ なので、もし $x\in B'$ なら $x\in B$ となって矛盾する。従って $x\notin B'$ であり、$x\in A'\setminus B'$ である。
任意の集合 $A,B$ に対して
$$
A=(A\cap B)\cup(A\setminus B),
\qquad
(A\cap B)\cap(A\setminus B)=\emptyset
$$
が成り立つ。すなわち $A$ は「$B$ に属する部分」と「$B$ に属さない部分」に重なりなく分かれる。
$x\in A$ とする。排中律により $x\in B$ または $x\notin B$ である。前者なら $x\in A\cap B$、後者なら $x\in A\setminus B$ なので、$A\subseteq(A\cap B)\cup(A\setminus B)$ である。逆の包含は各項が $A$ の部分集合であることから従う。
さらに $x$ が二つの部分に同時に属すると、$x\in B$ と $x\notin B$ が同時に成り立って矛盾する。従って共通部分は空集合である。
有限集合の場合、この分解の二つの部分は互いに素なので
$$
|A|=|A\cap B|+|A\setminus B|
$$
を得る。確率空間で事象 $A$ を $B$ が起きる場合と起きない場合に分ける操作も、同じ分解である。
全体集合 $U$ を固定したときの補集合 $A^c=U\setminus A$ は、差集合の特別な場合である。差集合は全体集合を指定しなくても定義できるが、補集合はどの集合の中で補うかに依存する。逆に、$A,B\subset U$ なら $A\setminus B=A\cap B^c$ なので、差集合は補集合と共通部分で書ける。補集合の基本法則と De Morgan の法則は補集合の記事が扱う。
二つの差集合の和 $(A\setminus B)\cup(B\setminus A)$ を $A$ と $B$ の対称差といい、$A\mathbin{\triangle}B$ と書く。これは $A,B$ のちょうど一方に属する元の集合である。対称差の演算法則(結合律、$A\mathbin{\triangle}A=\emptyset$ など)は対称差の記事が扱う。ここでは差集合による別の表し方だけを示す。
$$
(A\setminus B)\cup(B\setminus A)
=(A\cup B)\setminus(A\cap B)
$$
が成り立つ。特にこの集合は $A$ と $B$ を入れ替えても変わらない。
任意の $x$ について、左辺に属することは
$$
(x\in A\text{ かつ }x\notin B)
\text{ または }
(x\in B\text{ かつ }x\notin A)
$$
と同値である。これは $x$ が $A\cup B$ に属するが、$A\cap B$ には属さないことと同値なので、外延性により等式を得る。$\square$
差集合を二回とったり、和集合と組み合わせたりすると、元に戻る場合と戻らない場合がある。
任意の集合 $A,B$ について次が成り立つ。
1 について。$x\in A\setminus(A\setminus B)$ は「$x\in A$ かつ、($x\notin A$ または $x\in B$)」と同値である。$x\in A$ のもとで $x\notin A$ は成り立たないので、これは「$x\in A$ かつ $x\in B$」と同値である。
2 について。$x\in(A\setminus B)\cup B$ は「($x\in A$ かつ $x\notin B$) または $x\in B$」と同値である。$x\in B$ の場合と $x\notin B$ の場合に分けると、前者ではつねに成り立ち、後者では $x\in A$ と同値になる。したがって「$x\in B$ または $x\in A$」と同値であり、等式を得る。後半は、$A\cup B=A$ と $B\subseteq A$ が同値であること(prop-set-difference-inclusion-operations の 1 と 3 で $A,B$ の役割を入れ替えたもの)による。
3 について。$A\cap B=\emptyset$ なら、$x\in A$ は $x\notin B$ を導くので $A\subseteq A\setminus B$、逆の包含は定義から明らかである。逆に $A\setminus B=A$ なら、$x\in A\cap B$ は $x\in A=A\setminus B$ から $x\notin B$ となって矛盾するので、$A\cap B=\emptyset$ である。$\square$
2 の後半は、「取り除いてから加え直すと元に戻る」という直観が、取り除く集合が元の集合に含まれるときにしか正しくないことを示す。例えば $A=\{1\}$、$B=\{2\}$ なら $(A\setminus B)\cup B=\{1,2\}\ne A$ である。
写像 $f\colon X\to Y$ の逆像は差集合を正確に保存する。すなわち任意の $C,D\subseteq Y$ について $f^{-1}(C\setminus D)=f^{-1}(C)\setminus f^{-1}(D)$ である。これは逆像の記事の命題「逆像と集合の演算」の 4 である。像については包含が一方向にしか成り立たない。
写像 $f\colon X\to Y$ について次が成り立つ。
1 について。$y\in f(A)\setminus f(B)$ とすると、ある $a\in A$ で $y=f(a)$ であり、$y\notin f(B)$ である。もし $a\in B$ なら $y=f(a)\in f(B)$ となり矛盾するので $a\notin B$、すなわち $a\in A\setminus B$ であり、$y\in f(A\setminus B)$ である。
2 について。$f$ が単射とし、$y\in f(A\setminus B)$ とする。ある $a\in A\setminus B$ で $y=f(a)$ だから $y\in f(A)$ である。もし $y\in f(B)$ なら、ある $b\in B$ で $f(b)=y=f(a)$ となり、単射性から $a=b\in B$ となって矛盾する。よって $y\in f(A)\setminus f(B)$ であり、1 と合わせて等式を得る。逆に、等式がすべての $A,B$ で成り立つとし、$f(x)=f(x')$ とする。$A=\{x\}$、$B=\{x'\}$ とおくと $f(A)\setminus f(B)=\emptyset$ なので $f(\{x\}\setminus\{x'\})=\emptyset$、すなわち $\{x\}\setminus\{x'\}=\emptyset$ であり、$x=x'$ である。$\square$
等式が成り立たない例として、定値写像 $f\colon\{1,2\}\to\{0\}$ と $A=\{1,2\}$、$B=\{2\}$ を考えると、左辺 $f(A\setminus B)$ は $\{0\}$、右辺は空集合である。等式が成り立たない原因は、取り除いた $2$ と残した $1$ が同じ値へ写ることである。
差集合を使うと、重なりのある集合の列を、和集合を変えずに互いに素な列へ取り替えられる。確率や測度で「重なった事象の和の確率」を「重ならない事象の確率の和」に直すときの基本的な手法である。
集合の列 $A_1,A_2,\ldots$ に対し
$$
B_1:=A_1,\qquad B_n:=A_n\setminus(A_1\cup\cdots\cup A_{n-1})\quad(n\ge2)
$$
とおく。このとき $B_n\subseteq A_n$、$m\ne n$ なら $B_m\cap B_n=\emptyset$ であり、各 $N$ について $\bigcup_{n=1}^{N}B_n=\bigcup_{n=1}^{N}A_n$、さらに $\bigcup_{n\ge1}B_n=\bigcup_{n\ge1}A_n$ である。
$B_n\subseteq A_n$ は定義から明らかである。$m< n$ とし $x\in B_m$ とすると $x\in A_m$ であり、$A_m$ は $B_n$ の定義で取り除く集合 $A_1\cup\cdots\cup A_{n-1}$ に含まれるので $x\notin B_n$ である。よって $B_m\cap B_n=\emptyset$ である。
和集合について、$B_n\subseteq A_n$ から $\bigcup_{n\le N}B_n\subseteq\bigcup_{n\le N}A_n$ である。逆に $x\in\bigcup_{n\le N}A_n$ とし、$x\in A_n$ となる最小の $n$($\le N$)をとる。最小性から $x\notin A_1\cup\cdots\cup A_{n-1}$ なので $x\in B_n$ である。無限個の和集合についても、$x\in A_n$ となる最小の $n$ を同じようにとればよい。$\square$
$A_n=[0,n]$($n\ge1$)なら $B_1=[0,1]$、$B_n=(n-1,n]$($n\ge2$)であり、$[0,\infty)$ が互いに素な区間に分かれる。$A_n=[0,1/n]$ のように列が減少する場合は $B_1=[0,1]$、$B_n=\emptyset$($n\ge2$)となり、分解の各部分は空になりうる。
有限集合の元の個数や測度 $\mu$ について、$B\subseteq A$ なら prop-set-difference-disjoint-decomposition により $A=B\cup(A\setminus B)$ が互いに素な和なので、$\mu(A)=\mu(B)+\mu(A\setminus B)$ である。$\mu(B)$ が有限なら両辺から引いて $\mu(A\setminus B)=\mu(A)-\mu(B)$ を得る。$\mu(B)=\infty$ のときはこの引き算ができない。例えば実数直線の長さ(Lebesgue測度)で $A=\mathbb R$、$B=[0,\infty)$ とすると $\mu(A\setminus B)=\mu((-\infty,0))=\infty$ だが、右辺は $\infty-\infty$ となって意味をもたない。$A=B=\mathbb R$ なら $\mu(A\setminus B)=0$ で、右辺はやはり意味をもたない。
$A=\{1,2\}$、$B=\{2,3\}$ なら $A\setminus B=\{1\}$ だが $B\setminus A=\{3\}$ である。したがって $A\setminus B=B\setminus A$ は一般には成り立たない。成り立たないのは演算の交換法則である。$A\setminus B=B\setminus A$ が成り立つのは $A=B$ のときに限る。実際、$A\setminus B$ の元は $B$ に属さず、$B\setminus A$ は $B$ に含まれるので、二つは交わらない。等しいならその集合は自分自身と交わらないので空集合であり、$A\setminus B=\emptyset$ から $A\subseteq B$、$B\setminus A=\emptyset$ から $B\subseteq A$ を得る。
$A=\{1\}$、$B=\emptyset$、$C=\{1\}$ とすると
$$
(A\setminus B)\setminus C=\emptyset,
\qquad
A\setminus(B\setminus C)=\{1\}
$$
である。従って括弧を省略して $A\setminus B\setminus C$ と書くと曖昧になる。左から順に差を取る意味なら、必ず $(A\setminus B)\setminus C$ と解釈することを明示する。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $A=B$ | $\{1,2\}$ と $\{2,3\}$ | $A\setminus B=B\setminus A$ |
| 括弧の位置 | $A=C=\{1\}$、$B=\emptyset$ | $(A\setminus B)\setminus C=A\setminus(B\setminus C)$ |
| $B\subseteq A$ | $A=\{1\}$、$B=\{2\}$ | $(A\setminus B)\cup B=A$ |
| $f$ が単射 | 定値写像 $\{1,2\}\to\{0\}$ | $f(A\setminus B)=f(A)\setminus f(B)$ |
| $B\subseteq A$ | $A=\{1,2\}$、$B=\{2,3\}$ | $\lvert A\setminus B\rvert=\lvert A\rvert-\lvert B\rvert$ |
| $\mu(B)< \infty$ | $A=\mathbb R$、$B=[0,\infty)$ | $\mu(A\setminus B)=\mu(A)-\mu(B)$ |
5 行目は rem-set-difference-not-subtraction で確かめた。$B\subseteq A$ なら $A\cap B=B$ なので、正しい公式 $\lvert A\setminus B\rvert=\lvert A\rvert-\lvert A\cap B\rvert$ は $\lvert A\rvert-\lvert B\rvert$ になる。
差集合の定義は Ham Definition 1.5(§1.5, p. 18)による。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する