逻辑与证明

断言

数学是一场逻辑游戏：我们假设某些看来是基础或者自明的公理（axiom）为真断言，然后利用给定的一些推理规则（rules of inference），去得到或者发现其他的真断言．因此，在撸起袖子解数学题之前，有必要先谈谈这场游戏的规则.

在这场游戏中，我们可以说一些句子，这些句子称为断言（sentence）．每个断言要么是真的，要么是假的．可以用大写英文字母表记断言，比如 $P$，或 $Q$.

有的时候，我们希望把两个或者更多的断言合并起来形成新的断言，比如 “$x$ 是单数” 和 “$x$ 是双数” 可组合形成 “$x$ 是单数或 $x$ 是双数”，“明天下雪” 和 “学校停课” 可以组合成 “如果明天下雪，学校就停课”．为了不重复地说 “或”，“如果……那么……”，我们可以引入一些简写：

1. “非（not） $P$”，记作 $\neg P$．
2. “$P$ 和（and） $Q$”，记作 $P\wedge Q$．
3. “$P$ 或（or） $Q$”，记作 $P\vee Q$．
4. “$P$ 蕴含（entail） $Q$”，记作 $P \to Q$．$P$ 称为前件（antecedent）或者 $Q$ 的充分条件（sufficient condition）, $Q$ 称为后件（consequent）或者 $P$ 的必要条件（necessary condition）.
5. “$P$ 双向蕴含/当且仅当（if and only if） $Q$”，记作 $P \leftrightarrow Q$.

这里特地解释一下 “蕴含” 这个概念的含义：虽然 “蕴含” 形似我们日常语言中用 “因为…所以..” 表达的因果关系，但这种相似仅限于形似．“蕴含” 代表的并不是因果关系，也不是逻辑递进的关系，而仅仅是在形式上把两个断言连接起来的连接符．你也可以把 $P \to Q$ 当做 $\neg P \vee Q$ 的另一种表达形式．

断言中可以包含变量，这样的断言又可以称为谓词（predicate）．可以用 $P(x)$ 代表 “$x$ 是江苏省的省会” 这个谓词．我们可以选择带入特定的 $x$，使 $P(x)$ 有固定的真或者假的取值．例如，如果把 “无锡” 带入 $x$，那么这个断言为假；如果把 “南京” 带入 $x$，那么为真.

如果我们有谓词 $P(x)$，那么必须给出它的量词（quantifier）．量词限定了令谓词 $P(x)$ 为真的 $x$ 的取值范围；同时，谓词也不能脱离量词而存在．虽然在生活中可能会有各种各样的量词，但在数学中只讨论两种量词：

1. 全称量词（universal quantifier），记作 $\forall$．若令 $P(x)$ 表示 “$x$ 是德国人”，而 $x$ 可以从全体作家的名字中取值，那么 $\forall x:P(x)$ 表示的是 “所有的作家都是德国人”．
2. 存在量词（existential quantifier），记作 $\exists$．接上例，$\exists x: P(x)$ 表示，“存在作家是德国人”

$\exists$ 和 $\forall$ 的顺序不能调换：“每个人都有喜欢吃的食物”（喜欢吃的东西可以是不同的）显然和 “有食物令每个人都喜欢吃”（每个人都必须喜欢吃同一种东西） 是意义上不同的两个句子．我们约定一个量词所限定的范围（scope）是它的冒号右侧一直到断言的句尾.

同时，我们约定如果量词取值的范围内不含任何物件，那么此时谓词是真的，称为空真（vacuously true）的.

推理规则

我们的游戏的主要目标是运用推理规则，从一些简单的真断言来到更加复杂的真断言．如果我们能从真断言 $P$ 和一些其他的条件推导出另一个断言 $Q$，那么可以写 $P\Rightarrow Q$．

如果 $P \Rightarrow Q$ 和 $Q\Rightarrow P$，那么我们可以写 $P\Leftrightarrow Q$．

注意，$\to$ 和 $\Rightarrow$、$\leftrightarrow$ 和 $\Leftrightarrow$ 并非同样的意思：$\to$ 和 $\leftrightarrow$ 是构造新断言用的连接符，$\Rightarrow$ 和 $\Leftrightarrow$ 指示的是推导过程中由一个断言得出另一个断言的逻辑先后关系.

我们的推理规则其实就是俗话说的逻辑思维，具体地说，有以下几个规则；为了强调这些规则并非人造的规则，我用 “日常逻辑” 来示例它们的合理之处：

1. $\forall x: P(x) \Leftrightarrow \neg(\exists x: \neg P(x))$；“所有 $x$ 都有 $P$” 等价于 “不存在 $x$ 没有 $P$”
2. $P \Leftrightarrow \neg(\neg(P))$；俗话说的 “双重否定表示肯定”.
3. $P, Q \Leftrightarrow P\wedge Q$；如果 “大象有大耳朵” 和 “大象有长鼻子”，那么 “大象有大耳朵和长鼻子”；反之亦然．
4. $P\wedge Q \Leftrightarrow Q\wedge P$；“奶茶和咖啡是饮料” 等价于 “咖啡和奶茶是饮料”.
5. $P \Rightarrow P\vee Q$；如果 “明天下雨”，那么可以说 “明天下雨或明天是星期三”；“明天是星期三” 可以换成任意断言．
6. $P\vee Q \Leftrightarrow Q\vee P$；“奶茶或咖啡是饮料” 等价于 “咖啡或奶茶是饮料”
7. $\neg P \wedge (P\vee Q) \Rightarrow Q$；又称选言三段论（disjunctive syllogism）．如果 “奶茶或饼干是饮料” 且 “饼干不是饮料”，那么可推断 “奶茶是饮料”
8. $Q \Rightarrow P\to Q$；$\neg P \Rightarrow P\to Q$；这条规则与其说是规则不如说是一个约定，如果我们知道 “奶茶是饮料” 是真的，那么可选任何断言 $P$ 构成真断言 “如果 $P$，那么奶茶是饮料”；类似地，如果我们知道 “明天天会塌下来” 是假的，那么可选任何 $Q$ 组成真断言 “如果明天天会塌下来，那么 $Q$”．这和自然语言中隐含了因果关系的表述 “如果……那么……” 稍许不同.
9. $P \wedge (P\to Q) \Rightarrow Q$；又称肯定前件（modus ponens）规则；如果 “如果是人，那么就会死”，“苏格拉底是人”，那么可得 “苏格拉底会死”.
10. $\neg Q \wedge (P\to Q) \Rightarrow \neg P$；又称否定后件（modus tollens）规则；如果 “如果是人，那么就会死”，“花瓶不会死”，那么可得 “花瓶不是人”.
11. $(P\Rightarrow Q) \Leftrightarrow (P\to Q)$；又称条件证明律（conditional proof），在数理逻辑中又称演绎定理．如果我们可以从 $P$ 得到 $Q$，那么 $P\to Q$ 是真断言.
12. $P\to Q, Q\to P \Leftrightarrow P\leftrightarrow Q$；“如果有考试就要熬夜” 和 “如果要熬夜就一定有考试” 可得 “熬夜当且仅当有考试”.

对于复杂的断言，用括号来指定复杂断言的构成顺序：在括号里的部分需要先进行组合，其优先级由嵌入括号的深度决定：例如，$(P\vee Q)\wedge W$ 应当解读为 “$P \vee Q$ 和 $W$” 而不是 “$P$ 或 $Q\wedge W$”．若未标括号，那么默认从右往左组合.

推导的结果称为定理（theorem）．同时，我们也通过下定义（definition）的方式来简化我们的表达．定义只不过是语言上的简化，它们不需要证明.

我们不打算在这一节中发展数理逻辑（mathematical logic）中的任何结论，因此非正式地将逻辑作为一场“游戏”来讨论．现代的数理逻辑需要集合论为基础：函数、关系都是数理逻辑重要的部分，但是它们的严格定义只出自集论，然而集合论本身也需要逻辑的形式来严谨地定义．为了避免先有鸡还是先有蛋的问题，我们需要先像游戏一样地进行逻辑演练，在形成了一个公理系统（集合论）之后，再利用其中的工具来严谨地 “模拟” 我们走过的逻辑过程，从而反过来证明，我们的游戏中的不存在矛盾或者存在无法利用推理规则达到的真断言，而这才是数理逻辑登场的时候.

用电脑科学做一个比方：如果将数学比作一种程序语言，将我们的游戏比作它的编译器，那么发展数理逻辑就是用编程语言写它自己的编译器的自举（bootstrapping）的过程.

在游戏的开始，我们需要接受一套名为 Zermelo-Fraenkel 集合论的公理系统，这是一个由7条公理（外延、正规、配对、并集、幂集、无穷、选择公理）和2条公理模式（分类公理和置换公理；公理模式的定义会在下文解释）组成的公理系统，因为选择公理存在一定的争议，有时会把它独列在外，将含选择公理的 Zermelo-Fraenkel 集合论称作 ZFC，而将不含的称作 ZF.

