集合、关系与函数

这一章教你三件事：用集合的语言精确描述研究对象，用关系的语言描述对象之间的结构，用函数的语言描述对象之间的对应。学完你能做三件具体的事：用元素论证证明像德摩根律这样的集合恒等式；判定一个具体关系是否自反、对称、反对称、传递，并说明它为什么构成等价关系或偏序；构造双射来比较两个无限集合的大小。

2.1 集合

集合是不讲顺序、不含重复元素的一堆对象的总称，其中的对象叫元素。表示一个集合有两条路：

• 外延表示：把元素全部列出来，如 $A=\{1,2,3\}$；
• 内涵表示：用性质刻画，如 $A=\{x\in {\mathbb{Z}}^{+}\mid x\le 3\}$（竖线后面是元素要满足的条件）。${\mathbb{Z}}^{+}$ 表示正整数集，$\mathbb{R}$ 表示实数集，$\mathbb{N}$ 表示自然数集 $\{0,1,2,\dots \}$。

$a\in A$ 读作”$a$ 是 $A$ 的元素”，$a\notin A$ 读作”$a$ 不是”。若 $A$ 的每个元素都在 $B$ 中，称 $A$ 是 $B$ 的子集，记作 $A\subseteq B$；$A=B$ 当且仅当 $A\subseteq B$ 且 $B\subseteq A$。$A⊊B$ 表示真子集（子集且不相等）。空集 $\varnothing$ 不含任何元素，它是任何集合的子集——这一点由定义直接成立：”$\varnothing$ 的每个元素都在 $A$ 中”是一句空真（vacuously true）的命题。

幂集

集合 $A$ 的幂集 $P(A)$（也记作 $2^A$）是 $A$ 的所有子集构成的集合。有限集合的幂集大小有一个干净的公式：

定理. 若 $|A|=n$，则 $|P(A)|=2^n$。

证明. 构造一个从 $P(A)$ 到全体函数 $A\to \{0,1\}$ 的双射：每个子集 $S\subseteq A$ 对应它的特征函数 ${\chi }_S$，${\chi }_S(a)=1$ 当 $a\in S$，否则为 $0$。不同的子集给出不同的特征函数（单射），每个特征函数都是某个子集的特征函数（满射），所以这是一一对应。而函数 $A\to \{0,1\}$ 的个数是 $2^n$：定义这样的函数要对 $A$ 中 $n$ 个元素逐个独立决定取值，每次有 $2$ 种选择，由乘法原理共 $2^n$ 种。故 $|P(A)|=2^n$。$■$

直觉版：列子集时每个元素只有”进来”和”不进来”两种状态，$n$ 个元素的状态组合共 $2^n$ 种，每种组合恰好对应一个子集。

并、交、差、补与德摩根律

设 $A,B$ 是全集 $U$ 的子集：

• 并 $A\cup B=\{x\mid x\in A\text{或}x\in B\}$；
• 交 $A\cap B=\{x\mid x\in A\text{且}x\in B\}$，$A\cap B=\varnothing$ 时称两集不交；
• 差 $A\setminus B=\{x\mid x\in A\text{且}x\notin B\}$；
• 补 $\overline{A}=U\setminus A=\{x\in U\mid x\notin A\}$。

德摩根律在集合上的版本与逻辑上的一模一样（这不是巧合，见 2.4 节布尔代数的预告）：

$$\overline{A\cup B}=\overline{A}\cap \overline{B},\overline{A\cap B}=\overline{A}\cup \overline{B}.$$

用元素论证证明第一条：任取 $x$，

$$x\in \overline{A\cup B}⟺x\notin A\cup B⟺x\notin A\text{且}x\notin B⟺x\in \overline{A}\text{且}x\in \overline{B}⟺x\in \overline{A}\cap \overline{B}.$$

每一步都只是把集合运算的定义展开：第一步和最后一步用补集与交集的定义，中间一步用”不属于并集”等价于”两个都不属于”。链条两端刻画的集合相同，故两集合相等。集合等式的标准证法就是这样一串”任取 $x$，$x$ 在左边 $⟺$ $x$ 在右边”的等价推导。

笛卡尔积

$A$ 与 $B$ 的笛卡尔积是有序对构成的集合：

$$A\times B=\{(a,b)\mid a\in A,b\in B\},$$

