集合、关系与函数

本课程的语言

下一课借助一个函数，即后继函数，来定义自然数；它是单射，并且取不到 $1$。下一单元把整数和有理数构造为一个等价关系的等价类；组合学的课用双射定义元素的个数；自然数的顺序是一个序关系；第三单元对实函数作复合并求逆。所有这些词语都属于同一种语言，在使用之前宜先把它确定下来，连同课程以后要引用的最初几个定理。

应当说明哪些内容是提前使用的。例子中使用较小的自然数及其顺序、加法、乘法、整除性和除法的余数，就像在学校里学到的那样。下一课借助皮亚诺公理定义自然数，本单元的各课定义这些运算并证明它们的性质，而不使用本课的任何例子，因此不存在循环论证。本课的任何定理都不依赖于例子：数只是用来观察定理如何起作用。

承认的内容

集合是一些对象的总体，这些对象称为它的元素；写 $a \in A$ 表示 $a$ 属于 $A$，写 $a \notin A$ 表示否定这一点。集合与属于关系不加定义：它们是原始概念，正如算术中的 $1$ 与后继。然而，并不是每个性质都确定一个集合。假如存在集合 $R$，由所有不属于自身的集合组成，那么「$R$ 是否属于 $R$」这个问题就没有答案，因为由 $R$ 的定义将得到 $R \in R \leftrightarrow R \notin R$。这个矛盾由罗素在 1901 年发现，它迫使我们限制集合的构成：一个性质只能从一个已经给定的集合中挑选元素。

不加证明的事实（朴素集合论的规则）。本课所用的朴素集合论规则不加证明地予以承认：元素相同的两个集合相等；由一个给定的集合 $A$ 和一个性质 $P$ 可以构成集合 $\{ x \in A : P(x) \}$，它由 $A$ 中满足该性质的元素组成；并且存在空集、集合 $\{a, b\}$（其仅有的元素是 $a$ 和 $b$）、由集合组成的集合的元素之并，以及一个集合的全体子集组成的集合。具有自然数集性质的集合的存在性在下一课中承认。

这些规则属于策梅洛和弗兰克尔的公理，对它们的研究属于集合论，超出了本课程的范围；因此这里承认它们，并明确列出，以便确切知道用到了什么。

量词逻辑

证明用联结词 $\neg$、$\wedge$、$\vee$、$\rightarrow$ 和 $\leftrightarrow$ 把陈述组合起来；这些联结词的规律在辅助课程数理逻辑 I：命题逻辑中研究，从它的语言开始；这里只需回顾：蕴涵 $p \rightarrow q$ 仅当 $p$ 为真而 $q$ 为假时为假，它等价于其逆否命题 $\neg q \rightarrow \neg p$，而德摩根律给出合取或析取的否定：

此外，要谈论集合，还需要关于所有元素或关于某个元素的陈述。若 $P(x)$ 是 $A$ 的元素的一个性质，则陈述 $(\forall x \in A)\,P(x)$ 读作「对任意 $x$（属于 $A$），$P(x)$」，它断言 $A$ 的所有元素都满足这个性质；陈述 $(\exists x \in A)\,P(x)$ 读作「存在 $x$（属于 $A$），使得 $P(x)$」，它断言至少有一个元素满足这个性质；而 $(\exists! x \in A)\,P(x)$ 断言恰有一个元素满足这个性质。符号 $\forall$ 和 $\exists$ 称为量词，分别是全称量词和存在量词。

不加证明的事实（量词的否定）。否定所有元素都满足某个性质，就是断言有某个元素不满足它；否定有某个元素满足它，就是断言没有任何元素满足它：

这些规则属于一阶逻辑，这里予以承认；它们推广了德摩根律，因为若 $A = \{a, b\}$，则全称陈述就是 $P(a) \wedge P(b)$，存在陈述就是 $P(a) \vee P(b)$。量词的顺序很重要：陈述 $(\forall n \in \mathbb{N})(\exists m \in \mathbb{N})(n < m)$ 说每个自然数都有另一个比它大的自然数，它为真；陈述 $(\exists m \in \mathbb{N})(\forall n \in \mathbb{N})(n < m)$ 说有一个自然数比所有自然数都大，也比它自身大，它为假。

