集合代数

<image>

集合代数发展并描述了集合的基本性质和规律，集合论运算，如并集、交集、补集，以及集合的关系，如等于、包含。这门学科系统研究如何来表达和进行上述的运算和关系的操作。

## 导言

集合代数是研究集合运算和集合关系的基本性质的学科。研究这些性质可以深入探究集合的本质，也有助于实际应用。

像普通算术的表达和计算一样，集合的表达和计算可能相当复杂。通过系统研究将有助于熟练使用和理解这些表达方式并进行计算。

在算术研究方面，是通过初等代数来研究算术的运算和关系的。

例如：加法和乘法运算遵循人们看时候带吃熟知的交换律、结合律和分配律；而"小于等于"关系满足自反性、反对称性和传递性。

这些规律提供了简化计算的工具，并描述了算术的本质、运算和关系。

集合代数相当于集合论中的算术代数。它是关于集合论运算如交集、并集、补集，和集合论关系如等于、包含等的代数：本文主要介绍这些内容。对集合的基本介绍请参见集合，更详尽的内容请参见朴素集合论。

## 集合上的基本结构

集合上通常自然定义的结构包括：

二元关系

- 包含（$\subseteq$）：$A\subseteq B$ 当且仅当 $\forall e (e\in A \implies e\in B)$。
- 真包含（$\subset$）：$A\subset B$ 当且仅当 $A\subseteq B$ 且 $A\neq B$。

二元运算

- 交（$\cap$）：$A\cap B$定义为 $\{e \mid e\in A$ 且 $e\in B\}$。
- 并（$\cup$）：$A\cup B$ 定义为 $\{e \mid e\in A$ 或 $e\in B\}$。
- 差（$-$）：$A-B$ 定义为 $\{e \mid e\in A$ 且 $\neg(e\in B)\}$（亦称相对补）。
- 对称差（$\triangle$）：$A\triangle B$ 定义为 $(A-B)\cup (B-A)$。
- 补：补运算的前提是存在一个由上下文确定的全集$X$，其某个子集$A$对于$X$的补$A^c$ 定义为 $X-A$。

其它运算

- 幂集：$\mathcal{P}(A)$ 定义为 $\{E \mid E\subseteq A\}$（A 的幂集是 A 所有子集构成的集合）。
- 笛卡尔积：$X \times Y$ 定义为 $\left\{ \left( x,y \right) \mid x \in X \land y \in Y \right\}$（即所有可能的有序对组成的集合）。

特殊的集合

- 空集（$\varnothing$）：没有任何元素的集合。
- 全集：这是一个由上下文确定的集合，通常上下文中其它的集合都是它的子集。

这些二元关系和二元运算构成了集合上的基本结构，包括序结构和代数结构。

### 代数结构

代数结构是关于运算的结构。以下是集合间运算的基本性质：

交换律

- $$A \cap B = B \cap A$$
- $$A \cup B = B \cup A$$
- $$A \triangle B = B \triangle A$$

结合律

- $$(A \cap B) \cap C = A \cap (B \cap C)$$
- $$(A \cup B) \cup C = A \cup (B \cup C)$$
- $$(A \triangle B) \triangle C = A \triangle (B \triangle C)$$

分配律