其中 $(a,b)$ 是有序对——顺序有意义，$(a,b)\ne (b,a)$ 除非 $a=b$。若 $|A|=m,|B|=n$，则 $|A\times B|=mn$。$\mathbb{R}\times \mathbb{R}={\mathbb{R}}^2$ 就是平面，空间数据里每个点的坐标正是 ${\mathbb{R}}^2$ 或 ${\mathbb{R}}^3$ 的元素；一张属性表则是 $n$ 个 $\mathbb{R}$ 的笛卡尔积的子集。

2.2 关系及其四个性质

设 $A,B$ 是集合。从 $A$ 到 $B$ 的关系 $R$ 是 $A\times B$ 的一个子集：$R\subseteq A\times B$。若 $(a,b)\in R$，写作 $aRb$，读作”$a$ 与 $b$ 有关系 $R$”。$A$ 上的关系指 $A\times A$ 的子集。定义里没有任何神秘之处：关系就是一张”哪些对子算相关”的清单。

$A$ 上的关系 $R$ 有四个基本性质，判定任何具体关系时都按这四条逐一检查：

• 自反：对每个 $a\in A$ 都有 $(a,a)\in R$；
• 对称：若 $(a,b)\in R$ 则 $(b,a)\in R$；
• 反对称：若 $(a,b)\in R$ 且 $(b,a)\in R$，则 $a=b$（等价说法：不存在两个不同元素互相都有关系）；
• 传递：若 $(a,b)\in R$ 且 $(b,c)\in R$，则 $(a,c)\in R$。

注意”对称”与”反对称”不矛盾也不互补：一个关系可以同时是对称且反对称的（例如只含对角线 $R=\{(a,a)\mid a\in A\}$），也可以两者都不是。

关系图：把 $A$ 的元素画成点，$(a,b)\in R$ 就从 $a$ 到 $b$ 画一条有向边。自反表现为每个点上有自环；对称表现为所有边都是双向的；反对称表现为不存在双向边；传递表现为”只要有 $a\to b$ 和 $b\to c$，就必须补一条 $a\to c$”。

关系矩阵：把 $A$ 的元素按序编号，定义 $n\times n$ 的 $0$-$1$ 矩阵 $M_R$，其第 $(i,j)$ 元为 $1$ 当且仅当 $(a_i,a_j)\in R$。自反 $⟺$ 对角线全为 $1$；对称 $⟺$ 矩阵是对称矩阵（$M_R=M_R^T$）；反对称 $⟺$ 当 $i\ne j$ 时 $M_{ij}$ 与 $M_{ji}$ 不同时为 $1$。矩阵表示的好处是关系复合可以翻译成矩阵乘法：$M_{R_1\circ R_2}=M_{R_1}\odot M_{R_2}$，其中 $\odot$ 是布尔矩阵乘法——乘法是逻辑与，加法是逻辑或。

例题 2.1 设 $A=\{1,2,3\}$，$R=\{(1,1),(2,2),(1,2),(2,3)\}$。判断 $R$ 满足上述四个性质中的哪些。

解. 逐条检查。

自反：需要 $(1,1),(2,2),(3,3)$ 都在 $R$ 中，但 $(3,3)\notin R$，故不自反。

对称：$(1,2)\in R$，但 $(2,1)\notin R$，故不对称。（反对称与对称互不影响，继续检查。）

反对称：$R$ 中成对出现的只有 $(1,1),(2,2)$ 这类对角元，任何 $i\ne j$ 的两个不同元素之间至多一个方向有关系（$(1,2)$ 在而 $(2,1)$ 不在，$(2,3)$ 在而 $(3,2)$ 不在），满足反对称的定义，故反对称成立。

传递：$(1,2)\in R$ 且 $(2,3)\in R$，但 $(1,3)\notin R$，故不传递。

结论：$R$ 仅满足反对称。$■$

2.3 等价关系与划分

$A$ 上同时满足自反、对称、传递的关系叫等价关系。它的重要性来自下面的定理：等价关系与集合的一种分解方式——划分——是一回事。

集合 $A$ 的划分是把 $A$ 分成若干非空子块 $\{A_1,\dots ,A_k\}$，使得每两个不同子块不交（$A_i\cap A_j=\varnothing$），且所有子块的并是整个 $A$。

定理. 设 $A$ 是非空集合。(i) $A$ 上的每个等价关系 $R$ 决定一个划分：按”$aRb$ 当且仅当 $a,b$ 同块”把 $A$ 分成等价类；(ii) $A$ 的每个划分决定一个等价关系：$aRb$ 当且仅当 $a$ 与 $b$ 在同一个子块中。两个构造互为逆操作。

