1.2 集合、子集与幂集

上一节把电梯允许楼层写成 $\{1,2,3,4,5,6\}$，但只把大括号当作一张状态清单。现在我们正式研究这种结构。这样做不是为了增加符号，而是为了能够准确回答：一个对象是否在清单中？两张清单是否相同？一张清单是否完全包含在另一张清单中？

本节会按以下顺序前进：

• 先学会读写一个集合，并判断元素是否属于它。

• 再比较两个集合，理解相等、基数和子集。

• 最后把“所有可能子集”收集起来，得到幂集。

集合（set）把彼此不同的对象组织成一个整体。集合中的对象叫作元素（element）。如果元素 $x$ 属于集合 $A$，写作 $x\in A$；如果不属于，写作 $x\notin A$。

读符号时可以直接翻译：

• $3\in\{1,2,3\}$ 读作“3 属于集合 $\{1,2,3\}$”。

• $5\notin\{1,2,3\}$ 读作“5 不属于集合 $\{1,2,3\}$”。

• $A=\{1,2,3\}$ 表示我们给这个集合取名为 $A$。

元素不必是数字。$C=\{\text{红},\text{蓝},\text{黄}\}$ 是颜色集合；$M=\{\text{停止},\text{运行}\}$ 是机器模式集合；元素甚至可以是其他集合。

集合只关心成员资格，不关心书写顺序或重复次数。因此

最后一个写法虽然多余，却没有创造新的元素。三个集合都含有相同成员，所以相等。

集合中元素的数量叫作基数（cardinality），写作 $|A|$。例如，若 $A=\{1,2,3\}$，则 $|A|=3$。重复书写不会增加基数，因此 $|\{1,1,2,3\}|$ 仍然等于 3。

判断两个有限集合是否相等，可以使用一个可靠步骤：

• 检查左边的每个元素是否都在右边。

• 再检查右边的每个元素是否都在左边。

两个方向都通过，集合才相等。只比较基数不够，因为 $\{1,2\}$ 和 $\{3,4\}$ 的基数相同，但成员不同。

两种常见写法

我们已经使用了列举法：直接把元素写在大括号中。元素很多时，可以改用条件描述。例如

竖线 $\mid$ 读作“满足条件”。整句表示：“$E$ 是所有满足‘$x$ 是 1 到 8 之间偶数’这一条件的 $x$ 组成的集合。”逐个检查后得到 $E=\{2,4,6,8\}$。这叫作描述法或集合构造式。

元素、集合与子集

必须区分“一个元素属于集合”和“一个集合包含于另一个集合”。若

那么 $a\in S$，而 $\{a\}\subseteq S$。左边的 $a$ 是元素，$\{a\}$ 是只含一个元素的集合，这两个对象不相同。

可以把两种符号理解为两类问题：

例如，当 $S=\{a,b,c\}$ 时，$a\in S$ 为真，$\{a\}\subseteq S$ 也为真，但 $\{a\}\in S$ 为假，因为 $S$ 的三个元素是 $a,b,c$，其中没有集合 $\{a\}$。

若集合 $A$ 的每个元素也属于集合 $B$，就说 $A$ 是 $B$ 的子集（subset），写作

要推翻这个命题，只需找出一个见证元素：某个 $x\in A$ 但 $x\notin B$。若 $A\subseteq B$ 且 $A\ne B$，则 $A$ 是 $B$ 的真子集（proper subset），写作 $A\subset B$。

判断有限集合的子集关系时，可以机械地执行下面的检查：

• 从左侧集合取出第一个元素。

• 在右侧寻找它。找不到时立即停止，这个元素就是反例。

• 找到时继续检查左侧下一个元素。

• 左侧全部检查完毕仍未失败，子集关系成立。

例如，$A=\{1,3\}$、$B=\{1,2,3,4\}$。先在 $B$ 中找到 1，再找到 3，所以 $A\subseteq B$。反过来检查 $B\subseteq A$ 时，元素 2 不在 $A$ 中，因此 2 是推翻命题的见证。

每个集合都是自己的子集，因为集合中的每个元素当然也属于自身。所以 $A\subseteq A$ 总是成立，但 $A\subset A$ 不成立：真子集还要求两个集合不相等。

子集锻造炉把定义变成了约束系统。它不会只告诉你“错误”，还会寻找破坏 $A\subseteq B$ 的见证元素。这个思路以后会反复出现：证明全称命题需要覆盖所有情况，推翻它通常只需一个反例。

在实验中尝试“不可比较”目标。如果 $A$ 中存在一个不属于 $B$ 的元素，同时 $B$ 中也存在一个不属于 $A$ 的元素，那么两个方向的子集关系都失败。集合不必总是一大一小地套在一起。

空集与幂集

空集（empty set）没有任何元素，写作 $\emptyset$ 或 $\{\}$。它是每个集合的子集。原因不是“空集藏在所有集合里面”，而是不存在任何空集元素能够违反子集条件。

用刚才的检查步骤理解这一点：检查 $\emptyset\subseteq A$ 时，左侧没有第一个元素，也就不可能找到失败见证。检查过程直接完成，所以命题成立。这种“没有反例，因此条件成立”的情况以后会在逻辑中正式解释。

集合 $S$ 的幂集（power set）是由 $S$ 的全部子集组成的集合：

注意幂集中的元素本身是集合。若 $S=\{a,b\}$，则

每个原集合元素都有“选入子集”或“不选入子集”两个独立选择。若 $|S|=n$，则

先不背公式，亲手构造 $S=\{a,b\}$ 的幂集：

• 两个元素都不选，得到 $\emptyset$。

• 只选 $a$，得到 $\{a\}$。

• 只选 $b$，得到 $\{b\}$。

• 两个都选，得到 $\{a,b\}$。

可以把“选入”记为 1，“不选”记为 0：

两个位置各有两种选择，所以共有 $2\cdot2=4=2^2$ 种结果。若有 $n$ 个元素，就有 $n$ 个二元位置，因此出现 $2^n$ 个子集。这是公式背后的原因。

星座把子集按基数分层。第 $k$ 层包含所有大小为 $k$ 的子集，数量为 $\binom{n}{k}$。所有层合起来必须覆盖整个幂集：

这个等式目前可以从“左边按大小分组，右边按独立开关计数”来理解。第 6 章会系统学习其中的计数方法。

符号 $\binom{n}{k}$ 在这里是一个预告，表示“从 $n$ 个不同元素中恰好选 $k$ 个的方法数”。你现在不需要会计算一般公式，实验也只要求你观察：基数相同的子集位于同一层。第 6 章会从零推导它。

通向下一节

现在我们能够创建集合、检查成员、比较子集并枚举全部子集。但现实问题通常需要把两张清单组合起来，例如“参加课程 A 或课程 B 的学生”，或“每个用户可以执行哪些操作”。下一节从成员条件出发，引入并集、交集、差集和笛卡尔积。所有新运算都会建立在本节的 $\in$ 与 $\subseteq$ 之上。