対称差

同義語：symmetric difference対称差集合

概要

前提知識: 集合, 差集合, 冪集合, 特性関数(集合)

対称差（symmetric difference）は、2 つの集合 $A,B$ の「ちょうど一方に属する元」を集めた集合 $A\mathbin{\triangle}B$ である。共通部分 $A\cap B$ が 2 つの集合の一致する部分を取り出すのに対し、対称差は所属が食い違う部分を取り出す。元が集合に属するかどうかを $1$ と $0$ で記録すると、対称差への所属は 2 つの記録を $2$ を法として足したもの（排他的論理和）になる。この見方から、対称差は結合的で、空集合を単位元とし、どの集合も自分自身が逆元になる演算であることがわかり、冪集合は対称差を和として 2 元体 $\mathbb{F}_2$ 上のベクトル空間になる。この記事では、$n$ 個の集合の対称差が「奇数個の集合に属する元」の集合であること、有限部分集合と偶数個の元をもつ部分集合がなす部分空間の基底と次元、対称差の大きさで測る距離（有限集合の Hamming 距離と、測度による擬距離）、対称差と共通部分で閉じた族が和集合と差集合で閉じた族と一致することを証明する。

定義

対称差

集合 $A,B$ に対し、
$$ A\mathbin{\triangle}B:=(A\setminus B)\cup(B\setminus A) $$
を $A$ と $B$ の 対称差 という。

定義を展開すると、任意の対象 $x$ について
$$ x\in A\mathbin{\triangle}B\iff(x\in A\text{ かつ }x\notin B)\text{ または }(x\notin A\text{ かつ }x\in B) $$
であり、$x$ が $A,B$ の ちょうど一方 に属することと同値である。したがって「少なくとも一方に属し、両方には属さない」と言い換えられ、
$$ A\mathbin{\triangle}B=(A\cup B)\setminus(A\cap B) $$
が成り立つ（差集合の記事の命題「対称差の別表示」）。この式から $A\mathbin{\triangle}B=B\mathbin{\triangle}A$ も分かる。
記号は $A\mathbin{\triangle}B$ のほか $A\mathbin{\Delta}B$ とも書き、後で見る環の和とみて $A+B$ と書くこともある。この記事では $\mathbin{\triangle}$ を使う。定義は Tao11 Exercise 1.1.1（p. 5）の $E\Delta F:=(E\setminus F)\cup(F\setminus E)$ と同じである。
全体の集合 $X$ を 1 つ固定し、その部分集合だけを考えるときは、$A$ の補集合を $A^{c}:=X\setminus A$ と書く。$A\setminus B=A\cap B^{c}$ なので
$$ A\mathbin{\triangle}B=(A\cap B^{c})\cup(A^{c}\cap B) $$
である。

直感

透明なシートに $A$ を赤で、$B$ を青で塗って重ねたとき、1 色だけが塗られた場所が対称差である。2 色が重なった場所は除かれる。$A$ を昨日の名簿、$B$ を今日の名簿とすれば、$A\setminus B$ は抜けた人、$B\setminus A$ は加わった人であり、$A\mathbin{\triangle}B$ は増減の向きを忘れて「変わった人」だけを記録したものである。3 つ以上の集合を続けて対称差をとると、2 回現れた所属は打ち消し合い、奇数回現れた所属だけが残る。この「偶奇だけを見る」性質が、対称差を $2$ を法とする足し算として扱える理由である。

例と反例

有限集合と区間

$A=\{1,2,3,4\}$、$B=\{3,4,5\}$ なら $A\setminus B=\{1,2\}$、$B\setminus A=\{5\}$ なので $A\mathbin{\triangle}B=\{1,2,5\}$ である。$3,4$ は両方に属するので入らない。
実数の区間 $A=[0,2]$、$B=[1,3]$ なら $A\mathbin{\triangle}B=[0,1)\cup(2,3]$ である。共通部分 $[1,2]$ が取り除かれる。
$A\subset B$ なら $A\setminus B=\emptyset$ なので $A\mathbin{\triangle}B=B\setminus A$ である。$A\cap B=\emptyset$ なら $A\mathbin{\triangle}B=A\cup B$ である。
$A\mathbin{\triangle}A=\emptyset$、$A\mathbin{\triangle}\emptyset=A$ であり、$X$ の部分集合について $A\mathbin{\triangle}X=A^{c}$ である。

3 つの集合の対称差

$A=\{1,2,4,7\}$、$B=\{2,3,4,6\}$、$C=\{4,5,6,7\}$ とする。$A\mathbin{\triangle}B=\{1,3,6,7\}$ なので $(A\mathbin{\triangle}B)\mathbin{\triangle}C=\{1,3,4,5\}$ である。一方 $B\mathbin{\triangle}C=\{2,3,5,7\}$ なので $A\mathbin{\triangle}(B\mathbin{\triangle}C)=\{1,3,4,5\}$ であり、両者は一致する。$1,3,5$ はちょうど 1 つの集合に、$4$ は 3 つすべてに属し、$2,6,7$ はちょうど 2 つの集合に属する。結果に残ったのは、奇数個の集合に属する元 $1,3,4,5$ である（thm-symd-parity）。