证明思路. (i) 给定等价关系 $R$，对每个 $a\in A$ 定义它的等价类 $[a]=\{x\in A\mid aRx\}$。需要验证两点：等价类们覆盖 $A$（由自反性，$a\in [a]$，每个元素至少落在自己的类里）；不同的等价类不相交。后者用反证：若 $[a]\cap [b]\ne \varnothing$，取公共元素 $c$，则 $aRc$ 且 $bRc$。由对称性 $cRb$，再由传递性 $aRb$。于是任取 $x\in [b]$，有 $bRx$，结合 $aRb$ 得 $aRx$，即 $x\in [a]$，故 $[b]\subseteq [a]$；对称地 $[a]\subseteq [b]$。所以两个相交的等价类必然相等。这正是一个划分。

(ii) 给定划分，定义”$aRb$ 当且仅当 $a,b$ 同块”。自反：$a$ 与 $a$ 显然同块。对称：同块关系不分先后。传递：$a$ 与 $b$ 同块、$b$ 与 $c$ 同块，则 $a,b,c$ 都在 $b$ 所在的那一块里，故 $a$ 与 $c$ 同块。三公理全由”同块”这个定义直接读出。

最后，两个构造互逆：从 $R$ 出发分出等价类，再按同块定义关系，得到的仍是 $R$（$aRb⟺a,b$ 同类 $⟺b\in [a]⟺aRb$）；从划分出发定义关系再取等价类，每个等价类恰好是原划分的一个块。$■$

等价关系是”分类”的数学形式化：任何合理的分类标准（同余、同构、同一簇）都应当满足三公理，否则分出来的类会重叠或漏掉元素——这正是聚类算法里”相似度不满足传递性时结果不稳定”的根本原因。

2.4 偏序、Hasse 图与格

$A$ 上自反、反对称、传递的关系叫偏序关系，$(A,R)$ 叫偏序集（poset）。偏序给出一种”有先后但不全能比”的次序：$aRb$ 读作”$a$ 先于 $b$“或”$a$ 小于等于 $b$“（常直接写作 $a⪯b$）。

例题 2.2 证明正整数集 ${\mathbb{Z}}^{+}$ 上的整除关系 $a\mid b$（即存在 $k\in {\mathbb{Z}}^{+}$ 使 $b=ka$）是偏序。

解. 逐条验证三公理。

自反：$a=1\cdot a$，故 $a\mid a$ 对任意正整数成立。

反对称：设 $a\mid b$ 且 $b\mid a$，则存在正整数 $k,l$ 使 $b=ka$ 且 $a=lb$。代入得 $a=lka$。两边除以正整数 $a$ 得 $lk=1$。两个正整数之积为 $1$，只能 $l=k=1$，故 $a=b$。（注意这一步用到了”在正整数范围内”：若允许负数，$2\mid -2$ 且 $-2\mid 2$ 但 $2\ne -2$，反对称就垮了。）

传递：设 $a\mid b$ 且 $b\mid c$，则 $b=ka,c=lb$，于是 $c=(lk)a$，即 $a\mid c$。

三公理均成立，故 $({\mathbb{Z}}^{+},\mid )$ 是偏序集。$■$

偏序集中若任意两个元素都能比较（$a⪯b$ 与 $b⪯a$ 至少一个成立），称为全序（或线序）。${\mathbb{Z}}^{+}$ 上整除关系不是全序（$2$ 与 $3$ 互不整除）；实数的小于等于是全序。

Hasse 图是偏序集的简化画法：去掉所有自环；把传递性”蕴含”的边去掉（若 $a⪯b⪯c$，只保留 $a$ 到 $b$、$b$ 到 $c$ 的边，删去 $a$ 到 $c$）；规定”大”在上、“小”在下，并省略箭头。于是每个有限偏序集被压成一张无向图，传递性与自反性由读图规则隐含。

在偏序集 $(A,⪯)$ 中，子集 $S\subseteq A$ 的最大元是 $S$ 中比 $S$ 内一切元素都大的元素（注意它必须在 $S$ 内），$S$ 中不存在比它更小的其他元素的元素叫极小元（极小元可能不唯一）。若 $u\in A$（不必在 $S$ 中）满足 $u$ 比 $S$ 中一切元素大，称 $u$ 是 $S$ 的一个上界；下界类似。$S$ 的所有上界中最小的那个叫最小上界（上确界），下界中最大的叫最大下界（下确界）——它们不一定存在。

格是任意两个元素都有最小上界与最大下界的偏序集。格满足一组与集合运算同构的运算律（交并幂等、交换、结合、吸收），这正是第 8 章代数结构要展开的内容：格连同布尔代数一起，解释了为什么集合的 $\cap ,\cup$、逻辑的 $\wedge ,\vee$ 服从同一套规则。本章只要记住这个预告即可。