ZFC 是德国人 Ernst Zermelo 和 Abraham Fraenkel 在认识到 Cantor 的朴素集合论的不足之后总结形成的，Zermelo (1908，1930) 贡献了其中的7条公理和分类公理模式，Fraenkel (1922) 又添加了置换公理模式，最后形成现在的形式．这并不是唯一的集合论公理系统：类似的还有 NBG 系统和 W．V．Quine 的新基础（New Foundation，NF）系统．因 ZFC 的普适性，ZFC 是 CADMUS 选定的集论基础.

如果我们把 ZFC 的公理作为真断言，我们可以通过我们的数学游戏推导出大部分人在乎的大部分数学知识．在接下来的章节中我们将引入 ZFC 的公理来一步步构建数学宇宙．选择公理和置换公理在目前并无需要，因此留给将来的章节.

集论的公理基础

集与元素

想象一个数学宇宙，里面存在且仅存在一种名为 “集合” 的物件．我们粗略地想象 “集合” 是一系列物件的汇集，正如现实生活中的集合一样，因此冠其名曰 “集合” ．我们不知道数学宇宙有多少个 “集合” 也不知道已经存在的 “集合” 中的物件是什么．但是在我们的假想中，这个宇宙中存在至少一个“集合” ，而且不存在集合以外的东西 .

从字面上看，“集合” 往往和 “收容” 联系起来．我们希望数学宇宙和常识尽可能契合，因此给定一个集合 $a$，对于另一个集合 $A$，我们希望能够回答 “$a$ 是不是 $A$ 的元素？” 这个问题．如果 $a$ 的确是 $A$ 的元素，那么表记为 $a\in A$；如果不是，表记为 $a\notin A$.

部分 ZFC 公理

分类公理

到目前为止，我们只知道数学宇宙中存在 “集合”，却缺乏构建我们想要的集合的方法．这是因为集合的构造不应该是随心所欲的——缺乏限制的集合构造容易导致悖论．假想我们可以构建任意想要的集合，并因此造出了一个 “仅包含不在集合 $A$ 中的元素” 的集合 $A$，那么有两种可能：

1. 若 $A\in A$，那么 $A$ 是一个 “不在集合 $A$ 中的元素”，意味着 $A\notin A$，与假设矛盾.
2. 若 $A\notin A$，那么 $A$ 不在 $A$ 中，因此 $A$ 符合包含在 $A$ 内的标准，同样矛盾.

这就是 Russell 悖论，它揭示了集合构造中自我引用的危险性． 为了避免出现这个问题，我们正式地做出以下约定：

分类公理是一个公理模式 (schema)：逻辑谓词 $P(x)$ 可以是含变量 $x$ 的任意逻辑公式，所以分类公理起的是模板的作用，套入不同 $P(x)$ 才形成了不同的公理.

可见，任何新造的集合 $B$ 的元素，在我们的约定下，必须（1）要从已经存在的集合 $A$ 中取，确保了这些元素在我们的数学宇宙中是已经存在的，且（2）$B$ 的构造不允许引用它的本身，避免了罗素悖论中的自我引用问题.

更一般地，如果一个集合的元素取自另一个有良好定义的集合且其构成不包含自我引用，那么我们将默认引用分类公理认为该集合存在.

我们可以利用分类公理定义子集的概念：

我们马上有以下的结论：

存在一个不含任何元素的集合，称之为空集，以 $\varnothing$ 表示．空集是所有集合的子集.

取集合 $A$．存在至少一个集合，因此 $A$ 存在.

根据分类公理，可知存在集合 $\varnothing$，其中的元素 $a$ 满足谓词 $a\in A \wedge a\neq a$.

$b\neq b$ 是恒假的，因此 $a\in A \wedge a\neq a$ 恒假，因此不存在元素 $a$ 满足谓词．因此 $\varnothing$ 中不含任何元素．因为 $\varnothing$ 不含任何元素．

可见通过分类公理造出的新集都是比原来的集的子集．一个特殊的子集叫做并集：

对集合 $A$ 和集合 $B$，定义 $A$ 和 $B$ 的并集为 $A\cap B=\{ x\in A \mid x\in B\}$．并集存在

更一般地，称一个集合族 $\mathcal{C}$ 的交集 $\bigcap \mathcal{C}$ 为 $\mathcal{C}$ 中所有元素的交集，即 $$x\in \bigcap\mathcal{C} \Leftrightarrow \forall C \in \mathcal{C}: x \in C$$

通过分类公理直接证明.

另一个特殊的子集叫做补集：

对集合 $A$ 和集合 $B$，定义 $B$ 相对于 $A$ 的补集为$A-B=\{x \in A\mid x\notin B\}$．补集存在.

通过分类公理直接证明.

外延公理

因为有多于一个集合存在的可能，我们需要考虑什么情况下两个集合是相等的.

在生活中，一些事物的相同性是由它们的内涵决定的：一瓶水终究是一瓶水，不管是喝它的人是谁．另外一些事物不但有内涵，也有外延：很多人认为他们自食其力挣到的第一张钞票对他们是有特殊意义的，尽管在内涵（在交易媒介和价值储存的意义上，而非物质组成的意义上）上这第一张钞票和接下来挣到的每一张都是相同的.

我们不妨假设集合的身份完全由它的外延决定（即，仅由它所包含什么样的元素决定），做出以下约定，

马上有以下的结论：

1. 空集是独特的.
2. 任何给定集合的交集是独特的.
3. 任何给定集合的补集是独特的.
4. 若 $A \subseteq B$ 且 $B \subseteq A$，那么 $A=B$

1. 假设有另一个空集 $\varnothing'$，那么断言 $\forall a:a\in \varnothing\leftrightarrow a\in \varnothing'$ 是空真的，因此有 $\varnothing'= \varnothing$.
2. 由定义和外延公理直接证明.
3. 由定义和外延公理直接证明.
4. 若 $A \subseteq B$，那么 $\forall a: a\in A\to a\in B$ 为真；若 $B \subseteq A$，那么 $\forall b:b\in B\to b\in A$ 为真．因此 $\forall a:a\in A\leftrightarrow a\in B$ 为真，得 $A=B$

相等可让我们引入以下定义.

配对公理

分类公理只让我们构造一个给定集合的 $A$ 的子集．但是，若我们单独地知道元素 $a,b$ 的存在，但不知道它们属于什么集合，我们就无法利用分类公理构建集合 $\{a,b\}$了．配对公理正是为了弥补这一方面的缺陷而存在的：

对任意集合 $A$，存在集合 $\{A\}$；即，给定任何集合 $A$，都存在另一个集合，使这个新集合仅包含 $A$ 为元素，称为 $A$ 的单元素集.

应用配对公理，存在 $\{A,A\}=\{A\}$

一个常见的误区是 $\varnothing\neq \{\varnothing\}$：

• $\varnothing$ 是根据分类公理存在且唯一的空集；
• $\{\varnothing\}$ 是仅含空集为元素的单元素集，所以有 $\varnothing\in\{\varnothing\}$（注意这里 $\varnothing$ 是元素，而不是子集），因此它不是空集.

通过配对的运用，我们可以定义有序对（ordered pair）的数学结构：

对任意集合 $a, b, c$，定义 $$\begin{align*} ()&=\varnothing, \\ (a)&=((),a)=\{\{()\}, \{(),a\}\}, \\ (a,b)&=((a),b)\\ (a,b,c)&=((a,b),c)\\ \end{align*} $$

称 $(a,b)$ 为有序对，称 $(a,b,c)$ 为3维数组．

上述定义的集合都存在.

显然 $\varnothing$ 存在，那么 $()$ 是有定义的．

若 $a$ 和 $b$ 存在，那么应用配对公理，存在 $\{a,b\}$．在 $a$ 上应用配对定理两次，可见 $\{\{a\}\}$ 存在．因此二者的并集 $\{a,b\}\cup\{\{a\}\}=\{\{a\}, \{a, b\}\}$ 也存在.

那么根据定义 $(a)=((),a)$，$(a,b)=((a),b)$，$(a,b,c)=((a,b),c)$ 都存在.

对任意有序对 $(a,b)$ 和 $(c,d)$，$$(a,b)=(c,d) \Leftrightarrow a=c, b=d$$

• $\Rightarrow$：反证法：假设 $a\neq c$，那么根据外延公理和单元素集的定义，$\{a\}\neq \{c\}$，那么通过配对公理构成的 $\{\{\varnothing\}, \{a\}\}\neq \{\{\varnothing\}, \{c\}\}$，那么 $(a)\neq (c)$．根据定义，$\{(a)\}$ 和 $\{(a),b\}$ 是 $(a,b)$ 唯二的元素，$\{(c)\}$ 和 $\{(c),d\}$ 是 $(c,d)$ 唯二的元素，必有 $\{(a)\}=\{(c),d\}$，$\{(c)\}=\{(a),b\}$，蕴含 $(c)=(a)$，矛盾．
• $\Leftarrow$：显然成立.

正规公理

