対称差 - Wikipedia日本語版アーカイブ | wikipedia-is-dead.com

数学において、2 つの集合 $A$ と $B$ との対称差（たいしょうさ、英: symmetric difference^[1]）とは、“ $A$ に属し、 $B$ に属さないもの” と “ $B$ に属し、 $A$ に属さないもの” とを全て集めて得られる集合である^[2]。一般に、集合 $A$ と $B$ との対称差を、記号

$A △ B$ ^[2] あるいは $A ⊖ B$ あるいは $A \oplus B$

などで表す。例えば、 ${1, 2, 3}$ と ${3, 4}$ との対称差は ${1, 2, 4}$ に等しい： ${1, 2, 3}△{3, 4} = {1, 2, 4}$ 。

任意の集合に対して、その集合の冪集合は、対称差 $△$ を算法としてアーベル群となる^[3]。空集合 $\emptyset$ はその群の単位元であり、その群の任意の元はその元自身の逆元である。また、任意の集合に対して、その集合の冪集合は、対称差 $△$ を加法とし共通部分 $\cap$ を乗法とするとき、ブール環となる^[4]。

性質

対称差は、和集合と差集合の記号を用いて次のように表すことができる^[2]：

$A △ B = (A - B)\cup(B - A)$ 。

$X$ を 1 つの集合とし、 $A, B$ を $X$ の 2 つの部分集合とする。集合 ${0, 1}$ における二項演算として排他的論理和 $\oplus : {0, 1} \times {0, 1}$ → ${0, 1}$ を定義すれば、 $X$ における指示関数に関して次が成り立つ： $X$ の任意の元 $x$ に対して

$χ A △ B (x) = χ A (x) \oplus χ B (x)$ 。

アイバーソンの記法を用いれば次のようにも書ける：

$[x \in A △ B] = [x \in A] \oplus [x \in B]$ 。

対称差はまた、和集合、差集合、共通部分の記号を用いて次のように表すことができる^[2]：

$A △ B = (A \cup B) - (A \cap B)$ 。

特に、 $A △ B$ は $A \cup B$ の部分集合である： $A △ B \subset A \cup B$ 。また、 $A$ と $B$ とが互いに素であるときかつそのときに限り $A △ B = A \cup B$ である。さらには、 $A △ B$ と $A \cap B$ とは互いに素であって、集合 ${A △ B, A \cap B}$ は $A \cup B$ の 1 つの分割である。従って、対称差と共通部分とを最初に定義しておき、それらの記号を用いて、式

$A \cup B = (A △ B)△(A \cap B)$

によって和集合を定義することもできる。

代数学的な性質

対称差について、次の 4 つが成り立つ^[2]：

$(A △ B)△ C = A △(B △ C)$ （結合法則）、
$A △\emptyset = \emptyset△ A = A$ 、
$A △ A = \emptyset$ 、
$A △ B = B △ A$ （交換法則）。

$X$ を 1 つの集合とし、 $P(X)$ を $X$ の冪集合とする。 $P(X) \times P(X)$ の元 $(A, B)$ に $P(X)$ の元 $A △ B$ を対応させれば、 $P(X)$ における 1 つの二項算法が得られる。上の 4 つの性質から、その算法に関して $P(X)$ はアーベル群となる。空集合 $\emptyset$ はその群の単位元である。 $P(X)$ の任意の元 $A$ に対して $A$ は $A$ の逆元であるから、 $P(X)$ はブール群でもある。 $X$ がちょうど 2 個の元から成る集合であるならば、その可換群 $P(X)$ はクラインの四元群 $Z 2 \times Z 2$ ^{[注釈 1]}と同型である。

共通部分は対称差に対して分配法則を満たす^[2]：

$A \cap(B △ C) = (A \cap B)△(A \cap C)$ 。

よって、 $X$ を 1 つの集合とするとき、 $P(X) \times P(X)$ の元 $(A, B)$ に $P(X)$ の元 $A △ B$ を対応させて得られる二項算法を加法とし、 $P(X) \times P(X)$ の元 $(A, B)$ に $P(X)$ の元 $A \cap B$ を対応させて得られる二項算法を乗法とすれば、 $P(X)$ は環となる。また、 $P(X)$ はブール環でもある。

その他の性質

$X$ を 1 つの集合とし、 $A, B$ を $X$ の 2 つの部分集合とするとき、次が成り立つ：

$A △ B = (X - A)△(X - B)$ 。

$Λ$ を 1 つの集合とし、 $Λ$ の各元 $λ$ に対して 2 つの集合 $A λ, B λ$ が定められているとき、次が成り立つ：

${\biggl (}\bigcup _{\lambda \in \Lambda }A_{\lambda }{\biggr )}\bigtriangleup {\biggl (}\bigcup _{\lambda \in \Lambda }B_{\lambda }{\biggr )}\subset \bigcup _{\lambda \in \Lambda }{\bigl (}A_{\lambda }\bigtriangleup B_{\lambda }{\bigr )}$

$f$ を集合 $S$ から集合 $T$ への 1 つの写像とし、 $A, B$ を $T$ の 2 つの部分集合とするとき、次が成り立つ：

$f - 1 (A △ B) = f - 1 (A) △ f - 1 (B)$ 。

多項対称差

対称差は結合法則と交換法則を満たすので、 $n$ 個の集合 $A 0, \dots, A n -1$ の対称差 $A 0 △ \dots △ A n -1$ = (⋯( $A 0 △ A 1) △ \dots △ A n -1)$ は順番に依らない。このことから対称差はより一般に（各元における重複度が有限であるような）集合族　 ${\textstyle \{A_{\lambda }\}_{\lambda \in \Lambda }}$ 　に対し以下のように拡張できる。