集合代数

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

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

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

例如：加法和乘法运算遵循人们看时候带吃熟知的交换律、结合律和分配律；而"小于等于"关系满足自反性、反对称性和传递性。 这些规律提供了简化计算的工具，并描述了算术的本质、运算和关系。

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

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

二元关系

• 包含（${\displaystyle \subseteq }$）：${\displaystyle A\subseteq B}$ 当且仅当 ${\displaystyle \forall e(e\in A\implies e\in B)}$；
• 真包含（${\displaystyle \subset }$）：${\displaystyle A\subset B}$ 当且仅当 ${\displaystyle A\subseteq B}$ 且 ${\displaystyle A\neq B}$；

二元运算

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

其它运算

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

特殊的集合

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

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

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

比如很容易知道：

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

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

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

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

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

同一性：

• ${\displaystyle A\cup \varnothing =A}$
• ${\displaystyle A\cap {\mathcal {U}}=A}$

补集律：

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

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

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

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

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

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

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

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

支配律：

• ${\displaystyle A\cup {\mathcal {U}}={\mathcal {U}}}$
• ${\displaystyle A\cap \varnothing =\varnothing }$

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

证明：

${\displaystyle A\cup A}$	${\displaystyle =(A\cup A)\cap {\mathcal {U}}}$		交集的同一律
	${\displaystyle =(A\cup A)\cap (A\cup A^{c})}$		并集的补集律
	${\displaystyle =A\cup (A\cap A^{c})}$		并集对交集的分配律
	${\displaystyle =A\cup \varnothing }$		交集的补集律
	${\displaystyle =A}$		并集的同一律

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

证明：

${\displaystyle A\cap A}$	${\displaystyle =(A\cap A)\cup \varnothing }$		并集的同一律
	${\displaystyle =(A\cap A)\cup (A\cap A^{c})}$		交集的补集律
	${\displaystyle =A\cap (A\cup A^{c})}$		交集对并集的分配律
	${\displaystyle =A\cap {\mathcal {U}}}$		并集的补集律
	${\displaystyle =A}$		交集的同一律

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

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

德·摩根律：

• ${\displaystyle (A\cup B)^{c}=A^{c}\cap B^{c}}$
• ${\displaystyle (A\cap B)^{c}=A^{c}\cup B^{c}}$

重补集或对合律：

• ${\displaystyle (A^{c})^{c}=A}$

全集和空集的补集律：

• ${\displaystyle \varnothing ^{c}={\mathcal {U}}}$
• ${\displaystyle {\mathcal {U}}^{c}=\varnothing }$

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

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

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

补集的唯一性：

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

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

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

自反性：

• ${\displaystyle A\subseteq A}$

反对称性:

• ${\displaystyle A\subseteq B}$ 且 ${\displaystyle B\subseteq A}$，当且仅当 ${\displaystyle A=B}$

传递性:

• 若 ${\displaystyle A\subseteq B}$ 且 ${\displaystyle B\subseteq C}$，则 ${\displaystyle A\subseteq C}$

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

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

存在最小元和最大元：

• ${\displaystyle \varnothing \subseteq A\subseteq S}$

存在并运算:

• ${\displaystyle A\subseteq A\cup B}$
• 若 ${\displaystyle A\subseteq C}$ 且 ${\displaystyle B\subseteq C}$ 则 ${\displaystyle A\cup B\subseteq C}$

存在交运算:

• ${\displaystyle A\cap B\subseteq A}$
• 若 ${\displaystyle C\subseteq A}$ 且 ${\displaystyle C\subseteq B}$ 则 ${\displaystyle C\subseteq A\cap B}$

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

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

• ${\displaystyle A\subseteq B}$
• ${\displaystyle A\cap B=A}$
• ${\displaystyle A\cup B=B}$
• ${\displaystyle A-B=\varnothing }$
• ${\displaystyle B^{c}\subseteq A^{c}}$

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

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

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

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

• 集合
• 朴素集合论
• 公理集合论