§ 4. 自然整数。有限集合

Google 翻译生成的粗略草稿，质量较低。术语依照术语表，但句子可能有误；之后会由仔细的译文取代。

4. 自然整数。有限集合

1. 整数的定义

定义 1 03R9

如果 $\alpha \ne \alpha + 1$ ，基数 $\alpha$ 被认为是有限的。有限基数也称为自然整数（如果不存在混淆风险，则简称为整数 [^1]）。如果 $\operatorname{Card}(E)$ 是有限基数，则集合 $E$ 被称为有限；然后 $\operatorname{Card}(E)$ 被称为 $E$ 的元素的数。

引用了 1 · 被以下引用 1

引用了 II § 3. Correspondences

被以下引用推论 2

如果一个家庭 (章 II, § 3, no. 4) 的指标集合是有限的，则称其为“有限”。

当我们说某个型的对象的数是整数 $m$ 时，我们的意思是这些对象是有限集合的元素，其元素的数是 $m$ 。元素的数为 $m$ 的集合也称为 $m$ 元素的集合。

命题 1 03RA

基数 $\alpha$ 是有限的当且仅当 $\alpha + 1$ 是有限的。

引用了 1 · 被以下引用 1

引用了 Proposition 8, III § 3

被以下引用命题 1, III § 5

对于关系 $\alpha = \mathfrak{b}$ 和 $\alpha + 1 = \mathfrak{b} + 1$ ，基数 $\alpha$ 和 $\mathfrak{b}$ 之间是等价的（§ 3, no. 4，命题8）；因此，关系 $\alpha \ne \alpha + 1$ 和 $\alpha + 1 \ne (\alpha + 1) + 1$ 是等价的。

¶ 显然 $0 \ne 1$ ；因此 $0$ 是整数。由此可见 $1$ 和 $2$ 是整数。基数 $2 + 1$ 和 $(2 + 1) + 1$ 是整数，分别用 $3$ 和 $4$ 表示。

2. 整数之间的不等式

命题 2 03RB

令 $n$ 为整数。那么每个基数 $\alpha$ 使得 $\alpha \le n$ 是整数。如果 $n \ne 0$ ，则存在唯一的整数 $m$ ，使得 $n = m + 1$ ，并且关系 $\alpha < n$ 相当于 $\alpha \le m$ 。

引用了 4 · 被以下引用 11

引用了 Proposition 13, III § 3, Proposition 5, III § 3, III § 3. Equipotent sets. Cardinals, Proposition 8, III § 3

被以下引用 § 4. 自然整数。有限集合, 注, 推论 2, III § 5. 整数的特性, 推论, III § 5, 推论 1, III § 5, 命题 2, III § 5, 命题 5, III § 5, 命题 8, III § 5, 定理 1, III § 5, 定义 1, III § 6

如果 $\alpha \le n$ ，则存在基数 $\mathfrak{b}$ 使得 $n = \alpha + \mathfrak{b}$ （§ 3, no. 6，命题13）。那么 $(\alpha + 1) + \mathfrak{b} = (\alpha + \mathfrak{b}) + 1 = n + 1$ (§ 3, no. 3, 命题 5, 推论);从 $n \ne n + 1$ 开始，我们有

(\alpha + 1) + \mathfrak{b} \ne \alpha + \mathfrak{b}.

因此 $\alpha + 1 \ne \alpha$ ，这意味着 $\alpha$ 是整数。如果 $n \ne 0$ ，我们有 $n \ge 1$ （§ 3, no. 2），因此存在一个唯一的基数 $m$ ，使得 $n = m + 1$ （§ 3, no. 6，命题13和no. 4，命题8）。从 $m \leqslant n$ 开始， $m$ 就是整数，已经证明。最后，如果整数 $a$ 使得 $a < n$ ，我们有 $n = a + b$ ， $b \neq 0$ （§ 3, no. 6，命题13）；因为 $b$ 是整数，所以我们有 $b = c + 1$ 和 $n = m + 1 = (a + c) + 1$ 。由此可见 $m = a + c$ (§ 3, no. 4, 命题 8)，因此 $a \leqslant m$ 。相反，如果 $a \leqslant m$ ，我们有

a \leqslant m + 1 = n;

如果 $a = n = m + 1$ ，我们就会有 $a > m$ ，与假设相反。

推论 1 03RC

有限集合中的每个子集都是有限的。