如果说分类公理是为了解决 Russell 悖论而生的，那么正规公理存在的目的是排除 “病态” 的元素包容关系：

我们排除的 “病态” 包容关系是那些包含自己为元素的集合：

1. 对任何集合 $A$ 都有 $A\notin A$；没有集合是它自己的元素.
2. 不存在集合满足 $A\in B$ 且 $B\in A$.

1. 反证法： 假设存在集合 $A$ 满足 $A\in A$．根据配对公理，单元素集 $\{A\}$ 存在，且 $A\in \{A\}$．$\{A\}$ 显然非空，因此根据正规公理，存在一个 $a\in \{A\}$ 满足 $a\cap \{A\}=\varnothing$．因 $A$ 是单元素集，一定有 $a=A$，因此 $A=\varnothing$．但因为 $A\in A$，$A\neq \varnothing$，形成矛盾.
2. 反证法：假设满足条件的 $A,B$ 存在．根据配对公理，集合 $C=\{A,B\}$ 存在．对 $A\in C$，根据正规公理，必有（1）$C\cap A =\varnothing$ 或（2）$C\cap B =\varnothing$．不失一般性地假设（1）为真，那么显然 $B\notin A$.

并集公理

通过分类公理造出的新集都是比原来的集更“小”的子集；我们需要并集的概念来合并多个集合，构造更“大”的集：

显然，

任何给定集合的并集是独特的.

由定义和外延公理直接证明.

幂集公理

幂集公理为定义更复杂的数学结构建立了基础：

对任意集合 $A$ 和 $B$，定义$A$ 和 $B$ 的笛卡尔积 $A\times B$ 为 $\{(a,b) \mid a\in A \wedge b\in B \}$．笛卡尔积存在.

我们需要借助分类公理证明笛卡尔积是某个集的子集.

我们先要证明对 $a\in A'$, $b\in B'$，$\{\{a\},\{a,b\}\} \in \mathcal{P}(\mathcal{P}(A'\cup B'))$．因 $a\in A'$，$a\in A'\cup B'$ 且有 $\{a\} \in \mathcal{P}(A'\cup B')$；类似地有 $\{a, b\} \in \mathcal{P}(A'\cup B')$．那么 $\{\{a\},\{a,b\}\} \subseteq \mathcal{P}(A'\cup B')$，或 $\{\{a\},\{a,b\}\}\in \mathcal{P}(\mathcal{P}(A'\cup B'))$．

可见，对 $a\in A$，$(a)=\{\{\varnothing\},\{\varnothing,a\}\}$，有 $(a)\in \mathcal{P}(\mathcal{P}(\{\varnothing\}\cup A))=T$，根据幂集公理这是一个有良好定义的集合．对 $b\in B$，$(a,b)=((a),b)=\{\{(a)\},\{(a),b\}\}$，有 $(a,b)\in \mathcal{P}(\mathcal{P}(T\cup B))$，根据幂集公理这也是一个有良好定义的集合.

因此根据分类公理该集存在.

关系与函数

基本定义

因为笛卡尔积存在，我们可以取笛卡尔积的特定子集，并赋予它们特殊的意义：

给定二元关系 $R$，定义$R$ 的：

1. 定义域（domain）：$\mathrm{dom}(R) = \{x \mid \exists y : xRy\}$
2. 值域（range）：$\mathrm{ran}(R) = \{y \mid \exists x : xRy\}$
3. 域（field）：$\mathrm{fld}(R)=\mathrm{dom}(R) \cup \mathrm{ran}(R)$
4. 反关系（inverse relation）：$R^{-1} = \{(y,x) \mid \exists x:\exists y : xRy\}$
5. 在 $C\subseteq \mathrm{dom}(R)$ 上的限制（restriction）：$R\restriction C = \{(x,y) \mid x\in C \wedge xRy\}$

$R$ 的定义域、值域、域、反关系，限制都是集合.

对任意 $(a,b)\in R$，因为 $\{(a)\}\in (a,b)$，$(a,b)\in R$，有 $\{(a)\}\in \bigcup R$．又因为 $(a)\in \{(a)\}$，那么 $(a)\in \bigcup\bigcup R$．又有 $\{\varnothing,a\}\in (a)$，所以 $\{\varnothing,a\} \in \bigcup\bigcup\bigcup R$．最后，$a\in \{\varnothing,a\}$，因此 $a\in \bigcup\bigcup\bigcup\bigcup R$．类似地也有 $b\in \bigcup\bigcup\bigcup\bigcup R$．那么定义域，值域和域都是 $\bigcup\bigcup\bigcup \bigcup R$ 的子集，因此根据分类公理它们都是集合．

$R^{-1}\in \mathrm{ran}(f)\times \mathrm{dom}(f)$, $R\restriction C\subseteq R$，因此根据分类公理它们也都是集合.

有一类特殊的二元关系是数学的学生都很熟悉的：

如此定义的函数 $f$，就相当于在纸上画出 $f$ 的图像（graph），然后说 $f$ 的图像就是 $f$——我们知道图像是由一个个点构成的，每一个点可以根据它在纸上的位置用一对坐标 $(x,y)$ 表示，而 $f$ 就正是全体这样的点的集合，与此处的定义吻合.

给定一个函数，我们可以定义以下的集合：

给定函数 $f: A\to B$，定义

1. $f$ 在 $X\subseteq A$ 上的像（image）：$f(X) = \{y \mid \exists x\in X : xfy\}$．为了避免歧义，也可以记作$\{f(x)\}_{x\in X}$.
2. $f$ 在 $Y\subseteq B$ 上的原像（preimage）：$f^{-1}(Y) = \{x \mid \exists y\in Y :xfy\}$
3. 若 $g:B\to C$ 也是映射，$g$ 和 $f$ 的复合（compound）是：$$g\circ f= \{(a,c) \mid \exists b\in B: afb \wedge bgc\}$$

像，原像，复合都是集合.

显然 $f(X)\subseteq \mathrm{ran}(f)$, $f^{-1}(Y)\subseteq \mathrm{dom}(f)$，因此根据分类公理它们都是集合．显然 $f\circ g \subseteq \mathrm{dom} (f) \times \mathrm{ran}(g)$

给定函数 $f: A\times A\to A$，$f$ 又可称作（$A$ 上的）二元运算（binary operation）．二元运算通常使用中缀的形式表示．

对任意函数 $g:B\to A$，$h:C\to A$ 可以定义 $g$ 和 $h$ 的逐点（pointwise）的 $f$ 运算 $gfh$ 为： $$(g f h)(x,y)=g(x)fh(y))$$

显然 $\mathbb{ran}(gfh) \subseteq \mathbb{ran}(f) \subseteq A$，且 $\mathbb{dom}(gfh)\subseteq \mathbb{dom}(g)\times \mathbb{dom}(h)\subseteq B\times C$，且 $gfh$ 的定义中不含对自身的引用．因此根据分类公理其存在.

有三类具有特殊性质的函数：

其中，双射函数可被视为一种 “一一对应” 的关系：$A$ 中的每一个元素 $a$ 都可以找到 $B$ 中相应的一个元素 $b$，不存在另一个 $A$ 的元素 $a'$ 对应 $b$，也不存在另一个 $B$ 的元素 $b'$ 对应 $a$.

特别地，单射函数有如下性质：

1. 对单射函数 $f: A\to B$，称 $f$ 的反关系为反函数（inverse） $f^{-1}$ ．$f^{-1}$ 是函数，也是单射函数.
2. 对单射函数 $f: A\to B$，对 $C\subseteq A$, $f\restriction C$ 也是单射.
3. 对单射函数 $f: A\to B$ 和 $g: B\to C$，$g\circ f$ 也是单射.

1. 反证法：假设 $f^{-1}$ 不是函数，那么对 $y\in \mathrm{dom}(f^{-1})$，存在 $x, x'\in\mathrm{ran}(f^{-1})$，$x\neq x'$ 满足 $yf^{-1}x$ 和 $yf^{-1}x'$，即 $xfy$ 和 $x'fy$，与 $f$ 的单射性矛盾.
2. 反证法易证若 $f\restriction C$ 不是单射那么 $f$ 也不是单射，与假设相悖.
3. 显然对 $x,x'\in A$，若 $x\neq x'$，$f(x)\neq f(x')$，$g(f(x))\neq g(f(x'))$，因此 $g\circ f$ 也是单射.

等价关系

在函数之外，还有一类特殊的二元关系：

相等和等价，可类比于几何上的全等与相似．和相等不同，等价关系更松散地定义了一种“相等”的概念．它目的不在于比较两个物件是不是同一件物件（这是相等的功能），而是比较两件物体是不是在某种意义上是属于同一类的．而这种由等价关系而诱导产生的“类”允许我们作一下定义：

