対称差

対称差

のベン図。対称差は、交差のない和集合です。 ${\displaystyle A\Delta B}$ ${\displaystyle ~\setminus ~}$ ${\displaystyle ~=~}$
タイプ	集合演算
分野	集合論
声明	対称差は、どちらかの集合に含まれるが、共通集合には含まれない要素の集合です。
象徴的な声明	${\displaystyle A\,\Delta \,B=\left(A\setminus B\right)\cup \left(B\setminus A\right)}$

数学において、2 つの集合の対称差 は、選言的和や集合和とも呼ばれ、いずれかの集合に含まれるが、それらの共通部分には含まれない要素の集合です。たとえば、集合との対称差はです。 ${\displaystyle \{1,2,3\}}$${\displaystyle \{3,4\}}$${\displaystyle \{1,2,4\}}$

集合AとBの対称差は、一般に(または)、、またはで表されます。これは、 2 を法とする加算の形として考えることができます。 ${\displaystyle A\operatorname {\Delta } B}$${\displaystyle A\operatorname {\vartriangle } B}$${\displaystyle A\oplus B}$${\displaystyle A\ominus B}$

任意の集合のべき集合は対称差の演算によってアーベル群となり、空集合は群の中立元となり、この群の各元は自身の逆元となる。任意の集合のべき集合はブール環となり、対称差は環の加算、交差は環の乗算となる。

対称差は、両方の相対補集合の和集合と等しく、すなわち^[1]

${\displaystyle A\,\Delta \,B=\left(A\setminus B\right)\cup \left(B\setminus A\right),}$

対称差は、集合構築記法で2つの集合を記述する述語に対するXOR演算⊕を使用して表現することもできます。

${\displaystyle A\mathbin {\Delta } B=\{x:(x\in A)\oplus (x\in B)\}.}$

同じ事実は、対称差の指示関数（ここでは と表記）が、その2つの引数の指示関数のXOR（または2 を法とする加算）であるとして述べることもできます。または、アイバーソンの括弧表記を使用します。 ${\displaystyle \chi}$${\displaystyle \chi _{(A\,\Delta \,B)}=\chi _{A}\oplus \chi _{B}}$${\displaystyle [x\in A\,\Delta \,B]=[x\in A]\oplus [x\in B]}$

対称差は、2つの集合の和集合から積集合を引いたものとして表現することもできます。

${\displaystyle A\,\Delta \,B=(A\cup B)\setminus (A\cap B),}$^[1]

特に、この非厳密な包含における等式は、と が互いに素な集合である場合にのみ発生します。さらに、と とを表記すると、と は常に互いに素なので、と はを分割します。したがって、共通部分と対称差を基本演算と仮定すると、2 つの集合の和集合は、等式の右辺によって対称差の観点から 適切に定義できます。${\displaystyle A\mathbin {\Delta } B\subseteq A\cup B}$ ${\displaystyle A}$${\displaystyle B}$${\displaystyle D=A\mathbin {\Delta } B}$${\displaystyle I=A\cap B}$${\displaystyle D}$${\displaystyle I}$${\displaystyle D}$${\displaystyle I}$ ${\displaystyle A\cup B}$

${\displaystyle A\,\cup \,B=(A\,\Delta \,B)\,\Delta \,(A\cap B)}$。

対称差は交換可能かつ結合的である。

${\displaystyle {\begin{aligned}A\,\Delta \,B&=B\,\Delta \,A,\\(A\,\Delta \,B)\,\Delta \,C&=A\,\Delta \,(B\,\Delta \,C).\end{aligned}}}$

空集合は中立であり、すべての集合はそれ自身の逆集合である。

${\displaystyle {\begin{aligned}A\,\Delta \,\varnothing &=A,\\A\,\Delta \,A&=\varnothing .\end{aligned}}}$

したがって、任意の集合Xの冪集合は対称差演算の下でアーベル群になります。(より一般的には、任意の集合体は対称差を演算とする群を形成します。) すべての要素がそれ自身の逆である群(または、同等に、すべての要素の位数が2 である群)は、ブール群と呼ばれることがあります。^{[2] [3]}対称差は、そのような群の典型的な例を提供します。ブール群は、実際には集合上の対称差演算として定義されることがあります。^[4] X に要素が 2 つしかない場合、このようにして得られた群はクラインの 4 元群です。

同様に、ブール群は基本的なアーベル 2 群です。したがって、対称差によって誘導される群は、実際には2 つの要素を持つ体上のベクトル空間Z ₂です。X が有限の場合、シングルトンはこのベクトル空間の基底を形成し、したがってその次元はXの要素の数に等しくなります。この構成はグラフ理論で、グラフの サイクル空間を定義するために使用されます。

