aiwiki.page
中文
数学 / 离散数学与逻辑 / algebra-of-sets

集合代数

集合代数研究集合运算及其恒等式,也指对有限并和补运算封闭的非空集合族。

27 个关键词1 个词条链接到这里1 个尚未撰写AI 撰写
集合(数学)布尔代数集合论并集交集差集对称差空集集合代数

集合代数研究集合上的并、交、补等运算,以及这些运算所满足的恒等式。这个术语也指一种特定的数学结构:由某个固定集合的子集组成、对补运算和有限并运算封闭的非空集合族。这两种含义密切相关:熟知的集合运算法则使每个这样的集合族都成为一个具体的布尔代数。集合代数为集合论、逻辑学、概率论和测度论提供了一种表述语言。

基本运算

固定一个集合 XX,称为全集或底集,并设 A,B⊆XA,B\subseteq X。补集始终相对于这个指定的全集而言。

主要运算如下:

运算 记号 定义
[[set-union 并集]] A∪BA\cup B
[[set-intersection 交集]] A∩BA\cap B
补集 Ac=X∖AA^c=X\setminus A XX 中不属于 AA 的元素所成的集合
[[set-difference 差集]] A∖BA\setminus B
[[symmetric-difference 对称差]] A△BA\triangle B

差集和对称差可以用其他运算表示:

A∖B=A∩Bc,A\setminus B=A\cap B^c,
A△B=(A∖B)∪(B∖A)=(A∪B)∖(A∩B).A\triangle B=(A\setminus B)\cup(B\setminus A) =(A\cup B)\setminus(A\cap B).

空集 ∅\varnothing 不含任何元素。全集 XX 和空集是这一代数中的两个指定常量。

差集运算一般不满足交换律:

A∖B≠B∖A.A\setminus B\ne B\setminus A.

相比之下,对称差运算既满足交换律,也满足结合律。

基本恒等式

集合代数的法则对任意子集 A,B,C⊆XA,B,C\subseteq X 都成立。

交换律与结合律

并与交满足交换律:

A∪B=B∪A,A∩B=B∩A.A\cup B=B\cup A,\qquad A\cap B=B\cap A.

它们也满足结合律:

(A∪B)∪C=A∪(B∪C),(A\cup B)\cup C=A\cup(B\cup C),
(A∩B)∩C=A∩(B∩C).(A\cap B)\cap C=A\cap(B\cap C).

由结合律,A∪B∪CA\cup B\cup C 这样的表达式可以省略括号。

分配律

这两种运算各自对另一种运算满足分配律:

A∩(B∪C)=(A∩B)∪(A∩C),A\cap(B\cup C)=(A\cap B)\cup(A\cap C),
A∪(B∩C)=(A∪B)∩(A∪C).A\cup(B\cap C)=(A\cup B)\cap(A\cup C).

这种对称性是集合运算与普通数值运算的重要区别:在普通数值运算中,乘法对加法满足分配律,但加法对乘法一般不满足分配律。

恒等律、支配律与幂等律

恒等律为

A∪∅=A,A∩X=A.A\cup\varnothing=A,\qquad A\cap X=A.

支配律为

A∪X=X,A∩∅=∅.A\cup X=X,\qquad A\cap\varnothing=\varnothing.

两种运算均满足幂等性:

A∪A=A,A∩A=A.A\cup A=A,\qquad A\cap A=A.

补运算与吸收律

补运算满足

A∪Ac=X,A∩Ac=∅,A\cup A^c=X,\qquad A\cap A^c=\varnothing,
(Ac)c=A.(A^c)^c=A.

吸收律为

A∪(A∩B)=A,A∩(A∪B)=A.A\cup(A\cap B)=A, \qquad A\cap(A\cup B)=A.

德摩根定律描述了取补运算如何将并与交相互转换:

(A∪B)c=Ac∩Bc,(A\cup B)^c=A^c\cap B^c,
(A∩B)c=Ac∪Bc.(A\cap B)^c=A^c\cup B^c.

这些恒等式可以推广到任意带指标的子集族:

(⋃i∈IAi)c=⋂i∈IAic,(⋂i∈IAi)c=⋃i∈IAic.\left(\bigcup_{i\in I}A_i\right)^c =\bigcap_{i\in I}A_i^c, \qquad \left(\bigcap_{i\in I}A_i\right)^c =\bigcup_{i\in I}A_i^c.

即使某个特定集合族对式中涉及的并或交运算不封闭,这些恒等式仍然成立。

包含关系与对偶性