陈述的逻辑形式决定了证明它的方式。本课使用的策略如下；它们的逻辑依据在关于推演技巧的课中研究。

• 要证明 $(\forall x \in A)\,P(x)$，任取一个元素 $x$（属于 $A$），除了它属于 $A$ 之外不对它作任何假设，然后证明 $P(x)$。
• 要证明 $(\exists x \in A)\,P(x)$，就举出 $A$ 中一个满足 $P$ 的具体元素；要否定 $(\forall x \in A)\,P(x)$，只需一个反例，即一个不满足它的元素。
• 要证明 $p \rightarrow q$，可以假设 $p$ 并推出 $q$；或者证明逆否命题 $\neg q \rightarrow \neg p$；或者假设 $p \wedge \neg q$ 并导出矛盾。
• 要证明 $p \leftrightarrow q$，就证明两个蕴涵 $p \rightarrow q$ 和 $q \rightarrow p$。

集合

属于、相等与包含

集合可以用列举法描述，即在花括号中列出它的元素，如 $\{1, 2, 3\}$；也可以用描述法，借助一个性质来描述，如 $\{ n \in \mathbb{N} : n \leq 3 \}$，它是同一个集合。外延性规则说，集合由它的元素决定：

由此可知，在列举法的描述中，次序和重复都无关紧要：$\{1, 2, 2\}$ 和 $\{2, 1\}$ 是同一个集合，因为它们有相同的元素。还可知道只有一个没有元素的集合，即空集 $\emptyset$：两个没有元素的集合有相同的元素，也就是说，都没有元素。

定义（包含）。集合 $A$ 包含于集合 $B$，或者说是 $B$ 的子集，如果 $A$ 的每个元素都是 $B$ 的元素：

若还有 $A \neq B$，则称 $A$ 是 $B$ 的真子集。

空集包含于每个集合 $A$，因为蕴涵 $x \in \emptyset \rightarrow x \in A$ 的前件总是假的，因而它是真的。应当区分属于与包含：$1 \in \{1, 2\}$ 和 $\{1\} \subseteq \{1, 2\}$ 为真，而 $\{1\} \in \{1, 2\}$ 为假，因为 $\{1, 2\}$ 仅有的元素是 $1$ 和 $2$，而集合 $\{1\}$ 不等于其中任何一个：$\{1\} \neq 1$，因为以 $1$ 为唯一元素的集合不同于 $1$，并且 $\{1\} \neq 2$。

并集、交集与差集

定义（集合的运算）。$A$ 与 $B$ 的并集是属于其中至少一个的元素组成的集合；交集是同时属于两者的元素组成的集合；差集 $A \setminus B$ 是属于 $A$ 而不属于 $B$ 的元素组成的集合：

若 $B \subseteq A$，则差集 $A \setminus B$ 称为 $B$ 关于 $A$ 的补集。两个集合称为不相交的，如果它们的交集是空集。

每种运算都对应一个联结词：并集对应析取；交集对应合取；差集对应合取加上一个否定。若是这样，每条逻辑规律都产生一条集合的规律：并集与交集满足交换律、结合律以及相互之间的分配律，因为联结词满足这些规律；所有这些规律都可以像下面的定理那样证明。补集总是相对于一个参照集合来取，因为由一切不在 $B$ 中的东西组成的集合会重新造成罗素悖论。

幂集

一个集合的子集本身又组成一个集合，它的存在性在开头已经承认。$A$ 的幂集记作 $\mathcal{P}(A)$，是以 $A$ 的子集为元素的集合：

例如，$\{1, 2, 3\}$ 的幂集有八个元素：空集、三个单元素集合、三个两元素集合以及 $\{1, 2, 3\}$ 本身。

对任意集合 $A$，空集和 $A$ 本身都是 $\mathcal{P}(A)$ 的元素，并且对每个 $a$（属于 $A$）有 $\{a\} \in \mathcal{P}(A)$，而 $a$ 一般不是 $\mathcal{P}(A)$ 的元素。在关于组合学的课中将证明：有 $n$ 个元素的集合有 $2^n$ 个子集。