推论 2 03RD

如果* X 是有限集合 E 和 X $\neq$ E 的子集，*则

引用了 2 · 被以下引用 2

引用了命题 2, 定义 1

被以下引用推论 4, 命题 6, III § 5

\mathrm{Card}\ (\mathrm{X})\ <\ \mathrm{Card}\ (\mathrm{E}).

因为X包含在单个元素的E 由……组成的子集的补集X $'$ 中；我们有 $\mathrm{Card}\,(\mathrm{X}) \leqslant \mathrm{Card}\,(\mathrm{X}')$ 和 $\mathrm{Card}\,(\mathrm{E}) = \mathrm{Card}\,(\mathrm{X}') + 1$ ，因此 (命题 2) $\mathrm{Card}\,(\mathrm{X}') < \mathrm{Card}\,(\mathrm{E})$ 和 更不必说 $\mathrm{Card}\,(\mathrm{X}) < \mathrm{Card}\,(\mathrm{E})$ 。

定义 1 表明，相反，如果 E 是集合使得

\mathrm{Card}\ (\mathrm{X}) < \mathrm{Card}\ (\mathrm{E})

对于 E 的每个子集 X 使得 X $\neq$ E，则 E 是有限的。

推论 3 03RE

如果* $f$ 是有限集合 E 到集合 F 的映射，*则* $f(\mathrm{E})$ 是 F 的有限子集。

引用了 1 · 被以下引用 2

引用了 Proposition 3, III § 3

被以下引用 Set Theory, III, § 4, No. 2, p. 167, Corollary 3, 推论 1, III § 5

对于 $\mathrm{Card}\ (f(\mathrm{E})) \leqslant \mathrm{Card}\ (\mathrm{E})$ （§ 3, no. 2、命题 3）。

推论 4 03RF

设* E 和 F 为两个有限集合，且数与元素相同，并让 $f$ 为 E 的映射入 F。 *则以下叙述是等价的：

引用了 1 · 被以下引用 2

引用了推论 2

被以下引用推论, III § 5, 命题 8, III § 5

(a) $f$ 为单射； (b) $f$ 是一个满射； (c) $f$ 为双射.

只要证明(a)和(b)是等价的就足够了。如果 $f$ 是单射的，则 $\mathrm{Card}(f(\mathrm{E})) = \mathrm{Card}\,(\mathrm{E}) = \mathrm{Card}\,(\mathrm{F})$ ，从而 $f(\mathrm{E}) = \mathrm{F}$ （推论2）。如果 $f$ 不是单射，则令 $x$ 和 $x'$ 是E的两个元素，使得 $x \neq x'$ 和 $f(x) = f(x')$ 。然后，代入 $\mathrm{E}' = \mathrm{E} - \{x\}$ ，根据推论2，我们有 $f(\mathrm{E}') = f(\mathrm{E})$ ，从而 $\mathrm{Card}(f(\mathrm{E})) \leqslant \mathrm{Card}\,(\mathrm{E}') < \mathrm{Card}\,(\mathrm{E})$ ；但从 $\mathrm{Card}\,(\mathrm{F}) = \mathrm{Card}\,(\mathrm{E})$ 开始，就得出 $f(\mathrm{E}) \neq \mathrm{F}$ 。

3. 归纳原理

C61（原理 / 归纳）。设 $R\{n\}$ 理论上为关系 $\mathscr{T}$ （其中n不是 $\mathscr{T}$ *的常量）。* 假设关系

R\{0\} \quad \text{and} \quad (\forall n)((n \text{ is an integer and } R\{n\}) \Rightarrow R\{n+1\})

* 定理等于* $\mathscr{T}$ 。 在这些条件关系

(\forall n)((n \text{ is an integer}) \Rightarrow R\{n\})

* 定理等于* $\mathscr{T}$ 。

我们将通过矛盾来论证。假设关系

(\exists n)(n \text{ is an integer and } (\text{not } R\{n\}))

是真的。令 $q$ 为整数，这样“不是 $R\{q\}$ ”（辅助常数的方法；cf.章I, § 3, no. 3和§ 4, no. 1）。整数 $n$ ，其中“ $n \leqslant q$ 和（不是 $R\{n\}$ ）”形式是一个良序非空集合（§ 3, no. 2，注），因此它至少有元素 $s$ 。如果 $s = 0$ ，则“不是 $R\{0\}$ ”，与假设相反。如果 $s > 0$ ，则 $s = s' + 1$ ，其中 $s'$ 是整数，使得 $s' < s$ (no. 2，命题 2)。通过 $s$ 的定义，我们有 $R\{s'\}$ ，但是假设意味着 $R\{s\}$ 为真，与 $s$ 的定义相反。

