4. 数学对象

4.1特别的二元关系
4.2自然数集的构造
4.3实数集的构造

4.1特别的二元关系

这一节将引入关系与函数的概念, 并指出一些基本的集合论性质, 以资将来使用.

定义 4.1.1 (二元关系). 我们作以下定义:

定义两个集合 $a, b$ 构成的有序对为 $(a, b) = {{a}, {a, b}}$ .

定义两个集合的积为 $A \times B = {(a, b) ∣ a \in A, b \in B}$ .

定义二元关系为某个 $A \times B$ 的子集 $R$ . 特殊的, 若 $R \subseteq A \times A$ , 则称 $R$ 是 $A$ 上的二元关系.

对二元关系 $R \subseteq A \times B$ , 定义其定义域为 $dom (R) = {x \in A ∣\exists y \in B ((x, y) \in R)}$ , 值域为 $ran (R) = {y \in B ∣\exists x \in A ((x, y) \in R)}$ .

这里的二元关系的概念还很粗糙. 不过, 首要的任务是证明我们定义出来的东西确实是集合. 有序对显然是用三次对集公理, 但是积则需要从 $P (C)$ 中分离出来, 其中 $C \subseteq P (A \cup B)$ , 至于每一步怎么分离留予读者自证. 定义域和值域显然是直接分离.

接下来, 有序对当然要和对集显出不一样的特殊性质, 才对得起我们的苦心定义.

命题 4.1.2 (有序对相等的外延性). $(a, b) = (a^{'}, b^{'}) \leftrightarrow (a = a^{'} \land b = b^{'})$

证明. 从右向左是显然的, 考虑从左到右. 这时条件就是