- $$(A \cap B) \cup C = (A \cup C) \cap (B \cup C)$$
- $$(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$$
- $$(A -B) \cap C = (A \cap C) -(B \cap C)$$
- $$(A \triangle B) \cap C = (A \cap C) \triangle (B \cap C)$$

幂等律

- $$A \cup A = A$$
- $$A \cap A = A$$

幺元

- $A \cup \varnothing = \varnothing \cup A = A$（$\varnothing$ 是 $\cup$ 运算的幺元）
- $A \triangle \varnothing = \varnothing \triangle A = A$（$\varnothing$ 是 $\triangle$ 运算的幺元）
- $A - \varnothing = A$（$\varnothing$ 是 $-$运算的右幺元）

零元

- $A \cap \varnothing = \varnothing \cap A = \varnothing$ （$\varnothing$ 是 $\cap$ 运算的零元）
- $\varnothing -A = \varnothing$ （$\varnothing$ 是 $-$运算的左零元）

幂幺律

- $$A \triangle A = \varnothing$$

德·摩根律

- $C -(A \cup B) = (C -A) \cap (C -B)$。
- $C -(A \cap B) = (C -A) \cup (C -B)$。
- $(A \cup B)^c = A^c \cap B^c$（这条是第一条的补集形式）
- $(A \cap B)^c = A^c \cup B^c$（这条是第二条的补集形式）

吸收律

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

### 序结构

包含关系“$\subseteq$ ”有如下性质：

- 自反性：$A \subseteq A$；（任何集合都是其本身的子集）
- 反对称性：$A \subseteq B$且$B \subseteq A \iff A=B$；（这是证明两集合相等的常用手段之一）
- 传递性：$A \subseteq B$且$B \subseteq C \implies A \subseteq C$。

是集合间的一个非严格偏序关系。

真包含关系“ $\subset$ ”有如下性质：

- 反自反性：$A \subset A$不成立。
- 非对称性：$A \subset B \implies B \subset A$不成立；反之亦然。
- 传递性：$A \subset B$且$B \subset C \implies A \subset C$。

是集合间的一个严格偏序关系。

包含和真包含关系定义了集合间的一个偏序关系。在该偏序关系的意义下两者等价，通常不失一般性地将该偏序关系指为 $\subseteq$。该偏序关系还有如下的结构：

上确界运算： $\cup$

- $$A \subseteq C,B \subseteq C \implies A \cup B \subseteq C$$
- $$A \subseteq A \cup B$$

下确界运算： $\cap$

- $$C \subseteq A,C \subseteq B \implies C \subseteq A \cap B$$
- $$A \cap B \subseteq A$$

最小元（底）： $\varnothing$

- $\varnothing \subseteq A$（$\varnothing$ 是任何集合的子集）

## 集合上结构的最小定义

显然，上面的所有结果并不是独立的，大部分结果都可以从一个很小的结构推导出来。

比如很容易知道：

- 对称差可以用并和差来定义。
- 补可以用差来定义。
- 真包含关系可以用包含关系来定义。
- 包含关系可以用并，交，差之一来定义，这是因为 $A\subseteq B$等价于以下任一命题：
- $$A\cup B = B$$
- $$A\cap B = A$$
- $$A - B = \varnothing$$

因此我们完全可以用并，交，差三个运算以及它们的相关性质推导出上面所有二元运算和二元关系的性质。

当然这个“最小结构”的选择并不唯一，可以根据需要选择适当的方式。

下一个命题包含三种特殊集合：空集、全集、集合的补集，给出关于它们的两组规律。

命题 2：对全集 $\mathcal{U}$ 的任意子集 $A$，下列恒等式成立：

同一性：

- $$A \cup \varnothing = A$$
- $$A \cap \mathcal{U} = A$$

补集律：

- $$A \cup A^c = \mathcal{U}$$
- $$A \cap A^c = \varnothing$$

同一性（结合交换律）说明，就像 0 和 1 分别是加法和乘法的单位元，$\varnothing$ 和 $\mathcal{U}$ 也分别是并集和交集的单位元。

跟加法和乘法不同，并集和交集没有逆元。然而，补集律给出了类似逆运算的一元运算，集合的补集的基本性质。

上述五组性质：交换律、结合律、分配律、同一性和补集律，可以说包含了集合代数的所有内容，可以认为集合代数中所有正确的命题都是从它们得到的。

## 对偶性原理

上述命题有一个有趣的形式，就是每一组恒等式都是成对出现的。将 ∪ 和 ∩，或者 Ø 和 U 相互交换，一个恒等式就变成了相应的另一个。

这是集合代数的一个非常重要的性质，称作集合的对偶性原理。它对集合的所有真命题都有效。真命题通过相互交换 ∪ 和 ∩，Ø 和 U，改变包含符号的方向得到的对偶命题也是真的。若一个命题和其对偶命题相同，则称其为自对偶的。

## 更多关于并集和交集的定律

下列命题给出六条关于并集和交集的重要定律。

命题 3：对任意全集 $\mathcal{U}$ 的子集 $A$ 和 $B$，下列恒等式成立：

支配律：

- $$A \cup \mathcal{U} = \mathcal{U}$$
- $$A \cap \varnothing = \varnothing$$

如前所述，命题 3 里的每条定律都可以从命题 1 和命题 2 的五组基本定律推导出来。作为说明，下面给出并集的幂等律的证明。

证明：

$A \cup A$｜$= ( A \cup A) \cap \mathcal{U}$｜交集的同一律

$= ( A \cup A) \cap ( A \cup A^c)$｜并集的补集律

$= A \cup ( A \cap A^c)$｜并集对交集的分配律

$= A \cup \varnothing$｜交集的补集律

$= A$｜并集的同一律

下列证明说明，上述证明的对偶是对并集的幂等律的对偶，即交集的幂等律的证明。

证明：

$A \cap A$｜$= ( A \cap A) \cup \varnothing$｜并集的同一律

$= ( A\cap A) \cup ( A \cap A^c)$｜交集的补集律

$= A \cap ( A \cup A^c)$｜交集对并集的分配律

$= A \cap \mathcal{U}$｜并集的补集律

$= A$｜交集的同一律

## 更多关于补集的定律

下列命题给出五条关于补集的重要定律。

命题 4：设 $A$ 和 $B$ 为全集 $\mathcal{U}$ 的子集，则：

德·摩根律：

- $$(A \cup B)^c = A^c \cap B^c$$
- $$(A \cap B)^c = A^c \cup B^c$$

重补集或对合律：

- $$(A^c)^c = A$$

全集和空集的补集律：

- $$\varnothing ^c = \mathcal{U}$$
- $$\mathcal{U} ^c = \varnothing$$

注意，重补集律是自对偶的。

下一个命题也是自对偶的，说明集合的补集是唯一满足补集律的集合。也就是说，互补的特征通过补集律体现。

命题 5：设 $A$ 和 $B$ 为全集 $\mathcal{U}$ 的子集，则：

补集的唯一性：

- 若 $A \cup B = \mathcal{U}$ 且 $A \cap B = \varnothing$ 则 $B = A^c$。

## 包含的代数

下列命题说明包含是种偏序关系。

命题 6：若 $A, B, C$ 为集合，则下述成立：

自反性：

- $$A \subseteq A$$

反对称性:

- $A \subseteq B$ 且 $B \subseteq A$，当且仅当 $A = B$

传递性:

- 若 $A \subseteq B$ 且 $B \subseteq C$，则 $A \subseteq C$

下列命题说明对任意集合 $S$，$S$ 的幂集按照包含来排列是个有界格；因此，结合上述的分配律和补集律，它是一个布尔代数。

命题 7：若 $A, B, C$ 是集合 $S$ 的子集，则下述成立：

存在最小元和最大元：

- $$\varnothing \subseteq A \subseteq S$$

存在并运算:

- $$A \subseteq A \cup B$$
- 若 $A \subseteq C$ 且 $B \subseteq C$ 则 $A \cup B \subseteq C$

存在交运算:

- $$A \cap B \subseteq A$$
- 若 $C \subseteq A$ 且 $C \subseteq B$ 则 $C \subseteq A \cap B$

下列命题说明，" $A \subseteq B$ " 与各种采用并集、交集、补集的表示方法等价。

命题 8：对任意两个集合 $A$ 和 $B$，下述等价：

- $$A \subseteq B$$
- $$A \cap B = A$$
- $$A \cup B = B$$
- $$A - B = \varnothing$$
- $$B^c \subseteq A^c$$

上述命题说明，集合的包含关系可以采用并集运算或交集运算来表示，即包含关系在公理体系中是多余的。

## 相对补集的代数

下列命题给出一些关于相对补集或集合论差的恒等式。

命题 9：对任意全集 $\mathcal{U}$ 和 $\mathcal{U}$ 的子集 $A$，$B$，$C$，下列恒等式成立：

- $$C - (A \cap B) = (C - A) \cup (C - B)$$
- $$C - (A \cup B) = (C - A) \cap (C - B)$$
- $$C - (B - A) = (A \cap C) \cup (C - B)$$
- $$(B - A) \cap C = (B \cap C) - A = B \cap (C - A)$$
- $$(B - A) \cup C = (B \cup C) - (A - C)$$
- $$A - A = \varnothing$$
- $$\varnothing - A = \varnothing$$
- $$A - \varnothing = A$$
- $$B - A = A^c \cap B$$
- $$(B - A)^c = A \cup B^c$$
- $$\mathcal{U} - A = A^c$$
- $$A - \mathcal{U} = \varnothing$$

## 常用代数结构

### 半环

若集类$S$满足：

- 对交运算封闭：$\forall E,F\in S$，则 $E\cap F\in S$。
- $\forall E,F\in S$，若$E\subseteq F$，则存在$C^{0},C^{1}, \ldots ,C^{n}\in S$，使得$E\subseteq C^{0}\subseteq C^{1}\subseteq \ldots \subseteq C^{n}\subseteq F$，且$\forall 0\leq i\leq n,C^{i}-C^{i-1}\in S$；（即$E$可以通过和$S$中一些集合的无交并得到$F$）。

则$S$构成一个半环。

### 格

若集类$S$满足：

- 空集属于$S$。
- 对交运算封闭：$\forall E,F\in S$，则$E\cap F\in S$。
- 对并运算封闭：$\forall E,F\in S$，则$E\cup F\in S$。

则$S$构成一个格。

### 环，代数

非空集类S，若：

- S对集合的并和差运算封闭，即：$\forall E,F\in S \implies E\cup F\in S,E-F\in S$。
- S对集合的交和对称差运算封闭，即：$\forall E,F\in S \implies E\cap F\in S,E\triangle F\in S$。
- S对集合的交，差以及无交并运算封闭。

当且仅当$S$满足以上几个条件中任何一个时，$S$构成一个环，此时$S$被称为一个集环。

若集环$S$还满足：

- $\exists X\in S$，使得$\forall E\in S$，有$E\subseteq X$。（即$S$中的所有集合的全集$X$也在$S$中）

则$S$是$X$上的代数，称为X上的集代数。

- 从代数角度来看，集环（集代数）$S$以$\cap$ 为乘法，$\triangle$ 为加法；以空集为零元，并且由于乘法满足幂等律，$\forall E\in S,E\cap E=E\cdot E=E$，因此$S$还是布尔环（布尔代数）。
- 设$S$为一非空集类，可以知道，必存在唯一的集环R，使得$S\subseteq R$，且$\forall$ 集环$R'$使得$S\subseteq R'$有$R\subseteq R'$，则$R$称为包含$S$的最小集环或由$S$生成的集环。

### $\sigma$ 环，$\sigma$ 代数

设$S$是集环（集代数），若$S$对可列并运算封闭，则称$S$为一个σ环（σ代数）。