正規言語の等しさの判定

2 つの集合が等しいことは、対称差が空であることと同値である（prop-symd-group の 3）。この言い換えは計算に使われる。たとえば 2 つの正規言語 $L_1,L_2$ が等しいかどうかは、正規言語が差集合と和集合で閉じていること（正規言語の記事の命題「補集合・共通部分・差に関する閉包性」）から $L_1\mathbin{\triangle}L_2=(L_1\setminus L_2)\cup(L_2\setminus L_1)$ も正規言語であることを使い、それが空かどうかを調べれば判定できる（同じ記事の節「個数と決定問題」）。

反例の表

取り違え・外す条件	反例	成り立たなくなること
「ちょうど一方」を「少なくとも一方」にする	$A=B=\{1\}$	$A\mathbin{\triangle}B=A\cup B$（左辺は $\emptyset$、右辺は $\{1\}$）
対称差を差集合にする	$A=\{1,2\}$、$B=\{2\}$、$C=\{2\}$	結合律（$(A\setminus B)\setminus C=\{1\}$、$A\setminus(B\setminus C)=\{1,2\}$）
写像の単射性	定数写像 $f\colon\{1,2\}\to\{0\}$、$A=\{1\}$、$B=\{2\}$	$f(A\mathbin{\triangle}B)=f(A)\mathbin{\triangle}f(B)$
有限個であること	すべての $n$ で $A_n=\{0\}$	「奇数個の $A_n$ に属する元の集合」という $\mathop{\triangle}_nA_n$ の定義
測度が $0$ なら等しい、とすること	Lebesgue 測度で $A=\{0\}$、$B=\emptyset$	$\mu(A\mathbin{\triangle}B)=0\Rightarrow A=B$

反例の確かめ

1 行目の例は「$A\mathbin{\triangle}B=A\cup B$」という含意を破り、破れる原因は $A\cap B\neq\emptyset$ である。$A\mathbin{\triangle}B=(A\cup B)\setminus(A\cap B)$ なので、この等式が成り立つのは $A\cap B=\emptyset$ のときに限る。3 行目の例は像が対称差を保つという含意を破り、破れる原因は $f$ が単射でないことである（prop-symd-maps）。4 行目では、$0$ が無限個の $A_n$ に属するので「奇数個」が意味をもたない。

各行の計算を開く

1 行目：$A=B=\{1\}$ では $A\cup B=\{1\}$ だが $A\mathbin{\triangle}B=\emptyset$ である。

2 行目：$(A\setminus B)\setminus C=\{1\}\setminus\{2\}=\{1\}$、$A\setminus(B\setminus C)=A\setminus\emptyset=\{1,2\}$ である。差集合は結合的でないが、対称差は結合的である（prop-symd-group の 1）。

3 行目：$f(A\mathbin{\triangle}B)=f(\{1,2\})=\{0\}$ だが $f(A)\mathbin{\triangle}f(B)=\{0\}\mathbin{\triangle}\{0\}=\emptyset$ である。相異なる $1,2$ が同じ $0$ に移るので、「片方だけにあった」という情報が失われる。

4 行目：順に対称差をとった $A_0\mathbin{\triangle}\cdots\mathbin{\triangle}A_n$ は $n$ の偶奇に従って $\{0\}$ と $\emptyset$ を交互にとり、一定の集合に落ち着かない。無限個の対称差は、各元が有限個の $A_n$ にしか属さない場合にだけ「奇数個に属する元の集合」として定められる。

5 行目：$\mu$ を実数直線の Lebesgue 測度とすると、$\mu(\{0\}\mathbin{\triangle}\emptyset)=\mu(\{0\})=0$ だが $\{0\}\neq\emptyset$ である。$\mu(A\mathbin{\triangle}B)=0$ は「$A$ と $B$ の違いが測度 $0$ の集合に収まる」ことしか意味しない（prop-symd-measure）。

性質

演算の法則

証明には特性関数を使う。集合 $X$ の部分集合 $A$ の特性関数 $\chi_A\colon X\to\{0,1\}$ を 2 元体 $\mathbb{F}_2=\{0,1\}$ に値をとる関数とみると、
$$ \chi_{A\mathbin{\triangle}B}=\chi_A+\chi_B,\qquad \chi_{A\cap B}=\chi_A\chi_B,\qquad \chi_{A^{c}}=1+\chi_A $$
が各点で成り立ち、$A=B$ と $\chi_A=\chi_B$ は同値である（特性関数(集合) の記事の命題「集合演算と特性関数」の 1・3・4・5。$\mathbb{F}_2$ では $-1=1$ である）。いくつかの集合を同時に扱うときは、それらをすべて含む集合（たとえば和集合）を $X$ にとればよい。