{{a}, {a, b}} = {{a^{'}}, {a^{'}, b^{'}}}

, 分类讨论

a = b

与

a \neq = b

的两种情况, 由对集的定义就能得出结论.

$□$

接下来先考虑最重要的一类二元关系, 它们就是函数.

定义 4.1.3 (函数). 若二元关系 $f$ 满足 $\forall x \in A \forall y \in B \forall z \in B ((x, y) \in f \land (x, z) \in f \to y = z)$ , 则称 $f$ 是一个部分函数. 常用 $f (x) = y$ 代表 $(x, y) \in f$ . 在定义函数时, 又常常记为 $f, x \mapsto y$

如果 $d o m (f) = X$ 且 $r an (f) \subseteq Y$ , 则称 $f$ 是 $X$ 到 $Y$ 的函数, 简称函数, 记为 $f : X \to Y$ . 注意这很容易与逻辑连接词 " 蕴含 " 混淆, 故我们通常不使用这个记号, 而采取 $f \in Y^{X}$ .

由这个记法我们可以猜出以下定义: $Y^{X} = {f : X \to Y}$ 是全体从 $X$ 到 $Y$ 的函数组成的集合, 由分离公理模式保证.

由于我们这里是集合论, 函数的相等也是集合相等的一种, 自然也会有外延性.

命题 4.1.4 (函数相等的外延性). 两个函数满足 $f = g$ 当且仅当 $dom (f) = dom (g) \land \forall x \in dom (f) (f (x) = g (x))$

证明. 从左向右显然. 从右向左注意

f = {(x, f (x)) ∣ x \in dom (f)}

即可显然.

$□$

定义 4.1.5 (函数的操作). 函数有一些范畴化的性质, 我们一一构造如下.

1.	我们有自然的 $i d_{A} \in A^{A}, a \mapsto a$ 称作恒等函数.
2.	我们还当给定 $b \in B$ 时有自然的 $\overset{ˉ}{b} \in B^{A}, a \mapsto b$ 称作常函数. 在上下文不混淆时我们也会直接拿 $b$ 代称 $\overset{ˉ}{b}$ .
3.	如果有 $f \in B^{A}$ 和 $g \in C^{B}$ , 定义 $g \circ f \in C^{A}, a \mapsto g (f (a))$ .
4.	如果有 $f \in B^{A}$ 和 $A^{'} \subseteq A$ , 定义 $f ∣_{A^{'}} = {(x, y) \in A^{'} \times B ∣ f (x) = y}$ , 称作 $f$ 在 $A^{'}$ 上的限制.
5.	如果 $f \in B^{A}$ 满足 $\forall a_{1}, a_{2} \in A (a_{1} \neq = a_{2} \to f (a_{1}) \neq = f (a_{2}))$ , 则称 $f$ 是单射, 记为 $f : A ↪ B$ .
6.	如果 $f \in B^{A}$ 满足 $\forall b \in B \exists a \in A (f (a) = b)$ , 则称 $f$ 是满射, 记为 $f : A ↠ B$ .
7.	如果 $f$ 又是单射又是满射, 则称 $f$ 是双射, 又称一一对应.

显然, $f \in B^{A} \to f = f \circ i d_{A} = i d_{B} \circ f$ , 在有定义时 $f \circ (g \circ h) = (f \circ g) \circ h$ .

定理 4.1.6 (可消去性). 我们称一个函数 $f \in B^{A}$ 右可消去, 若 $\forall C \forall g_{1}, g_{2} \in C^{B} (g_{1} \circ f = g_{2} \circ f \to g_{1} = g_{2})$ .

我们称一个函数 $g \in C^{B}$ 左可消去, 若 $\forall A \forall f_{1}, f_{2} \in B^{A} (g \circ f_{1} = g \circ f_{2} \to f_{1} = f_{2})$ .

函数左可消去当且仅当是单射, 右可消去当且仅当是满射.

证明. 我们只证左可消等价于单, 另一个留给读者.

单则左可消: 由函数相等的外延性, 左可消去无非是要求说明 $\forall a \in A (g (f_{1} (a)) = g (f_{2} (a)) \to f_{1} (a) = f_{2} (a))$ , 这恰好就由 $g$ 单射指出.

左可消则单: 我们考虑证明不单则不左可消. 若不单, 一定有

b_{1} \neq = b_{2}

使得

g (b_{1}) = g (b_{2})

. 考虑常函数, 我们有

g \circ b_{1} = g \circ b_{2}

, 这说明

g

不左可消.

$□$

定义 4.1.7 (单侧逆). 我们称函数 $f \in B^{A}$ 是函数 $g \in A^{B}$ 的左逆, 若 $f \circ g = i d_{B}$ . 存在左逆简称左可逆.

我们称函数 $f \in B^{A}$ 是函数 $g \in A^{B}$ 的右逆, 若 $g \circ f = i d_{A}$ . 存在右逆简称右可逆.

我们称函数 $f \in B^{A}$ 是函数 $g \in A^{B}$ 的逆, 若它既是左逆又是右逆. 存在逆简称可逆, $g$ 的逆记为 $g^{- 1}$ .

定理 4.1.8 (可逆). 对 $g \in A^{B}$ , 以下等价.

1.	$g$ 可逆
2.	$g$ 有唯一一个逆
3.	$g$ 同时有左逆和右逆
4.	$g$ 是双射

证明. 过于显然, 留作练习. (双射给出逆其实就是有序对里的元素交换一下位置)

$□$

注 4.1.9. 显然左可逆推出左可消去等价于单, 右可逆推出右可消去等价于满, 我们会猜倒过来也成立. 运用和上面相同的方式可以说明单则左可逆, 但是满则右可逆其实是 ZF 不可证明的, 它等价于大名鼎鼎的选择公理, 我们之后将看到它.

此外, 部分函数的概念也并非毫无用处.

定理 4.1.10 (相容函数族). 若有一族 $A \times B$ 上的部分函数 ${f_{i} \subseteq A \times B ∣ i \in I}$ 满足 $\forall a \in A \forall i, j \in I (\exists y, z \in B (f_{i} (a) = y \land f_{j} (a) = z) \to y = z)$ , 则称这族函数是相容的, 或称这是一个相容函数族.

若 $F = {f_{i} \subseteq A \times B ∣ i \in I}$ 是相容函数族, 则 $f = \cup F$ 也是一个部分函数.

证明. 由部分函数的定义显然.

$□$

注 4.1.11. 如果这相容函数族里面的函数的定义域并起来是 $A$ 的话, 这个 $f$ 就是货真价实的函数了. 这个想法将来会有许多用处.

接下来我们讨论另外一些特别的单个集合上的二元关系.

定义 4.1.12 (单个集合上的二元关系的性质). 我们给集合 $X$ 上的二元关系 $R \subseteq X \times X$ 以下这些性质依次命名:

1.	自反性: $\forall x \in X ((x, x) \in R)$
2.	反自反性: $\forall x \in X ((x, x) \neq \in R)$
3.	对称性: $\forall x, y \in X ((x, y) \in R \to (y, x) \in R)$
4.	非对称性: $\forall x, y \in X ((x, y) \in R \to (y, x) \neq \in R)$
5.	反对称性: $\forall x, y \in X ((x, y) \in R \to (y, x) \in R \to x = y)$
6.	传递性: $\forall x, y, z \in X ((x, y) \in R \to (y, z) \in R \to (x, z) \in R)$
7.	完全性: $\forall x, y \in X ((x, y) \in R \lor (y, x) \in R)$
8.	三岐性: $\forall x, y \in X ((x, y) \in R \lor (y, x) \in R \lor x = y)$
9.	外延性: $\forall x, y \in X (\forall z \in X ((z, x) \in R \leftrightarrow (z, y) \in R) \to x = y)$
10.	良基性: $\forall S \subseteq X (S \neq = \emptyset \to \exists s \in S \forall x \in S ((x, s) \neq \in R))$ , 这个 $s$ 又称 $S$ 的最小元.

有了这些名字, 我们就可以顺畅的定义以下这些特殊二元关系的名字了.

定义 4.1.13 (等价关系, 良基关系与各种序). 满足自反性、对称性和传递性的二元关系称作等价关系.

满足良基性的二元关系称作良基关系, 满足外延性和良基性的二元关系称作外延良基关系.

满足自反性和传递性的二元关系称作拟序.

满足自反性、反对称性和传递性的二元关系称作偏序, 满足反自反性、非对称性和传递性的二元关系称作严格偏序.

满足完全性的偏序称作全序, 满足三岐性的严格偏序称作严格全序.

满足良基性的全序称作良序.

对于这些二元关系 $R$ , 我们习惯性地记 $(x, y) \in R$ 为 $x R y$ . 为了强调某个集合带有这样的二元关系, 我们会用有序对把他们装在一起, 例如 $(X, R)$ .

接下来, 我们依次查考这些关系. 首先是等价关系.

定义 4.1.14 (划分, 无交并). 如果一个非空集的集族 ${X_{i} ∣ i \in I}$ 满足 $\forall i, j \in I (i \neq = j \to X_{i} \cap X_{j} = \emptyset)$ , 就称这是一族无交的集合. 此时特别的将 $⋃_{i \in I} X_{i}$ 记为 $∐_{i \in I} X_{i}$ , 称作无交并.

如果 $X = ∐_{i \in I} X_{i}$ , 则称 ${X_{i} ∣ i \in I}$ 构成集合 $X$ 的一族划分.

注 4.1.15. 很多时候, 我们写 ${X_{i} ∣ i \in I}$ 并不是说这时替换公理从 $I$ 里面由某个公式替换出来的集合, 而是单纯的没事找事给这个集合编个号, 免得写出 ${X_{i}}$ 这种因空白而显得有些尴尬的东西. 由于我们可以把 $X = {x$ 们 $}$ 当成 $X^{'} = {(x, {x})$ 们 $}$ , 即用有序对的方法给 $X$ 每个元素带上一个标号, 就是它自己定义的单点集, 我们这样写也不妨事, 大不了我说 $I$ 就是 ${{x}$ 们 $}$ .

引理 4.1.16 (无交化). 对任何集族 ${X_{i} ∣ i \in I}$ , 我们有一族无交的集合 ${(X_{i}, {X_{i}}) ∣ i \in I}$ 与它之间有双射.

证明. 这就是延续上面注记的精神.

$□$

定理 4.1.17 (商). 集合 $X$ 上的全体等价关系与全体划分之间存在一个双射.

证明. 我们定义 $X$ 的元素 $x$ 在等价关系 $\sim$ 下的等价类为 $[x]_{\sim} = {y \in X ∣ x \sim y}$ . 定义商映射 $X /$ 如下, 它把等价关系变成划分:

$X / \sim= {[x]_{\sim} ∣ x \in X}$ .

来证明这是个划分. 首先, $x \in [x]_{\sim}$ 指出每个集都非空; 其次, $[x]_{\sim} \cap [y]_{\sim} \neq = \emptyset \to \exists z (x \sim z \sim y) \to x \sim y \to [x]_{\sim} = [y]_{\sim}$ , 于是不同的两个等价类确实无交.

反过来, 我们用划分 $P$ 来定义等价关系 $\sim_{P}$ 如下:

$x \sim_{P} y \leftrightarrow \exists p \in P (x \in p \land y \in p)$ .

这是个等价关系只要按定义拆开看一看就好了.

不难发现我们上面定义的这俩函数互为逆, 所以它们都是双射.

$□$

注 4.1.18. 商关系甚为常见, 我们不但可以给集合做商, 还可以给许多数学构造做商, 我们遇到的时候再说.

接下来是良基关系. 其实大部分时候主流数学家并不会用到这个关系, 他们最多用到良序, 但是我们这里刻意强调它是因为集合们的属于关系由外延公理和良基公理恰好是个外延良基关系, 而外延良基关系恰好就是集合的属于.

定理 4.1.19 (Mostowski’s Collapsing). 外延良基关系集一定和一个配上属于关系的传递集同构.

这个定理的证明需要良基归纳法与良基递归定义原理, 我们这里略去. 不过下一小节我们将看到归纳法和递归定义在 $N$ 上的特化形式, 也是数学史上人们最开始提出这些想法的形式.

最后是序关系. 拟序太弱, 一般没人考虑. 我们先来看我们定义中的严格是啥意思.

定理 4.1.20 (严格序与序). 严格偏序一一对应于偏序, 严格全序一一对应于全序.

证明. 定义

X

上的对角线为

Δ = {(x, x) ∣ x \in X}

. 偏序就是严格偏序并上对角线, 全序就是严格全序并上对角线.

$□$

注 4.1.21. 因此, 我们以后就把 $<$ 默认作为严格偏序/严格全序的符号, 而 $\leq$ 默认作为 $<$ 对应的偏序/全序的符号. 反过来也一样.

定义 4.1.22 (单调与同构). 如果函数 $f \in B^{A}$ 把带有偏序 $<_{A}$ 的集 $A$ 映到带有偏序 $<_{B}$ 的集 $B$ , 我们定义:

$f$ 是单调函数, 若 $a_{1} \leq a_{2} \to f (a_{1}) \leq f (a_{2})$ .

$f$ 是严格单调函数, 若 $a_{1} < a_{2} \to f (a_{1}) < f (a_{2})$ .

$f$ 是序同构, 若 $f$ 是双射且单调的函数 (当然此时也是严格单调的).

如果 $<_{A}$ 和 $<_{B}$ 同时升格为全序或良序, 定义照旧.

现在我们来到了最重要的良序关系. 良序关系的很多东西几乎会照搬到序数理论里, 而后者是我们在需要做超过有限次操作时的计数器.

定义 4.1.23 (真前段). 对良序集 $(W, <)$ , 定义其中元素 $w$ 定义的真前段为这集合的真子集 $W [w] = {x \in W ∣ x < w}$ , 它经由从 $W$ 上继承而来的良序关系仍然成良序集.

定理 4.1.24 (良序集比较定理). 若有两个良序集 $(W_{1}, <_{1})$ 与 $(W_{2}, <_{2})$ , 则以下三个情况一定成立一个:

1.	存在 $(W_{1}, <_{1})$ 与 $(W_{2}, <_{2})$ 之间的序同构.
2.	存在 $w_{1} \in W_{1}$ 和 $(W_{1} [w_{1}], <_{1})$ 与 $(W_{2}, <_{2})$ 之间的序同构.
3.	存在 $w_{2} \in W_{2}$ 和 $(W_{1}, <_{1})$ 与 $(W_{2} [w_{2}], <_{2})$ 之间的序同构.

我们将存在 $(W_{1}, <_{1})$ 与 $(W_{2}, <_{2})$ 之间的序同构记为 $(W_{1}, <_{1}) ≅ (W_{2}, <_{2})$ .

证明. 我们考虑 (部分) 函数 $F \subseteq W_{1} \times W_{2}$ , $(w_{1}, w_{2}) \in F \leftrightarrow W_{1} [w_{1}] ≅ W_{2} [w_{2}]$ .

首先证明这是从其定义域到其值域的双射. 显然由对称性只需要证明它是个函数, 这也就是要说一个良序集的同构真前段一定是同一个集:

假定在 $(W, <)$ 中有两个同构的真前段 $W [w_{1}] ≅ W [w_{2}]$ , 这个序同构函数 $f \in W [w_{2}]^{W [w_{1}]}$ 是单调函数首先指出 $f (x) \geq x$ : 反证, 若 $X = {x \in W [w_{1}] ∣ f (x) < x}$ 非空, 其最小元 $x$ 一定满足 $f (x) < x$ , 所以由最小性质有 $f (f (x)) \leq f (x)$ , 这说明 $f$ 不单调, 矛盾. 这立刻指出同构 $f$ 是恒等函数, 因为 $f (x) \leq x$ , 而同时也必须有 $f^{- 1} (x) \leq x$ . 于是这两个集合相等, 因为恒等函数限制在上面变成双射.

于是我们就得到了 $F$ 是 $dom F$ 与 $ran F$ 之间的双射. 显然 $F$ 单调, 于是 $dom F ≅ ran F$ .

若 $F$ 恰好就是 $W_{1}$ 到 $W_{2}$ 的函数, 情况 (1) 就成立了. 下面假定 $W_{1} - dom F \neq = \emptyset$ , 我们来证明 $ran F = W_{2}$ , 而且情况 (2) 成立. 同理则可得 (1)(2)(3) 总有一个成立.

首先证明这时 $dom F$ 一定是 $W_{1} [w_{1}]$ , 其中 $w_{1}$ 是 $W_{1} - dom F$ 的最小元. 这是因为若还存在 $w > w_{1}$ 在 $F$ 的定义域内, 则见证 $W_{1} [w]$ 与某个 $W_{2} [-]$ 同构的函数 $f$ 限制在 $W_{1} [w_{1}]$ 上可以得到同构 $W_{1} [w_{1}] ≅ W_{2} [f (w_{1})]$ , 这与 $w_{1} \neq \in dom F$ 矛盾.

接下来证明

ran F

一定是

W_{2}

. 还是假定

W_{2} - ran F

非空, 有最小元

w_{2}

, 我们同理可以证明

W_{1} [w_{1}] ≅ W_{2} [w_{2}] = ran F

. 然而再假定

W_{1} [w_{1}] \cup {w_{1}} = W_{1} [w_{3}]

,

W_{2} [w_{2}] \cup {w_{2}} = W_{2} [w_{4}]

, 我们可以发现显然的同构

W_{1} [w_{3}] ≅ W_{2} [w_{4}]

, 这与

w_{1}

和

w_{2}

的最小性矛盾.

$□$

注 4.1.25. 我们还可以证明 $≅$ 代表的序同构一旦存在就一定是唯一的, 具体证明留给读者.

4.2自然数集的构造

接下来的两节中, 我们将从自然数开始, 一路构造直到得到 Dedekind 实数. 别的实数构造方式我们放到后面合适的地方再行讨论.

定义 4.2.1. 若 $\emptyset \in X$ 且 $\forall u \in X (u \cup {u} \in X)$ , 则称 $X$ 是一个归纳集. 无穷公理说, 存在一个归纳集.

所有归纳集的交是最小的归纳集, 我们称之为 (标准) 自然数集, 记作 $N$ . 其中的元素称为 (标准) 自然数.

证明. 我们要证明所有归纳集的交还是个归纳集, 虽然这由定义是显然的.

$□$

命题 4.2.2 (自然数集的性质). 我们列举如下几个显然的性质:

1.	$N$ 是传递集. 换言之, $n \in N \to n = {m \in N ∣ m \in n}$ .
2.	每个 $n \in N$ 是传递集. 换言之, $m \in n \to m = {k \in n ∣ k \in m}$ .
3.	每个 $n \in N$ 都满足 $n \neq = \emptyset \to \exists m (n = m \cup {m})$ .
4.	每个 $n \in N$ 对属于关系都成良序集. 更一般的, $N$ 对属于关系也成良序集.

这些命题的证明都不难, 技巧都是这样的: 我们假定 $X$ 是归纳集, 然后证明满足某性质 $φ$ 的全体 $x \in X$ 组成的集合还是归纳集, 这样就能推断 $N$ 里的元素都满足性质 $φ$ . 具体细节留给读者自行验证.

这个自然数集又被称作自然数标准模型, 但不幸的是我们有定理证明 $N$ 的理论是不可公理化的, 换言之任何自然数理论都有非标准的模型. 我们一般会默认自然数理论为以下的 Peano 算术 (PA), 默认我们的模型是这个标准模型.

定义 4.2.3 (PA). $L = {0, S, +, \cdot}$ , 其中 $0$ 是常元, $S$ 是一元函数, $+$ 和 $\cdot$ 是二元函数. 所用的公理为

1.	$\forall x (0 \neq = S x)$
2.	$\forall x \forall y (S x = S y \to x = y)$
3.	$\forall x (x + 0 = x)$
4.	$\forall x \forall y (x + S y = S (x + y))$
5.	$\forall x (x \cdot 0 = 0)$
6.	$\forall x \forall y (x \cdot S y = x \cdot y + x)$
7.	$(I n d_{φ}) \forall y ((φ (0, y) \land \forall x (φ (x, y) \to φ (S x, y))) \to \forall x (φ (x, y)))$

其中 $S$ 称作后继函数, $(I n d_{φ})$ 称作对公式 $φ$ 的归纳原理, 它们也合称归纳原理模式, $y$ 是有限个参数的缩写. 为了符合习惯, $+ (x, y)$ 记为 $x + y$ , $\cdot (x, y)$ 记为 $x \cdot y$ .

我们现在来把 $N$ 建设成 PA 的模型. 为此, 我们要指明 $0$ 、后继函数、加法和乘法分别是什么. 前两个其实已经写在归纳集的定义上了, 关键是后面的函数如何定义且证明其存在. 我们引入以下自然数上的归纳定理.

定理 4.2.4. $\forall y ((φ (\emptyset, y) \land \forall x (φ (x, y) \to φ (x \cup {x}, y))) \to \forall x (φ (x, y)))$

其中 $x$ 是自然数, $y$ 是有限个自然数参数, $φ$ 是集合上的一个公式.

证明. 只要注意到按定义

{x \in N ∣ φ (x, y)}

是一个归纳集, 从而包含自然数集, 而按定义它又必须是自然数的子集, 从而必然恰好是自然数集.

$□$

定理 4.2.5 (含参递归原理). 若有函数 $a \in A^{P}$ 和 $g \in A^{P \times A \times N}$ , 则它们决定唯一的函数 $f \in A^{P \times N}$ , 满足

1.	$\forall p \in P (f (p, \emptyset) = a (p))$
2.	$\forall n \in N \forall p \in P (f (p, n \cup {n}) = g (p, f (p, n), n))$

证明. 我们先来证明 $P = {*}$ 是个单点集的情况, 此时函数 $a$ 退化为一个点 $a \in A$ , 函数 $g$ 只需要后两个参数即可运作.

首先证明 $f$ 的存在性. 任取函数 $t \in A^{m \cup {m}}$ , 其中 $m \in N$ , 若 $t (\emptyset) = a$ 且 $\forall k \in m (t (k \cup {k}) = g (t (k), k))$ , 则称 $t$ 是一个基于 $a$ 和 $g$ 的 $m$ 近似. 令 $F = {t \in P (N \times A) ∣ t$ 是 $m$ 近似 $}$ , 作 $f = \cup F$ , 我们证明这就是我们所要的那个 $f$ .

(i) $f$ 是函数: 其实就是要证明 $F$ 是个相容函数族. 假设 $t, u \in F$ , 进一步记 $dom (t) = n, dom u = m$ , 再假定 $n \leq m$ , 我们证明 $\forall k \in n (t (k) = u (k))$ . 显然 $t (0) = u (0) = a$ , 由归纳法, 注意到 $t (s) = u (s) \to t (s \cup {s}) = g (t (s), s) = g (u (s), s) = u (s \cup {s})$ 即可.

(ii) $f \in A^{N}$ : 只要证明 $\forall n \in N$ 存在 $t \in F$ 使得 $dom t = n$ . 反证, 若有最小的 $n$ 使得不存在, 显然 $n \neq = \emptyset$ , 于是有 $n = m \cup {m}$ , 用 $m$ 存在的那个 $u \in F, dom u = m$ 不难得到一个 $t$ , 这引发矛盾.

(iii) $f$ 满足题目要求: 对 (1) 只要注意到 $\forall t (t (\emptyset) = a)$ , 对 (2) 只要提取一个定义域为 $n \cup {n}$ 的 $t \in F$ 即可.

接下来证明 $f$ 的唯一性. 这由函数相等的外延性很容易验证, 细节交给读者.

现在, 我们来证明一般情形. 我们定义

G

是一个从

A^{P} \times N

到

A^{P}

的函数, 它把

(t, n)

映到一个

h

, 使得

\forall p \in P (h (p) = g (p, t (p), n))

. 这

h

显然唯一, 故

G

确实函数. 运用上面的结论, 我们就有唯一一个

F

从

N

到

A^{P}

, 满足

F (0) = a \land F (n \cup {n} = G (F (n), n))

, 最后只要令

f (p, n) = F (n) (p)

即可.

$□$

注 4.2.6. 我们用到的这个技巧叫做柯里化 (Currying).

可能有的读者会心生疑惑: 递归定义是我们司空见惯的定义方式, 为何这里要花如此大量的篇幅来证明这个定义可行呢? 事实上, 这里就是 PA 向我们第一次展示出它弱小的地方: 对于某些增长速度超级快的函数, PA 是无法证明它们是全函数 (即, 在每个可能的地方都有定义) 的! 最著名的例子当属 Goodstein Theorem(Kirby-Paris), 而稍冷的还有 Strenthened Ramsey Theorem(Paris-Harrington). 它们的特点都是, 用 $N$ 做的证明需要在 ZFC 中运用超穷序数的理论, 而 PA 对此则一无所知.

有了含参递归引理后, 我们就可以根据以下递归定义来确信加法和乘法确实是 $N$ 上的两个函数.

定义 4.2.7 (加与乘). 加法定义为满足以下条件的函数 $+^{N} : N^{N \times N}$

1.	$\forall n \in N (+^{N} (n, \emptyset) = n)$
2.	$\forall m, n \in N (+^{N} (n, m \cup {m}) = +^{N} (n, m) \cup {+^{N} (n, m)})$

乘法定义为满足以下条件的函数 $\cdot^{N} : N^{N \times N}$

1.	$\forall n \in N (\cdot^{N} (n, 0) = 0)$
2.	$\forall m, n \in N (\cdot^{N} (n, m \cup {m}) = +^{N} (\cdot^{N} (n, m), m))$

为了符合习惯, 将 $+^{N} (n, m)$ 记作 $n +^{N} m$ , 将 $\cdot^{N} (n, m)$ 记作 $n \cdot^{N} m$ .

定义 4.2.8 (自然数标准模型). $(N, \emptyset, - \cup {-}, +^{N}, \cdot^{N})$ 是 PA 的一个模型.

证明. 验证几乎已经做完了.

$□$

今后, 在方便的时候, 我们将地记 $0^{N} = \emptyset$ , $1^{N} = {\emptyset}$ , $2^{N} = {\emptyset, {\emptyset}}$ , ....

命题 4.2.9 (自然数运算的性质).

1.	加法交换律: $m +^{N} n = n +^{N} m$
2.	加法结合律: $(m +^{N} n) +^{N} k = m +^{N} (n +^{N} k)$
3.	乘法交换律: $m \cdot^{N} n = n \cdot^{N} m$
4.	乘法结合律: $(m \cdot^{N} n) \cdot^{N} k = m \cdot^{N} (n \cdot^{N} k)$
5.	分配律: $m \cdot^{N} (n +^{N} k) = (m \cdot^{N} n) +^{N} (m \cdot^{N} k)$

这些性质小学生都知道, 但是现在我们可以给它们以严格的证明. 如果读者有兴趣自行验证, 可以参考 The Natural Number Game(By Kevin Buzzard and Mohammard Pedramfar). 这是一个交互式的在线游戏, 旨在引导人们进入运用证明助手 Lean 进行数学证明的形式化验证的殿堂.

接下来, 我们要进军整数和有理数了. 我们会发现, 它们不过是一些稍显复杂的商关系.

定义 4.2.10 (整数). 整数集定义为 $Z = (N \times N) / \sim_{Z}$ , 其中 $(a, b) \sim_{Z} (c, d) \leftrightarrow (a +^{N} d) = (b +^{N} c)$ .

注 4.2.11. 先验地看来, $(a, b) \sim_{Z} (c, d)$ 就是 $a - b = c - d$ .

定理 4.2.12 (整数的运算). 我们有三个函数 $+^{Z}$ 、 $-^{Z}$ 和 $\cdot^{Z}$ , 定义如下:

1.	$[(a, b)]_{\sim_{Z}} +^{Z} [(c, d)]_{\sim_{Z}} = [(a +^{N} c, b +^{N} d)]_{\sim_{Z}}$
2.	$[(a, b)]_{\sim_{Z}} -^{Z} [(c, d)]_{\sim_{Z}} = [(a +^{N} d, b +^{N} c)]_{\sim_{Z}}$
3.	$[(a, b)]_{\sim_{Z}} \cdot^{Z} [(c, d)]_{\sim_{Z}} = [((a \cdot^{N} c) +^{N} (b \cdot^{N} d), (a \cdot^{N} d) +^{N} (b \cdot^{N} c)]_{\sim_{Z}}$

定理 4.2.13 (自然数嵌入整数). 定义 $i_{N ↪ Z} \in Z^{N}, n \mapsto [(n, 0^{N})]_{\sim_{Z}}$ . 这是个单射, 且保持加法和乘法.

因此, 我们又可以记 $0^{Z} = i_{N ↪ Z} (0^{N})$ , $1^{Z} = i_{N ↪ Z} (1^{N})$ , .... 负整数是什么, 以及为何整数就是正整数、零和负整数, 请自行思考.

定义 4.2.14 (有理数). 有理数集定义为 $Q = (Z \times (Z - {0^{Z}})) / \sim_{Q}$ , 其中 $(a, b) \sim_{Q} (c, d) \leftrightarrow a \cdot^{Z} d = b \cdot^{Z} c$

注 4.2.15. 先验地看来, $(a, b) \sim_{Q} (c, d)$ 就是 $a / b = c / d$ .

定理 4.2.16 (有理数的运算). 我们有四个函数 $+^{Q}$ 、 $-^{Q}$ 、 $\cdot^{Q}$ 和 $/^{Q}$ , 定义如下:

1.	$[(a, b)]_{\sim_{Q}} +^{Q} [(c, d)]_{\sim_{Q}} = [((a \cdot^{Z} d) +^{Z} (b \cdot^{Z} c), b \cdot^{Z} d)]_{\sim_{Q}}$
2.	$[(a, b)]_{\sim_{Q}} -^{Q} [(c, d)]_{\sim_{Q}} = [((a \cdot^{Z} d) -^{Z} (b \cdot^{Z} c), b \cdot^{Z} d)]_{\sim_{Q}}$
3.	$[(a, b)]_{\sim_{Q}} \cdot^{Q} [(c, d)]_{\sim_{Q}} = [(a \cdot^{Z} c, b \cdot^{Z} d)]_{\sim_{Q}}$
4.	$[(a, b)]_{\sim_{Q}} /^{Q} [(c, d)]_{\sim_{Q}} = [(a \cdot^{Z} d, b \cdot^{Z} c)]_{\sim_{Q}}$ , 这里 $[(c, d)]_{\sim_{Q}} \neq = [(0^{Z}, 1^{Z})]_{\sim_{Q}}$

定理 4.2.17 (整数嵌进有理数). 定义 $i_{Z ↪ Q} \in Q^{Z}, n \mapsto [(n, 1^{Z})]_{\sim_{Q}}$ . 这是个单射, 且保持加法、减法和乘法.

因此, 我们又可以记 $0^{Q} = i_{Z ↪ Q} (0^{Z})$ , $1^{Q} = i_{Z ↪ Q} (1^{Z})$ , .... 分数是什么, 以及为什么有理数就是分数, 请自行思考.

对于 $Z$ 和 $Q$ 中的运算法则, 仔细验证并无教益, 我们歇息一下, 来看看 $Z$ 和 $Q$ 怎么作为环和域的最简单的模型.

定义 4.2.18 (群, 交换群). 群的语言 $L_{G r p} = {e, (-)^{- 1}, \cdot}$ , 分别是常元、一元函数和二元函数, 其公理集为

1.	$x \cdot e = e \cdot x = x$
2.	$x \cdot x^{- 1} = x^{- 1} \cdot x = e$
3.	$(x \cdot y) \cdot z = x \cdot (y \cdot z)$

交换群只要再加上一句 $x \cdot y = y \cdot x$ .

定义 4.2.19 (环, 交换环, 域). 环的语言 $L_{R in g} = {0, 1, +, -, \cdot}$ , 分别是常元、常元、二元函数、一元函数和二元函数, 其公理集为

1.	$0 \neq = 1$
2.	$x + 0 = 0 + x = x$
3.	$x + (- x) = (- x) + x = 0$
4.	$(x + y) + z = x + (y + z)$
5.	$x + y = y + x$
6.	$x \cdot 1 = 1 \cdot x = x$
7.	$(x \cdot y) \cdot z = x \cdot (y \cdot z)$
8.	$x \cdot (y + z) = (x \cdot y) + (x \cdot z)$
9.	$(x + y) \cdot z = (x \cdot z) + (y \cdot z)$

交换环只要再加上一句 $x \cdot y = y \cdot x$ , 域只要在交换环上加一句 $x \neq = 0 \to \exists! y (x \cdot y = y \cdot x = 1)$ .

定理 4.2.20 (环和域的模型). $Z$ 是交换环的模型, $Q$ 是域的模型.

证明. 对应的函数连名字都已经一模一样地起好了.

$□$

域将是我们将来最常见到的数学对象, 因为实数集也是个域, 而且作为一个理论而言域已经得到了相当充分的发展和反思, 我们有很多可以说的结果.

最后, 我们来补充 $N, Z, Q$ 上的 (典范) 序结构. $Z, Q$ 上面其实还有别的序, 它们和 p 进数理论有关, 我们这里不做涉及.

定义 4.2.21 (序). 定义 $\leq^{N}$ 为 $\forall n, m \in N (n \leq^{N} m \leftrightarrow n \subseteq m)$

定义 $\leq^{Z}$ 为 $\forall a, b \in Z (a \leq^{Z} b \leftrightarrow b - a \in ran i_{N ↪ Z})$

定义 $\leq^{Q}$ 为 $\forall a, b \in Q (a \leq^{Q} b \leftrightarrow b - a \geq^{Q} 0^{Q})$ , 而 $[(a, b)]_{\sim_{Q}} \geq^{Q} 0^{Q} \leftrightarrow 0^{Z} \leq^{Z} a \cdot^{Z} b$ .

序与群、序与域均可形成理论.

定义 4.2.22 (有序交换群, 有序域). 有序交换群 (OAG aka. Ordered Abelian Group) 的语言是 $L_{O A G} = {0, -, +, \leq}$ 分别是常元, 一元函数, 二元函数和二元谓词, 其公理集则为

1.	$x + 0 = 0 + x = x$
2.	$x + (- x) = (- x) + x = 0$
3.	$x + y = y + x$
4.	$(x + y) + z = x + (y + z)$
5.	$x \leq x$
6.	$x \leq y \to y \leq x \to x = y$
7.	$x \leq y \to y \leq z \to x \leq z$
8.	$x \leq y \lor y \leq x$
9.	$x \leq y \to x + z < y + z$

有序环的语言 $L_{OR} = {0, 1, +, -, \cdot, \leq}$ 在环的语言里加了一个二元关系, 有序域是用有序环的语言, 在域的公理集之外另加公理:

1.	$x \leq x$
2.	$x \leq y \to y \leq x \to x = y$
3.	$x \leq y \to y \leq z \to x \leq z$
4.	$x \leq y \lor y \leq x$
5.	$x \leq y \to x + z < y + z$
6.	$x \leq y \to 0 \leq z \to x \cdot z \leq y \cdot z$

定理 4.2.23. $Z$ 忘掉乘法看加法, 是 OAG 的模型, $Q$ 是有序域的模型.

这些定义的有效性, 以及它们确实满足我们已经习惯的那些性质等等的证明都没有教益, 读者有兴趣可以自行验证. 以后我们不会刻意指出某个加法/减法/乘法/序是哪个集合里的, 因为我们相信读者有能力自行判断.

4.3实数集的构造

现在, 我们正式由 Dedekind 的著名构造法来构造实数集.

定义 4.3.1 (Dedekind 实数). 我们称 $A \subseteq Q$ 是一个 (Dedekind) 实数 (Dedekind 分割), 若

1.	$A \neq = \emptyset$ 且 $A \neq = Q$
2.	$\forall p, q \in Q (q < p \to p \in A \to q \in A)$ , 又称向下封闭.
3.	$\forall p \in A \exists q \in A (p < q)$ 又称向上无极大.

所有实数构成的集合称为实数集, 记为 $R \subseteq P Q$ . 实数将默认用 x,y,z 等字母表示.

此外, 我们还可以定义两个符号重载: $- \infty = \emptyset$ , $+ \infty = Q$ . 我们称 $\overset{ˉ}{R} = R \cup {- \infty, + \infty}$ 为扩展实数集.

这定义方式给我们带来的最大好处是, 大小关系与上界性质变得非常易于描述.

定义 4.3.2 (序关系). 我们在扩展实数集上定义显然的偏序关系 $x \leq y \leftrightarrow x \subseteq y$ .

定理 4.3.3. 扩展实数集的这个偏序是全序.

证明. 也就是要证明

x \leq y \lor y \leq x

. 反证, 若由两个实数使得

x \neq \subseteq y \land y \neq \subseteq x

, 假定有两个有理数

p \in x \land q \in y

, 同时

p \neq \in y \land q \neq \in x

. 由于有理数上的序是全序, 又显见

p \neq = q

, 不妨设

p < q

, 则

q \in y \to p \in y

, 与假定矛盾.

$□$

定义 4.3.4 (上界与上确界). 定义一个扩展实数集的子集 $S$ 的上确界为 $sup S = \cup S$ .

如果扩展实数 $r$ 满足 $\forall s \in S (s \leq r)$ , 则称 $r$ 是 $S$ 的上界.

定理 4.3.5 (确界存在定理的实现). 上确界小于等于任何上界. 由此推论, 有实数上界则必有实数上确界.

证明. 注意非空的扩展实数集的子集的上确界要不然是实数要不然是

+ \infty

, 接下来完全是显然的.

$□$

今后我们将会知道, 这个定理是著名的实数完备性的表达方式之一. 接下来我们来看实数上的域结构.

定义 4.3.6 (实数运算). 首先我们有有理数到实数的嵌入 $i_{Q ↪ R} \in R^{Q}, p \mapsto {q \in Q ∣ q < p}$ , 因此可以不区分有理数 $p$ 与它对应的实数 $i_{Q ↪ R} (p)$ . 记 $ran i_{Q ↪ R} = Q$ , $R - Q = Irr$ .

实数加法可以直接定义为 $x + y = {p + q ∣ p \in x \land q \in y}$ .

实数的相反数分开定义: $x \in Q$ 时 $- x$ 定义为对应有理数的相反有理数的嵌入, $x \in Irr$ 时 $- x = {p \in Q ∣\forall q \in x (p < - q)}$ .

实数的乘法相对麻烦. 我们先定义正实数的乘法为 $x \cdot y = {p \cdot q ∣ p \in x \cap Q^{+} \land q \in y \cap Q^{+}} \cup {p \in Q ∣ p \leq 0}$ , 其中 $Q^{+} = {p \in Q ∣ p > 0}$ . 然后再令 $(- x) \cdot y = x \cdot (- y) = - (x \cdot y)$ , $(- x) \cdot (- y) = x \cdot y$ .

我们先引入实数的一个重要特征.

定理 4.3.7 (Archimedes 性). 对任何实数 $x$ 和任何正有理数 $p$ 而言, 存在自然数 $n$ 使得 $\forall q \in x (q < n \cdot p)$ .

证明. 反证. 若

\forall n \in N \exists q_{n} \in x (q_{n} \geq n \cdot p)

, 注意

m, n \in N - {0} \to m / n \geq 1/ n

指出

\forall r \in Q^{+} \exists r_{n} \in N (p / r \geq 1/ r_{n})

, 换言之

r \leq r_{n} \cdot p \leq q_{r_{n}} \in x

, 由实数定义即得

r \in x

, 但

r

是任取的, 故

Q \subseteq x \subseteq Q

, 即

x = Q

, 与

x

是实数矛盾.

$□$

定理 4.3.8 (实数是域). 上面定义的这些运算让实数成为一个域.

证明. (i) 首先, 我们证明这些对实数作为集合进行操作得出的东西仍然是个实数.

1.	加法: 显然非空, Archimedes 性指出非 $Q$ , 有理数有序域给出向下封闭和向上无极大.
2.	相反数: 有理数自不必说, 无理数非空变非 $Q$ , Archimedes 性指出非空, 向下封闭显然, 向上无极大利用反证法. 若 $- x$ 有最大元素 $p \in Q$ , 则 $x = - p \in Q$ , 与无理矛盾.
3.	正数乘法: 显然非空, Archimedes 性指出非 $Q$ , 向下封闭非正数显然正数算一算, 向上无极大来源于原来的向上无极大.
4.	一般乘法: 略.

(ii) 接下来我们验证加法和取相反数确实形成交换群.

1.	交换性和结合性由定义和有理数加法交换且结合是显然的.
2.	$x + 0 = 0 + x = {p + q ∣ p \in x \land q < 0} = ⋃_{p \in x} {q \in Q ∣ q < p}$ , 向下封闭使它包含于 $x$ , 向上无极大使 $x$ 包含于它, 故这就是 $x$ .
3.	$x + (- x) = (- x) + x = 0$ 对有理数显然; 对无理数, 显然 $x + (- x) = (- x) + x$ ; 如果它严格大于 $0$ , 那么一定包含有有理数 $0$ , 于是有 $p \in x$ 使得 $- p \in (- x)$ , 换言之 $\forall q \in x (p > q)$ , 这与向上无极大矛盾. 如果它严格小, 那么一定有负有理数 $t \in Q$ 不在其中, 即 $\forall p \in x \forall q \in Q (\forall r \in x (r + q < 0)) \to (p + q < t)$ , 即 $\forall q \in Q ((\exists p \in x (p \geq t - q))) \to (\exists r \in x (r \geq - q))$ , 换言之 $\forall q \in Q (t - q \in x \to - q \in x)$ , 即 $\forall q \in Q (q + t \in x \to q \in x)$ , 又注意向下封闭, 我们有 $\forall q \in Q (q + t \in x \leftrightarrow q \in x)$ , 当然这也就是 $\forall q \in Q (q \in x \leftrightarrow q + (- t) \in x)$ , 然而由有理数 Archimedes 性知道这说明 $x = Q$ , 矛盾. 于是全序三岐指出 $x + (- x) = (- x) + x = 0$ .

这些论证同时还指出了负实数的相反数是正实数, 正实数的相反数是负实数. 群的性质告诉我们相反数的相反数就是自己.

(iii) 验证乘法交换且结合: 先证明正实数, 然后推广到一般实数. 细节从略.

(iv) $1 \neq = 0$ 显然. 验证乘法以 $1 \in Q$ 为幺元:

1.	对 $x > 0$ , 这时 $x \cdot 1 = 1 \cdot x = {p \cdot q ∣ p \in x \land 0 < p \land 0 < q < 1} \cup (Q - Q^{+})$ . 由前面 $p \cdot q < p$ 显见 $x \cdot 1 \leq x$ . 反证, 如果严格小, 则 $\exists t \in x \forall p \in x \forall0 < q < 1 (t > 0 \land p > 0 \to p \cdot q < t)$ , 但由向上无极大我们一定有 $\exists s \in x (s > t)$ , 这表明 $0 < t / s < 1$ 而 $s \cdot (t / s) = t \geq t$ , 立即矛盾.
2.	对 $x = 0$ , 显然.
3.	对 $x < 0$ , $- x > 0$ , 于是 $x \cdot 1 = 1 \cdot x = - (1 \cdot (- x)) = - (- x) = x$ .

(v) 乘法对加法的分配律: 由交换性只需要证明左分配, 不妨只证明正实数分配别人的情形, 于是由有理数的分配律显然.

(vi) 域的特殊公理, 即非零实数存在乘法逆: 我们通过以下构造来定义正实数的乘法逆, 负实数还是老方法取一下相反数.

对 $x > 0$ , 令 $x^{- 1} = {p \in Q ∣\forall q \in x (q > 0 \to p \cdot q < 1)}$ .

只要验证

x \cdot x^{- 1} = 1

. 小于等于还是显然的, 还是反证, 严格小于和

x > 0

给出一个正有理数

0 < t < 1

不在

x \cdot x^{- 1}

里面, 即

\forall0 < p \in x \forall0 < q \in Q (\forall r \in x (q \cdot r < 1)) \to p \cdot q < t

, 然后故技重施地变成逆否命题

\forall0 < q \in Q (\exists p \in x (p \geq t / q)) \to (\exists r \in x (r \geq 1/ q))

, 也就是

\forall0 < q \in Q (t \cdot q \in x \to q \in x)

, 最后得到

q \in x \to \forall n \in N (q \cdot (1/ t)^{n} \in x)

, 于是向下封闭性立即指出

x = Q

产生矛盾.

$□$

注意, 我们还可以把加法和相反数的定义推到 $\overset{ˉ}{R}$ 上面, 得到 $(+ \infty) + (- \infty) = - \infty$ , $(+ \infty) + x = + \infty$ , $(- \infty) + x = - \infty$ , $- (+ \infty) = - \infty$ , $- (- \infty) = + \infty$ 等等等式. 为了符合直觉, 一般我们会重新规定 $(+ \infty) + (- \infty) = 0$ . 这时 $\overset{ˉ}{R}$ 已经不是一个群了. 同理, 也可以对它们做乘法, 但如果照搬定义我们会得到 $(+ \infty)^{- 1} = - \infty$ , 所有一般我们会重新规定这玩意儿是 $0$ , 以符合我们对这个运算的直觉. 这样做也不会得到一个域.

最后, 实数按我们定义的这些运算和关系是个有序域.

定理 4.3.9 (实数定理). Dedekind 实数是有最小上界性的有序域.

证明. 我们几乎证明完了, 有序域的证明的部分散落在域的部分的证明中, 读者有兴趣可以自行补全.

$□$

名字空间

视图

4. 数学对象

4.1特别的二元关系

4.2自然数集的构造

4.3实数集的构造