有序对与笛卡儿积

平面上的点、分数或一个尚未进行的减法，都由按确定次序排列的两个对象来描述：对 $(3, 5)$ 不是对 $(5, 3)$。集合 $\{3, 5\}$ 不能用来表示它，因为它等于 $\{5, 3\}$。对有序对唯一的要求是它的特征性质：两个对相等当且仅当它们的第一分量相同且第二分量相同。库拉托夫斯基在 1921 年指出，只用集合的概念就足以构造具有这一性质的对象。

定义（有序对）。第一分量为 $a$、第二分量为 $b$ 的有序对是集合

特征性质一经证明，库拉托夫斯基的构造就可以忘掉：课程关于对所说的一切都可以从这一性质推出。

定义（笛卡儿积）。$A$ 与 $B$ 的笛卡儿积是这样的对组成的集合：第一分量属于 $A$，第二分量属于 $B$：

写法 $\{ (a, b) : a \in A \wedge b \in B \}$ 本身并不是所承认的规则之一，那些规则只允许从已构成的集合中分离出元素。然而，这个集合是存在的：若 $a \in A$ 且 $b \in B$，则集合 $\{a\}$ 和 $\{a, b\}$ 包含于 $A \cup B$，因而是 $\mathcal{P}(A \cup B)$ 的元素；由此可知，对 $(a, b) = \{ \{a\}, \{a, b\} \}$ 包含于 $\mathcal{P}(A \cup B)$，也就是说，它是 $\mathcal{P}(\mathcal{P}(A \cup B))$ 的元素。因此，笛卡儿积可以在这个集合内部用分离的方法构成，而该集合由所承认的规则保证存在：$A \cup B$ 是 $\{A, B\}$ 的元素之并，再两次取幂集。

这个名称让人想起笛卡儿：解析几何的平面就是 $\mathbb{R} \times \mathbb{R}$。积不满足交换律：$\{1\} \times \{2\}$ 只含 $(1, 2)$，而 $\{2\} \times \{1\}$ 只含 $(2, 1)$，由特征性质，后者与前者不同。

关系

说 $2$ 整除 $6$、$3$ 小于 $5$，或两个日期落在星期中的同一天，就是断言某些对象对之间有关系。若是这样，一个关系由它所联系的对决定，因而可以定义为对的集合。

定义（关系）。从 $A$ 到 $B$ 的关系是一个子集 $R$，它包含于积 $A \times B$；$A$ 上的关系是从 $A$ 到 $A$ 的关系。若 $(a, b) \in R$，则说 $a$ 与 $b$ 由 $R$ 相联系。