対称差の演算法則

集合 $A,B,C$ について次が成り立つ。

（結合律・交換律）$(A\mathbin{\triangle}B)\mathbin{\triangle}C=A\mathbin{\triangle}(B\mathbin{\triangle}C)$、$A\mathbin{\triangle}B=B\mathbin{\triangle}A$。
（単位元と逆元）$A\mathbin{\triangle}\emptyset=A$、$A\mathbin{\triangle}A=\emptyset$。
$A\mathbin{\triangle}B=\emptyset$ と $A=B$ は同値である。
（方程式の解）集合 $Y$ についての方程式 $A\mathbin{\triangle}Y=B$ の解はちょうど 1 つあり、それは $Y=A\mathbin{\triangle}B$ である。特に $A\mathbin{\triangle}C=B\mathbin{\triangle}C$ なら $A=B$ である。
（分配律）$A\cap(B\mathbin{\triangle}C)=(A\cap B)\mathbin{\triangle}(A\cap C)$。
（補集合）全体の集合 $X$ の部分集合について、$A^{c}\mathbin{\triangle}B^{c}=A\mathbin{\triangle}B$、$A^{c}\mathbin{\triangle}B=(A\mathbin{\triangle}B)^{c}$。

$X:=A\cup B\cup C$ とし（6 では与えられた $X$）、$a:=\chi_A$、$b:=\chi_B$、$c:=\chi_C$ を $\mathbb{F}_2$ 値の関数とみる。関数の和と積は各点でとるので、$\mathbb{F}_2$ での計算規則（和の結合律・交換律、$0$ が和の単位元、$t+t=0$、分配律）がそのまま使える。
1：$\chi_{(A\mathbin{\triangle}B)\mathbin{\triangle}C}=(a+b)+c=a+(b+c)=\chi_{A\mathbin{\triangle}(B\mathbin{\triangle}C)}$ であり、特性関数が等しいので集合も等しい。交換律も $a+b=b+a$ から従う。2〜6 も同じく $\mathbb{F}_2$ での計算に帰着する。

2〜6 の計算を開く

2：$\chi_{A\mathbin{\triangle}\emptyset}=a+0=a$、$\chi_{A\mathbin{\triangle}A}=a+a=0=\chi_\emptyset$ である。

3：$a+b=0$ と $a=b$ は $\mathbb{F}_2$ で同値である（両辺に $b$ を足せばよい）。

4：$Y=A\mathbin{\triangle}B$ とおくと、1・2 により $A\mathbin{\triangle}Y=(A\mathbin{\triangle}A)\mathbin{\triangle}B=\emptyset\mathbin{\triangle}B=B$ なので解である。逆に $A\mathbin{\triangle}Y=B$ なら、両辺と $A$ の対称差をとって $Y=(A\mathbin{\triangle}A)\mathbin{\triangle}Y=A\mathbin{\triangle}(A\mathbin{\triangle}Y)=A\mathbin{\triangle}B$ である。後半は、$A\mathbin{\triangle}C=B\mathbin{\triangle}C$ の両辺と $C$ の対称差をとればよい。

5：$\chi_{A\cap(B\mathbin{\triangle}C)}=a(b+c)=ab+ac=\chi_{(A\cap B)\mathbin{\triangle}(A\cap C)}$。

6：$(1+a)+(1+b)=a+b$、$(1+a)+b=1+(a+b)$ である。$\square$

