集合运算 | Codeboy's Blog

形式陈述

对集合 $A,B$ ，基本二元运算由成员条件定义：

\begin{aligned} A\cup B&=\{x:x\in A\lor x\in B\},\\ A\cap B&=\{x:x\in A\land x\in B\},\\ A\setminus B&=\{x:x\in A\land x\notin B\},\\ A\mathbin\triangle B&=(A\setminus B)\cup(B\setminus A). \end{aligned}

补集必须相对于固定环境集合 $U$ 才有意义。若 $A\subseteq U$ ，记

A^{\mathsf c}=U\setminus A.

对于集合索引族 $(A_i)_{i\in I}$ ，定义

\bigcup_{i\in I}A_i = \{x:\exists i\in I, x\in A_i\}.

若 $I\ne\varnothing$ ，还可定义

\bigcap_{i\in I}A_i = \{x:\forall i\in I, x\in A_i\}.

在 ZF 中，前一个集合由替换与并集公理获得；非空交集可以在 $\bigcup_iA_i$ 内分离出来。空并等于 $\varnothing$ 。若 $I=\varnothing$ ，全称成员条件对每个对象都成立，会描述“所有集合”而非一个集合，所以绝对的空交没有集合值。只有先固定 $U$ 且把各 $A_i$ 视为 $U$ 的子集时，才约定相对空交为 $U$ 。

直觉

固定一个候选元素 $x$ ，命题 $x\in A$ 与 $x\in B$ 各提供一个真值。并、交、相对补依次把 $\lor$ 、 $\land$ 、 $\neg$ 搬到集合层；对称差则记录两个真值恰有一个成立的位置。集合恒等式因而可以逐元素降为命题逻辑恒等式，再由外延性返回集合相等。

补集依赖论域，因为“排除 $A$ ”还没有说明剩余对象从哪里取。若讨论整数，偶数的补集通常指奇数；若论域改成实数，同一偶数集的补集还包含全部非整数。省略 $U$ 会把一个相对运算写成貌似绝对的运算。

索引并与索引交分别对应“至少满足一个局部条件”和“同时满足全部局部条件”。这个量词差别也解释了边界：空索引下存在量词为假，所以空并自然为空；全称量词为空真，却没有一个包含所有对象的全集可充当绝对空交。

例子与边界

设软件发布流程中的三个检查集合分别是：通过单元测试的提交 $T$ 、通过安全扫描的提交 $S$ 、获得人工批准的提交 $R$ 。能够发布的集合是

T\cap S\cap R,

而至少触发一项告警的提交属于三个失败集合的并。这个写法只合并判定结果；它不会说明检查怎样执行，也不会假定三项结果相互独立。

差集有方向。 $A\setminus B$ 保留只在 $A$ 一侧的元素，通常与 $B\setminus A$ 不同；对称差 $A\triangle B$ 才把两侧差异平等处理。它满足

x\in A\triangle B \iff (x\in A)\mathbin{\oplus}(x\in B),

所以适合描述两个版本、两个标签集或两个边集在哪些位置发生变化。

交集族还需要区分“交集为空”和“两两不交”。三个集合可以每两者都有公共元素，却没有三者共同元素；也可以总交非空，因而每对当然相交。两两不交要求 $A_i\cap A_j=\varnothing$ 对所有 $i\ne j$ ，其量词比 $\bigcap_iA_i=\varnothing$ 强得多。

推论与应用

集合代数的公式可由逐元素推导。例如，

\begin{aligned} x\in A\cap(B\cup C) &\iff x\in A\land(x\in B\lor x\in C)\\ &\iff (x\in A\land x\in B)\lor(x\in A\land x\in C)\\ &\iff x\in(A\cap B)\cup(A\cap C). \end{aligned}

外延性于是给出分配律。用同一方法可证吸收律、幂等律以及相对于 $U$ 的 De Morgan 律

\left(\bigcup_iA_i\right)^{\mathsf c}=\bigcap_iA_i^{\mathsf c}, \qquad \left(\bigcap_iA_i\right)^{\mathsf c}=\bigcup_iA_i^{\mathsf c}.

固定 $U$ 后，幂集 $\mathcal P(U)$ 配上 $\cup,\cap,{}^{\mathsf c}$ 成为布尔代数。拓扑从中选出对任意并和有限交封闭的子族； $\sigma$ -代数改为对补和可数并封闭。两类结构复用集合运算，却通过不同闭包量词表达不同需求。

函数逆像严格保留这些逻辑运算：

f^{-1}\!\left[\bigcup_iA_i\right]=\bigcup_i f^{-1}[A_i], \qquad f^{-1}[B\setminus A]=f^{-1}[B]\setminus f^{-1}[A].

原因是逆像只把“ $f(x)$ 是否属于某集合”代回成员条件。函数像虽然保留并，却可能因不同输入合并到同一输出而破坏交与差，这一不对称在连续性和可测性的逆像定义中反复出现。

参考资料

Paul R. Halmos, Naive Set Theory, Dover, 2017, §§4–5。
Herbert B. Enderton, Elements of Set Theory, Academic Press, 1977, Chapters 1–2。
Daniel J. Velleman, How to Prove It, 3rd ed., Cambridge University Press, 2019, Chapter 3。

形式陈述 ​

反向链接

形式陈述