差集合

同義語：set difference

概要

差集合（set difference）とは、集合 $A$ の元のうち集合 $B$ に属さないもの全体からなる集合 $A\setminus B$ である。
差集合は第一の集合に属し、第二の集合には属さない元を残す操作である。順序に依存するため、和集合や共通部分と異なり一般には交換法則を満たさない。

定義

差集合

集合 $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| $$
である。

性質と証明

包含と演算の言い換え

次の三つは同値である。

$A\subseteq B$。
$A\cap B=A$。
$A\cup B=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$ の対称差（symmetric difference）を
$$ A\mathbin{\triangle}B :=(A\setminus B)\cup(B\setminus A) $$
と定める。これは $A,B$ のちょうど一方に属する元の集合である。

対称差の別表示

$$ A\mathbin{\triangle}B =(A\cup B)\setminus(A\cap B) $$
が成り立つ。特に $A\mathbin{\triangle}B=B\mathbin{\triangle}A$ であり、通常の差集合とは異なり対称である。

対称差の別表示の証明

任意の $x$ について、左辺に属することは
$$ (x\in A\text{ かつ }x\notin B) \text{ または } (x\in B\text{ かつ }x\notin A) $$
と同値である。これは $x$ が $A\cup B$ に属するが、$A\cap B$ には属さないことと同値なので、外延性により等式を得る。

写像との関係

写像 $f\colon X\to Y$ の逆像は差集合を正確に保存する。

逆像は差集合を保存する

任意の $C,D\subseteq Y$ に対して
$$ f^{-1}(C\setminus D)=f^{-1}(C)\setminus f^{-1}(D) $$
が成り立つ。

逆像が差集合を保存することの証明

任意の $x\in X$ について
$$ \begin{aligned} x\in f^{-1}(C\setminus D) &\Longleftrightarrow f(x)\in C\text{ かつ }f(x)\notin D\\ &\Longleftrightarrow x\in f^{-1}(C)\text{ かつ }x\notin f^{-1}(D)\\ &\Longleftrightarrow x\in f^{-1}(C)\setminus f^{-1}(D) \end{aligned} $$
である。

像については一般に $f(A\setminus B)=f(A)\setminus f(B)$ は成り立たない。たとえば定値写像 $f\colon\{1,2\}\to\{0\}$ と $A=\{1,2\}$、$B=\{2\}$ を考えると、左辺は $\{0\}$、右辺は空集合である。失敗の原因は、取り除いた $2$ と残した $1$ が同じ値へ写ることである。$f$ が単射なら、この等式はすべての $A,B$ について成り立つ。

反例：差集合は交換的でない

$A=\{1,2\}$、$B=\{2,3\}$ なら $A\setminus B=\{1\}$ だが $B\setminus A=\{3\}$ である。したがって $A\setminus B=B\setminus 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$ と解釈することを明示する。

定義と集合演算の法則については Hara20（第1章 §1.3）、Matsusaka68（第1章 §2, pp. 12--21）を参照した。