两个集合的对称差,是由属于其中一个集合、但不同时属于两者的元素组成的集合。通常记作 A△B 或 AΔB,它反映了两个集合在元素归属上的差异,不偏重其中任何一个集合。对称差是集合论中的基本运算,对应于逻辑中的异或以及代数中的模二加法。
定义与示例
对于集合 A 和 B,它们的对称差为
A△B=(A∖B)∪(B∖A).
等价地,
A△B=(A∪B)∖(A∩B).
因此,
x∈A△B⟺(x∈A and x∈/B) or (x∈B and x∈/A).
例如,若
A={1,2,3},B={3,4,5},
则
A△B={1,2,4,5}.
共同元素 3 被排除在外。
以下几种特殊情形有助于理解这一定义:
- 若 A 与 B 不相交,则 A△B=A∪B。
- 若 A=B,则 A△B=∅,即空集。
- 若 A 是 B 的子集,则 A△B=B∖A。
与普通的差集运算不同,交换两个集合的次序不会改变对称差。与不交并不同,对称差会移除共有元素,而不是为它们分别加上标签并保留各自的副本。
基本恒等式
对称差满足交换律和结合律:
A△B=B△A,
(A△B)△C=A△(B△C).
结合律使得 A△B△C 这样的表达式可以省略括号。
空集是对称差运算的单位元,每个集合与自身作对称差都会抵消:
A△∅=A,A△A=∅.
因此,
(A△B)△B=A.
更一般地,对称差满足消去律:
A△C=B△C⟺A=B.
交运算对对称差满足分配律:
A∩(B△C)=(A∩B)△(A∩C).
对称差对并运算一般不满足分配律。
若补集均相对于固定的全集 U 而言,则
A△U=U∖A,
并且
Ac△Bc=A△B.
因此,对两个集合同时取补集不会改变它们的差异;而只对其中一个集合取补集,则会使原本归属一致和归属不同的部分互换:
Ac△B=(A△B)c.
示性函数与奇偶性
集合 A 的示性函数定义为
1A(x)={1,0,x∈A,x∈/A.
对称差可以逐点表示为
1A△B(x)=∣1A(x)−1B(x)∣.
等价地,使用模算术中的模二运算,有
1A△B(x)=1A(x)+1B(x)(mod2).
这说明,元素是否属于 A△B,等价于对它是否属于两个集合的命题进行异或运算。
对于有限集合族 A1,…,An,
△i=1nAi=A1△⋯△An
恰好包含出现在奇数个集合中的元素。特别地,三个集合的对称差也包含同时属于这三个集合的元素,而不只是恰好属于其中一个集合的元素。
对于无限集合族,有限情形下的奇偶规则并不能自动定义一种运算:一个元素可能属于无穷多个集合,此时通常的奇偶计数不再适用。如果每个元素都只属于该集合族中有限多个集合,就可以通过奇偶性定义无限对称差;但对于不加限制的无限集合族,则需要额外的定义或收敛框架。
代数结构
固定集合 U,以 P(U) 表示它的幂集。则
(P(U),△)
是一个阿贝尔群。其单位元为 ∅,每个元素都是自身的逆元。
这个群也是二元有限域 F2 上的向量空间。向量加法就是对称差,标量乘法定义为
0A=∅,1A=A.
若 U 是含有 n 个元素的有限集,则所有单元素子集构成一组基,该向量空间的维数为 n。
当 U 为无限集时,单元素子集只能张成 U 的有限子集所组成的空间,因为向量空间中的线性组合都是有限的。整个幂集则对应于 U 上所有取值于 F2 的函数。
以对称差为加法、以交运算为乘法,便使 P(U) 成为以 U 为乘法单位元的交换环。每个元素都满足
每个元素在乘法下都幂等的环称为布尔环。这一构造将对称差与布尔代数联系起来:并运算可以通过对称差和交运算恢复,即
A∪B=(A△B)△(A∩B).
基数与差异的度量
对于有限集,其基数满足
∣A△B∣=∣A∣+∣B∣−2∣A∩B∣.
交集的基数要减去两次,因为其中每个元素在两个集合中各被计数一次,却不应出现在对称差中。
在有限全集的所有子集上,
d(A,B)=∣A△B∣
定义了一个度量。其三角不等式可由下式推出:
A△C⊆(A△B)∪(B△C).
当用二进制示性向量编码子集时,这一距离等于两个向量中取值不同的坐标个数,通常称为汉明距离。
在测度论中,类似的构造为
dμ(A,B)=μ(A△B).
在有限测度空间上,这是一个伪度量:它满足对称性和三角不等式,但两个不同的集合如果仅在一个零测集上有差异,它们之间的距离也可以为零。将这样的集合视为同一对象后,就得到了真正的度量。这种等同方式是一个等价关系,定义为
A∼B⟺μ(A△B)=0.
对于一般的测度空间,dμ 可能取值 +∞。
由示性函数公式可得
μ(A△B)=∫∣1A−1B∣dμ.
因此,对称差距离就是两个集合的示性函数之间的 L1 距离。
在概率论中,对于事件 A 和 B,有
Pr(A△B)=Pr(A)+Pr(B)−2Pr(A∩B).
这表示恰好发生其中一个事件的概率。条件 Pr(A△B)=0 意味着它们的示性函数几乎必然相等,但这两个事件作为集合未必完全相同。
在计算与图论中的应用
在软件中,对称差用于找出存在于一个集合中、却不存在于另一个集合中的元素。它可用于比较标识符集合、检测元素归属的变化,以及切换元素的选中状态。将同一个更新集合应用两次,就会恢复原来的集合:
(A△B)△B=A.
具体实现取决于数据的表示方式。以位向量表示的集合使用按位异或运算;有序集合可以通过类似归并的扫描过程处理;基于哈希的集合可以通过成员资格测试进行比较,其性能取决于对哈希过程的假设。这些过程实现的都是普通集合语义;对于需要考虑重复元素的容器,则必须另行规定规则。
在图论中,具有相同顶点集的子图可以通过对其边集取对称差来组合。共有的边相互抵消,恰好出现在其中一个子图中的边则被保留。使每个顶点的度数均为偶数的边子集,在这一运算下是封闭的,并构成该图在 F2 上的圈空间。
虽然圈可以生成这一空间,但两个单独的圈的对称差未必仍是一个圈。它可能为空,也可能由多个圈组成,这体现了共有边在代数运算中的抵消。