1 と 2 は、全体の集合 $X$ を固定したとき、冪集合 $\mathcal{P}(X)$ が対称差を演算として Abel群になり、単位元が $\emptyset$、各元 $A$ の逆元が $A$ 自身であることを述べている。5 の分配律と合わせると、$\mathcal{P}(X)$ は対称差を和、共通部分を積、$\emptyset$ を零元、$X$ を単位元とする可換環になり、すべての元が $A\cap A=A$ を満たすので Boole環である。特性関数 $A\mapsto\chi_A$ はこの環から $\mathbb{F}_2$ 値関数の環 $\mathbb{F}_2^{X}$ への同型である（Boole環の記事の例「冪集合環」）。
同じことは冪集合に限らない。$\mathcal{P}(X)$ で $A\mathbin{\triangle}B=(A\cap B^{c})\cup(A^{c}\cap B)$ であったのと同じ式で、一般の Boole代数 $(\mathcal{B},\vee,\wedge,{}')$ に和 $a+b:=(a\wedge b')\vee(a'\wedge b)$ と積 $ab:=a\wedge b$ を入れると Boole 環になり、逆に Boole 環から Boole 代数が復元される。これが Stone による Boole 代数と Boole 環の対応である（BS12 Chapter IV §2, Theorem 2.3、pp. 123–124。Boole環の記事の定理「Boole環とBoole代数の対応」）。対称差は、Boole 代数の言葉では「排他的論理和」にあたる演算である。

$n$ 個の集合の対称差と偶奇

結合律（prop-symd-group の 1）により、$n$ 個の集合の対称差は括弧の付け方によらず、交換律により順序にもよらない。これを $A_1\mathbin{\triangle}A_2\mathbin{\triangle}\cdots\mathbin{\triangle}A_n$ と書く。$n=0$ のときは $\emptyset$ と約束する。

対称差は奇数個の集合に属する元を集める

$n\ge1$ とし、集合 $A_1,\dots,A_n$ をとる。元 $x$ に対し、$x$ を含む $A_i$ の個数を $k(x):=\bigl|\{i\mid 1\le i\le n,\ x\in A_i\}\bigr|$ とおく。このとき
$$ A_1\mathbin{\triangle}A_2\mathbin{\triangle}\cdots\mathbin{\triangle}A_n=\{x\in A_1\cup\cdots\cup A_n\mid k(x)\text{ は奇数}\} $$
である。

$n$ についての数学的帰納法で示す。$S_n:=A_1\mathbin{\triangle}\cdots\mathbin{\triangle}A_n$ とし、$x$ を含む $A_i$（$i\le n$）の個数を $k_n(x)$ と書く。$n=1$ なら $S_1=A_1$ であり、$x\in A_1$ と $k_1(x)=1$（奇数）は同値なので成り立つ。
$n$ で成り立つとして、$S_{n+1}=S_n\mathbin{\triangle}A_{n+1}$ を考える。定義から、$x\in S_{n+1}$ は「$x\in S_n$ と $x\in A_{n+1}$ のちょうど一方が成り立つ」ことと同値である。

$x\in A_{n+1}$ のとき：$k_{n+1}(x)=k_n(x)+1$ である。$x\in S_{n+1}$ は $x\notin S_n$ と同値で、帰納法の仮定によりこれは $k_n(x)$ が偶数、すなわち $k_{n+1}(x)$ が奇数であることと同値である。
$x\notin A_{n+1}$ のとき：$k_{n+1}(x)=k_n(x)$ である。$x\in S_{n+1}$ は $x\in S_n$ と同値で、帰納法の仮定によりこれは $k_n(x)=k_{n+1}(x)$ が奇数であることと同値である。
どちらの場合も $x\in S_{n+1}$ と「$k_{n+1}(x)$ が奇数」は同値であり、$k_{n+1}(x)$ が奇数なら $x$ はどれかの $A_i$ に属するので、$n+1$ でも成り立つ。$\square$

右辺は $A_i$ の並べ方にも括弧の付け方にもよらない形をしているので、この定理は結合律と交換律の別証明にもなっている。特性関数で書けば $\chi_{A_1\mathbin{\triangle}\cdots\mathbin{\triangle}A_n}\equiv\chi_{A_1}+\cdots+\chi_{A_n}\pmod 2$ であり、これは整数値の和 $\sum_i\chi_{A_i}(x)=k(x)$ の偶奇を見ていることにあたる。
無限個の集合 $(A_i)_{i\in I}$ については、各元 $x$ を含む $A_i$ が有限個しかないときに限り、右辺と同じ式で $\mathop{\triangle}_{i\in I}A_i:=\{x\mid k(x)\text{ は奇数}\}$ と定めることができる（そうでない場合の困難は ex-symd-counterexamples の 4）。

$\mathbb{F}_2$ 上のベクトル空間

$\mathcal{P}(X)$ は対称差について Abel 群で、どの元も $A\mathbin{\triangle}A=\emptyset$ を満たす。スカラー倍を $0\cdot A:=\emptyset$、$1\cdot A:=A$ と定めると、$\mathcal{P}(X)$ は 2 元体 $\mathbb{F}_2$ 上のベクトル空間になる。実際、スカラーは $0,1$ だけなので、ベクトル空間の公理のうち群の法則から直ちに従わないのは $(1+1)\cdot A=1\cdot A\mathbin{\triangle}1\cdot A$ だけであり、これは左辺が $0\cdot A=\emptyset$、右辺が $A\mathbin{\triangle}A=\emptyset$ で成り立つ。このベクトル空間は、特性関数によって $\mathbb{F}_2^{X}$ と同一視される。
有限集合 $A,B$ の元の個数について、
$$ |A\mathbin{\triangle}B|=|A|+|B|-2|A\cap B| $$
が成り立つ。$A\mathbin{\triangle}B$ は交わらない 2 つの集合 $A\setminus B$、$B\setminus A$ の和であり、$A$ は交わらない $A\setminus B$ と $A\cap B$ の和なので $|A\setminus B|=|A|-|A\cap B|$、同様に $|B\setminus A|=|B|-|A\cap B|$ となるからである。

冪集合のベクトル空間の基底と偶部分集合

$X$ を集合とし、$X$ の有限部分集合全体を $\mathcal{P}_{\mathrm{fin}}(X)$ と書く。

$\mathcal{P}_{\mathrm{fin}}(X)$ は $\mathcal{P}(X)$ の部分空間であり、1 元集合の全体 $\{\{x\}\mid x\in X\}$ はその基底である。特に $X$ が $n$ 元の有限集合なら $\dim_{\mathbb{F}_2}\mathcal{P}(X)=n$ であり、各部分集合 $A$ は $A=\mathop{\triangle}_{x\in A}\{x\}$ と相異なる 1 元集合の対称差にただ 1 通りに書ける。
$X$ が $n\ge1$ 元の有限集合のとき、写像 $\varepsilon\colon\mathcal{P}(X)\to\mathbb{F}_2$、$\varepsilon(A):=|A|\bmod 2$ は全射な線形写像である。その核 $\mathcal{E}(X)$、すなわち元の個数が偶数の部分集合の全体は部分空間であり、$|\mathcal{E}(X)|=2^{n-1}$、$\dim_{\mathbb{F}_2}\mathcal{E}(X)=n-1$ である。

1：$\emptyset$ は有限であり、有限集合 $A,B$ について $A\mathbin{\triangle}B\subset A\cup B$ は有限なので、$\mathcal{P}_{\mathrm{fin}}(X)$ は対称差（和）で閉じる。スカラー倍 $0\cdot A=\emptyset$、$1\cdot A=A$ でも閉じるので部分空間である。
生成すること：有限集合 $A=\{x_1,\dots,x_k\}$（$x_j$ は相異なる）をとる。$\{x_1\}\mathbin{\triangle}\cdots\mathbin{\triangle}\{x_k\}$ は、thm-symd-parity により、ちょうど奇数個の $\{x_j\}$ に属する元の集合である。各 $x_j$ はちょうど 1 つの $\{x_j\}$ に属し、それ以外の元はどれにも属さないので、この対称差は $A$ に等しい（$k=0$ なら $A=\emptyset$ は空の和）。
1 次独立であること：相異なる $x_1,\dots,x_k$（$k\ge1$）について $\{x_1\}\mathbin{\triangle}\cdots\mathbin{\triangle}\{x_k\}=\emptyset$ となったとする。上と同じ理由で左辺は $\{x_1,\dots,x_k\}$ であり、$x_1$ を含むので空でない。これは矛盾なので、どの有限個の相異なる 1 元集合も 1 次独立である。スカラーが $0,1$ だけなので、1 次結合は「いくつかを選んで対称差をとる」ことにほかならず、これで基底であることが示された。$X$ が有限なら $\mathcal{P}(X)=\mathcal{P}_{\mathrm{fin}}(X)$ で、基底の元の個数は $n$ である。表し方の一意性は基底の性質である。
2：上の個数の式から $|A\mathbin{\triangle}B|\equiv|A|+|B|\pmod 2$、すなわち $\varepsilon(A\mathbin{\triangle}B)=\varepsilon(A)+\varepsilon(B)$ であり、$\varepsilon(0\cdot A)=\varepsilon(\emptyset)=0$ なので $\varepsilon$ は線形である。$x_0\in X$ をとれば $\varepsilon(\{x_0\})=1$ なので全射である。線形写像の核は部分空間なので $\mathcal{E}(X)$ は部分空間である。
個数を数える。写像 $\tau\colon\mathcal{P}(X)\to\mathcal{P}(X)$、$\tau(A):=A\mathbin{\triangle}\{x_0\}$ は $\tau\circ\tau=\mathrm{id}$ を満たすので全単射であり、$\varepsilon(\tau(A))=\varepsilon(A)+1$ なので偶数個の元をもつ部分集合と奇数個の元をもつ部分集合を入れ替える。したがって両者は同数で、$|\mathcal{P}(X)|=2^n$ の半分ずつ、$|\mathcal{E}(X)|=2^{n-1}$ である。$\mathbb{F}_2$ 上の $d$ 次元の空間の元の個数は $2^d$ なので、$\dim\mathcal{E}(X)=n-1$ である。$\square$

3 元集合の偶部分集合

$X=\{1,2,3\}$ のとき、$\mathcal{E}(X)=\{\emptyset,\{1,2\},\{1,3\},\{2,3\}\}$ である。$\{1,2\}\mathbin{\triangle}\{1,3\}=\{2,3\}$ のように、偶数個の元をもつ集合どうしの対称差はまた偶数個の元をもち、$\{1,2\},\{1,3\}$ が基底になる。$\{1\}\mathbin{\triangle}\{2\}=\{1,2\}$ のように、奇数個どうしの対称差は偶数個になる。

2 は、二項係数で書けば $\sum_{k\text{ 偶数}}\binom{n}{k}=\sum_{k\text{ 奇数}}\binom{n}{k}=2^{n-1}$（$n\ge1$）ということである。同じ考え方をグラフの辺の集合に使うと、有限グラフの辺の部分集合のうち、どの頂点の次数も偶数になるものの全体が $\mathbb{F}_2$ 上の部分空間をなす。これが閉路の記事の節「閉路空間」で扱う閉路空間である。
$X$ が無限集合なら $\mathcal{P}_{\mathrm{fin}}(X)\neq\mathcal{P}(X)$ であり、1 元集合は $\mathcal{P}(X)$ 全体を生成しない。1 元集合の有限個の対称差は有限集合なので、たとえば $X$ 自身はそのように書けない。

対称差の大きさで測る距離

2 つの集合が「どれだけ違うか」は、対称差の大きさで測れる。

有限集合の対称差距離

集合 $X$ の有限部分集合 $A,B$ に対し $d(A,B):=|A\mathbin{\triangle}B|$ とおく。

$d$ は $\mathcal{P}_{\mathrm{fin}}(X)$ 上の距離である。すなわち $d(A,B)\ge0$ で、$d(A,B)=0\iff A=B$、$d(A,B)=d(B,A)$、$d(A,C)\le d(A,B)+d(B,C)$ が成り立つ。
（平行移動で不変）$X$ の任意の有限部分集合 $C$ について $d(A\mathbin{\triangle}C,B\mathbin{\triangle}C)=d(A,B)$。
$X$ が有限なら、$d(A,B)$ は特性関数 $\chi_A,\chi_B\in\{0,1\}^{X}$ の値が食い違う点の個数（Hamming 距離）に等しい。

1：$d(A,B)=0$ は $A\mathbin{\triangle}B=\emptyset$、すなわち $A=B$ と同値である（prop-symd-group の 3）。対称性は交換律から従う。三角不等式を示す。結合律と $B\mathbin{\triangle}B=\emptyset$ から
$$ A\mathbin{\triangle}C=(A\mathbin{\triangle}B)\mathbin{\triangle}(B\mathbin{\triangle}C) $$
であり、一般に $P\mathbin{\triangle}Q\subset P\cup Q$ なので $A\mathbin{\triangle}C\subset(A\mathbin{\triangle}B)\cup(B\mathbin{\triangle}C)$ である。有限集合の和の個数は各個数の和以下なので $|A\mathbin{\triangle}C|\le|A\mathbin{\triangle}B|+|B\mathbin{\triangle}C|$ を得る。
2：結合律・交換律と $C\mathbin{\triangle}C=\emptyset$ から $(A\mathbin{\triangle}C)\mathbin{\triangle}(B\mathbin{\triangle}C)=A\mathbin{\triangle}B$ である。
3：$x\in A\mathbin{\triangle}B$ は $x$ が $A,B$ のちょうど一方に属すること、すなわち $\chi_A(x)\neq\chi_B(x)$ と同値である。$\square$

$X=\{1,\dots,n\}$ の部分集合を長さ $n$ の $0,1$ の列と同一視すると、$d$ は 2 つの列の食い違う桁の個数である。符号理論では、送った列と受け取った列の $d$ が誤りの個数にあたる。
測度が与えられているときは、元の個数の代わりに測度を使う。以下 $(X,\mathcal{S},\mu)$ を測度空間とする。$\mathcal{S}$ は差集合と和集合で閉じているので、$A,B\in\mathcal{S}$ なら $A\mathbin{\triangle}B\in\mathcal{S}$ である。

測度による擬距離

$A,B,C\in\mathcal{S}$ とし、$d_\mu(A,B):=\mu(A\mathbin{\triangle}B)\in[0,\infty]$ とおく。

$d_\mu(A,A)=0$、$d_\mu(A,B)=d_\mu(B,A)$、$d_\mu(A,C)\le d_\mu(A,B)+d_\mu(B,C)$。
$\mu(A),\mu(B)<\infty$ なら $|\mu(A)-\mu(B)|\le d_\mu(A,B)$。
関係 $A\sim B:\iff d_\mu(A,B)=0$ は $\mathcal{S}$ 上の同値関係であり、$A\sim A'$、$B\sim B'$ なら $d_\mu(A,B)=d_\mu(A',B')$ である。したがって $d_\mu$ は、測度が有限な集合の同値類全体の上の距離を定める。

測度の単調性と有限劣加法性（測度の記事の命題「測度の基本性質」の 2・4）を使う。
1：$A\mathbin{\triangle}A=\emptyset$ なので $d_\mu(A,A)=\mu(\emptyset)=0$。対称性は交換律から従う。prf-symd-hamming と同じく $A\mathbin{\triangle}C\subset(A\mathbin{\triangle}B)\cup(B\mathbin{\triangle}C)$ なので、単調性と劣加法性から $\mu(A\mathbin{\triangle}C)\le\mu(A\mathbin{\triangle}B)+\mu(B\mathbin{\triangle}C)$。
2：$A\subset B\cup(A\setminus B)$ なので $\mu(A)\le\mu(B)+\mu(A\setminus B)\le\mu(B)+\mu(A\mathbin{\triangle}B)$。$A,B$ を入れ替えた式と合わせれば、両辺が有限なので $|\mu(A)-\mu(B)|\le\mu(A\mathbin{\triangle}B)$ を得る。
3：反射律と対称律は 1 の前半から、推移律は三角不等式から従う。代表元によらないことも三角不等式から従う。

3 の細部を開く

推移律：$d_\mu(A,B)=d_\mu(B,C)=0$ なら $d_\mu(A,C)\le0$ である。代表元によらないこと：$A\sim A'$、$B\sim B'$ なら、三角不等式を 2 回使って $d_\mu(A,B)\le d_\mu(A,A')+d_\mu(A',B')+d_\mu(B',B)=d_\mu(A',B')$、同様に逆向きの不等号も成り立つ。距離であること：測度が有限な集合どうしでは $d_\mu(A,B)\le\mu(A\cup B)\le\mu(A)+\mu(B)<\infty$ なので値は実数であり、同値類の上で $d_\mu([A],[B])=0$ なら $A\sim B$、すなわち $[A]=[B]$ である。対称性と三角不等式は 1 から従う。$\square$

$A\sim B$ は「$A$ と $B$ の違い $A\mathbin{\triangle}B$ が零集合である」ことであり、「ほとんど至る所で等しい」集合を同一視することにあたる。2 から、$A\mapsto\mu(A)$ はこの距離について連続（Lipschitz 定数 $1$）である。Tao11 Exercise 1.2.24（p. 42）は、有限個の直方体の和集合（基本集合）$A\subset\mathbb{R}^d$ を 1 つ固定し、$A$ の部分集合を外測度 $m^{*}$ による $m^{*}(E\mathbin{\triangle}E')$ で比べると完備な距離空間が得られ、その中で Lebesgue 可測集合の類の全体が、基本集合の類の全体の閉包になることを演習として述べている。Lebesgue 可測集合を、基本集合でこの距離の意味でいくらでも近似できる集合として捉える見方である。この記事ではこれを証明しない。

写像との関係

逆像と像

$f\colon X\to Y$ を写像とする。

$A,B\subset Y$ について $f^{-1}(A\mathbin{\triangle}B)=f^{-1}(A)\mathbin{\triangle}f^{-1}(B)$ である。$f^{-1}(A\cap B)=f^{-1}(A)\cap f^{-1}(B)$、$f^{-1}(Y)=X$ と合わせて、$A\mapsto f^{-1}(A)$ は環 $\mathcal{P}(Y)$ から環 $\mathcal{P}(X)$ への単位元を保つ環準同型である。
$A,B\subset X$ について $f(A)\mathbin{\triangle}f(B)\subset f(A\mathbin{\triangle}B)$ である。すべての $A,B$ で等号が成り立つことと、$f$ が単射であることは同値である。

1：$x\in f^{-1}(A\mathbin{\triangle}B)$ は $f(x)$ が $A,B$ のちょうど一方に属すること、すなわち $x$ が $f^{-1}(A),f^{-1}(B)$ のちょうど一方に属することと同値である。共通部分と全体についても同様に所属を確かめればよい。
2：$y\in f(A)\mathbin{\triangle}f(B)$ とし、$y\in f(A)\setminus f(B)$ の場合を考える（逆の場合も同様）。$y=f(a)$ となる $a\in A$ がある。$a\in B$ なら $y\in f(B)$ となって仮定に反するので $a\in A\setminus B$ であり、$y\in f(A\mathbin{\triangle}B)$ である。
$f$ が単射でなければ、$x\neq x'$ で $f(x)=f(x')$ となるものがあり、$A=\{x\}$、$B=\{x'\}$ とすると $f(A\mathbin{\triangle}B)=\{f(x)\}$ だが $f(A)\mathbin{\triangle}f(B)=\emptyset$ で等号が成り立たない。$f$ が単射なら、$A\setminus B$ の元の像は $f(B)$ に入らないので逆の包含も成り立つ。

単射のときの逆の包含を開く

$y\in f(A\mathbin{\triangle}B)$ とし、$y=f(x)$、$x\in A\setminus B$ とする（$x\in B\setminus A$ も同様）。$y\in f(A)$ である。もし $y\in f(B)$ なら $y=f(b)$ となる $b\in B$ があり、単射性から $x=b\in B$ となって矛盾する。よって $y\in f(A)\setminus f(B)\subset f(A)\mathbin{\triangle}f(B)$ である。$\square$

対称差と共通部分で閉じた族

測度論や確率論では、和集合・差集合をとる操作で閉じた集合の族を扱う。この条件は、環の言葉では「対称差と共通部分で閉じる」ことと同じである。

閉じた族の 2 通りの記述

集合 $X$ の部分集合の族 $\mathcal{R}\subset\mathcal{P}(X)$ で $\emptyset\in\mathcal{R}$ となるものについて、次は同値である。
(i) $A,B\in\mathcal{R}$ なら $A\mathbin{\triangle}B\in\mathcal{R}$ かつ $A\cap B\in\mathcal{R}$。
(ii) $A,B\in\mathcal{R}$ なら $A\cup B\in\mathcal{R}$ かつ $A\setminus B\in\mathcal{R}$。
したがって (ii) を満たす族は、環 $\mathcal{P}(X)$ の部分集合で和・積・零元について閉じたもの（単位元 $X$ を含むとは限らない部分環）にほかならない。

次の 4 つの等式を使う。
$$ A\cup B=(A\mathbin{\triangle}B)\mathbin{\triangle}(A\cap B),\qquad A\setminus B=A\mathbin{\triangle}(A\cap B), $$
$$ A\mathbin{\triangle}B=(A\setminus B)\cup(B\setminus A),\qquad A\cap B=A\setminus(A\setminus B). $$
3 つ目は定義であり、4 つ目は $x\in A\setminus(A\setminus B)$ が「$x\in A$ かつ（$x\notin A$ または $x\in B$）」すなわち $x\in A\cap B$ と同値であることから従う。前の 2 つは、右辺に現れる 2 つの集合のうち奇数個（ちょうど 1 つ）に属する元を数えて確かめる（thm-symd-parity）。

前の 2 つの等式の確かめを開く

1 つ目：$x\in A\cap B$ なら $x$ は $A\mathbin{\triangle}B$ に属さず $A\cap B$ に属するので、$(A\mathbin{\triangle}B)\mathbin{\triangle}(A\cap B)$ に属する。$x$ が $A,B$ のちょうど一方に属するなら $A\mathbin{\triangle}B$ だけに属するので、やはり属する。$x\notin A\cup B$ ならどちらにも属さない。

2 つ目：$x\in A\cap B$ なら $A$ と $A\cap B$ の 2 つに属するので右辺に属さず、$x\in A\setminus B$ なら $A$ だけに属するので右辺に属し、$x\notin A$ ならどちらにも属さない。

(i) を仮定すると、1 つ目と 2 つ目の等式の右辺は $\mathcal{R}$ の元の対称差と共通部分なので $\mathcal{R}$ に属し、(ii) が成り立つ。(ii) を仮定すると、3 つ目と 4 つ目の等式の右辺は $\mathcal{R}$ の元の和集合と差集合なので $\mathcal{R}$ に属し、(i) が成り立つ。最後の主張は、環 $\mathcal{P}(X)$ で $-A=A$ なので、和と零元について閉じていれば加法の逆元についても閉じていることによる。$\square$

閉じた族の例と反例

σ-代数は和集合と差集合で閉じているので (i) を満たす。
$\mathbb{N}$ の有限部分集合の全体は (ii) を満たし、したがって (i) を満たすが、単位元 $\mathbb{N}$ を含まない（Boole環の記事の例「反例：単位元をもたない場合」）。有限集合または補集合が有限な集合の全体は、単位元 $\mathbb{N}$ も含む（同記事の例「有限または補有限な部分集合の環」）。
反例：実数直線の閉区間 $[a,b]$（$a\le b$）の全体に $\emptyset$ を加えた族は、共通部分では閉じているが、$[0,2]\mathbin{\triangle}[1,3]=[0,1)\cup(2,3]$ が区間でないので対称差で閉じていない。和集合でも閉じていない（$[0,1]\cup[2,3]$）。この族は「共通部分で閉じていれば (i) を満たす」という含意を破る例であり、満たさない条件は対称差についての閉性である。

補足

対称差は、集合を「各点での $0,1$ の記録」とみたときの $2$ を法とする足し算であり、論理演算の排他的論理和（XOR）を集合の言葉に移したものである。$\mathbb{F}_2$ 上の線形代数が集合の問題に使えるのはこの対応による。グラフ理論では辺集合の対称差が閉路空間の和を与え、測度論では prop-symd-measure の擬距離によって可測集合の近似を論じる。集合の等しさ $A=B$ を「$A\mathbin{\triangle}B$ が空」と言い換えられること（prop-symd-group の 3）は、等しさの判定を空であることの判定に帰着させるときに使われる（ex-symd-language）。