1.1 集合、函数与符号

在本书中，我们尽量使用通用的符号和术语。我们采用将集合用大写字母表示，集合的元素用小写字母表示的约定。直观地说，我们将集合视为满足某个给定条件或属性的对象的集合，例如整数的集合、本书中的页面或在列表中列出的对象的集合。这些对象被称为集合的元素。给定一个集合$A$，表示为$x \in A$，意味着$x$是$A$的一个元素，符号$\in$ 表示“是集合的元素”或“是集合的成员”，而符号 $\notin$ 对应于“不是集合的成员”或“不是集合的元素”。存在一个集合没有任何元素，这个集合被称为空集，用符号 $\varnothing$ 表示。

本书中，我们将使用一些符号逻辑的符号来缩短陈述。例如，如果$p$和$q$代表数学命题，那么论断$p \Rightarrow q$表示“$p$蕴含$q$”，或者等价地说，“如果$p$为真，则$q$为真”。论断$p \Leftrightarrow q$读作“$p$当且仅当$q$”，意味着$p$和$q$在逻辑上等价，即$p \Rightarrow q$和$q \Rightarrow p$。

对于表达式 $p(x)$，当特定论域的值代入 $x$ 后变成一个命题，则称该表达式为一个"propositional function"（命题函数）。或者等价的，$x$为条件，$p$为性质（property）或谓词。断言“$x$ 具有性质 $p$” 意味着 $p(x)$ 为真。例如，如果 $p(x)$ 是命题函数“$x$是整数”，那么 $p$ 表示性质“是整数”，$p(2)$ 为真，而 $p(\frac{1}{2})$ 为假。

---

Harry:

在谓词逻辑中，$p(x)$代表一个谓词（predicate），它是一个包含变量的命题，表示$x$具有某种性质或满足某种条件。这里，$x$是一个变量，可以代表任意个体或对象。当你为变量$x$指定一个特定的值时，$p(x)$就成为一个命题，可以是真（true）或假（false）。

例如，如果我们定义一个谓词$P(x)$表示“$x$是一个偶数”，那么$P(2)$是真，$P(3)$是假。在这个例子中，$x$代表一个整数，而$P(x)$表示一个性质，即偶数性质。

---

一个集合可以通过描述其特性属性或列举其元素来定义。通常，这两种描述方式都可以用大括号括起来。当使用特性属性描述时，集合的表示形式为$\{ x : p(x) \}$，它的意思是“所有满足性质 $p(x)$ 的元素 $x$ 组成的集合”。例如，正整数 1 到 5 的集合可以表示为$\{ x : x \text{ 是小于 6 的正整数} \}$。在这里， $p(x)$ 是命题“$x$ 是小于 6 的正整数”，而 $p$ 表示性质“是小于 6 的正整数”。这个集合也可以通过列举其元素来定义：$\{1, 2, 3, 4, 5\}$。在我们的讨论中，我们假设构造$X = \{x : p(x)\}$是一个集合，当且仅当对于给定的对象 $x$，命题 $p(x)$ 要么为真，要么为假（即，不能同时为真和假）。这使得我们可以确定某个对象是否是集合 $X$ 的元素。

存在量词“存在”用符号$\exists$ 表示，而符号 $\nexists$ 表示“不存在”。存在量词“存在一个且仅一个”或等价地“存在唯一的”用符号 $\exists!$ 表示。全称量词“对于所有”用符号 $\forall$ 表示。连接词“使得”的常用符号是 $\ni$。因此，命题$\forall x \exists y \ni \forall z : p(x, y, z)$ 的含义是：“对于每个 $x$，存在一个$y$ 使得对于所有的 $z$，命题 $p(x, y, z)$ 为真。”

---

Harry:

在数学命题中，"implies(蕴含)" 表示逻辑蕴含关系，通常用符号 "$\Rightarrow$" 表示，表示一个命题的成立蕴含着另一个命题的成立。而"so that（使得）"则通常用于描述一个行动或条件，指的是某个结果或目的，它并不涉及逻辑关系。在数学语境中，通常我们使用 "implies" 来表示逻辑关系，而 "so that" 则用于描述目的或结果。

换言之， $\Rightarrow$用在命题间，而$\ni$用于命题中

---

如果 $X$ 和 $Y$ 是集合，那么 $X = Y$ 意味着它们具有相同的元素；即，$\forall x : x \in X \Rightarrow x \in Y$。符号 $X \subseteq Y$ 读作“$X$ 是 $Y$ 的子集”，表示 $X$ 的每个元素都是 $Y$ 的元素。更准确地说，$\forall x : x \in X \Rightarrow x \in Y$。这里并不排除相等的情况。因此，在必要时，我们会说如果 $X \subseteq Y$ 且 $X \neq Y$，那么 $X$ 是 $Y$ 的真子集（proper subset）。集合的所有子集构成的集合称为给定集合 $X$ 的幂集，表示为 $2^X$。上述定义直接导出了以下子集关系定律：

$S_1$：对于任意集合 $X$，$X \subseteq X ;\\$$S_2$：如果 $X \subseteq Y$ 且 $Y \subseteq Z$，那么 $X \subseteq Z ;\\$$S_3$：$X = Y$ 当且仅当 $X \subseteq Y$ 且 $Y \subseteq X ;\\$$S_4$：对于任意集合 $X$，$\varnothing \subseteq X ;\\$$S_5$：$\varnothing \in 2^X$ 且对于任意 $x \in X$，$\{x\} \in 2^X$

---

Harry:

在数学中，定理（Theorem）和定律（Law）是两个不同的概念：

1. 定理：定理是数学中的一个重要概念，是通过严格的推导和证明得出的数学命题。一个定理通常是基于一组公理或已经被证明的定理，并且在特定的逻辑体系下被证明成立。定理通常用于描述更一般性的数学关系和性质，它的证明需要严密的逻辑推理和数学符号的运用。定理在数学中具有普遍性和广泛应用性。

2. 定律：定律通常是对一类现象或数学关系的普适性规律的描述。定律并不一定需要进行严格的证明，而是基于观察和实验得出的普遍性规律。在数学中，定律通常指代一些基本的数学关系，例如交换律、结合律、分配律等。这些定律在特定的数学运算中具有普遍适用性。

总的来说，定理是通过严密证明得出的数学命题，而定律通常是基于观察和实验得出的一般性规律。

---

尽管这些子集关系是不言而喻的，但它们具有根本的重要性，因为我们将讨论许多其他与$S_1$到$S_4$中所述类似的关系。

除了子集关系外，还有为集合的集合（a collection of sets）的代数结构提供了三种基本的集合操作。对于这样的代数结构，习惯上将所考虑的集合视为某个更大的集合$U$的子集，称为全集（universal set）或论域全集（universe of discouse），通常用符号$U$表示。例如，在平面几何中，全集包含了平面上的所有点。

定义 1.1

令 $X$ 和 $Y$ 为两个集合。$X$ 和 $Y$ 的并集，用符号 $X \cup Y$ 表示，定义为那些在 $X$ 中或在 $Y$ 中、或者同在两者中的元素的集合。因此，

$$X \cup Y = \{z : z \in X \text{ 或 } z \in Y\}$$

$X$ 和 $Y$ 的交集，用符号 $X \cap Y$ 表示，定义为那些既在 $X$ 中又在 $Y$ 中的所有元素的集合。因此，

$$X \cap Y = \{z : z \in X \text{ 且 } z \in Y\}$$

尽管符号 $X^c$ 通常用于表示 $X$ 的补集，但本书中将使用符号 $X'$ 来表示补集。

补集 $X'$ 不应与 $X$ 和 $Y$ 的差集混淆。二者差集也称为 $X$ 减去 $Y$，以及相对于 $Y$ 的补集。$X$ 和 $Y$ 的差集，表示为 $X \backslash Y$，其定义为 $X \backslash Y = \{x : x \in X \text{ 且 } x \notin Y\}$。因此，$X' = U \backslash X$。以下定理给出了 $\cup$、$\cap$ 和 $\subseteq$ 之间的关系：

定理1.1 以下陈述是等价的：

(i) $X \subseteq Y \\$(ii) $X = X \cap Y \\$(iii) $Y = X \cup Y \\$(iv) $Y' \subseteq X'$ 且 $X \cap Y'= \varnothing$

基本集合操作（并、交、差）的规则如下：

$S_6$（恒等律）： $\begin{array}{l} X \cup U = U \\ X \cup \varnothing = X \end{array}$ 及 $\begin{array}{l} X \cap U = X \\ X \cap \varnothing = \varnothing \end{array}$；

$S_7（幂等律）$：$X \cup X = X$, $X \cap X = X$；