1. 若 $R\subseteq X \times X$ 是等价关系，对任意 $a\in X$ 都可以定义 $a$ 的等价类（equivalence class） $$[a]=\{b\in X \mid aRb \}$$
2. 由 $R$ 所有等价类的集合 $\mathcal{C}=\{[x] \mid x\in X\}$． $\mathcal{C}$ 称作 $X$ 相对于 $R$ 的商集（quotient set），记作 $X/R$．
3. 每一个 $[x] \in X/R$ 都非空且两两不相交，并有 $\bigcup X/R =X$．因此我们说 $X/R$ 是 $X$ 的划分（partition）
4. 映射 $\pi(x)=[x]$ 存在，称为 $R$ 的规范投影映射（canonical projection map）

1. 对任意 $x\in X$, 每一个等价类 $[x]$ 都是 $\mathrm{ran} R=X$ 的子集，因此据分类公理是集合．
2. 因为每个 $[x]\in X/R$ 都是集合，根据配对公理，$X/R$ 也是集合．

3. 显然 $\bigcup X/R \subseteq X$． 等价类是非空的，因为对每个 $x\in X$，根据等价关系的反身性有 $x\in [x]$，因此又有 $X\subseteq \bigcup X/R$，得 $X = \bigcup X/R$．

   反证等价类不相交：假设有相交的独特等价类 $[a]$ 和 $[b]$，存在 $c\in [a]\cap [b]$．那么必有 $aRc$ 和 $bRc$，根据传递性，有 $aRb$，也就是说 $b\in [a]$，$a\in [b]$，$[a]=[b]$，与独特性假设矛盾．

4. 显然映射 $\pi \subseteq X\times X/R$ 是集合．假设存在独特的 $[x]'$, $[x]$ 满足 $\pi(x)=[x]$, $\pi(x)= [x]'$，那么根据 $3$ 有 $[x]\cap [x]'=\varnothing'$，这与 $x\in[x]$, $x\in[x]'$ 相悖.

相容性的意思是，如果一个映射 $f$ 和一个等价关系 $R$ 相容，若它的所有自变量都被等价的元素替代，它的像仍然会落在原来的像的等价类中．这似乎意味着 $f$ 在某种意义上似乎起到了一个从等价类到等价类的映射的作用．自然，$f$ 本身并不是这样的函数，但是下面这条定理告诉我们确实可以利用 $f$ 构造一个符合条件的等价类到等价类的映射 $g$：

若 $R\subseteq X \times X$ 是等价关系且函数 $f:X\to X$ 与 $R$ 相容，那么存在映射 $g:X/R\to X/R$，其定义如下： $$g=\{([x], [f(x)])\mid x\in X\}$$ 类似地，若函数 $f:X \times X\to X$ 与 $R$ 相容，那么存在映射 $g:(X/R\times X/R)\to X/R$，其定义如下： $$g=\{([x], [y], [f(x,y)])\mid x,y\in X\}$$

显然 $g\subseteq X/R \times X/R$ 根据分类公理是集合.

须反证 $g$ 是映射．若 $g$ 不是映射，那么对某个 $[x]$，存在 $[f(x)]\neq [f(x)]'$，满足 $([x],[f(x)]), ([x],[f(x)])\in g$．$[f(x)]\neq [f(x)]'$ 蕴含 $[f(x)]\cap [f(x)]' =\varnothing$，蕴含存在独特的 $y\in [f(x)]$ 和 $y'\in [f(x)]'$ 满足 $xfy$, $xfy'$．这和 $f$ 是映射的前提相悖．因此 $[f(x)]=[f(x)]'$.

$f:(X \times X)\to X$ 的情况的证明完全类似.

排序关系

还有第三种常见二元关系．同样也是延展相等的概念，排序关系的目的是在两个元素的比较中引入 “大” 和 “小” 的相对概念.

排序关系有以下性质.

若 $R\subseteq X \times X$ 是排序关系，那么它有反反身性（irreflexive）；那么对任意 $a\in R$，$aRa$ 恒假．

反证法：显然 $a=a$ 恒真．若 $aRa$ 为真，那么根据三分性 $a=a$ 为假，显然矛盾.

对于一个集合 $A$，若能找到并找到 $A$ 上的一个排序关系，就可以称它是有序的．一个集合可能有多个排序关系，但一般来说，我们不会同时研究同一个集合中一个以上的排序关系，因此 “有序集” 中具体指的是哪个排序关系是由上下文指明的.

对于一个有序集 $A$，我们可以研究那些在大小上是极值的元素：

自然数 $\mathbb{N}$

Peano 算数公理

目前，我们的数学宇宙中已经有各种各样的集了，但是还没有一种能代表数的概念．最简单的一种数是 “自然数”．我们希望能用集合表示 “自然数”.

在构造自然数之前，我们需要先反思我们期望一个 “自然数” 应该具有什么样的性质．面对 “'3' 是什么？” 这个问题时，一个普通人往往会给出近似以下三个观点之一的答复：

1. 竖起三根指头，示意 “3” 是竖起的指头.
2. 用算筹摆出 “|||” 的形状，示意 “3” 是 “把算筹 | 放在桌上” 这个动作重复的次数代表的概念.
3. “3” 是三个苹果，三个人和三分钟的抽象共性（Russell 1919）．

从这些例子不难看出，不管是实物的数量、某个过程的特征还是某种抽象的性质，常识上自然数 “3” 的概念都与某些可以用人类心智的常识可以理解的概念相照应．更基础地说，你的中文^注语言能力也是拜你的常识中对 “自然数” 的理解所赐的：为了读懂汉字，你必须能够 “理解” 不同的汉字有不同的笔画；如果让 “日” 代表自然数 $4$，让 “目” 代表 $5$，那么能读或写这两个字，并且能认识到这是两个因为笔画而不同的字，意味着你具备对自然数 $4$ 和 $5$ 的理解．可见，如果你能看懂这个网页上的东西的话，那么 “自然数” 的概念就已经弥散在我们的讨论中了.

既然 “自然数” 的概念这么基本，那么为什么还要浪费时间从集合构建自然数呢？因为我们感兴趣的数学问题往往涉及研究全体自然数所具有的特点．

比如，一个人可以问 “所有的自然数 $a$ 都可以写成另一个自然数 $b$ 加 $0$ 的形式吗？” 为了回答这个问题，我们可以朴素地枚举写出我们知道的所有自然数并一一带入这个谓词中验证，直到谓词对所有的自然数都成立或者找到一个反例为止.显然这是不合实际的，因为我们永远也无法完成逐个验证自然数的任务：.

以上的讨论指出，人类有结合直觉理解一个给定的自然数 $n$ 的心智能力，但是因为没有人真正 “体验” 过无限是什么，因此人类心智无法准确地描述 “全体自然数” 这个无限的概念，更不用说能够证明关于全体自然数的性质了．换句话说，我们连在我们的数学宇宙中能否不出悖论地存在 “全体自然数” 这个集合都无法证明.

虽然我们无法用枚举的形式来定义自然数，我们可以避开提及无穷枚举，而试用以下的描述：

1. 0 是自然数.
2. 如果 $k$ 是自然数，那么 $k$ 的 “下一个元素” $\sigma(k)$ 也是自然数.

这个描述看似是可行的，但是考虑以下的例子：对于 $A=\{a,b\}$，如果定义 $0=a$ 以及 $\sigma(a)=b$ 和 $\sigma(b)=a$．$A$ 显然符合以上的条件，但它显然不是我们想象中 “全体自然数” 的样子——“全体自然数”显然不仅只有两个元素．因此，我们需要采用更加严谨的定义：这一次，

自然数是通过 Peano 算数公理定义的，任何符合这套公理的集合都可以认为是全体自然数的集合；这比定义一个特定的集合为自然数更有灵活性．对满足 Peano 公理的任何集合，如果我们表记 $e$ 为 $0$，$\sigma(0)$ 为 $1$，$\sigma(\sigma(0))=\sigma(1)$ 为 $2$ … 那么我们得到的就是我们习以为常的用阿拉伯数字表现的自然数了.

Peano 公理定义的自然数是从 $0$ 而不是 $1$ 开始的．你或许会说，把 $e$ 记成 $1$ 和记成 $0$ 有什么区别？其实是没有区别的．只不过，从 $1$ 开始的自然数缺乏一个加法零元：缺乏一个令 “任何自然数 $n$ 加 $x$ 仍等于 $n$” 的自然数 $x$．如果我们要让自然数成为一个完整的代数结构（幺半群，见下文），那么在定义自然数加法和乘法的时候 $1$ 就得起 $0$ 的作用．我们自然不希望形如 “任何自然数 $n$ 加 $1$ 仍等于 $n$” 这样的算数定律，因此把 $0$ 算作自然数是一个更加合理的选择.

同时，这样的定义让像 “‘3’ 的本质是什么？” 的哲学命题失去了意义：如果问的是形而上的数学本体（ontology），那么显然这个问题的答案是简单干脆的 “集合”，因为我们约定数学宇宙中存在且仅存在集合，不存在什么模糊神秘的宇宙奥妙．

构建自然数

目前，我们只定义了自然数需要满足什么性质，还不确定有没有满足这个性质的集合．所以接下来， 我们要通过集论公理，构建出一个满足 Peano 公理的自然数模型（model）．