在序申请归纳原理特别需要证明关系

(n \text{ is an integer and } R\{n\}) \Rightarrow R\{n+1\}.

为此，通常使用辅助假设（章I, § 3, no. 3）的方法，也正是因为这个原因，关系“ $n$ 是整数和 $R\{n\}$ ”（甚至 $R\{n\}$ ）被称为*归纳法假设*。

注 077T

有各种判据，经常以“归纳的原理”的名称使用。它们都可以很容易地从 C61 推导出来，我们在这里指出其中最重要的：

(1) 设 $S\{n\}$ 为关系

(\forall p)((n \text{ is an integer and } p \text{ is an integer and } p < n) \Rightarrow R\{p\})

并假设 $S\{n\}$ 暗示 $R\{n\}$ 。然后关系

(\forall n)((n \text{ is an integer}) \Rightarrow R\{n\})

是真的。对于关系 $S\{0\}$ 为真，假设 $S\{n\}$ 意味着 $R\{n\}$ ；由于关系 $m < n + 1$ 等价于 $m \leqslant n$ （no. 2，命题2），关系 $S\{n + 1\}$ 等价于“ $S\{n\}$ 和 $R\{n\}$ ”，因而， $S\{n\}$ 意味着 $S\{n + 1\}$ 。因而，准则 C61 证明关系

(\forall n)\ ((n \text{ is an integer}) \Rightarrow S\{n\})

是真的，并且由于 $S\{n\}$ 意味着 $R\{n\}$ ，关系

(\forall n)\ ((n \text{ is an integer}) \Rightarrow R\{n\})

是真的。

(2) 令 $k$ 为整数，并令 $R\{n\}$ 为关系，使得关系

R\{k\} \text{ and } (\forall n)\ ((n \text{ is an integer} \geqslant k \text{ and } R\{n\}) \Rightarrow R\{n + 1\})

是真的。然后关系

(\forall n)\ ((n \text{ is an integer} \geqslant k) \Rightarrow R\{n\})

为 true（“归纳从 k 开始”）。让 $S\{n\}$ 为关系

(n \geqslant k) \Rightarrow R\{n\}.

然后通过案例析取方法，我们发现 $S\{0\}$ 为真。另一方面，很容易验证关系

(n \text{ is an integer and } S\{n\}) \Rightarrow S\{n + 1\}

是真的。从 C61 可以得出关系

(n \text{ is an integer}) \Rightarrow S\{n\}

是真的，这就证明了我们的断言。

(3) 令 $a$ 和 $b$ 为两个整数，使得 $a \leqslant b$ ，并令 $R\{n\}$ 为关系，使得

R\{a\} \text{ and } (\forall n)((n \text{ is an integer and } a \leqslant n < b \text{ and } R\{n\}) \Rightarrow R\{n + 1\}).

然后关系

(\forall n)((n \text{ is an integer and } a \leqslant n \leqslant b) \Rightarrow R\{n\})

是真的。证明与上例类似；我们将 $S\{n\}$ 视为关系“ $(a \leqslant n < b) \Rightarrow R\{n\}$ ”（“归纳限制在一个区间”）。

(4) 设 $a$ 、 $b$ 为两个整数，使得 $a \leqslant b$ ，并令 $\mathrm{R}\{n\}$ 为关系，使得

$\mathrm{R}\{b\}$ 和 $(\forall n)((n$ 是整数和 $a \leqslant n < b$ 和 $\mathrm{R}\{n+1\}) \Rightarrow \mathrm{R}\{n\})$ 。

然后关系

(\forall n)((n \text{ is an integer and } a \leqslant n \leqslant b) \Rightarrow \mathrm{R}\{n\})

是真的。因为我们有关系