$S_8$（补集律）： $\begin{array}{l} (X')'=X \\ X \cup X' = U \end{array}$ 及 $\begin{array}{l} \varnothing' = U, U'=\varnothing\\ X \cap X' =\varnothing \end{array}$；

$S_9$（结合律）：$(X \cup Y) \cup Z = X \cup (Y \cup Z)$, $(X \cap Y) \cap Z = X \cap (Y \cap Z)$；

$S_{10}$（交换律）：$X \cup Y = Y \cup X$, $X \cap Y = Y \cap X$；

$S_{11}$（分配律）：$X \cup (Y \cap Z) = (X \cup Y) \cap (X \cup Z)$, $X \cap (Y \cup Z) = (X \cap Y) \cup (X \cap Z)$；

$S_{12}$（德摩根定律）：$(X \cup Y)' = X' \cap Y'$, $(X \cap Y)' = X' \cup Y'$；

$S_{13}$（等价律）：$\varnothing = A \backslash A'$, $A \cap B = A \backslash (A \backslash B)$。

除了并集和交集等集合操作之外，集合的笛卡尔积是将两个集合组合起来的最重要的构造方法之一，因为它使我们能够用集合的术语来表示许多概念。

定义 1.2 假设$X$和$Y$是两个集合。$X$和$Y$的笛卡尔积，表示为$X \times Y$，它是所有有序对$\{(x, y) : x \in X \text{且} y \in Y\}$组成的集合。

笛卡尔积也被称为叉积。集合$X × Y$中的元素$(x, y)$表示该有序对的第一个分量$x$必须是集合$X$的元素，而第二个分量$y$必须是集合$Y$的元素。此外，这些有序对受到以下条件的限制：$(a,b) = (c,d) \Leftrightarrow a = c,b = d$。有序对的分量也被称为坐标。

笛卡尔积的概念扩展了基本集合论操作集。然而，与并集和交集相比，笛卡尔积既不满足交换律也不满足结合律。当$X ≠ Y$时，$X × Y ≠ Y × X$。根据该乘积的定义，$(X × Y) × Z ≠ X × (Y × Z)$。例如，集合$(X × Y) × Z$中元素$((x,y),z)$的第一个分量可能对应于一个位置$(x,y)$，而第二个分量$z$对应该位置的温度。在这种情况下，元素$(x,(y,z))$属于集合$X × (Y × Z)$具有完全不同的含义。而等式$((x,y),z) = (x,(y,z))$意味着$x = (x,y)$且$z = (y,z)$。此外，$X × Y = \varnothing \Leftrightarrow X = \varnothing \text{或} Y = \varnothing$（或者两者都是）。

笛卡尔积与并集和交集的关系可以总结如下：

定理 1.2

$$X \times (Y \cup Z) = (X \times Y) \cup (X \times Z) \; \text{且} \; X \times (Y \cap Z) = (X \times Y) \cap (X \times Z)$$

习题 1.1

1. 假设$A = \{a, b, c\}，B = \{b, d\}，C = \{a, c, e\}$，计算$A \cup B \cup C$，$A \cap B \cap C$，及$A×B×C$和$(A×B)\cap(B×A)$。

---

Harry:

$$\begin{aligned} A \cup B \cup C & = \{a,b,c,d,e\} \\ A \cap B \cap C & = \varnothing \\ A \times B \times C & = \{(a,b,a),(a,b,c),(a,b,e),(a,d,a),(a,d,c),(a,d,e),...,(c,d,e)\} \\ (A \times B) \cap (B \times A) &= (b,b) \end{aligned}$$

---

1. 证明定理1.1。

Harry:

(i) 求证: $X \subseteq Y \iff X=X \cap Y$

首先证明 $$X \subseteq Y \implies X=X \cap Y$$

$$\begin{aligned} (\forall x) \; x \in X & \Rightarrow x \in Y &(\because X \subseteq Y)\\ & \Rightarrow x \in X \text{且} x \in Y \\ & \Rightarrow x \in X \cap Y \\ \end{aligned}$$

故

$$X \subseteq X \cap Y \qquad (1.1)$$

又

$$\begin{aligned} (\forall x) \; x \in X \cap Y & \Rightarrow x \in X \text{且} x \in Y\\ & \Rightarrow x \in X \\ \end{aligned}$$

故

$$X \cap Y \subseteq X \qquad (1.2)$$

由1.1，1.2可得

$$X = X \cap Y \qquad (S_{3})$$

因此，$X \subseteq Y \implies X=X \cap Y$ 得证 $\qquad$（1.3）

然后证明 $X = X\cap Y \implies X \subseteq Y$：

$$\begin{aligned} (\forall x) \; x \in X & \Rightarrow x \in X \cap Y & (\because X=X \cap Y)\\ & \Rightarrow x \in X \text{且} x \in Y\\ & \Rightarrow x \in Y \\ \end{aligned}$$

故

$$X \subseteq Y$$

因此，$X = X\cap Y \implies X \subseteq Y$ 得证 $\qquad$ （1.4）

由1.3、1.4可知 ：

$$X \subseteq Y \iff X=X \cap Y$$

证毕。

(iv) 求证：$X \subseteq Y \iff Y' \subseteq X'$ 且 $X \cap Y'= \varnothing$

首先证明

$$X \subseteq Y \implies Y' \subseteq X' \,\text{且} \,X \cap Y'= \varnothing$$

如下：

$$\begin{aligned} (\forall y) \; y \in Y' & \Rightarrow y \in U \;\text{且}\; y \notin Y\\ & \Rightarrow y \in U \;\text{且}\; y \notin X & (\because X \subseteq Y)\\ & \Rightarrow y \in X' \\ \end{aligned}$$

故：

$$Y' \subseteq X' \qquad (4.1)$$

现在通过反证法证明$X \cap Y' = \varnothing$。假设

$$X \cap Y' \neq \varnothing$$

则

$$\begin{aligned} (\exists x) \; x \in X \cap Y' & \Rightarrow x \in X \;\text{且}\; x \in Y'\\ & \Rightarrow x \in X \;\text{且}\; y \notin Y \\ \end{aligned}$$

这与 $X \subseteq Y$矛盾。故

$$X \cap Y' = \varnothing \qquad (4.2)$$

由4.1、4.2可得

$$X \subseteq Y \implies Y' \subseteq X' \,\text{且} \,X \cap Y'= \varnothing \qquad (4.3)$$

然后证明

$$Y' \subseteq X' \,\text{且} \,X \cap Y'= \varnothing \implies X \subseteq Y$$

如下：

使用反证法，假设

$$\begin{aligned} X \nsubseteq Y &\Rightarrow (\exist x) \; x \in X \,\text{且}\, x \notin Y \\ & \Rightarrow x \in X \;\text{且}\; x \in Y'\\ & \Rightarrow x \in X \cap Y' \\ \end{aligned}$$

这与 $X \cap Y'= \varnothing$矛盾。故

$$Y' \subseteq X' \,\text{且} \,X \cap Y'= \varnothing \implies X \subseteq Y \qquad (4.4)$$

由4.3,4.4可得

$$X \subseteq Y \iff Y' \subseteq X' \text{且} X \cap Y'= \varnothing$$

证毕。

1. 证明定律$S_6$到$S_{13}$。

Harry:

($S_{12}$) 求证（德摩根定律）：$(X \cup Y)' = X' \cap Y'$, $(X \cap Y)' = X' \cup Y'$；

以证明$(X \cup Y)' = X' \cap Y'$为例。

首先证明

$$(X \cup Y)' \subseteq X' \cap Y'$$

使用反证法，假设

$$\begin{aligned} (X \cup Y)' \nsubseteq X' \cap Y' & \Rightarrow (\exist x) \; x \in (X \cup Y)' \,\text{且}\, x \notin X' \cap Y' \\ & \Rightarrow x \notin (X \cap Y) \;\text{且}\; x \notin X' \;\text{且}\; x \notin Y'\\ & \Rightarrow x \notin (X \cap Y) \;\text{且}\; x \in X \;\text{且}\; x \in Y\\ & \Rightarrow x \notin (X \cap Y) \;\text{且}\; x \in (X \cap Y)\\ \end{aligned}$$

以上推论自相矛盾，故以下成立

$$(X \cup Y)' \subseteq X' \cap Y' \qquad (12.1)$$

同样可是使用反证法，假设

$$\begin{aligned} X' \cap Y' \nsubseteq(X \cup Y)' & \Rightarrow (\exist x) \; x \in X' \cap Y' \,\text{且}\, x \notin (X \cup Y)' \\ & \Rightarrow x \in X' \;\text{且}\; x \in Y' \;\text{且}\; x \in (X \cup Y)\\ & \Rightarrow x \notin X \;\text{且}\; x \notin Y \;\text{且}\; x \in (X \cup Y)\\ & \Rightarrow x \notin X \;\text{且}\; x \notin Y \;\text{且}\; x \in X \;\text{或}\; x \in Y\\ \end{aligned}$$

以上推论自相矛盾，故以下成立

$$X' \cap Y' \subseteq(X \cup Y)' \qquad (12.2)$$

由12.1、12.2可得

$$(X \cup Y)' = X' \cap Y'$$

证毕。

1. 证明定理1.2。

---

Harry:

设 $(a,b) \in X \times ( Y \cup Z)$，则由笛卡尔积定义有：

$$\begin{aligned} (a,b) \in X \times ( Y \cup Z) & \Rightarrow a \in X \text{ 且 } b \in Y \cup Z \\ & \Rightarrow a \in X \text{ 且 } b \in Y \text{或} b \in Z \\ & \Rightarrow (a,b) \in X \times Y \quad \text{或} \quad (a,b) \in X \times Z \\ & \Rightarrow (a,b) \in (X \times Y) \cup (Y \times Z) \end{aligned}$$

因此有

$$X \times (Y \cup Z) \subseteq (X \times Y) \cup (X \times Z)$$

同理可得

$$(X \times Y) \cup (X \times Z) \subseteq X \times (Y \cup Z)$$

因此可得

$$X \times (Y \cup Z) = (X \times Y) \cup (X \times Z)$$

同理可证

$$X \times (Y \cap Z) = (X \times Y) \cap (X \times Z)$$

故，定理1.2得证

---

1.1.1 特殊集合和集合族

在本书中，某些数集自然而然地出现，我们将符号 $\mathbb{R}$ 保留用于表示实数集， $\mathbb{R}^+$ 表示正实数集， $\mathbb{R}^-$ 表示负实数集，而 $\mathbb{R}_{[0,\infty)}$ 表示非负实数集合.符号 $\mathbb{Z}$ 表示整数集 {⋯, -3, -2, -1, 0, 1, 2, 3, ⋯}，$\mathbb{N}$ 表示自然数集 {1, 2, 3, ⋯}，$\mathbb{N}_{[0,\infty)}n$ 表示非负整数集合 {0, 1, 2, ⋯}，$\mathbb{N}_n$ 表示小于等于 n 的自然数集合 {1, 2, 3, ⋯, n}，而 $\mathbb{Z}_n$ 表示小于等于 n 的整数集合 {0, 1, 2, ⋯, n-1}。

当 $a$ 和 $b$ 为实数时，关系 $a < b$、$a ≤ b$、$b > a$ 和 $b ≥ a$ 分别表示 $a$ 严格小于 $b$、$a$ 小于等于 $b$、$b$ 严格大于 $a$ 和 $b$ 大于等于 $a$。关系 $≤$（或 $≥$）是实数集 $mathbb{R}$ 上的一种称为实数集的自然序的序关系。这个序关系具有额外的性质，对于任意的实数 $a$ 和 $b$，要么 $a ≤ b$，要么 $b ≤ a$。这种类型的序被称为全序，因为任意两个元素都是相关联的。关于集合的序关系的精确定义将在第三章给出。在整数的顺序法则和子集法则之间存在一些相似之处。例如，在考虑集合 $\mathbb{N}_{[0,\infty)}$ 时，我们可以看到以下陈述：

$\begin{aligned} S_1. \quad & x \leq x \, \forall x \in \mathbb{N}_{[0,\infty)} \\ S_2. \quad & \text{如果} x \leq y \text{且} y \leq z, \text{则} x \leq z \\ S_3. \quad & x=y \text{当且仅当}, x \leq y \text{且} y \leq x \\ S_4. \quad & 0 \leq x \, \forall x \in \mathbb{N}_{[0,\infty)} \\ \end{aligned}$

这些法则除了使用不同的符号之外，实质上是 上文$S_1$ 到 $S_4$ 的镜像。这种相似性并不止步于此。考虑到集合的并、交运算的恒等律、结合律和分配律，可以明显看出它们类似于非负整数 $\mathbb{N}_{[0,\infty)}$ 上的加法和乘法法则：

恒等律：$x + 0 = x \text{和} x × 0 = 0$

结合律：$(x + y) + z = x + (y + z) \text{和} (x × y) × z = x × (y × z)$；

交换律：$x + y = y + x \text{和} x × y = y × x$；

分配律：$x × (y + z) = (x × y) + (x × z)$。

这种相似性将贯穿于本书的全文。

实数集可以通过引入最大元素和最小元素的概念进行扩展。分别称为正无穷和负无穷的符号$\infty$和$-\infty$,可用来以以下三种方式扩展$\mathbb{R}$设置:

$\mathbb{R}_{\infty} = \mathbb{R} \cup \{\infty\} \\ \mathbb{R}_{-\infty} = \mathbb{R} \cup \{-\infty\} \\ \mathbb{R}_{\pm\infty} = \mathbb{R}_{\infty} \cup \mathbb{R}_{-\infty} = \mathbb{R} \cup \{\infty,-\infty\} \\ \mathbb{R}_{[0,\infty]} = \mathbb{R}_{[0,\infty)}\cup \{\infty\}$

通过声明$\infty$大于任何实数，$-\infty$小于任何实数，这些集合成为有序集。$\mathbb{R}_{[0,\infty]}$的子集$\mathbb{N}_{[0,\infty]}$是通过设置$\mathbb{N}_{[0,\infty]}=\mathbb{N}_{[0,\infty)} \cup \{\infty\}$ 来定义的。最后，有理数集和复数集分别用$\mathbb{Q}$和$\mathbb{C}$表示。

如果对于某个非空集合$\Lambda$的每个元素$\lambda$都对应一个集合$X_λ$，则集合$\{X_\lambda:\ \lambda \in \Lambda\}$称为集合族，$Λ$称为该族的索引集(indexing set)。这样的索引族通常也用$\{X_\lambda\}_{\lambda \in \Lambda}$表示。如果索引集$Λ = \mathbb{N}$，则索引族$\{X_i\}_{i \in \mathbb{N}}$称为一个序列（集合的序列），也可以用$\{X_i\}_{i=1}^{\infty}$表示。

并集和交集的概念可以推广到任意的索引集族，这些集合是全集$U$的子集。

定义1.3 令$\{X_\lambda\}_{\lambda \in \Lambda}$是全集$U$的子集族。该族的并集用$\bigcup_{\lambda \in \Lambda} X_{\lambda}$表示，即集合：

$$\{ x \in U\ :\ \text{至少存在一个} \lambda \in \Lambda, \text{有} x \in X_{\lambda} \}$$

交集用$\bigcap_{\lambda \in \Lambda} X_{\lambda}$表示，即集合：

$$\{ x \in U\ :\ \text{对任意} \lambda \in \Lambda, \text{有} x \in X_{\lambda} \}$$

对于有限和无限序列$\{X_i\}_{i=1}^n$和$\{X_i\}_{i=1}^\infty$，我们也将使用如下符号：

$$\begin{aligned} \bigcup_{i=1}^n X_i & = X_1 \cup X_2 \cup \ldots \cup X_n \\ \bigcup_{i=1}^{\infty} X_i & = X_1 \cup X_2 \cup \ldots \\ \bigcap_{i=1}^n X_i & = X_1 \cap X_2 \cap \ldots \end{aligned}$$

示例 1.1 令$\Lambda = \{ \lambda : \lambda \in \mathbb{R} \text{ 且 } 0 \leq \lambda \leq 1 \}$。对每个$\lambda \in \Lambda$，令$X_\lambda = \{ r : r \in \mathbb{R}, 0 \leq r \leq \lambda \}$。那么：

$$\bigcup_{\lambda \in \Lambda} X_\lambda = \{ r : r \in \mathbb{R}, 0 \leq r \leq 1 \} = \Lambda$$

$$\bigcap_{\lambda \in \Lambda} X_\lambda = \{ 0 \}$$

这个例子可以推广为：令$X$ 是任意集合，对于每个 $x \in X$，令 $X_x$ 是 $X$ 的一个子集，使得 $x \in X_x \subset X$. 那么 $X = \bigcup_{x \in X} X_x$。

假设 $\{ A_\lambda \}_{\lambda \in \Lambda}$ 是一组（以$\Lambda$为索引集的）集合，$X$ 是任意集合。那么并集和交集遵循以下等价律：

$\begin{aligned} S_{14}. \quad & X \backslash (\bigcup_{\lambda \in \Lambda} A_\lambda) = \bigcap_{\lambda \in \Lambda} (X \backslash A_\lambda) \\ S_{15}. \quad & X \backslash \bigcap_{\lambda \in \Lambda} A_\lambda^\prime = \bigcup_{\lambda \in \Lambda} (X \backslash A_\lambda) \\ \end{aligned}$

这些律规在我们对测度论（measure theory）的讨论中发挥了关键作用。

一组集合 $\{ X_i \}_{i=1}^n$ 的 $n$ 次笛卡尔积可以通过归纳法定义，得到以下形式：

$$\prod_{i=1}^n X_i = X_1 \times X_2 \times \ldots \times X_n = \{(x_1, x_2, \ldots, x_n) : x_i \in X_i \text{ , } i \in \mathbb{N}\}$$

其中 $x_i$ 被称为第 $i$ 个坐标。如果 $X = X_i$ 对于 $i = 1, \ldots, n$，那么我们定义 $X^n = \prod_{i=1}^n X_i$。特别地，如果 $\mathbb{R} = X_i$ 对于 $i = 1, \ldots, n$，那么 $n$ 维欧几里得空间由 $\mathbb{R}^n = \prod_{i=1}^n \mathbb{R}$ 给出。类似地，$\mathbb{R}_{\infty}^{n} = \prod_{i=1}^n \mathbb{R}_{\infty}$，$\mathbb{R}_{-\infty}^{n} = \prod_{i=1}^n \mathbb{R}_{-\infty}$，$\mathbb{R}_{\pm \infty}^n = \prod_{i=1}^n \mathbb{R}_{\pm \infty}$。

习题 1.1.1

1. 设 $A = \{(x, y) : x, y \in \mathbb{R} \text{ 且 } 3x + y = 4\}$，以及 $B = \{(x, y) : x, y \in \mathbb{R} \text{ 且 } x - 2y = 2\}$。确定 $A$、$B$、$A \cap B$ 和 $A \times B$ 的图形。

Harry:

$A$ 与 $B$分别是两条直线，$A \cap B$是两条直线的交点。

⭕ 比较不好理解的是 $A \times B$，按照笛卡尔积定义, $A \times B = \{((x_1,y_1),(x_2,y_2) : (x_1,y_1) \in A, (x_2,y_2) \in B)\}$ 。 这如何在二维空间绘制出来？

⭕ 事实上，$A \times B$中的元素是形如 $(x_1, y_1, x_2, y_2)$ 的四元组，其中 $(x_1, y_1)$ 满足 $3x_1 + y_1 = 4$，而 $(x_2, y_2)$ 满足 $x_2 - 2y_2 = 2$。$A \times B$ 的图形可以在四维空间中表示，其中 $x_1, y_1, x_2, y_2$ 分别是四个坐标轴。然而，由于我们无法直观地在三维或二维空间中表示四维对象，因此通常我们会采用其他方法来可视化。

在实际应用中，可以通过选择一些特定的值，例如 $x_1 = x_2 = 0$，来观察 $A \times B$ 中的一些元素，从而对其性质有一些直观的认识。

1. 证明等价律 $S_{14}$。

Harry:

证明如下：

$$\begin{aligned} \forall x, x \in X \backslash (\bigcup_{\lambda \in \Lambda} A_\lambda) & \Rightarrow x \in X \text{ 且 } x \notin \bigcup_{\lambda \in \Lambda} A_\lambda \\ & \Rightarrow x \in X \text{ 且 } (\forall \lambda \in \Lambda, x \notin A_\lambda)\\ & \Rightarrow \forall \lambda \in \Lambda, x \notin A_\lambda \text{ 且 } x \in X\\ & \Rightarrow \forall \lambda \in \Lambda, x \in X \backslash A_\lambda \\ & \Rightarrow x \in \bigcap_{\lambda \in \Lambda} (X \backslash A_\lambda ) \end{aligned}$$

因此有

$$X \backslash (\bigcup_{\lambda \in \Lambda} A_\lambda) \subseteq \bigcap_{\lambda \in \Lambda} (X \backslash A_\lambda) \qquad (14.1)$$

另，

$$\begin{aligned} \forall x, x \in \bigcap_{\lambda \in \Lambda} (X \backslash A_\lambda ) & \Rightarrow \forall \lambda \in \Lambda, x \in (X \backslash A_\lambda)\\ & \Rightarrow \forall \lambda \in \Lambda, x \in X \text{ 且 } x \notin A_\lambda\\ & \Rightarrow x \in X \text{ 且 } \forall \lambda \in \Lambda,x \notin A_\lambda\\ & \Rightarrow x \in X \text{ 且 } x \notin \bigcup_{\lambda \in \Lambda}A_\lambda\\ & \Rightarrow x \in X \backslash \bigcup_{\lambda \in \Lambda}A_\lambda\\ \end{aligned}$$

因此有

$$\bigcap_{\lambda \in \Lambda} (X \backslash A_\lambda) \subseteq X \backslash (\bigcup_{\lambda \in \Lambda} A_\lambda) \qquad (14.2)$$

由 14.1, 14.2可得

$$X \backslash (\bigcup_{\lambda \in \Lambda} A_\lambda) = \bigcap_{\lambda \in \Lambda} (X \backslash A_\lambda)$$

故，$S_{14}$得证

1.1.2 函数

函数或映射的概念在所有数学中都是基础的。直观地说，从集合 $X$ 到集合 $Y$ 的函数 $f$，表示为 $f : X \to Y$，是一种规则，它将 $X$ 中的每个元素 $x$ 分配给 $Y$ 中的某个元素 $y$，其中规则 $f$ 对 $x$ 到 $y$ 的分配表示为 $f(x) = y$。然而，我们将根据集合的术语正式定义函数的概念。

定义 1.4 设 $X$ 和 $Y$ 是两个集合。从 $X$ 到 $Y$ 的函数 $f$，表示为 $f : X \to Y$，是满足性质的 $X \times Y$ 的子集 $f \subseteq X \times Y$：对于每个 $x \in X$ 存在 $y \in Y$ 使得 $(x, y) \in f$。所有从 $X$ 到 $Y$ 的函数的集合将被表示为 $Y^X$。因此，$Y^X = \{f : f$ 是从 $X$ 到 $Y$ 的函数}。函数也称为映射。

我们用$f(x) = y$ 表示 $(x, y) \in f$，并说 $y$ 是 $f$ 在 $x$ 处的取值，或者说 $y$ 是 $f$ 在 $x$ 处的求值。例如，定义 $X = Y = \mathbb{N}$，那么由以下规则定义的 $f \subseteq X \times Y$ 集合：

$$f = \{(x, y) : y = 2x + 1, x \in X\}$$

或者等价地，

$$f = \{(x, 2x + 1) : x \in X\}$$

表示一个函数 $f : X \to Y$。这个函数由规则 $f(x) = 2x + 1$ 或等价地由 $y = 2x + 1$ 完全确定。

我们将定期提到一些特殊属性和类型的函数。区分以下类型的函数是特别重要的：

• $f_1$：如果 $f : X \to Y$，$f(x) \neq f(z)$当且仅当 $x \neq z$ 。 或等价地，$f(x) = f(z) \Rightarrow x = z$，则称函数 $f$ 是 单射(injective) 或 一一对应(one-to-one) 的。

Harry:

显然，函数$f(x) = x$是单射，而$f(x)= x^2$则不是单射，因为$f(-1)=1=f(1)$，而$-1 \neq 1$

• $f_2$：如果 $f : X \to Y$，当且仅当每个 $y$ 都存在 $X$ 中的 $x$ 使得 $f(x) = y$ 时，即 $\forall y \in Y, \exist x \in X \ni f(x)=y$ ，则称函数 $f$ 是 满射（surjective 或 onto） 。

Harry:

函数$f: \mathbb{R} \to \mathbb{R},f(x) = x^2$是满射，而$f: \mathbb{N} \to \mathbb{N},f(x)=x^2$则不是满射

• $f_3$：如果函数 $f : X \to Y$ 同时是单射和满射的，则称其为双射。

Harry:

以下是各种映射的图示

例如，函数$f(x) = x, x \in \mathbb{R}$是双射

• $f_4$：具有性质 $f(x) = x, \forall x \in X$ 的函数 $f : X \to X$ 称为恒等函数。

Harry:

例如，函数$f:\mathbb{R} \to \mathbb{R},f(x) = x$是恒等函数，记作$1_\mathbb{R}$

• $f_5$：当且仅当对于某个 $y \in Y$，有 $f(x) = y, \forall x \in X$时，则称函数 $f$ 为常函数。

Harry:

公式表达为 $\forall x \in X, \exist y \in Y, f(x)=y$

例如 $f:\mathbb{R} \ to \mathbb{R}, f(x)=0$

• $f_6$：给定函数 $f : X \to Y$ 和 $W \subseteq X$，则定义在 $W$ 上的函数 $f\vert_W : W \to Y$，由 $f\vert_W = f \cap (W \times Y) = \{(x, f(x)) : x \in W\}$，称为 $f$ 对 $W$ 的限制(restriction)。

Harry:

公式表达为 $\forall x \in X, \exist y \in Y, f(x)=y$

例如 $f:\mathbb{R} \to \mathbb{R}, f(x)=0$

• $f_7$：给定集合 $X_1, \ldots, X_n$，对于 $1 \leq j \leq n$，由 $p_j : \prod_{i=1}^{n} X_i \to X_j$ 定义的函数，其中 $p_j(x_1, \ldots, x_j, \ldots, x_n) = x_j$ 称为投影到第 $j$ 个坐标。

Harry:

例如：$p_1: X \times Y \times Z \to X, g_1(x,y,z)=x$

• $f_8$：对于 $X \subseteq U$，由 $\chi_X : U \to \{0, 1\}$ 定义的函数，

$$\chi_X(x) = \begin{cases} 1 & \text{如果} \ x \in X \\ 0 & \text{如果} \ x \notin X \end{cases}$$

$\qquad$ 称为集合 $X$ 的特征函数。

$f_4$定义的恒等函数通常表示为 $1_X$。

请注意，两个函数 $f: X \to Y$ 和 $g: Y \to Z$ 的复合函数是一个函数 $g \circ f: X \to Z$，由 $(g \circ f)(x) = g[f(x)], \ \forall x \in X$ 定义。下面的定理说明了建立给定函数 $f$（或 $g$）是一对一（或满射）的简单方法。

定理1.3 令 $f: X \to Y$, $g: Y \to X$, 以及 $h: Y \to Z$。

1. 如果 $g \circ f = 1_X$, 那么 $f$ 是单射的，而 $g$ 是满射的。
2. 如果 $f$ 和 $h$ 是满射的，那么 $h \circ f: X \to Z$ 也是满射的。
3. 如果 $f$ 和 $h$ 是单射的，那么 $h \circ f: X \to Z$ 也是单射的。

证明。我们只证明定理的第1部分，将剩余的部分留作习题。

由于

$$f(x) = f(z) \Rightarrow x = (g \circ f)(x) = g(f(x)) = g(f(z)) = (g \circ f)(z) = z$$

我们得知 $f$ 是单射的。

又由于

$$\forall x \in X, \ \exists y \in Y， y = f(x) \Rightarrow x = (g \circ f)(x) = g(f(x)) = g(y)$$

所以 $g$ 是满射的。$\Box$

在定理1.3 证明的最后一句话后面是 Halmos 符号 $\Box$。这个符号代表拉丁短语 "Q.E.D"(“quod erat demonstrandum”的缩写)，意为“即所证明的”，在本文末尾的定理证明中将会经常使用。

Harry:

Halmos符号是数学家Paul Halmos提出的一个数学符号。

Paul Halmos是一位20世纪的数学家，他提倡使用这个符号来标记证明的结束，以增加数学文献的清晰度。虽然这个符号的使用并非普遍规范，但在许多数学文献中都可以看到。

我们展示一个定理1.3的简单示例。对于任意函数 $h: X \to Z$和函数 $f: X \to Y$，其中 $Y = X \times Z$ 且 $f(x) = (x, h(x))$ 是单射的。设 $p_1: X \times Y \to X$ 是到第一个坐标的投影。那么 $p_1 \circ f: X \to X$ 是 $1_X$。因此，根据定理1.3，$f$ 是单射的（且 $p_1$ 是满射的）。

Harry:

• ⭕ 不清楚这部分描述的意义：

$\quad$ 对于任意函数$h: X \to Z$和函数 $f: X \to Y$，其中 $Y = X \times Z$ 且 $f(x) = (x, h(x))$ 是单射的。

$\quad$ 为什么要定义$f$是单射？这不是想利用定理1.3推出的结论吗？

• 我们可以另外给一个例子：假设 $X=Z=\mathbb{N}$，对$\forall x, y \in \mathbb{N}$，有$f(x) = (x, x+1)$, $g(x,y)=x$，则$g \circ f (x) = g (x,x+1) = x$，即$g \circ f = 1_X$，则显然$f$是单射（$\because (x_1,x_1+1)=(x_2,x_2+1) \Rightarrow x_1=x_2$），而$g$确实是满射。

定义 1.5 假设 $f: X \to Y$，$A \subset X$，$B \subset Y$。那么：

• 函数 $f$ 的值域（range）是集合 $R(f) = \{f(x) : x \in X\}$；
• 集合 $A$ 的像是集合 $f(A) = \{y : y = f(x), x \in A\}$；
• 集合 $B$ 的原像（pre-image）是集合 $f^{-1}(B) = \{x : f(x) \in B\}$。

函数 $f: X \to Y$ 的定义域（domain）是集合 $X$。原像也被称为逆像。这些定义的直接结果是 $f^{-1}(R(f)) = X$，$R(f) \subset Y$，且 $R(f) = Y \Leftrightarrow f \text{是满射}$ 。此外，当$B \neq \varnothing$，$f^{-1}(B)$ 也可能为空。

Harry:

设函数$f: ℝ → ℝ$，其中$f(x) = x^2$。有集合$B = \{y : y ∈ ℝ , y < 0\}$，即所有负实数的集合。在这种情况下，$f^{−1}(B)$ 将为空集，因为平方根函数的定义域是非负实数。所以，尽管$B ≠ \varnothing$，但$f^{−1}(B)$可能为空。

原像的概念引出了一个函数 $f^{-1}: 2^Y \to 2^X$，其定义为 $f^{-1}(B) \in 2^X, \forall B \in 2^Y$。类似地，函数$f$引出的函数$2^X \to 2^Y$ 也被表示为 $f$，其定义为 $f(A) \in 2^Y, \forall A \in 2^X$，其中 $f(\varnothing) = \varnothing$。这两个引出的函数被称为集合函数，因为它们将集合映射到集合。我们通过列举一些集合函数的基本属性来结束本节。这里列出的许多属性将在后面的章节中以类似的形式周期性地出现。

Harry:

$2^X$是$X$的幂集，$2^Y$是$Y$的幂集

定理 1.4 令 $f: X \to Y$，$A \subset B \subset X$，且$\{A_\lambda\}_{\lambda \in \Lambda}$ 是 $X$ 的子集族。那么：

1. $f(A) \subset f(B)$
2. $f(\bigcup_{\lambda \in \Lambda} A_\lambda) = \bigcup_{\lambda \in \Lambda} f(A_\lambda)$
3. $f(\bigcap_{\lambda \in \Lambda} A_\lambda) \subset \bigcap_{\lambda \in \Lambda} f(A_\lambda)$

如果 $A \subset B \subset Y$，$\{B_\lambda\}_{\lambda \in \Lambda}$ 是 $Y$ 的子集族。那么：

4. $f^{-1}(A) \subset f^{-1}(B)$
5. $f^{-1}(B') \subset (f^{-1}(B))'$
6. $f^{-1}(\bigcup_{\lambda \in \Lambda} B_\lambda) = \bigcup_{\lambda \in \Lambda} f^{-1}(B_\lambda)$
7. $f^{-1}(\bigcap_{\lambda \in \Lambda} B_\lambda) = \bigcap_{\lambda \in \Lambda} f^{-1}(B_\lambda)$

证明：我们只证明性质 7，因为性质 1 到性质 6 的证明同样简单。注意到：

$$\begin{aligned} x \in f^{-1}(\bigcap_{\lambda \in \Lambda} B_\lambda) & \Leftrightarrow f(x) \in \bigcap_{\lambda \in \Lambda} B_{\lambda} \\ & \Leftrightarrow f(x) \in B_{\lambda} \quad \forall \lambda \in \Lambda \\ & \Leftrightarrow x \in f^{-1}(B_{\lambda}) \quad \forall \lambda \in \Lambda \\ & \Leftrightarrow x \in \bigcap_{\lambda \in \Lambda} f^{-1}(B_\lambda) \qquad \Box \end{aligned}$$

以上关系证明了 $f^{-1}(\bigcap_{\lambda \in \Lambda} B_\lambda) \subset \bigcap_{\lambda \in \Lambda} f^{-1}(B_\lambda)$。

Harry:

⭕ 这只能证明$f^{-1}(\bigcap_{\lambda \in \Lambda} B_\lambda) \subseteq \bigcap_{\lambda \in \Lambda} f^{-1}(B_\lambda)$ ,而不是 $\subset$

关于两个集合函数之间的重要关系也很容易验证：

定理 1.5 设 $f: X \to Y$，$A \subset X$，$B \subset Y$。那么：

1. $A \subset f^{-1} \circ f(A)$
2. $f \circ f^{-1}(B) \subset B$

下面的例子说明了定理 1.4 中的推论 (3) 和定理 1.5 中的包含关系通常不能被等式替代。

例 1.2 设 $A = \{(x, y) : 1 \leq x \leq 2, 1 \leq y \leq 2\}$，$B = \{(x, y) : 1 \leq x \leq 2, 3 \leq y \leq 4\}$，$p_1 : \mathbb{R} \times \mathbb{R} \to \mathbb{R}$ 是到第一个坐标（即 $x$ 轴）的投影。由于 $A \cap B = \varnothing$，所以

$$p_1(A \cap B) = \varnothing \neq \{x : 1 \leq x \leq 2 \}=p_1(A) \cap p_1(B)$$

此外，

$$A \neq p_1^{-1}(p_1(A)) = p_1^{-1}( \{x : 1 \leq x \leq 2\} ) = \{(x, y) : 1 \leq x \leq 2, -\infty < y < \infty\}$$

如果 $f: X \to Y$ 是双射，那么对于所有 $y \in Y$，集合 $f^{-1}(\{y\})$ 包含单个元素 $x \in X$，使得 $\{x\} = f^{-1}(\{y\})$。因此，集合函数 $f^{-1}$ 定义了从 $Y$ 到 $X$ 的双射，记作 $f^{-1}$，定义为 $f^{-1}(y) = f^{-1}(\{y\})$。在这种情况下，我们有 $(f^{-1})^{-1} = f$，该等式对定理 1.5 的性质（1）和（2）都成立。此外，如果 $g : Y \to Z$ 也是双射，那么 $f \circ g$ 和 $(g \circ f)^{-1}$ 都是双射。这来自于定理 1.3 以及事实 $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$。

习题 1.1.2

1. 证明定理 1.3 的第 2 部分和第 3 部分。

Harry:

先证定理1.3的第2部分，即$h \circ f: X \to Z$ 也是满射。

$$\begin{aligned} \forall z \in Z, z = h \circ f & \Rightarrow \exist y \in Y, z= h(y), y=f \qquad (\because h\text{是满射})\\ & \Rightarrow \exist x \in X , y=f(x)\qquad (\because f\text{是满射}) \\ \end{aligned}$$

即

$$\forall z \in Z, z = h \circ f \Rightarrow \exist x \in X, h\circ f(x) = z$$

故$h \circ f: X \to Z$是满射 $\Box$

现在证第3部分，即对于单射函数$h$和$f$，其复合函数$h \circ f: X \to Z$ 也是单射。

$$\begin{aligned} \forall x, z \in Z, h \circ f(x) = h \circ f(z) & \Rightarrow f(x) = f(z) \qquad (\because h\text{是单射})\\ & \Rightarrow x=z \qquad (\because f\text{是单射}) \\ \end{aligned}$$

即

$$\forall x,z \in Z,h \circ f(x) = h \circ f(z) \Rightarrow x=z$$

故$h \circ f: X \to Z$是单射 $\Box$

2. 证明定理 1.4 的第 1、2、3 部分。

Harry:

先证第1部分。

首先使用反证法先证明 $f(A) \subseteq f(B)$：

$$\begin{aligned} f(A) \nsubseteq f(B) & \Rightarrow \exist x \in A, f(x) \in f(A), f(x) \notin f(B) \\ & \Rightarrow x \in B, f(x) \notin f(B)\\ \end{aligned}$$

显然以上结论自相矛盾，因此$f(A) \subseteq f(B)$

然后证明$f(A) \neq f(B)$

$$\begin{aligned} A \subset B & \Rightarrow \exist x \in A, x \notin B \\ & \Rightarrow f(x) \in f(A), f(x) \notin f(B)\\ & \Rightarrow f(A) \neq f(B) \end{aligned}$$

综上， $f(A) \subset f(B)$ 得证 $\qquad \Box$

再证第2部分。

$$\begin{aligned} f(x) \in f(\bigcup_{\lambda \in \Lambda}A_\lambda) & \Leftrightarrow x \in \bigcup_{\lambda \in \Lambda}A_\lambda \\ & \Leftrightarrow x \in A_\lambda, \ \exist \lambda \in \Lambda \\ & \Leftrightarrow f(x) \in f(A_\lambda), \ \exist \lambda \in \Lambda \\ & \Leftrightarrow f(x) \in \bigcup_{\lambda \in \Lambda}f(A_\lambda) \\ \end{aligned}$$

故，$f(\bigcup_{\lambda \in \Lambda}A_\lambda)=\bigcup_{\lambda \in \Lambda}f(A_\lambda)$得证 $\qquad \Box$

再证第3部分。

$$\begin{aligned} f(x) \in f(\bigcap_{\lambda \in \Lambda}A_\lambda) & \Rightarrow x \in \bigcap_{\lambda \in \Lambda}A_\lambda \\ & \Rightarrow x \in A_\lambda, \ \forall \lambda \in \Lambda \\ & \Rightarrow f(x) \in f(A_\lambda), \ \forall \lambda \in \Lambda \\ & \Rightarrow f(x) \in \bigcap_{\lambda \in \Lambda}f(A_\lambda) \\ \end{aligned}$$

故，$f(\bigcap_{\lambda \in \Lambda}A_\lambda) \subseteq \bigcap_{\lambda \in \Lambda}f(A_\lambda)$ 得证 $\qquad \Box$

1. 证明定理 1.4 的第 4、5、6 部分。

Harry:

先证第4部分：

$$\begin{aligned} x \in f^{-1} (A) & \Rightarrow f(x) \in A \\ & \Rightarrow f(x) \in B \qquad (\because A \subset B)\\ & \Rightarrow x \in f^{-1}(B) \\ & \therefore f^{-1}(A) \subseteq f^{-1}(B) \end{aligned}$$

再证明 $f^{-1}(A) \neq f^{-1}(B)$。

$$\begin{aligned} A \subset B \subset Y & \Rightarrow \exist y \in B , y \notin A \\ & \Rightarrow \exist x \in X, y=f(x), f(x) \in f(B), f(x) \notin f(A) \\ & \Rightarrow x \in f^{-1}(B), x \notin f^{-1}(A) \\ & \therefore f^{-1}(A) \neq f^{-1}(B) \end{aligned}$$

故，$f^{-1}(A) \subset f^{-1}(B)$得证 $\qquad \Box$

现在证明第5部分：

$$\begin{aligned} x \in f^{-1} (B') & \Rightarrow f(x) \in B' \\ & \Rightarrow f(x) \notin B \\ & \Rightarrow x \notin f^{-1}(B) \\ & \Rightarrow x \in (f^{-1}(B))' \\ & \therefore f^{-1} (B') \subseteq (f^{-1}(B))' \end{aligned}$$

⭕

⭕ 下面的证明貌似正确

$$\begin{aligned} \forall x, x \in (f^{-1}(B))' & \Rightarrow x \notin f^{-1}(B)\\ & \Rightarrow f(x) \notin B \\ & \Rightarrow f(x) \in B' \\ & \Rightarrow x \in f^{-1}(B') \\ & \therefore (f^{-1}(B))' \subseteq f^{-1} (B') \end{aligned}$$

问题在于第二步， $x \notin f^{-1}(B) \nRightarrow f(x) \notin B$，例如$f:A \to B,f(x)=x^2,A=\{x:0 \leq x \leq 1 \}, B=\{y:0 \leq y \leq 1 \}$，若$x = -1$，显然$x \notin A$，但是$f(x)=1 \in B$

⭕ 注意： $x \notin X \nRightarrow f(x) \notin f(X)$。例如 $f:\mathbb{R} \to \mathbb{R} ,f(x)=0, X=\{x:0 \leq x \leq 1\}，f(X)=\{0\}，\text{ 有 }2 \notin X, \text{ 但 } f(2)=0 \in f(X)$

现在证明第6部分：

$$\begin{aligned} x \in f^{-1} (\bigcup_{\lambda \in \Lambda} B_\lambda) & \Rightarrow f(x) \in \bigcup_{\lambda \in \Lambda} B_\lambda \\ & \Rightarrow \exist \lambda \in \Lambda, f(x) \in B_\lambda \\ & \Rightarrow x \in \bigcup_{\lambda \in \Lambda} f^{-1}(B_\lambda) \\ & \therefore f^{-1} (\bigcup_{\lambda \in \Lambda} B_\lambda) \subseteq \bigcup_{\lambda \in \Lambda} f^{-1}(B_\lambda) \end{aligned}$$

又：

$$\begin{aligned} x \in \bigcup_{\lambda \in \Lambda} f^{-1}(B_\lambda) & \Rightarrow \exist \lambda \in \Lambda, x \in f^{-1}B_\lambda \\ & \Rightarrow f(x) \in B_\lambda \\ & \Rightarrow f(x) \in \bigcup_{\lambda \in \Lambda}B_\lambda \\ & \Rightarrow x \in f^{-1}\bigcup_{\lambda \in \Lambda}B_\lambda \\ & \therefore \bigcup_{\lambda \in \Lambda} f^{-1}(B_\lambda) \subseteq f^{-1} (\bigcup_{\lambda \in \Lambda} B_\lambda) \end{aligned}$$

故，$\bigcup_{\lambda \in \Lambda} f^{-1}(B_\lambda) = f^{-1} (\bigcup_{\lambda \in \Lambda} B_\lambda)$ 得证 $\qquad \Box$

1. 证明定理 1.5。

Harry:

先证明第1部分。

$$\begin{aligned} \forall x, x \in A & \Rightarrow f(x) \in f(A) \\ & \Rightarrow x \in f^{-1} \circ f(A) \\ & \therefore A \subseteq f^{-1} \circ f(A) \end{aligned}$$

⭕

再证明第2部分。

$$\begin{aligned} \forall y, y \in f \circ f^{-1}(B) & \Rightarrow f^{-1}(y) \in f^{-1}(B) \\ & \Rightarrow y \in B \\ & \therefore f \circ f^{-1}(B) \subseteq B \end{aligned}$$

⭕

---

Harry: 从目前看，本书中的$\subset$ 就是$\subseteq$。

---

1.1.3 有限集、可数集和不可数集

两个集合被称为等价，如果存在一个双射 $f: X \to Y$。因此，两个集合 $X$ 和 $Y$ 等价的概念意味着它们除了元素的名称之外是相同的。也就是说，我们可以将 $Y$ 视为通过使用元素 $x$ 在 $X$ 中的名称更名为 $Y$ 中某个唯一元素 $y$ 而得到的。如果这两个集合是有限的，那么它们等价当且仅当它们包含相同数量的元素。实际上，有限集合 $X$ 的概念等同于说 $X$ 等价于 $N$ 的某个整数 $n \in \mathbb{N}$ 的子集 $\mathbb{N}_n \subset \mathbb{N}$。为了使这一概念及相关概念更加明确，我们列举以下涉及集合 $X$ 和集合 $N$ 的定义。

定义 1.6 一个集合 $X$ 被称为：

• 有限的(finite)，当且仅当 $X = \varnothing$ 或$\exist n \in \mathbb{N}$ 使得 $X$ 等价于 $\mathbb{N}_n$；
• 无限的(infinite)，如果它不是有限的；
• 可列的(denumerable)，当且仅当它等价于 $\mathbb{N}$；
• 可数的(countable)，当且仅当它是有限的或可列的；
• 不可数的(uncountable)，如果它不是可列的。

一些可数集的性质在下面的例子中给出。

例子 1.3

1. $X \subset \mathbb{N} \Rightarrow X$ 是可数的。
2. $X$ 是可数的 $\Leftrightarrow$ $\exist Y \subset \mathbb{N}$，使得 $X$ 与 $Y$ 是等价的。
3. 如果 $X$ 与 $Y$ 是等价的，且 $Y$ 是可数的，那么 $X$ 也是可数的。
4. 如果 $X \subset Y$ 且 $Y$ 是可数的，那么 $X$ 是可数的。
5. 如果 $f: X \to Y$ 是满射，且 $X$ 是可数的，那么 $Y$ 是可数的。
6. 如果 $f: X \to Y$ 是单射，且 $Y$ 是可数的，那么 $X$ 是可数的。
7. 如果 $\Lambda$ 是可数的，且 $\{X_\lambda: \lambda \in \Lambda\}$ 是一组可数集合，那么 $\bigcup_{\lambda \in \Lambda} X_\lambda$ 是可数的。换句话说，可数个可数集的并集是可数的。

假定例 1.3 是事实，我们可以很容易地证明集合 $\mathbb{Z}^2$ 和有理数集 $\mathbb{Q}$ 都是可数集。首先注意到函数 $f: \mathbb{N} \to \mathbb{Z}$，定义为 $f(2n) = n$ 和 $f(2n-1) = -n+1$，是一个双射。因此$\mathbb{Z}$ 等价于 $\mathbb{N}$，因而是可数的。对于每个 $i \in \mathbb{Z}$，集合 $X_i = \{f(i,n) : n \in \mathbb{Z}\}$ 是可数的。然后，由于 $\mathbb{Z}$ 是可数的，且 $\{X_i : i \in \mathbb{Z}\}$ 是一组可数集合，根据例 1.3(7)，我们得知 $\mathbb{Z}^2 = \bigcup_{i \in \mathbb{Z}} X_i$ 也是可数的。

要证明 $\mathbb{Q}$ 是可数的，我们定义一个映射 $f: \mathbb{Z}^2 \to \mathbb{Q}$如下：

$$\begin{equation} f(i, j) = \begin{cases} \frac{i}{j} & \text{如果} j \neq 0 \\ 0 & \text{如果} j = 0 \end{cases} \tag{1.2} \end{equation}$$

$f$ 显然是满射。现在根据例子1.3(5)，我们得到 $\mathbb{Q}$ 是可数的。

我们给每个集合 $X$ 都附上一个标签 $card(X)$，称为 $X$ 的势(cardinality)，它提供了 $X$ 大小的度量。特别是，这个标签应以某种方式区分两个给定集合中哪一个有更多的成员。

Harry:

• 势是一种相对的概念，它表示两个集合之间是否可以建立一一对应的关系。如果两个集合可以建立一一对应，那么它们就是等势的，记为$A \sim B$。如果一个集合的势不小于另一个集合的势，那么就存在一个单射（一对一的映射）从一个集合到另一个集合，记为$A \preceq B$。如果一个集合的势严格大于另一个集合的势，那么就不存在一个双射（一一对应的映射）从一个集合到另一个集合，记为$A \prec B$。势的英文是cardinality或power。

• 基数是一种绝对的概念，它表示一个集合的势所对应的一个具体的数或符号。基数可以用来比较不同集合的大小，而不需要考虑它们之间是否可以建立一一对应。基数通常用符号$\aleph$或$\beth$来表示，后面跟着一个下标，表示不同的无限基数。例如，$\aleph_0$表示可数无限集的基数，$\aleph_1$表示第一个不可数无限集的基数，$\beth_0$表示自然数集的基数，$\beth_1$表示实数集的基数。基数的英文是cardinal number。

我们说两个集合 $X$ 和 $Y$ 具有相同的势，当且仅当它们是等价的。对于有限集而言，通过当$X$ 等价于 $\mathbb{N}_n$ 时分配 $card(X) = n$，并且约定当且仅当 $X = \varnothing$ 时 $card(X) = 0$ ，满足了这一要求。因此，如果 $X$ 和 $Y$ 是有限集，那么当且仅当 $X$ 的元素比 $Y$ 少时，$card(X) < card(Y)$。特别地，如果 $X$ 是 $Y$ 的真子集，那么 $card(X) < card(Y)$。然而，对于无限可数集，这不再成立，因为我们有严格的子集序列 $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q}$，而 $card(\mathbb{N}) = card(\mathbb{Z}) = card(\mathbb{Q})$。尽管这三个集合包含不同的元素，它们在某种意义上的大小都是相同的，因为对于 $\mathbb{Q}$ 的每个元素都存在唯一的整数 $n \in \mathbb{N}$，这意味着每个有理数都可以用唯一的整数标记。这表明整数和有理数一样多。因此，它们在大小上都是相同的。

Harry:

⭕ 如何构建$\mathbb{Q} \to \mathbb{Z}$的双射？ 我们可以考虑以下一个可能的构建方式：

假设我们有一个有理数 $r = \frac{a}{b}$，其中 $a$ 和 $b$ 是整数，且 $b$ 不等于零，那么我们可以将有理数 $r$ 映射到整数：

$$f(r) = 2^a \times 3^b$$

这个映射是一个从有理数到整数的双射。为了证明它是一个双射，我们需要证明两个方向：

1. 单射（Injective）：如果 $f(r_1) = f(r_2)$，则 $r_1 = r_2$。

这是因为如果两个有理数 $r_1$ 和 $r_2$ 对应的 $a$ 和 $b$ 相等，那么它们的唯一表示 $2^a \times 3^b$ 也必然相等。

2. 满射（Surjective）：对于任意整数 $n$，存在有理数 $r$ 使得 $f(r) = n$。

这是因为任何整数都可以分解为 $2^a \times 3^b$ 的形式，其中 $a$ 和 $b$ 可以是负数。 这个映射实际上是 Cantor 提出的一种将有理数映射到自然数（整数的一部分）的方式，展示了有理数和整数之间存在一一对应的关系。这种对应的存在说明了有理数的基数是可数无穷的。

⭕ 负数的情况呢？

$C_1$. $\qquad card(X) \leq card(Y) \Leftrightarrow \aleph(X) \leq \aleph(Y)$。

$C_2$. $\qquad card(X) = card(Y) \Leftrightarrow \aleph(X) = \aleph(Y)$。

Georg Cantor证明了不存在从自然数 $N$ 到实数 $R$ 的双射 $f : \mathbb{N} \to \mathbb{R}$ [37, 38]。由于 $\mathbb{N} \subset \mathbb{R}$ 是一个严格的子集，结合Cantor的结果，我们必须有 $card(\mathbb{N}) < card(\mathbb{R})$。 $\mathbb{N}$ 的基数通常用符号 $\alef(N) = {\alef}_0$ 表示，而 $\mathbb{R}$ 的基用 ${\alef}(R) = \zeta$ 表示，其中 $\zeta$ 被称为连续体(continuum)的基数。我们注意到，任何满足 $\alef(X) \leq {\alef}_0$ 的集合 $X$ 都是可数的，而任何满足 $\alef(X) > {\alef}_0$ 的集合 $X$ 都是不可数的。

读者需要记住，基数是集合，即使在有限的情况下也是如此，但它与基于性质 $C_1$ 和 $C_2$ 的 card 的概念密切相关。因此，我们可以将唯一的整数与有限集关联起来，但需要用超限数来标记无限集。例如，定义符号 $\overline{0} = \varnothing$，$\overline{1} = \{\varnothing\}$，$\overline{2} = \{\varnothing, \{\varnothing\}\}$，$\overline{3} = \{\varnothing, \{\varnothing\}, \{\varnothing, \{\varnothing\}\}\}$，依此类推，那么 $\alef(\mathbb{N}_n) = \overline{n}$ 是一个集合，而 $card(\mathbb{N}_n) = n$。由此还可得到 $\alef(\alef(\mathbb{N}_n)) = \alef(\overline{n}) = \overline{n}$。

Harry:

“基数就是集合”这个说法，可以从 Cantor 的观点出发，他认为集合的大小主要由其中元素的数量来刻画，而基数就是用来度量这个数量的。因此，每个集合都有一个唯一对应的基数。

需要注意的是，基数本身也是一个集合。在 Cantor 的集合论中，基数通常被定义为等势集合中的一个代表。例如，$\overline{0}$ 代表空集，$\overline{1}$代表包含一个元素的集合，$\overline{2}$ 代表包含两个元素的集合，以此类推。这种方式使得我们可以通过集合的基数来描述集合的大小。

Cantor的工作的另一个结果是对于任何集合 $X$，都有 $card(X) < card(2^X)$。如果 $\alef(X) = {\alef}_0$，则 $2^X$ 的基数用 $\alef(2^X) = {\alef}_1$ 表示。因此，${\alef}_0 < {\alef}_1$ 且 ${\alef}_0 < \zeta$。关于 ${\alef}_1 = \zeta$ 是否成立的问题被称为连续体假设。Kurt Godel证明了基于Zermelo-Fraenckel公理，无论是否包括选择公理，都不可能反驳连续体假设，而Paul J. Cohen证明了基于Zermelo-Fraenckel公理，无论是否包括选择公理，都不可能证明连续体假设 [97, 56]。对于我们的目的，我们将任何满足 ${\alef}_(X) \geq {\alef}_0$ 的集合 $X$ 简单地标识为无穷大符号 $\infty$。这简化了测量集合大小的问题。

定义 1.7 如果 $U$ 表示论域的全集，那么计数函数(counting function) $| \cdot | : 2^U \to \mathbb{N}[0, 1]$ 被定义为：

$$|A| = \begin{cases} \text{$card$}(A) & \text{如果 } A \text{ 是有限的} \\ \infty & \text{如果 } \alef(A) \geq \aleph_0 \end{cases}$$

因此，对于任意 $A \in 2^U$，都有 $0 \leq |A| \leq 1$，且 $|A| = 0$ 当且仅当 $A = \varnothing$。对于所有无限集，它们都映射到相同的符号 1，代表无穷大。

如果一个集合 X 是可列(denumerable)的，那么存在一个双射 $f : \mathbb{N} \to X$。这样的双射为计数 $X$ 中元素提供了一个方便的工具，这是通过将 $X$ 的每个元素与由 $f$ 确定的唯一数值标签相对应来进行标识的。具体而言，对于 $x \in X$，我们设 $x = x_i$，其中 $f(i) = x$。由于 $f$ 是一对一的，有$x_i = x_j \Leftrightarrow i = j$。由于 $f$ 也是满射，集合 $X$ 现在可以表示为序列 $X = \{x_1, x_2, x_3, \ldots\}$。

例 1.4 设 $g : \mathbb{N}^2 \to \mathbb{N}$ 定义为

$$g(i, j) = \frac{1}{2} \left( (i+j-1)(i+j-2) + j \right) \quad \forall (i, j) \in \mathbb{N}^2$$

根据 $g$ 的定义，我们有 $g(1,1) = 1, g(2,1) = 2, g(1,2) = 3, g(3,1) = 4$ 等。当 $j = 1$ 或 $i = 1$ 时，函数分别取得简单的形式 $g(i,1) = 2i(i-1) + 1$ 和 $g(1,j) = 2j(j-1) + j$。这些观察也使得很容易证明 $g$ 是一一对应（即单射）的，并且是满射的。因此，$g$ 有一个逆 $g^{-1} : \mathbb{N} \to \mathbb{N}^2$。这意味着我们有两种等效的方式来标记 $\mathbb{N}^2$ 中的点 $\mathbf{x} = (i, j)$。具体而言，我们定义 $\mathbf{x}_\mathcal{l} = \mathbf{x} \in \mathbb{N}^2 \Leftrightarrow g^{-1}(\mathcal{l}) = \mathbf{x}$，或等价地，$\mathbf{x}_\mathcal{l} = \mathbf{x} \Leftrightarrow g(\mathbf{x}) = \mathcal{l}$。图 1.1 说明了 $\mathbb{N}^2$ 元素的这种特定标记方式。

图 1.1 $\mathbb{N}^2$ 元素的序列标记。$\mathbb{N}^2$ 中元素的排序如箭头所示，沿着负斜率为 -1 的对角线经过$\mathbb{N}^2$ 中的点。这里$k = g(i, 1)$，$k + (i-1) = g(1, j)$，其中$i = j$，且$\mathcal{l} = g(i, j)$。

练习 1.1.3

1. 形如 $x^2 + bx + c = 0$ 的方程的解，其中 $b,c \in \mathbb{Z}$，被称为二次整数。证明二次整数的集合是可数的。 您好，这是Bing。我可以帮您证明二次整数的集合是可数的。😊

Harry:

为了证明二次整数的集合是可数的，我们需要构造一个从自然数集$\mathbb{N}$到二次整数的集合的双射，也就是说，我们需要找到一个一一对应的函数，使得每个自然数都对应一个唯一的二次整数，反之亦然。这样，我们就可以用自然数来编号二次整数，从而说明二次整数的集合和自然数集有相同的势，也就是可数无限。

为了构造这样的双射，我们可以利用二次整数的定义，即形如 $x^2 + bx + c = 0$ 的方程的解，其中 $b,c \in \mathbb{Z}$。我们可以将二次整数看作是由三个整数$(x,b,c)$组成的有序三元组，其中$x$是方程的一个解，$b$和$c$是方程的系数。例如，$(2,3,-4)$是一个二次整数，因为它对应了方程$x^2 + 3x - 4 = 0$的一个解$x = 2$。

我们可以将二次整数的集合表示为$\{(x,b,c) \mid x^2 + bx + c = 0, x,b,c \in \mathbb{Z}\}$，这是一个由整数构成的三维空间中的一个曲面。我们可以将这个曲面划分为无限多个水平的层，每个层对应一个固定的$x$值，例如$x = 0, x = 1, x = -1, x = 2, x = -2$等。每个层上的点都是形如$(x,b,c)$的二次整数，其中$b$和$c$可以取任意的整数值，只要满足$x^2 + bx + c = 0$。

我们可以用以下的方法来编号每个层上的点：

• 首先，我们从原点$(x,0,0)$开始，这是每个层上的唯一的点，我们将它编号为$0$。
• 然后，我们沿着$b$轴的正方向移动一个单位，得到点$(x,1,-x^2)$，我们将它编号为$1$。
• 接着，我们沿着$b$轴的负方向移动两个单位，得到点$(x,-1,-x^2)$，我们将它编号为$-1$。
• 依此类推，我们沿着$b$轴的正负方向交替移动，每次增加一个单位，得到点$(x,b,-x^2 - bx)$，我们将它编号为$b$。

我们可以用以下的公式来表示这个编号的规律：

$$(x,b,-x^2 - bx) \mapsto b$$

这样，我们就可以用一个整数$b$来表示每个层上的一个点$(x,b,-x^2 - bx)$，并且这个对应是一一的，也就是说，不同的$b$值对应不同的点，反之亦然。

我们可以用类似的方法来编号每个层之间的点：

• 首先，我们从$x = 0$的层开始，这是最低的层，我们将它编号为$0$。
• 然后，我们沿着$x$轴的正方向移动一个单位，得到$x = 1$的层，我们将它编号为$1$。
• 接着，我们沿着$x$轴的负方向移动两个单位，得到$x = -1$的层，我们将它编号为$-1$。
• 依此类推，我们沿着$x$轴的正负方向交替移动，每次增加一个单位，得到$x = n$的层，我们将它编号为$n$。

我们可以用以下的公式来表示这个编号的规律：

$$(x,b,c) \mapsto (n,b)$$

其中$n$是$x$的编号，$b$是$(x,b,c)$在$x = n$的层上的编号。这样，我们就可以用一个有序整数对$(n,b)$来表示一个二次整数$(x,b,c)$，并且这个对应是一一的，也就是说，不同的$(n,b)$对应不同的二次整数，反之亦然。

最后，我们可以用以下的方法来将一个有序整数对$(n,b)$转换为一个自然数，从而完成从二次整数到自然数的双射：

• 首先，我们将$n$和$b$分别转换为二进制数，例如，$n = 5$转换为$101$，$b = -3$转换为$-11$。
• 然后，我们将$n$和$b$的二进制数交错排列，得到一个新的二进制数，例如，$(101,-11)$交错排列为$1-011-1$。
• 接着，我们在新的二进制数的最前面加上一个符号位，表示正负，例如，$1-011-1$加上符号位为$01-011-1$。
• 最后，我们将新的二进制数转换为十进制数，例如，$01-011-1$转换为$23$。

我们可以用以下的公式来表示这个转换的规律：

$$(n,b) \mapsto \text{sign}(n,b) \cdot 2^{|n| + |b|} + \sum_{i = 0}^{|n| + |b| - 1} \text{bit}(n,b,i) >\cdot 2^i$$

其中$\text{sign}(n,b)$是$(n,b)$的符号位，如果$n$和$b$同号，就为$0$，如果异号，就为$1$；$|n|$和$|b|$分别是$n$和$b$的二进制位数；$\text{bit}(n,b,i)$是$(n,b)$的第$i$个二进制位，从右往左数，如果是$n$的位，就取$n$的绝对值的第$i$个二进制位，如果是$b$的位，就取$b$的绝对值的第$i$个二进制位。

这样，我们就可以用一个自然数来表示一个有序整数对$(n,b)$，从而表示一个二次整数$(x,b,c)$，并且这个对应是一一的，也就是说，不同的自然数对应不同的二次整数，反之亦然。

综上所述，我们已经构造了一个从自然数集$\mathbb{N}$到二次整数的集合的双射，这就证明了二次整数的集合是可数的。$\qquad \Box$

2. 假设例 1.3 为事实，证明区间 $(0,1) = \{x \in \mathbb{R} : 0 < x < 1\}$ 是不可数的。

Harry

使用反证法：

• 假设区间 $(0,1)$ 是可数的，那么它的所有元素可以排成一个无穷序列，记为 $x_1, x_2, x_3, \dots, x_n, \dots$，其中每个 $x_i$ 都是一个介于 $0$ 和 $1$ 之间的实数。
• 把每个 $x_i$ 表示为一个十进制的无限小数，即 $x_i = 0.a_{i1}a_{i2}a_{i3}\dots a_{in} \dots$，其中每个 $a_{ij}$ 都是一个 $0$ 到 $9$ 之间的整数。为了避免有限小数的两种表示法，例如 $0.5$ 和 $0.499\dots$，我们规定不允许小数部分以无限多个 $9$ 结尾，即如果 $x_i$ 是有限小数，那么它的最后一位不能是 $9$。

$\because \qquad$由于我们规定不允许小数部分以无限多个 $9$ 结尾，那么我们就可以推出如果 $x_i$ 是有限小数，那么它的最后一位不能是 $9$。这是因为如果 $x_i$ 的最后一位是 $9$，那么我们就可以将它变成一个以无限多个 $9$ 结尾的小数，方法是将最后一位 $9$ 去掉，并在后面补上无限多个 $9$。例如，$0.29$ 可以变成 $0.28999\dots$，$0.009$ 可以变成 $0.008999\dots$，$0.9$ 可以变成 $0.8999\dots$。这样就违反了我们的规定，所以我们必须排除这种情况，即如果 $x_i$ 是有限小数，那么它的最后一位不能是 $9$。

• 构造一个新的实数 $y = 0.b_1b_2b_3\dots b_n \dots$，其中每个 $b_i$ 都是一个 $0$ 到 $9$ 之间的整数，且满足 $b_i \neq a_{ii}$，即每个 $b_i$ 都不等于对应的 $x_i$ 的小数部分的第 $i$ 位。为了保证 $y$ 不以无限多个 $9$ 结尾，我们可以进一步规定 $b_i \neq 9$。
• 由于 $y$ 是一个介于 $0$ 和 $1$ 之间的实数，那么它应该属于区间 $(0,1)$，但是由于 $y$ 和序列中的每个 $x_i$ 都至少有一位小数不同，那么它又不可能属于序列中的任何一个元素。这就产生了矛盾，说明我们的假设是错误的，即区间 $(0,1)$ 不是可数的。$\qquad \Box$