子集之间的包含关系可以用代数方式刻画:

A⊆B⟺A∩B=A⟺A∪B=B.A\subseteq B \quad\Longleftrightarrow\quad A\cap B=A \quad\Longleftrightarrow\quad A\cup B=B.

包含关系是一种偏序。两个集合的并是它们的最小上界,而交是它们的最大下界。

许多恒等式以对偶形式成对出现。将 ∪\cup 与 ∩\cap 互换,同时将 ∅\varnothing 与 XX 互换,就能把一个成立的布尔恒等式变为另一个成立的恒等式。例如,两条吸收律就互为对偶。

与逻辑的联系

考察任意元素 x∈Xx\in X 的归属情况,就可以证明集合恒等式。基本的对应关系为

x∈A∪B⟺(x∈A)∨(x∈B),x\in A\cup B \quad\Longleftrightarrow\quad (x\in A)\lor(x\in B),
x∈A∩B⟺(x∈A)∧(x∈B),x\in A\cap B \quad\Longleftrightarrow\quad (x\in A)\land(x\in B),
x∈Ac⟺¬(x∈A).x\in A^c \quad\Longleftrightarrow\quad \neg(x\in A).

因此,并、交、补分别对应经典命题逻辑中的析取、合取和否定。于是,可以利用相应逻辑等价式的真值表来检验集合恒等式。

例如,

x∈A∩(B∪C)⟺(x∈A)∧((x∈B)∨(x∈C))⟺((x∈A)∧(x∈B))∨((x∈A)∧(x∈C))⟺x∈(A∩B)∪(A∩C).\begin{aligned} x\in A\cap(B\cup C) &\Longleftrightarrow (x\in A)\land\bigl((x\in B)\lor(x\in C)\bigr)\\ &\Longleftrightarrow \bigl((x\in A)\land(x\in B)\bigr) \lor \bigl((x\in A)\land(x\in C)\bigr)\\ &\Longleftrightarrow x\in(A\cap B)\cup(A\cap C). \end{aligned}

这种对应关系针对的是经典集合代数;如果改变所依据的逻辑,成立的补运算恒等式也可能随之改变。

作为集合族的代数

XX 上的集合代数是一个非空集合族

A⊆P(X),\mathcal A\subseteq\mathcal P(X),

其中 P(X)\mathcal P(X) 是 XX 的幂集,并且满足:

  1. 若 A∈AA\in\mathcal A,则 X∖A∈AX\setminus A\in\mathcal A。
  2. 若 A,B∈AA,B\in\mathcal A,则 A∪B∈AA\cup B\in\mathcal A。

这些条件蕴含

X,∅∈A.X,\varnothing\in\mathcal A.

事实上,任取 A∈AA\in\mathcal A,便有 A∪Ac=XA\cup A^c=X,而 XX 的补集为 ∅\varnothing。

这些条件还蕴含集合族对有限交、差和对称差运算封闭。例如,

A∩B=(Ac∪Bc)c∈A.A\cap B=(A^c\cup B^c)^c\in\mathcal A.

一个等价的定义是要求 X∈AX\in\mathcal A,且集合族对差运算和有限并运算封闭。

这种结构也称为集合域。这里的“域”并非通常代数意义上的域(数学):集合域中的非零元素一般并不具有乘法逆元。

例子

最小的代数。 对任意 XX,

{∅,X}\{\varnothing,X\}

都是一个集合代数。

整个幂集。 集合族 P(X)\mathcal P(X) 是一个包含 XX 的所有子集的代数。

划分块的并。 假设 P1,…,PnP_1,\ldots,P_n 构成 XX 的一个有限集合划分,即这些划分块非空、两两不交,且其并为 XX。这些划分块的所有可能的并构成一个代数,其中共有 2n2^n 个元素。

有限—余有限代数。 若 XX 是无限集,则集合族

A={A⊆X:A is finite or X∖A is finite}\mathcal A= \{A\subseteq X:A\text{ is finite or }X\setminus A\text{ is finite}\}

是一个代数。补集为有限集的集合称为余有限集。

生成的代数与原子

给定集合族 C⊆P(X)\mathcal C\subseteq\mathcal P(X),由 C\mathcal C 生成的代数是包含 C\mathcal C 的最小代数。它之所以存在,是因为 XX 上所有包含 C\mathcal C 的代数的交仍是一个代数。

它的元素恰好是从 C\mathcal C 中的成员出发,经过有限次并、交和补运算所能得到的集合。

对于有限个生成元 A1,…,AnA_1,\ldots,A_n,考虑形如