ブール群の逆の性質から、2 つの繰り返し対称差の対称差は、 2 つの多重集合の結合の繰り返し対称差と等価であることが分かります。ここで、各二重集合は両方とも削除できます。具体的には、

${\displaystyle (A\,\Delta \,B)\,\Delta \,(B\,\Delta \,C)=A\,\Delta \,C.}$

これは三角不等式を意味します。^[5] AとCの対称差は、AとBの対称差とBとCの対称差の和集合に含まれます。

交差は対称差に対して 分配されます:

${\displaystyle A\cap (B\,\Delta \,C)=(A\cap B)\,\Delta \,(A\cap C),}$

これは、 Xの冪集合が、対称差が加算、共通部分が乗算となる環になることを示しています。これはブール環の典型的な例です。

対称差のその他の特性は次のとおりです。

• ${\displaystyle A\mathbin {\Delta } B=\emptyset }$の場合に限ります。${\displaystyle A=B}$
• ${\displaystyle A\mathbin {\Delta } B=A^{c}\mathbin {\Delta } B^{c}}$ここで、 は、両方を含む任意の（固定された）集合に対する、それぞれの補数、の補数です。${\displaystyle A^{c}}$${\displaystyle B^{c}}$${\displaystyle A}$${\displaystyle B}$
• ${\displaystyle \left(\bigcup _{\alpha \in {\mathcal {I}}}A_{\alpha }\right)\Delta \left(\bigcup _{\alpha \in {\mathcal {I}}}B_{\alpha }\right)\subseteq \bigcup _{\alpha \in {\mathcal {I}}}\left(A_{\alpha }\mathbin {\Delta } B_{\alpha }\right)}$ここで、 は任意の空でないインデックス セットです。${\displaystyle {\mathcal {I}}}$
• が任意の関数であり、がの共役域内の任意の集合である場合、${\displaystyle f:S\rightarrow T}$${\displaystyle A,B\subseteq T}$${\displaystyle f}$${\displaystyle f^{-1}\left(A\mathbin {\Delta } B\right)=f^{-1}\left(A\right)\mathbin {\Delta } f^{-1}\left(B\right).}$

対称差は、 任意のブール代数で次のように定義できます。

${\displaystyle x\,\Delta \,y=(x\lor y)\land \lnot (x\land y)=(x\land \lnot y)\lor (y\land \lnot x)=x\oplus y.}$

この演算は、集合の対称差と同じ特性を持ちます。

反復対称差は、ある意味では、多数の集合（同じ集合が複数回出現する場合もある）に対する演算と同等であり、奇数の集合に含まれる要素の集合が返されます。

集合の集合の対称差には、集合内の奇数個の集合に含まれる要素だけが含まれます。 $${\displaystyle \Delta M=\left\{a\in \bigcup M:\left|\{A\in M:a\in A\}\right|{\text{ is odd}}\right\}.}$$

明らかに、これは、和集合の各要素が有限個の 要素によって寄与される場合にのみ明確に定義されます。 ${\textstyle \bigcup M}$${\displaystyle M}$

が多重集合で、 であるとします。このとき、の要素の数はの要素の交差のみで与えられる、の公式が存在します。 ${\displaystyle M=\left\{M_{1},M_{2},\ldots ,M_{n}\right\}}$${\displaystyle n\geq 2}$${\displaystyle |\Delta M|}$${\displaystyle \Delta M}$${\displaystyle M}$$${\displaystyle |\Delta M|=\sum _{l=1}^{n}(-2)^{l-1}\sum _{1\leq i_{1}<i_{2}<\ldots <i_{l}\leq n}\left|M_{i_{1}}\cap M_{i_{2}}\cap \ldots \cap M_{i_{l}}\right|.}$$

集合が「どれくらい大きいか」という概念がある限り、2 つの集合間の対称差は、それらの集合が「どれくらい離れているか」の尺度と見なすことができます。

まず有限集合Sと、その大きさによって決まる部分集合上の計数測度について考えます。次にSの 2 つの部分集合を考え、それらの距離を対称差の大きさとします。この距離は実際には計量であり、S上の冪集合は計量空間になります。S に n 個の要素がある場合、空集合からSまでの距離はnであり、これは部分集合の任意のペアの最大距離です。^[6]

測度論の考え方を用いると、測定可能な集合の分離はそれらの対称差の測度として定義できる。σ-代数Σ上で定義されたσ-有限 測度μであれば、関数

${\displaystyle d_{\mu }(X,Y)=\mu (X\,\Delta \,Y)}$