例如，$\{1, 2, 3\}$ 上的关系「小于或等于」是对的集合 $\{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$。对于常用的关系，在两项之间写一个符号，如 $a \leq b$ 或 $a \mid b$，代替 $(a, b) \in R$。集合上的关系的四个性质贯穿整个课程。

定义（关系的性质）。关系 $R$（在 $A$ 上）称为自反的、对称的、反对称的或传递的，如果它分别满足下列条件。

• 若每个元素都与自身有关系，则称它是自反的：$(\forall a \in A)\,((a, a) \in R)$；
• 若 $a$ 与 $b$ 有关系蕴涵 $b$ 与 $a$ 有关系，则称它是对称的：$(\forall a, b \in A)\,((a, b) \in R \rightarrow (b, a) \in R)$；
• 若在两个方向上都有关系的两个元素相等，则称它是反对称的：$(\forall a, b \in A)\,((a, b) \in R \wedge (b, a) \in R \rightarrow a = b)$；
• 若 $a$ 与 $b$ 有关系且 $b$ 与 $c$ 有关系蕴涵 $a$ 与 $c$ 有关系，则称它是传递的：$(\forall a, b, c \in A)\,((a, b) \in R \wedge (b, c) \in R \rightarrow (a, c) \in R)$。

在 $A \times A$ 的方格网中，一个关系是一个点集。它是自反的，当它包含整条对角线，即由对 $(a, a)$ 组成的对角线；它是对称的，当它的图形关于对角线对称；它是反对称的，当对角线外没有任何一点的对称点也在关系中。反对称并不意味着「不对称」：相等关系两者都是，练习题 1 要求给出一个两者都不是的关系。

等价关系

关系「奇偶性相同」的表现像一种部分的相等：它把在某一方面（即奇偶性）一致的数等同起来，而忽略其他方面。使它具有这种表现的三个性质有一个名称。

定义（等价关系）。$A$ 上的关系若是自反的、对称的和传递的，就称为等价关系。这时写 $a \sim b$，并说 $a$ 等价于 $b$。$a$ 的等价类是与 $a$ 等价的元素组成的集合，其中每个元素都是该类的一个代表元：

所有等价类组成的集合称为商集，记作 $A/{\sim}$。

等价关系的例子有：相等关系，它的每个等价类只有一个元素；奇偶性相同，有两个等价类；除以 $3$ 余数相同，有三个；以及落在星期中的同一天，有七个，这就是例题 3。一般地，若 $g$ 是定义在 $A$ 上的函数，则关系 $g(x) = g(y)$ 从相等关系继承了三个性质，而例题 5 表明每个等价关系都具有这种形式。

因此，等价类把集合分成互不重叠的块。这种分割集合的方式值得单独定义。

定义（划分）。集合 $A$ 的划分是由 $A$ 的子集组成的集合，这些子集称为块，它们非空、两两不相交，并且它们的并是 $A$；等价地说，$A$ 的每个元素恰属于一个块。

因此，给出 $A$ 上的一个等价关系和给出 $A$ 的一个划分，是说同一件事的两种方式；例题 4 利用这一点来计数等价关系。商集就是被看作一个新集合的划分：从 $A$ 过渡到 $A/{\sim}$ 时，等价的元素融合为一个。

同样，在关于有理数的课中，两个分数 $(p, q)$ 和 $(r, s)$ 当 $ps = qr$ 时等价，有理数是一个等价类；在关于同余的课中，模 $n$ 的剩余类是整数之间一个等价关系的等价类。

序关系

上一个例子中的整除关系不是对称的，而是反对称的：它不是把元素等同起来，而是把它们排序。这类关系有专门的名称。

定义（序）。$A$ 上的关系若是自反的、反对称的和传递的，就称为序关系或偏序；这时写 $a \preceq b$，并说 $a$ 先于 $b$。若任意两个元素都可比较，即对任意 $a$ 和 $b$ 有 $a \preceq b$ 或 $b \preceq a$，则称这个序为全序。

序的例子有：自然数之间的关系 $\leq$，由在关于自然数的运算的课中证明的三歧性，它是全序；包含关系，由它的性质定理，它是序，但不是全序，因为 $\{1\}$ 和 $\{2\}$ 不可比较；以及自然数之间的整除关系，它的反对称性在关于整除的课中证明，它不是全序，因为 $2 \mid 3$ 和 $3 \mid 2$ 都不成立。有限的序用哈斯图来画：每个元素画一个点，$b$ 画在 $a$ 的上方，条件是 $a$ 先于 $b$，并且当两者之间没有其他元素时连一条线段；传递性使得其余线段可以省略。

定义（界与极端元素）。设 $\preceq$ 是 $A$ 上的序，$X$ 是 $A$ 的子集。$X$ 的界与极端元素定义如下。

• 元素 $c$（属于 $A$）称为 $X$ 的下界，如果它先于 $X$ 的所有元素；称为上界，如果 $X$ 的所有元素都先于它。
• $X$ 的最小元是 $X$ 的一个下界，并且它属于 $X$；最大元是一个上界，并且它属于 $X$。
• 元素 $m$（属于 $X$）称为极小元，如果 $X$ 中没有异于它的元素先于它；称为极大元，如果它不先于 $X$ 中任何异于它自身的元素。
• $X$ 的下确界是它的下界组成的集合的最大元，上确界是它的上界组成的集合的最小元，如果它们存在的话。