2.5 函数

从 $A$ 到 $B$ 的函数 $f:A\to B$ 是一种特殊的关系 $f\subseteq A\times B$：对每个 $a\in A$，恰存在一个 $b\in B$ 使 $(a,b)\in f$，记作 $f(a)=b$。$A$ 叫定义域，$B$ 叫陪域。函数与关系的差别就在”恰有一个”这四个字上：关系允许一对多或多对零。

• 像：对 $S\subseteq A$，$f(S)=\{f(a)\mid a\in S\}\subseteq B$ 是 $S$ 的像；$f(A)$ 叫值域。
• 原像：对 $T\subseteq B$，$f^{-1}(T)=\{a\in A\mid f(a)\in T\}\subseteq A$ 是 $T$ 的原像。注意原像对任何函数都有定义（它是一个集合，可能为空），不要求 $f$ 可逆。

函数按覆盖方式分三类，判定双射是本章的基本功：

• 单射：$f(a_1)=f(a_2)\Rightarrow a_1=a_2$（不同输入给不同输出）；等价地 $a_1\ne a_2\Rightarrow f(a_1)\ne f(a_2)$；
• 满射：$f(A)=B$，即每个 $b\in B$ 都是某个 $a$ 的像；
• 双射：既单又满，即一一对应。

有限集上有一个好用的计数判据：若 $|A|=|B|$ 有限，则 $f:A\to B$ 是单射当且仅当它是满射，因而单射、满射、双射三者等价。

复合：$f:A\to B$、$g:B\to C$ 的复合 $g\circ f:A\to C$ 定义为 $(g\circ f)(a)=g(f(a))$。复合保持单射与满射：$g\circ f$ 单射蕴含 $f$ 单射，$g\circ f$ 满射蕴含 $g$ 满射。复合满足结合律，一般不满足交换律。

逆函数的存在性有精确的判据：

定理. $f:A\to B$ 有逆函数（即存在 $g:B\to A$ 使 $g\circ f={\mathrm{id}}_A$ 且 $f\circ g={\mathrm{id}}_B$）当且仅当 $f$ 是双射。

证明. （必要性）设 $f$ 有逆 $g$。单射：若 $f(a_1)=f(a_2)$，两边作用 $g$ 得 $g(f(a_1))=g(f(a_2))$，即 $a_1=a_2$。满射：任取 $b\in B$，$b=f(g(b))$，故 $b$ 是 $g(b)$ 的像。

（充分性）设 $f$ 双射。定义 $g:B\to A$：$g(b)=$ 满足 $f(a)=b$ 的那个 $a$。这个定义合法因为满射保证这样的 $a$ 存在，单射保证它唯一。验证：$(g\circ f)(a)=g(f(a))=a$（$a$ 正是 $f(a)$ 的唯一原像），$(f\circ g)(b)=f(g(b))=b$（由 $g$ 的定义）。故 $g$ 是 $f$ 的逆，记作 $f^{-1}$。$■$

基数：无限集的大小

两个集合等势（有相同的基数）当且仅当它们之间存在双射——这个定义对有限集和无限集一视同仁，是 Cantor 的贡献。称一个无限集可数（countably infinite），如果它与 $\mathbb{N}$ 等势；直觉是”可以排成一个序列”。反直觉的结论是：无限集的真子集可以和它本身等势。

例题 2.3 构造双射证明 $\mathbb{N}$ 与正偶数集 $E=\{0,2,4,\dots \}$ 等势。

解. 定义 $f:\mathbb{N}\to E$，$f(n)=2n$。

单射：若 $f(n_1)=f(n_2)$，即 $2n_1=2n_2$，两边除以 $2$ 得 $n_1=n_2$。

满射：任取 $m\in E$，由 $E$ 的定义存在 $k\in \mathbb{N}$ 使 $m=2k$，于是 $f(k)=2k=m$，$m$ 有原像 $k$。

既单又满，故 $f$ 是双射，$\mathbb{N}$ 与 $E$ 等势。$■$

并非所有无限集都可数：Cantor 的对角线法（diagonalization）证明实数集 $\mathbb{R}$ 不可数——把任何 $\mathbb{N}$ 到 $(0,1)$ 的对应列成表，沿对角线构造一个与表中每一项都不同的实数，它就漏在表外，故不存在双射。方法的名字与结论值得记住，证明本身放在进一步的读物里。

2.6 常见错误