首先，我们需要一些辅助的概念：

一个集合 $A$ 的后继集为 $A\cup \{A\}$，记 $$A^+=A\cup \{A\}$$

对给定集合 $A\in \mathcal{A}$，显然 $a\in \mathcal{P}(A)$，$\{A\} \subseteq \mathcal{P}$ 或 $\{A\} \in \mathcal{P}(\mathcal{P}(A))$，因此 $f\subseteq \mathcal{P}\times \{A\} \in \mathcal{P}(\mathcal{P}(A))$，根据分类公理 $f$ 是集合.

对于归纳集 $N$，映射 $\sigma=\{ (n,n^+) \mid n\in N\}$ 满足

1. $\sigma$ 是单射函数.
2. $\varnothing \notin \mathrm{ran}(\sigma)$

1. 我们首先需要证明 $\sigma$ 是映射．显然给定 $n\in\mathbb{N}$，根据配对公理和并集公理，其后继集是独特的，因此 $\sigma$ 是映射．

   $\sigma$ 也是单射的；若存在 $n_1\neq n_2$ 有 $\sigma(n_1)=\{n_1,n_1^+\}=\sigma(n_2)=\{n_2,n_2^+\}$，因为后继集只含两个元素，必有 $n_1=n_2^+=\{n_2,\{n_2\}\}$，因此 $n_2\in n_1$；类似地有 $n_2=n_1^+=\{n_1,\{n_1\}\}$ 且 $n_1\in n_2$．但根据定理 8.2 这是不可能的．因此 $\sigma$ 是单射的．

2. 根据后继集定义，对任意 $n^+\in \sigma$，显然 $n\in n^+$，$n^+\neq \varnothing$．因此（2）显然成立.

归纳集似乎有希望满足 Peano 公理．归纳集存在吗？目前我们的公理系统无法给出明确答案．因此我们需要一条新的公理.

无穷公理其实是比我们需要的更强的命题：它保证了归纳集的存在，但是可能存在许许多多结构臃肿的归纳集．这些归纳集不一定都能满足 Peano 公理．所以，不妨考虑以下这个 “最小” 的归纳集：

所有归纳集的集合 $\mathcal{N}$ 的交集 $\omega =\bigcap\mathcal{N}$ 也是归纳集．$\omega$ 满足 Peano 公理.

根据无穷公理，$\mathcal{N}$ 非空．根据归纳集定义，任意归纳集都含 $\omega$ 为元素，因此必有 $\varnothing\in \omega$.

假设 $n\in \omega$，那么 $n$ 必在所有归纳集内，根据归纳集定义, $n^+$ 也在所有归纳集内，因此 $n^+\in\omega$．因此 $\omega$ 也是归纳集.

为证明 $\omega$ 满足 Peano 公理，我们首先定义 $e=\varnothing \in \omega$ 和 $\sigma=\{ (n,n^+) \mid n\in \omega\}$．显然根据定理 19，$\sigma$ 满足 Peano 公理的前两条．考虑任意 $S\subseteq \omega$．如果 $S$ 满足 $e\in S$ 且对任意 $k\in S$, $\sigma(k)\in S$，那么 $S$ 是归纳集；又因为 $\omega$ 是所有归纳集的并集，有 $\omega\subseteq S$，因此 $\omega=S$.

$\omega$ 之所以 “最小”，是因为它是所有归纳集的交集．定理 20 证明了 $\omega$ 是一个符合 Peano 公理的集合，即它是自然数的模型．在这个模型中， $\varnothing$ 代表了自然数 $0$，$\varnothing^+=\{\varnothing, \{\varnothing\}\}$ 代表自然数 $1$，$(\varnothing^+)^+=\{\varnothing, \{\varnothing\},\{\varnothing, \{\varnothing\}\}\}$ 代表自然数 $2$……以此类推.

在下文中，我们将讨论自然数的泛有性质，而并非模型 $\omega$ 的特殊性质．因此在下文中，“自然数”或 $\mathbb{N}$ 将表示满足 Peano 公理的任意集合，不一定是 $\omega$.

数学归纳法与递归定义

Peano 公理的第三则描述的是自然数的数学归纳性质（property of induction），它有着深远的实际意义．如果我们需要证明某性质 $P(n)$ 对全体自然数成立，那么我们只需要证明子集 $S=\{n\mid n\in\mathbb{N} \wedge P(n)\}$ 是归纳集就行了，而证明 $S$ 是归纳集有两个充要的步骤：

1. $P(0)$ 成立
2. 对自然数 $k$，若 $P(k)$ 成立，那么 $P(\sigma(k))$ 也成立

这就是数学归纳证明法，它是证明自然数性质最强有力的证明工具．对于归纳法，有两点值得强调：

1. 归纳法并不是哲学意义上的归纳（根据有限的样本对无法直接观察的整体进行推断），它是依赖自然数的定义进行的严谨的演绎证明.
2. 在很多场合下，大小为 $\sigma(k)$ 的问题能被拆解成大小为 $k$ 的子问题，使推导步能被应用（在图论中尤其常见）．从 $k$ 问题倒着复原 $\sigma(k)$ 问题的倒着解题的方式在这种情况下往往会出错．

作为练习和示范，让我们试着证明 “$n$维有序数组是有定义的.” 这一断言对全体自然数 $n$ 都成立.

• 显然当 $n=0$，$0$ 维有序数组即 $()=\varnothing$ 是有定义的
• 假设 $k$ 维有序数组是有定义的.
• 给定一个 $k$ 维有序数组 $a$ 和一个元素 $b$，根据定理 6，我们知道 $((a),b)$ 是有定义的，那么 $k+1$ 维有序数组是有定义的.

因此，我们可以定义 $n$ 维的有序数组，简写为 $(x_1,x_2,x_3,…,x_n)$.

目前，$\mathbb{N}$ 还没有后继函数以外的任何结构．为了在做其上做基本的算数，我们需要借助数学归纳证明一个新的定理，使我们可以通过递归（recursion）来严谨地定义相关的函数.

对集合 $A$, 给定一个元素 $a \in A$, 对映射 $f: A \to A$，存在唯一的函数 $h: \mathbb{N} \to A$ 满足

1. $h(0) = a$，
2. 对所有 $n\in \mathbb{N}$, $h(\sigma(n)) = f(h(n))$.

我们不知道有没有类似的函数存在，因此最好的证明 $h$ 存在的方式是构造法．因此定义一系列辅助函数 $h_k: \mathbb{N}\to \mathbb{N}$, $k\in\mathbb{N}$ 满足以下性质：