$(n$ 是整数和 $a \leqslant n < b$ 并且（不是 $\mathrm{R}\{n\}$ ）） $\Rightarrow$ 不是 $\mathrm{R}\{n+1\}$ 。

如果对于某些 $n$ ，这样我们有 $a \leqslant n \leqslant b$ （不是 $\mathrm{R}\{n\}$ ），则可以从（3）得出（不是 $\mathrm{R}\{b\}$ ），与假设、从而相反，结果（*“降序归纳”*）。

引用了 1

引用了命题 2

4. 有限子集共有序集

命题 3 03L9

令* E 为右向预序集合（分别为*格子*，分别为*全序集*）。然后 E 的每个非空有限子集都在上方（分别*具有至少上界和下确界*，分别*具有最大元素和至少元素*）。

被以下引用 3

被以下引用定理 1, 命题 6, III § 5, 推论 2, III § 6

证明正在考虑子集元素数 $n$ 的归纳。对于 $n = 1$ 来说，结果是微不足道的。令X为E的 $n + 1$ 元素的子集（与 $n \geqslant 1$ ），并放入 $\mathrm{X} = \mathrm{Y} \cup \{x\}$ ，其中Y有 $n$ 元素，因此不为空。归纳假设意味着Y存在上界（分别至少上界、最大元素） $y$ 。由于E是右向的（分别是格子、全序）， $\{x, y\}$ 有上界（分别至少上界，最大元素），显然是X的上界（至少上界，最大元素）。

推论 1 03LA

每个全序有限集合都是良序的并且有最大元素。

被以下引用 5

被以下引用例 3, III § 2, 推论 2, 定理 1, 推论 2, III § 5, 命题 6, III § 5

推论 2 03LB

每个有限有序集合都有极大元素。

引用了 2 · 被以下引用 1

引用了定理 2（“佐恩的引理”）, III § 2, 推论 1

被以下引用推论 2, III § 6

对于这样的集合由推论 1 (cf. § 2, no. 4, 定理 2) 归纳。

5. 有限特征标的性质

定义 2 03LC

令*E 为集合。集合 $\mathfrak{S}$ of 子集 of E * 被认为是有限的特征标，如果关系* $\mathrm{X} \in \mathfrak{S}$ 等价于关系“每有限子集 of X 属于到 $\mathfrak{S}$ ”。

A property $P\{X\}$ of a subset $X$ of a set $E$ is said to be of finite character if the set of subsets $X$ of $E$ for which $P\{X\}$ is true is of finite character.

例

例 1 03T9

有序集合 $E$ 的总共有序子集中的集合是有限的特征标。事实上， $E$ 的子集 $X$ 是全有序的当且仅当两个元素的 $X$ 由……组成中的每一个子集都是全有序的。

例 2 03TA

\* 模的所有自由子集中的集合是有限的特征标。对于域的扩张的所有代数自由子集的集合也是如此。

例 3 03TB

模 $E$ 子模集合不是有限的特征标，因为 $E$ 子模有限子集不一定是 $E$ 子模。 \

定理 1 03LD

集合 $E$ 的子集的每个集合 $\mathfrak{S}$ ，其有限特征标都有极大元素（按包含排序时）。

引用了 4

引用了推论 2, III § 2, 定理 2（“佐恩的引理”）, III § 2, 命题 3, 推论 1

通过定理 2 of § 2, no. 4 足以证明 $\mathfrak{S}$ 是归纳性的。为此，我们将证明，如果 $\mathfrak{G}$ 是完全按包含排序的 $\mathfrak{S}$ 中的任何子集，则 $\mathfrak{G}$ 属于到 $\mathfrak{S}$ 的集合到并 $X$ （§ 2, no. 4，定理） 2、推论2)。由于 $\mathfrak{S}$ 是有限的特征标，因此足以证明 $X$ 属于到 $\mathfrak{S}$ 的每一个有限子集 $Y$ 。现在，对于每个 $y \in Y$ ，都存在集合 $Z_y \in \mathfrak{G}$ ，这样 $y \in Z_y$ 。由于集合 $Z_y$ $(y \in Y)$ 的集合是有限的且按包含全序，因此有最大元素 $S$ （no. 4，推论 1 至命题 3）；在其他字中，存在集合 $S \in \mathfrak{G}$ 使得 $Y \subset S$ 。但是由于 $S \in \mathfrak{S}$ 和 $Y$ 是 $S$ 的有限子集，我们有 $Y \in \mathfrak{S}$ ，因为 $\mathfrak{S}$ 是有限的特征标；这样就完成了证明。

习题

参见习题为 § 4。

[^1]: The notion of “integer” will be generalized later, in Algebra, where we shall define the rational integers and the algebraic integers.