错误 1：把”对称且传递”当等价关系。 等价关系要求自反、对称、传递三条，缺一不可。对称且传递的关系可以不自反。反例：取 $A=\{1,2,3\}$，$R=\{(1,1),(2,2),(1,2),(2,1)\}$。$R$ 对称（每条非对角边都有反向边），也传递（仅有的”两步链”是 $1\to 2\to 1$，其首尾 $1\to 1$ 在 $R$ 中），但它不是自反的，因为 $(3,3)\notin R$——$3$ 与任何元素都没有关系。注意这类反例的构造规律：关系在 $\{1,2\}$ 这个子集内部是”满”的，在 $3$ 上完全为空。正因为这个漏洞常见，有些教材把等价关系定义成”自反关系上的对称传递关系”。

错误 2：混淆逆关系与逆函数。 任何关系 $R\subseteq A\times B$ 都有逆关系 $R^{-1}=\{(b,a)\mid (a,b)\in R\}\subseteq B\times A$，无条件存在。但 $f^{-1}$ 作为函数要求每个 $b\in B$ 恰好有一个原像——这正是双射的定义。$f(x)=x^2:\mathbb{R}\to \mathbb{R}$ 的逆关系是"$\pm \sqrt{y}$"，它对正数 $y$ 给出两个值、对负数 $y$ 不给值，所以不是函数；只有限制定义域（如 ${\mathbb{R}}_{\ge 0}$）并相应取陪域，才能得到逆函数。另外，$f^{-1}(T)$ 表示原像集合，对任意函数都合法，不要看到 $f^{-1}$ 的记号就以为 $f$ 可逆。

2.7 练习

练习 2.1 写出 $A=\{a,b,c\}$ 的幂集 $P(A)$ 的全部元素，并验证 $|P(A)|=2^3=8$。

答案：$P(A)=\{\varnothing ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$。按子集大小分组计数：$0$ 元子集 $1$ 个、$1$ 元子集 $3$ 个、$2$ 元子集 $3$ 个、$3$ 元子集 $1$ 个，合计 $1+3+3+1=8=\left(\genfrac{}{}{0ex}{}{3}{0}\right)+\left(\genfrac{}{}{0ex}{}{3}{1}\right)+\left(\genfrac{}{}{0ex}{}{3}{2}\right)+\left(\genfrac{}{}{0ex}{}{3}{3}\right)=2^3$。

练习 2.2 设 $A=\{1,2,3,4\}$，$R=\{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(2,3),(3,2)\}$。判断 $R$ 是否自反、对称、反对称、传递，是否为等价关系。

答案：自反成立（对角线四个元素全在）。对称成立（$(1,2)$ 与 $(2,1)$、$(2,3)$ 与 $(3,2)$ 成对出现）。反对称不成立（$1\ne 2$ 但 $(1,2),(2,1)$ 都在）。传递不成立：$(1,2)\in R$ 且 $(2,3)\in R$，但 $(1,3)\notin R$。故不是等价关系，只满足自反与对称。

练习 2.3 画出偏序集 $(\{1,2,3,6,12\},\mid )$ 的 Hasse 图，指出最大元、最小元，并求子集 $\{2,3\}$ 的上界与最小上界。

答案：Hasse 图共四层：$1$ 在最底；$2,3$ 在第二层，分别与 $1$ 相连；$6$ 在第三层，与 $2,3$ 相连；$12$ 在最顶，与 $6$ 相连（边 $1-6$、$2-12$、$3-12$ 被传递性省略）。最小元是 $1$（整除所有元素），最大元是 $12$（被所有元素整除）。$\{2,3\}$ 的上界须同时被 $2$ 和 $3$ 整除且在集合中：$6$ 与 $12$；最小上界是 $6$。

练习 2.4 判断 $f:\mathbb{R}\to \mathbb{R}$，$f(x)=x^2$ 是否单射、满射。若否，如何限制定义域与陪域使它成为双射？

答案：不单射：$f(1)=f(-1)=1$。不满射：$-1$ 没有原像（任何实数平方非负）。限制为 $f:{\mathbb{R}}_{\ge 0}\to {\mathbb{R}}_{\ge 0}$ 后：单射，因为 $x_1^2=x_2^2$ 且 $x_1,x_2\ge 0$ 蕴含 $x_1=x_2$；满射，因为任意 $y\ge 0$ 有原像 $\sqrt{y}$。故这是双射，逆函数为 $f^{-1}(y)=\sqrt{y}$。

学习路径

• 返回 离散数学总览
• 返回 数学基础专题首页
• PREV：命题逻辑与证明
• NEXT：组合计数