はΣ 上の擬距離である。d μ_が距離となるのは、Σ が同値関係 X ~ Yを法として考えられる場合と、 の場合に限ります。これはフレシェ-ニコディム距離と呼ばれることもあります。結果として得られる距離空間が分離可能であるのは、 L ² (μ)が分離可能である場合に限ります。 ${\displaystyle \mu (X\,\Delta \,Y)=0}$

ならば、次のようになります。確かに、 ${\displaystyle \mu (X),\mu (Y)<\infty }$${\displaystyle |\mu (X)-\mu (Y)|\leq \mu (X\,\Delta \,Y)}$

${\displaystyle {\begin{aligned}|\mu (X)-\mu (Y)|&=\left|\left(\mu \left(X\setminus Y\right)+\mu \left(X\cap Y\right)\right)-\left(\mu \left(X\cap Y\right)+\mu \left(Y\setminus X\right)\right)\right|\\&=\left|\mu \left(X\setminus Y\right)-\mu \left(Y\setminus X\right)\right|\\&\leq \left|\mu \left(X\setminus Y\right)\right|+\left|\mu \left(Y\setminus X\right)\right|\\&=\mu \left(X\setminus Y\right)+\mu \left(Y\setminus X\right)\\&=\mu \left(\left(X\setminus Y\right)\cup \left(Y\setminus X\right)\right)\\&=\mu \left(X\,\Delta \,Y\right)\end{aligned}}}$

が測度空間で が可測集合である場合、それらの対称差も可測です。と が のとき 関連しているとすることで、可測集合上の同値関係を定義できます。 この関係は と表されます。 ${\displaystyle S=\left(\Omega ,{\mathcal {A}},\mu \right)}$${\displaystyle F,G\in {\mathcal {A}}}$${\displaystyle F\Delta G\in {\mathcal {A}}}$${\displaystyle F}$${\displaystyle G}$${\displaystyle \mu \left(F\Delta G\right)=0}$${\displaystyle F=G\left[{\mathcal {A}},\mu \right]}$

が与えられたとき、それぞれに対してとなるような が存在する場合、と書きます。関係「」は の部分集合の族における半順序です。 ${\displaystyle {\mathcal {D}},{\mathcal {E}}\subseteq {\mathcal {A}}}$${\displaystyle {\mathcal {D}}\subseteq {\mathcal {E}}\left[{\mathcal {A}},\mu \right]}$${\displaystyle D\in {\mathcal {D}}}$${\displaystyle E\in {\mathcal {E}}}$${\displaystyle D=E\left[{\mathcal {A}},\mu \right]}$${\displaystyle \subseteq \left[{\mathcal {A}},\mu \right]}$${\displaystyle {\mathcal {A}}}$

および の場合、 と書きます。関係 " " は のサブセット間の同値関係です。 ${\displaystyle {\mathcal {D}}={\mathcal {E}}\left[{\mathcal {A}},\mu \right]}$${\displaystyle {\mathcal {D}}\subseteq {\mathcal {E}}\left[{\mathcal {A}},\mu \right]}$${\displaystyle {\mathcal {E}}\subseteq {\mathcal {D}}\left[{\mathcal {A}},\mu \right]}$${\displaystyle =\left[{\mathcal {A}},\mu \right]}$${\displaystyle {\mathcal {A}}}$

の対称閉包は、あるに対してであるすべての -可測集合の集まりです。 の対称閉包にはが含まれます。が の部分-代数である場合、 の対称閉包も の部分 -代数です。 ${\displaystyle {\mathcal {D}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle =\left[{\mathcal {A}},\mu \right]}$${\displaystyle D\in {\mathcal {D}}}$${\displaystyle {\mathcal {D}}}$${\displaystyle {\mathcal {D}}}$${\displaystyle {\mathcal {D}}}$${\displaystyle \sigma }$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {D}}}$

${\displaystyle F=G\left[{\mathcal {A}},\mu \right]}$ほぼどこでもそうです。 ${\displaystyle \left|\mathbf {1} _{F}-\mathbf {1} _{G}\right|=0}$ ${\displaystyle \left[{\mathcal {A}},\mu \right]}$

ハウスドルフ距離と対称差 (の面積) は、どちらも測定可能な幾何学的形状の集合上の疑似計量です。ただし、動作はまったく異なります。右の図は、「赤」と「赤 ∪ 緑」という 2 つの形状のシーケンスを示しています。それらの間のハウスドルフ距離が小さくなると、それらの間の対称差の面積は大きくなり、その逆も同様です。これらのシーケンスを両方向に続けると、それらの間のハウスドルフ距離が 0 に収束し、それらの間の対称距離が発散する、またはその逆の 2 つのシーケンスを取得できます。

• ハルモス、ポール R. (1960)。素朴集合論。大学数学シリーズ。ヴァン・ノストランド社。Zbl 0087.04403  。
• 集合の対称差。数学百科事典より