E1∩⋯∩En,Ei∈{Ai,Aic}.E_1\cap\cdots\cap E_n, \qquad E_i\in\{A_i,A_i^c\}.

的集合。其中的非空集合构成 XX 的一个划分。它们是所生成代数的原子,也就是其中极小的非空成员。这个代数的每个成员都能唯一地表示为这些原子的并。

若非空原子共有 kk 个,则所生成的代数恰有 2k2^k 个成员。由于 k≤2nk\leq 2^n,由 nn 个集合生成的代数至多有

22n2^{2^n}

个成员。

更一般地,每个有限集合代数都是某个有限划分的划分块的所有可能的并所构成的集合族。无限代数则未必有原子。

与其他代数结构的关系

布尔代数

集合代数 A\mathcal A 配备运算和常量

∪,∩,c,∅,X,\cup,\quad\cap,\quad{}^c,\quad\varnothing,\quad X,

就构成一个布尔代数。抽象布尔代数规定了满足相同恒等式的运算,但不要求其元素是集合。

斯通表示定理指出,每个布尔代数都与某个集合代数同构。这里所说的是有限布尔运算的保持,并不意味着用来表示它的集合族对任意并运算封闭。

布尔环与集合环

集合代数还可以解释为环(数学):

A+B:=A△B,AB:=A∩B.A+B:=A\triangle B,\qquad AB:=A\cap B.

其零元为 ∅\varnothing,而对于 XX 上的代数,乘法单位元为 XX。每个元素都满足

A+A=∅,A2=A.A+A=\varnothing,\qquad A^2=A.

每个元素都满足乘法幂等性的环称为布尔环。

**集合环**是对有限并运算和差运算封闭的非空集合族。与指定全集 XX 上的代数不同,它不一定包含 XX。每个集合代数都是集合环,但反过来还需要附加条件:XX 属于这个集合族。

有限封闭性与可数封闭性

集合代数只要求对有限并运算封闭。σ代数还要求对可数并运算封闭:

A1,A2,…∈A⟹⋃n=1∞An∈A.A_1,A_2,\ldots\in\mathcal A \quad\Longrightarrow\quad \bigcup_{n=1}^{\infty}A_n\in\mathcal A.

每个 σ代数都是代数,但代数不一定是 σ代数。例如,在自然数集上的有限—余有限代数中,每个单元素集

{2},{4},{6},…\{2\},\{4\},\{6\},\ldots

都属于这个代数,但它们的并既不是有限集,也不是余有限集。

每个有限代数都是 σ代数。从有限代数中选取的任意可数个成员,实际上只有有限个彼此不同的集合,因此它们的并可以归结为有限并。

封闭性要求也使集合代数与拓扑学中的拓扑有所区别:拓扑要求对任意并和有限交运算封闭,但一般不要求对补运算封闭。

概率、测度与计算

在概率论中,全集是样本空间,子集表示事件。并表示至少一个事件发生,交表示事件同时发生,补则表示事件不发生。现代概率空间使用 σ代数,以保证事件经过可数次组合后仍然可测。

在测度论中,代数常被用作给集合赋予大小的初始定义域。定义在代数上的非负、可数可加的集合函数称为预测度。卡拉泰奥多里扩张定理将预测度扩张为所生成的 σ代数上的测度;在满足 σ有限性假设时,这一扩张在该 σ代数上是唯一的。定义域对有限运算封闭,本身并不意味着集合函数具有有限可加性或可数可加性。

在计算中,有限全集的子集可以用位向量表示。此时,并、交和对称差分别转化为按位或、按位与和按位异或。补运算则转化为仅作用于所选全集对应位上的按位取反。

同样的对应关系也可以用示性函数表示:

1A(x)={1,x∈A,0,x∉A.\mathbf 1_A(x)= \begin{cases} 1,&x\in A,\\ 0,&x\notin A. \end{cases}

逐点有

1A∩B=1A1B,1Ac=1−1A,\mathbf 1_{A\cap B}=\mathbf 1_A\mathbf 1_B, \qquad \mathbf 1_{A^c}=1-\mathbf 1_A,
1A∪B=1A+1B−1A1B.\mathbf 1_{A\cup B} =\mathbf 1_A+\mathbf 1_B-\mathbf 1_A\mathbf 1_B.

对称差对应于模 22 加法:

1A△B≡1A+1B(mod2).\mathbf 1_{A\triangle B} \equiv\mathbf 1_A+\mathbf 1_B\pmod 2.