1. $h_0=\{(0,a)\}$
2. $h_{\sigma(k)}=h_k\cup \{(\sigma(k),f(h_k(k))\}$

可以通过归纳法证明，对任意自然数 $k\in\mathbb{N}$，$h_k$ 都满足 $h_k \in \mathbb{N}\times A$，因此是因分类公理良好定义的集合

• $h_0$ 显然是集合．
• 假设 $h_k$ 是集合．
• 根据配对定理 $h_{\sigma(k)}$ 是 $h_k$ 和另一个良好定义集合的并集，也是集合.

那么，考虑 $h=\bigcup_{k\in \mathbb{N}} h_k$，因为 $h$ 是集合的并集，所以根据并集公理也是集合．并且，因为每一个 $h_k$ 都是有序对的集合，$h$ 也是有序对的集合，因此它是一个二元关系，因此 $\mathrm{dom}(h)$，$\mathrm{ran}(h)$ 都是集合.

我们需要证明 $\mathrm{dom}(h)=\mathbb{N}$，用归纳法结合定义证明非常简单：

• 对 $0\in \mathbb{N}$，有 $h_0\in h$，所以显然 $0\in \mathrm{dom}(h)$．
• 假设对 $k\in \mathbb{N}$，有 $k\in \mathrm{dom}(h)$
• 我们要反证 $k\in \mathrm{dom} (h)$．若 $\sigma(k)\notin \mathrm{dom}(h)$，这意味不存在 $h_{\sigma(k)}\in h$ 满足 $h_{\sigma(k)}(\sigma(k))=f(h(k))$．但是我们知道 $h_{\sigma(k)}$ 被定义为 $h_{\sigma(k)}=h_k\cup \{(\sigma(k),f(h_k(k))\}$ 且根据公理存在．所以一定有 $\sigma(k)\in \mathrm{dom}(h)$.

接下来需用归纳法证明 $h$ 在全体自然数上是函数（注意，我们并不是证明每个 $h_k$ 都是函数，而只是证明它们的并集 $h$ 是）．

• 对 $0\in \mathbb{N}$，显然仅存在 $y$ 满足 $0hy$；若存在 $y\neq y'$ 满足 $0hy'$，那么 $(0,y)$, $(0,y')$ 中必有一个是 $(\sigma(k), f(h(k)))$ 的形式，即 $0=\sigma(k)$ 对某 $k\in\mathbb{N}$；这是不可能的，因为 $0\notin \mathrm{ran}(\sigma)$
• 假设对 $k\in \mathbb{N}$，仅存在一个 $y'$ 满足 $h(k)=y'$．
• 我们用反证证明 $\sigma(k)$ 的情况．假设存在 $y\neq y'$ 满足 $h(\sigma(k))=y$ 及 $h(\sigma(k))=y'$，那么必存在 $h_{\sigma(a)}$, $h_{\sigma(b)} \in h$ 使得 $h_{\sigma(a)}(\sigma(k))=y=f(h_a(k))$，$h_{\sigma(b)}(\sigma(k))=y'=f(h_b(k))$．若 $h_a(k)\neq h_b(k)$，那么和归纳假设是矛盾的．因此必有 $h_a(k)=h_b(k)$，因为 $f$ 是函数，蕴含 $y=f(h_a(k))=f(h_b(k))=y'$，与 $y\neq y'$ 的假说矛盾，因此仅存在独特的 $y$ 满足 $h(\sigma(k))=y$.

因为 $h$ 是函数，且每一个组成 $h$ 的 $h_k$ 都有 $h_k\in \mathbb{N}\times A$，因此我们可以写作 $h:\mathbb{N}\to A$．到此，我们已经证明了 $h$ 的存在性．为反证唯一性，假设存在同样满足条件的函数 $h'\neq h$．我们再一次用归纳法，证明 $h$ 和 $h'$ 在全体自然数上取同样的值：

• 对 $0\in \mathbb{N}$，显然必有 $(0,a)\in h'$, $(0,a)\in h$，又因为它们都是函数，所以不能在 $0$ 取其他的值，所以 $h(0)=h'(0$．
• 假设对 $k\in \mathbb{N}$，有 $h(k)=h'(k)$．
• 我们用反证证明 $\sigma(k)$ 的情况．假设 $h(\sigma(k))\neq h'(\sigma(k))$，那么根据定义有 $f(h(k))\neq f(h'(k))$，可根据归纳假说 $h(k)=h'(k)$，因此与 $f$ 是函数的条件矛盾．所以一定有 $h(\sigma(k))= h'(\sigma(k))$

因为对任意 $n\in\mathbb{N}$，$h(n)=h'(n)$，它们一定包含相同的有序对，根据集合相等的定义有 $h=h'$.

这条定理非常重要：当我们需要以递归的形式定义任何函数时，构造出来的函数的良好定义性与唯一性都依赖这条定理.

$\mathbb{N}$ 的代数结构

在自然数上定义我们熟知的加法和乘法的算数法则，就需要递归定义.

给定一个自然数 $n$，都存在一个独特的映射 $+_n: \mathbb{N} \to \mathbb{N}$ 满足对任意 $m\in\mathbb{N}$， $$+_n(0)=n$$ $$+_n(\sigma(m))=\sigma(+_n(m))$$ 以及 $\cdot_n: \mathbb{N}\to \mathbb{N}$，满足对任意 $m\in\mathbb{N}$， $$\cdot_n(0)=0$$ $$\cdot_n(\sigma(m))=+_n(\cdot_n(m))$$ 利用 $+_n$，可定义映射自然数加法 $+: \mathbb{N}\times \mathbb{N} \to \mathbb{N}$ 和自然数乘法 $\cdot: \mathbb{N}\times \mathbb{N}\to \mathbb{N}$ ，对 $m,n\in\mathbb{N}$ 有 $$m+n=+(m,n)=+_m(n)$$ $$m\cdot n=\cdot(m,n)=\cdot_m(n)$$

$+_n$ 的存在性和独特性只需要在定理 22 中带入 $f(n)=\sigma(n)$ 就可以直接得出．因为 $+_n$ 是映射，$+$ 也是映射.

$\cdot_n$ 的存在性和独特性只在定理 22 中带入 $f(m)=+_n$ 就可以直接得出．类似地 $\cdot$ 也是映射.

$+_n(m)$ 和 $+(n, m)$ 之间的关系近似于函数式语言中柯里化的概念．$+_n(m)$ 像一个叫 $\mathtt{addOne(m)}$ 的递归程序．这个程序在 $m\neq 0$ 时返还 $\mathtt{addOne(m)}=1+\mathtt{addOne(m-1)}$，当 $m= 0$ 时返还 $\mathtt{addOne(0)}=0$．因此 $\mathtt{addOne(m)}$ 的最终返还的结果会是 $n$ 加上 $m$ 个 1，因此等于 $m+n$．而 $+(n, m)$ 则是“包装”$+_n(m)$ 的一个母函数，后者是前者第一个变量赋值 $n$ 柯里化的结果.

自然数上的加和乘的运算符合一些代数规律．代数指的是集合中的元素在二元运算下具有的性质．集合以及集合上的二元运算一并构成了代数结构（algebraic structure），通常以有序对的方式写出来．如果说 Peano 公理是 “自然数” 这个概念的抽象的话，那么代数结构的公理就是 “加减乘除” 的概念的抽象.

代数结构的定义同样也是外延性的：如果一个集合和运算的组合满足某个代数结构的定义，那么就可以说它就 “是” 那个代数结构．这正如那句著名的英谚：

If it looks like a duck, swims like a duck, and quacks like a duck, then it is a duck.

当然，这里的 “是” 并非集论的 “相等”，因为代数结构是概念，而不是具体的集合，所以不能说集合等于它.

我们可以定义一些基本代数结构的名称和它们相应的公理：

正因为代数结构是从算数的特性抽象得来的，对于半环 $(R, \phi, \psi)$，一般会把 $\phi$ 称作加法 $+$，其单位元记作 $0$；把 $\psi$ 称为乘法 $\cdot$，其单位元记作 $1$.

通过幺半群的公理，我们可以得到以下定理：

对幺半群 $(G,\phi)$，$\phi$ 的单位元是唯一的

若 $\phi$ 有独特单位元 $e, e'$，对任意 $a\in A$ 满足 $\phi(a,e)=\phi(e,a)=\phi(a,e')=\phi(e',a)=a$．那么一定 $\phi(e,e')=\phi(e',e)=e=e'$，那么 $e=e'$，和独特性假设相悖.

不难发现，上一节中定义的自然数加、乘法，就是自然数上的二元运算．自然数、自然数加、自然数乘构成半环的代数结构.

$(\mathbb{N},+)$ 和 $(\mathbb{N},\cdot)$ 都是交换幺半群．$(\mathbb{N},+,\cdot)$ 是半环.

证明加法的代数规律：

1. 证明加法单位元是 $0$：归纳证明对任意 $n\in \mathbb{N}$，$0+n=n+0=n$：
   • 显然对$n=0$, $+_0(0)=+_0(0)=0$．
   • 若对 $+_0(k)$ 有 $+_0(k)=+_k(0)=k$，那么根据 $+_0$ 的定义，$+_0(\sigma(k))=\sigma(+_0(k))=\sigma(+_k(0))=\sigma(k)=\sigma(k)+0=+_{\sigma(k)}(0)$.
2. 归纳证明任意 $a,b,c\in \mathbb{N}$ 的加法都符合结合律：$(a+b)+c=a+(b+c)$．固定 $a, b$，在 $c$ 的取值上归纳：
   • 若 $c=0$，那么根据0的加法规律显然有 $(a+b)+0=a+b=a+(b+0)$．
   • 若 $c=k$ 时有 $(a+b)+k=a+(b+k)$，那么根据 $+_{a+b}$ 的定义有 $(a+b)+\sigma(k)=+_{a+b}(\sigma(k))=+_{a+b}(\sigma(k))=\sigma((a+b)+k)$, 根据归纳假说 $\sigma((a+b)+k)=\sigma(a+(b+k))=a+\sigma(b+k)=a+(b+\sigma(k))$．
   因此加法满足结合律.
3. 归纳证明任意 $n, m\in \mathbb{N}$ 的加法都是交换的：$+_m(n)=+_n(m)$．固定 $m$，在 $n$ 的取值上归纳：
   • 若 $n=0$，那么根据上条显然有 $+_m(0)=+_0(m)$．
   • 若 $n=k$ 时有 $+_m(k)=+_k(m)$，那么根据定义 $+_m(\sigma(k))=\sigma(+_m(k))=+_k(\sigma(m))$．
   因此加法满足交换律.

因此 $(\mathbb{N},+)$ 是交换幺半群．乘法的规律的证明是完全相似的．乘法的单位元是 $\sigma(0)=1$．

证明乘法在加法上分配：给定 $b,c$，在 $a$ 的取值上归纳:

• 当 $a=0$，显然 $0(b+c)=0=0+0=0b+0c$．
• 假设当 $a=k$，$k(b+c)=kb+kc$ 成立，那么对 $a=\sigma(k)$，有 $\sigma(k)(b+c)=(b+c)\sigma(k)=\cdot_{b+c}\sigma(k)=\cdot_{b+c}\sigma(k)=\sigma(kb+kc)=\sigma(k)b+\sigma(k)c$

定理 25.2 和 25.3 通常称为消除率．或许你会认为这两条定律是稀松平常的，但并非所有的幺半群都满足这两条定律．这体现在我们无法通过幺半群的公理达到这两条定理，而必须通过 Peano 系统的特性来证明.

1. 对任意 $a\in\mathbb{N}$，有 $\sigma(a)=a+1$
2. 对任意 $a,b,c\in\mathbb{N}$，$a+c=b+c$ 当且仅当 $a=b$
3. 对任意 $a,b \in\mathbb{N}$ 和 $c\neq 0$，$ac=bc$ 当且仅当 $a=b$

1. 在 $a$ 的取值上归纳：
   • 显然对 $a=0$, 根据定义有 $\sigma(0)=1=0+1$．
   • 若对 $k\in\mathbb{N}$ 有 $\sigma(k)=k+1$，那么对 $\sigma(k)$，有 $\sigma(\sigma(k))=\sigma(k+1)=\sigma(k)+1$.
2. $\Leftarrow$: 显然成立．$\Rightarrow$: 在 $c$ 的取值上归纳：
   • 当 $c=0$，对任意 $a, b$ 显然 $a+0=b+0$ 蕴含 $a=b$
   • 假设当 $c=k$，对任意 $a, b$，有 $a+k=b+k$ 蕴含 $a=b$
   • 考虑 $c=\sigma(k)=k+1$，对任意 $a, b$，有 $a+k+1=b+k+1$．运用交换律和结合律得 $(a+1)+k=(b+1)+k$，运用归纳假设显然有 $\sigma(a)=a+1=b+1=\sigma(b)$，根据 $\sigma$ 的单射性有 $a=b$.
3. $\Leftarrow$: 显然成立．$\Rightarrow$: 固定 $c\neq 0$，在 $a$ 的取值上归纳：
   • 当 $a=0$，显然成立.
   • 假设 $kc=bc$ 蕴含 $a=0$ 或 $k=b$.
   • 考虑当 $a=\sigma(k)=k+1$，假设有 $(k+1)c=kc+c=bc$．显然 $b\neq 0$，那么存在 $b'$ 满足 $b=b'+1$，那么有 $kc=b'c$．应用归纳假设有 $k=b'$，那么 $a=k+1=b$.

$\mathbb{N}$ 上的序关系

为了在自然数上建立序关系，我们作以下的观察：

$\mathbb{N}$ 有如下性质：

1. 对任意 $x\in \mathbb{N}$，若 $x\neq 0$，那么存在 $k$ 满足 $x = \sigma(k)$.
2. 对任意 $x\in \mathbb{N}$，$x\neq \sigma(x)$.
3. 对任意 $x, y\in \mathbb{N}$，若 $y\neq 0$，$x\neq x+y$.
4. 对任意 $x, y\in \mathbb{N}$，若 $x\neq y$，那么存在自然数 $m\neq 0$ 满足 $x+m=y$ 或 $y+m=x$.

1. 令 $S=\{x\in \mathbb{N}\mid \exists k: x=0\vee x= \sigma(k) \}$.
   • 显然 $0\in S$.
   • 若 $k \in S$.
   • 考虑 $x=\sigma(k)$．显然存在 $k$ 使得 $\sigma(k)=x$.
   因此 $S=\mathbb{N}$.
2. 令 $S=\{x\in \mathbb{N}\mid x\neq \sigma(x) \}$.
   • 显然 $0\notin \mathbb{ran}(\sigma)$，因此 $0\neq \sigma(0)$．
   • 若 $k \neq \sigma(k)$.
   • 考虑那么对 $\sigma(k)$．若有 $\sigma(\sigma(k))=\sigma(k)$，与 $\sigma$ 是单射函数的事实矛盾，因此必有 $\sigma(\sigma(k))\neq \sigma(k)$
   因此 $S=\mathbb{N}$.
3. 欲证 $S=\{x\in\mathbb{N}\mid \forall y\neq 0 : x\neq x+y \}=\mathbb{N}$.
   • 显然对任意 $y\neq 0$ 都有 $0\neq 0+y=y$，因此 $0\in T$．
   • 若 $k \in S$．那么对任意 $y\neq 0$ 都有 $k\neq k+y$
   • 考虑 $\sigma(k)=k+1$．显然根据 2 有 $k\neq k+1$，根据 $\sigma$ 的单射性有 $\sigma(k)\neq \sigma(k+y)$ 即 $k+1\neq k+1+y$，那么 $\sigma(k)\in S$.
   因此 $S=\mathbb{N}$.
4. 对任意一个自然数 $x$，我们都可以研究和 $x$ 可以 “相比” 的自然数 $y$ 的集合：$S(x)=\{y\in \mathbb{N}\mid \exists m\neq 0: x=y\vee x+m=y \vee y+m=x \}$．我们希望证明对任意 $x$，$S(x)=\mathbb{N}$.
   • 显然 $0=0$，因此 $0\in S(0)$．若 $y\in S(0)$，那么有三种可能：
     1. $y=0$，那么 $\sigma(y)=1$，存在自然数 $1$ 有 $0+1=1$，因此 $\sigma(y)\in S(0)$；
     2. 存在自然数 $m\neq 0$ 有 $y+m=0$．这是不可能的，因为对 $m\neq 0$，$m$ 可写成 $\sigma(k)$，令 $0=y+m=\sigma(+_{y}(k))$，而 $0\notin \mathrm{ran}(\sigma)$
     3. 要么（3）存在自然数 $m\neq 0$，$y=m+0=m$，那么 $\sigma(y)=\sigma(m)=0+\sigma(m)$，有 $\sigma(y)\in S(0)$．
     那么 $S(0)=\mathbb{N}$.
   • $S(k)=\mathbb{N}$．
   • 考虑 $S(\sigma(k))$．因为 $\sigma(k)=k+1$，对任意 $y \in S(k)$，有三种可能：
     1. $y=k$，那么存在自然数 $1$ 有 $\sigma(k)=y+1$，因此 $y\in S(\sigma(k))$；
     2. 存在自然数 $m\neq 0$ 有 $y+m=k$，那么存在自然数 $m+1$ 有 $\sigma(k)=y+(m+1)$，因此 $y\in S(\sigma(k))$；
     3. 存在自然数 $m\neq 0$ 有 $y=m+k$, 因为 $m\neq 0$，那么根据 2 存在自然数 $l$ 令 $m=l+1$．那么存在自然数 $l$ 有 $y=\sigma(k)+l$，因此 $y\in S(\sigma(k))$；
     因此$S(\sigma(k))=\mathbb{N}$.
   因此对任意自然数 $k$，$S(k)=\mathbb{N}$.

借此，我们可以严格地定义排序关系：称一个自然数 $a$ 小于另一个自然数 $b$，当且仅当存在另一个非零的自然数 $k$，使得 $a$ 还要 “增长” $k$，才会达到 $b$.

存在关系 $< \subseteq \mathbb{N}\times \mathbb{N}$，对任意 $x, y\in\mathbb{N}$，有 $x<y$ 当且仅当存在 $k\in \mathbb{N}$，$k\neq 0$，满足 $$x +k = y$$

$<$ 是排序关系.

• 三分性：对任意自然数 $x, y$，根据定理 26.2，$m=n$，$m<n$，$n<m$ 至少有一个为真．

  为证明三个关系中最多一个为真，不失一般性地，假设 $m=n$ 且 $m<n$．那么存在自然数 $m+k=n=m$，这与但因定理 25.2 相悖.

  假设 $m<n$ 且 $m>n$，那么存在非零自然数 $i, j$ 满足 $m+i=n$，$n+j=m$，那么有 $n+i+j=n$，因定理 25.3 有 $i+j=0$，显然是不可能的．

• 传递性：若 $a<b$，$b<c$，那么存在自然数 $m,n\neq 0$ 满足 $a+n=b$，$b+m=c$，那么 $a+(m+n)=c$，即 $a<c$.

很容易得到以下结论；易见 28.2 和 28.3 是 25.2 和 25.3 的不等式版本：

1. $0<1$
2. 对任意 $a,b,c\in\mathbb{N}$，$a+c< b+c$ 当且仅当 $a<b$
3. 对任意 $a,b\in\mathbb{N}$ 和自然数 $c\neq 0$，$ac< bc$ 当且仅当 $a<b$

1. 显然存在 $1=\sigma(0)\neq 0$ 有 $0 + 1= 1$
2. • $\Rightarrow$: 若 $a+c<b+c$，那么存在 $m\neq 0$ 使得 $a+c+m=b+c$．假设 $a>b$，那么存在 $m' \neq 0$ 使得 $a=b+m'$．那么有 $b+m'+c+m=b+c$，由定理 25.2 得 $m'+m=0$，由 $+$ 的定义知这是不可能的．因此必有 $a\leq b$．假设 $a=b$，那么 $a+c=b+c$，矛盾，因此 $a\neq b$．因此必有 $a<b$.
   • $\Leftarrow$：由定理 25.2 直接得．
3. • $\Rightarrow$: 若 $ac<bc$，那么存在 $m\neq 0$ 使得 $ac+m=bc$．假设 $a>b$，那么存在 $m' \neq 0$ 使得 $a=b+m'$．那么有 $bc+m'c+m=bc$，由定理 25.2 得 $m'c+m=0$，由 $+$ 的定义知这是不可能的．因此必有 $a\leq b$．假设 $a=b$，那么 $a+c=b+c$，矛盾，因此 $a\neq b$．因此必有 $a<b$.
   • $\Leftarrow$：由定理 25.2 直接得．

有限和无限

既然自然数是无限的，那么也就代表着我们有了区分有限和无限的基准：：

根据自然数的定义，每个自然数都含比它小的所有自然数为元素；因为我们的自然数含 0，因此有 $n$ 个比 $n$ 小的元素．那么，存在双射函数 $f:A\to n$ 的意思 $A$ 中的元素可以通过 $f$ 和 $n$ 个元素一一对应，即被这 $n$ 个元素 “编号”．因此，称 $A$ 含 $n$ 个元素.

可数无限的意思是，如果给集合 $A$ 中的每一个元素编号，自然数是够用的．虽然这听起来不是很合常理（毕竟无限的东西有什么不够用的？）但在将来，我们会遇到自然数不够用的情况，即不可数无限的集合.

对于自然数来说，每个给定的自然数都是有限的，但是全体自然数的集合是可数无限的．这可以用归纳法证明：

1. 对任意非零自然数 $n\in\mathbb{N}$，$n$ 是有限的，有 $|n|=n$.
2. 全体自然数的集合 $\mathbb{N}$ 是可数无限的.

1. 显然 $\{(k, k)\mid k\in n \}$ 是一个 $n\to n$ 的双射函数.
2. 显然 $\{(n, n)\mid n\in\mathbb{N} \}$ 是一个 $\mathbb{N}\to \mathbb{N}$ 的双射函数.

组合计数学（enumerative combinatorics）研究的主要内容就是用有创意的方法来证明一些有限集合的大小．例如，我们可以研究从不相交的有限集合 $A$ 和 $B$ 中各抽一个元素有多少抽法，而这个问题要求的就是笛卡尔积 $A\times B$ 的势，$|A\times B|$．我们在组合数学的章节里会回到这个话题上来.

附录

集合代数的常见规律

定义了并集后，交、并、补后，常用集合代数的运算就已经齐全了．在将来的章节中，我们会用到以下的常用关系：

对集合 $A, B, C, \mathcal{B}, \mathcal{C}$,

1. 交和并的交换律 $$A\cup B=B\cup A$$ $$A \cap B = B \cap A$$
2. 交和并的结合律 $$A \cup (B \cup C) = (A \cup B) \cup C$$ $$A \cap (B \cap C) = (A \cap B) \cap C$$
3. 交和并的分配律 ($\mathcal{D}\neq \varnothing$) $$A \cap \bigcup \mathcal{C} =\bigcup_{C\in \mathcal{C}} A\cap C$$ $$A \cup \bigcap \mathcal{D} = \bigcap_{D\in \mathcal{D}} A\cup D$$
4. 补的德摩根律 $$B - \bigcup \mathcal{A} = \bigcap_{A\in \mathcal{A}} B -A$$ $$B - \bigcap \mathcal{A} = \bigcup_{A \in \mathcal{A}}B - A$$
5. 子集的性质
   1. 若 $A\subseteq B$，那么 $A \cup C \subseteq B \cup C$
   2. 若 $A\subseteq B$，那 么$A \cap C \subseteq B \cap C$
   3. 若 $A\subseteq B$，那么 $C-B \subseteq C-A$
   4. 若 $\mathcal{B}\subseteq \mathcal{C}$，那么 $ \bigcup \mathcal{B} \subseteq \bigcup \mathcal{C}$
   5. 若 $\mathcal{B}\subseteq \mathcal{C}$ 且 $\mathcal{B}\neq \varnothing$，那么 $ \bigcap \mathcal{C} \subseteq \bigcap \mathcal{B}$

所有运算关系都可以用交、并、补的定义及 “逻辑与证明” 中的相应规律证明.

函数复合集合代数的运算规律

给定函数 $f$ 和集合 $A, B, \mathcal{C}$

1. 并集的像等于像的并集：$$f(\bigcup \mathcal{C}) = \bigcup_{C \in \mathcal{C}} f(C)$$
2. 交集的像是像的交集的子集，若 $f$ 单射，那么两者相等：$$f(\bigcap \mathcal{C}) \subseteq \bigcap_{C \in \mathcal{C}} f(C)$$
3. 补集的像是像的补集的子集，若 $f$ 单射，那么两者相等：$$f(B)-f(A) \subseteq f(B-A)$$
4. 并集的原像等于原像的并集：$$f^{-1}(\bigcup \mathcal{C}) = \bigcup_{C \in \mathcal{C}} f^{-1}(C)$$
5. 交集的原像等于原像的交集：$$f^{-1}(\bigcap \mathcal{C}) = \bigcap_{C \in \mathcal{C}} f^{-1}(C)$$
6. 补集的原像等于原像的补集：$$f^{-1}(B)-f^{-1}(A) = f^{-1}(B-A)$$

1. 根据定义，$y\in f(\bigcup \mathcal{C})$ 当且仅当存在 $x\in \bigcup \mathcal{C}$ 满足 $f(x)=y$，当且仅当存在 $C\in \mathcal{C}$ 令 $x\in C$ 满足 $f(x)=y$，当且仅当 $y\in f(C)$ 对某 $C\in \mathcal{C}$．
2. 根据定义，$y\in f(\bigcap \mathcal{C})$ 当且仅当存在 $x\in \bigcap \mathcal{C}$ 满足 $f(x)=y$，当且仅当对所有 $C\in \mathcal{C}$ 都存在 $x\in C$ 满足 $f(x)=y$，蕴含 $y\in f(C)$ 对所有的 $C\in \mathcal{C}$．若 $f$ 单射，$y\in \bigcap_{C\in \mathcal{C}}f(C)$ 当且仅当对所有 $C\in \mathcal{C}$ 对所有 $C\in \mathcal{C}$ 都存在唯一的 $x'\in C$ 满足 $f(x')=y$，蕴含 $x'\in\bigcap \mathcal{C}$，蕴含 $y\in f(\bigcap \mathcal{C})$
3. 根据定义，$y\in f(B)-f(A)$ 当且仅当存在 $b\in B$ 满足 $f(b)=y$ 但不存在 $a\in A$ 满足 $f(a)=y$，蕴含 $b\notin A$，蕴含 $b\in B-A$，蕴含 $y\in f(B-A)$．若 $f$ 单射，$y\in f(B-A)$ 当且仅当存在唯一的 $x'\in B-A$满足 $f(x')=y$，蕴含不存在 $x\in A$ 满足 $f(x)=y$，蕴含 $y\notin f(A)$，蕴含 $f(B)-f(A)$
4. 根据定义，$x\in f^{-1}(\bigcup \mathcal{C})$ 当且仅当存在 $y\in \bigcup \mathcal{C}$ 满足 $f(x)=y$，当且仅当存在 $C\in \mathcal{C}$ 令 $x\in C$ 满足 $f(x)=y$，当且仅当 $x\in f^{-1}(C)$ 对某 $C\in \mathcal{C}$．
5. 根据定义，$x\in f^{-1}(\bigcap \mathcal{C})$ 当且仅当存在 $y\in \bigcap \mathcal{C}$ 满足 $f(x)=y$，当且仅当对所有 $C\in \mathcal{C}$ 都存在 $y\in C$ 满足 $f(x)=y$，当且仅当 $x\in f^{-1}(C)$ 对所有的 $C\in \mathcal{C}$
6. 根据定义，$x\in f^{-1}(B)-f^{-1}(A)$ 当且仅当存在 $b\in B$ 满足 $f(b)=y$ 但不存在 $a\in A$ 满足 $f(a)=y$，当且仅当存在 $x\in B-A$ 满足 $f(x)=y$

参考文献

• Enderton, H．B．1977．Elements of set theory．1st ed．Cambridge: Academic Press.
• Fraenkel, A．1922．Zu den grundlagen der cantor-zermeloschen mengenlehre．Mathematische Annalen 86 (3) (09/01): 230-7.
• Frank, M．C., Daniel L．Everett, Evelina Fedorenko, and Edward Gibson．2008．Number as a cognitive technology: Evidence from Pirahã language and cognition．Cognition 108 (3) (09/01): 819-24.
• Halmos, P．R．1960．Naive set theory．1st ed．Princeton, NJ: D．Van Nostrand Company.
• Jech, T．2002．Set theory．The Third Millennium ed．New York: Springger.
• Russell, B．1919．Introduction to mathematical philosophy．London: George Allen & Unwin, Ltd.
• Zermelo, E．1908．Untersuchungen Über die grundlagen der mengenlehre．I．Mathematische Annalen 65 (2) (06/01): 261-81.
• Zermelo, E．1930．Über grenzzahlen und mengenbereiche．Fundamenta Mathematicae 16 (1): 29-47.