====== 第一章 集合与基数 ====== ===== 1.1 集合的基本概念 ===== ==== 1.1.1 集合的定义 ==== **定义 1.1** 集合是由确定的、互不相同的对象组成的整体。这些对象称为集合的元素。 我们用大写字母 $A, B, C, \ldots$ 表示集合，用小写字母 $a, b, c, \ldots$ 表示元素。 记号： - $a \in A$ 表示 $a$ 是集合 $A$ 的元素 - $a \notin A$ 表示 $a$ 不是集合 $A$ 的元素 **定义 1.2** 不包含任何元素的集合称为**空集**，记作 $\emptyset$ 或 $\varnothing$。 ==== 1.1.2 集合的表示方法 ==== **列举法**: 直接列出集合的所有元素。 $$A = \{1, 2, 3, 4, 5\}$$ **描述法**: 用元素的性质来描述集合。 $$A = \{x \mid x \text{ 满足性质 } P\}$$ 例如： $$\mathbb{N} = \{n \mid n = 1, 2, 3, \ldots\}$$（自然数集） $$\mathbb{Z} = \{n \mid n = 0, \pm 1, \pm 2, \ldots\}$$（整数集） $$\mathbb{Q} = \left\{\frac{p}{q} \mid p, q \in \mathbb{Z}, q \neq 0\right\}$$（有理数集） ===== 1.2 集合的运算 ===== ==== 1.2.1 基本运算 ==== 设 $A, B$ 为两个集合，定义以下运算： **并集**: $$A \cup B = \{x \mid x \in A \text{ 或 } x \in B\}$$ **交集**: $$A \cap B = \{x \mid x \in A \text{ 且 } x \in B\}$$ 若 $A \cap B = \emptyset$，则称 $A$ 与 $B$ **不相交**。 **差集**: $$A \setminus B = \{x \mid x \in A \text{ 且 } x \notin B\}$$ **补集**: 设 $X$ 为全集，$A \subset X$，则 $$A^c = X \setminus A = \{x \in X \mid x \notin A\}$$ ==== 1.2.2 运算律 ==== **定理 1.1** 集合运算满足以下基本定律： **交换律**: $$A \cup B = B \cup A, \quad A \cap B = B \cap A$$ **结合律**: $$(A \cup B) \cup C = A \cup (B \cup C)$$ $$(A \cap B) \cap C = A \cap (B \cap C)$$ **分配律**: $$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$$ $$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$$ **De Morgan律**: $$(A \cup B)^c = A^c \cap B^c$$ $$(A \cap B)^c = A^c \cup B^c$$ **证明** 以第一个De Morgan律为例： 设 $x \in (A \cup B)^c$，则 $x \notin A \cup B$，即 $x \notin A$ 且 $x \notin B$。 因此 $x \in A^c$ 且 $x \in B^c$，即 $x \in A^c \cap B^c$。 反之，设 $x \in A^c \cap B^c$，则 $x \in A^c$ 且 $x \in B^c$。 即 $x \notin A$ 且 $x \notin B$，故 $x \notin A \cup B$，即 $x \in (A \cup B)^c$。 ==== 1.2.3 任意并与任意交 ==== 设 $\{A_\alpha\}_{\alpha \in I}$ 是一族集合，其中 $I$ 为指标集。 **任意并**: $$\bigcup_{\alpha \in I} A_\alpha = \{x \mid \exists \alpha \in I, x \in A_\alpha\}$$ **任意交**: $$\bigcap_{\alpha \in I} A_\alpha = \{x \mid \forall \alpha \in I, x \in A_\alpha\}$$ **推广的De Morgan律**: $$\left(\bigcup_{\alpha \in I} A_\alpha\right)^c = \bigcap_{\alpha \in I} A_\alpha^c$$ $$\left(\bigcap_{\alpha \in I} A_\alpha\right)^c = \bigcup_{\alpha \in I} A_\alpha^c$$ ===== 1.3 映射与函数 ===== ==== 1.3.1 映射的定义 ==== **定义 1.3** 设 $X, Y$ 是两个非空集合。若存在对应关系 $f$，使得对每个 $x \in X$，都有唯一的 $y \in Y$ 与之对应，则称 $f$ 为从 $X$ 到 $Y$ 的**映射**，记作 $f: X \to Y$。 称 $y = f(x)$ 为 $x$ 在 $f$ 下的像，$x$ 为 $y$ 的原像。 **定义 1.4** 设 $f: X \to Y$： - 若 $f(X) = Y$，称 $f$ 为**满射**（surjective） - 若 $f(x_1) = f(x_2)$ 蕴含 $x_1 = x_2$，称 $f$ 为**单射**（injective） - 若 $f$ 既是单射又是满射，称 $f$ 为**双射**或**一一对应**（bijective） ==== 1.3.2 像与原像 ==== 设 $f: X \to Y$，$A \subset X$，$B \subset Y$： **像集**: $$f(A) = \{f(x) \mid x \in A\}$$ **原像集**: $$f^{-1}(B) = \{x \in X \mid f(x) \in B\}$$ **定理 1.2** 原像运算保持集合运算： - $f^{-1}(A \cup B) = f^{-1}(A) \cup f^{-1}(B)$ - $f^{-1}(A \cap B) = f^{-1}(A) \cap f^{-1}(B)$ - $f^{-1}(A^c) = (f^{-1}(A))^c$ **注意**: 像运算只满足包含关系： - $f(A \cup B) = f(A) \cup f(B)$ - $f(A \cap B) \subset f(A) \cap f(B)$（等号一般不成立） ==== 1.3.3 复合映射与逆映射 ==== **定义 1.5** 设 $f: X \to Y$，$g: Y \to Z$，定义**复合映射** $g \circ f: X \to Z$ 为 $$(g \circ f)(x) = g(f(x))$$ **定理 1.3** 映射的复合满足结合律： $$(h \circ g) \circ f = h \circ (g \circ f)$$ **定义 1.6** 设 $f: X \to Y$ 为双射，定义**逆映射** $f^{-1}: Y \to X$： 对每个 $y \in Y$，存在唯一的 $x \in X$ 使 $f(x) = y$，令 $f^{-1}(y) = x$。 ===== 1.4 可数集 ===== ==== 1.4.1 集合的对等与基数 ==== **定义 1.7** 若存在从集合 $A$ 到集合 $B$ 的双射，则称 $A$ 与 $B$ **对等**（equivalent），记作 $A \sim B$。 **定义 1.8** 若 $A \sim B$，称 $A$ 与 $B$ 具有相同的**基数**（cardinality），记作 $\overline{\overline{A}} = \overline{\overline{B}}$ 或 $|A| = |B|$。 **性质**: 对等关系满足 - 自反性: $A \sim A$ - 对称性: $A \sim B \Rightarrow B \sim A$ - 传递性: $A \sim B, B \sim C \Rightarrow A \sim C$ ==== 1.4.2 可数集的定义与性质 ==== **定义 1.9** 与自然数集 $\mathbb{N}$ 对等的集合称为**可数集**（countable set）或**可列集**。 **等价表述**: 集合 $A$ 可数当且仅当 $A$ 的元素可以排列成一个序列： $$A = \{a_1, a_2, a_3, \ldots\}$$ **定理 1.4** 可数集的无限子集仍可数。 **证明** 设 $A$ 可数，$B \subset A$ 无限。设 $A = \{a_1, a_2, a_3, \ldots\}$。 按原序列的顺序选取 $B$ 中的元素，得到 $B = \{a_{n_1}, a_{n_2}, a_{n_3}, \ldots\}$。 这给出了 $B$ 与自然数集的一一对应。 $\square$ **定理 1.5** 有限个可数集的并集可数。 **证明** 设 $A_1, A_2, \ldots, A_n$ 可数。设 $A_k = \{a_{k1}, a_{k2}, a_{k3}, \ldots\}$。 对角线排列法： $$\begin{array}{cccc} a_{11} & a_{12} & a_{13} & \cdots \\ a_{21} & a_{22} & a_{23} & \cdots \\ a_{31} & a_{32} & a_{33} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{array}$$ 按箭头方向遍历：$a_{11}, a_{21}, a_{12}, a_{31}, a_{22}, a_{13}, \ldots$ 这给出了 $\bigcup_{k=1}^n A_k$ 的一个枚举。 $\square$ **定理 1.6** 可数个可数集的并集可数。 **证明** 设 $\{A_n\}_{n=1}^\infty$，每个 $A_n$ 可数。使用上述对角线法，按 $i+j$ 递增的顺序排列 $(i,j)$，跳过已出现的元素。 $\square$ ==== 1.4.3 可数集的例子 ==== **例 1.1** 整数集 $\mathbb{Z}$ 可数。 排列方式：$0, 1, -1, 2, -2, 3, -3, \ldots$ **例 1.2** 有理数集 $\mathbb{Q}$ 可数。 **证明** 首先，$\mathbb{Q}^+ = \{p/q \mid p, q \in \mathbb{N}, (p,q) = 1\}$ 可数。 对每个正整数 $n$，令 $A_n = \{p/q \mid p+q = n, (p,q)=1\}$。 每个 $A_n$ 有限，故 $\mathbb{Q}^+ = \bigcup_{n=2}^\infty A_n$ 可数。 同理 $\mathbb{Q}^-$ 可数，加上 $\{0\}$，得 $\mathbb{Q}$ 可数。 $\square$ **例 1.3** 平面上的有理点集 $\mathbb{Q} \times \mathbb{Q}$ 可数。 **证明** 由于 $\mathbb{Q}$ 可数，设 $\mathbb{Q} = \{r_1, r_2, r_3, \ldots\}$。 则 $\mathbb{Q} \times \mathbb{Q} = \{(r_i, r_j) \mid i, j \in \mathbb{N}\}$。 按 $i+j$ 递增排列即可。 $\square$ **例 1.4** 整系数多项式全体可数。 **证明** 对每个次数 $n$，$n$ 次整系数多项式与 $\mathbb{Z}^{n+1}$ 对等。 由于 $\mathbb{Z}$ 可数，由归纳法 $\mathbb{Z}^n$ 可数。 故所有整系数多项式可数。 $\square$ **推论** 代数数（整系数多项式的根）全体可数。 ===== 1.5 不可数集 ===== ==== 1.5.1 区间 $(0,1)$ 不可数 ==== **定理 1.7** (Cantor) 区间 $(0,1)$ 是不可数集。 **证明** (对角线法) 假设 $(0,1)$ 可数，则可将其元素排列为： $$\begin{aligned} x_1 &= 0.a_{11}a_{12}a_{13}\cdots \\ x_2 &= 0.a_{21}a_{22}a_{23}\cdots \\ x_3 &= 0.a_{31}a_{32}a_{33}\cdots \\ &\vdots \end{aligned}$$ 构造 $x = 0.b_1b_2b_3\cdots$，其中 $$b_n = \begin{cases} 5, & a_{nn} \neq 5 \\ 6, & a_{nn} = 5 \end{cases}$$ 则 $x \in (0,1)$，但对所有 $n$，$x \neq x_n$（因第 $n$ 位小数不同）。 矛盾！故 $(0,1)$ 不可数。 $\square$ ==== 1.5.2 连续统的基数 ==== **定义 1.10** 与 $(0,1)$ 对等的集合称为具有**连续统的基数**，记作 $\mathfrak{c}$ 或 $2^{\aleph_0}$。 **定理 1.8** 以下集合具有连续统的基数： - 任意区间 $(a,b)$, $[a,b]$, $(a,b]$, $[a,b)$ - 实数集 $\mathbb{R}$ - 无理数集 - 超越数集 - $\mathbb{R}^n$ ($n \geq 1$) **证明** (1) $f(x) = a + (b-a)x$ 是 $(0,1)$ 到 $(a,b)$ 的双射。 (2) $f(x) = \tan(\pi(x-\frac{1}{2}))$ 是 $(0,1)$ 到 $\mathbb{R}$ 的双射。 (3) 无理数集 $= \mathbb{R} \setminus \mathbb{Q}$。由于 $\mathbb{Q}$ 可数，若无理数可数，则 $\mathbb{R}$ 可数，矛盾。 (4) 超越数是不可数代数数的补集。 (5) 对 $\mathbb{R}^n$，可用空间填充曲线或逐位交错法。 $\square$ ==== 1.5.3 基数比较 ==== **定义 1.11** 设 $A, B$ 为集合： - 若存在 $B$ 的子集与 $A$ 对等，称 $|A| \leq |B|$ - 若 $|A| \leq |B|$ 且 $|A| \neq |B|$，称 $|A| < |B|$ **定理 1.9** (Cantor-Bernstein-Schröder) 若 $|A| \leq |B|$ 且 $|B| \leq |A|$，则 $|A| = |B|$。 **定理 1.10** (Cantor) 对任意集合 $A$，有 $|A| < |\mathcal{P}(A)| = |2^A|$。 **证明** 显然 $|A| \leq |\mathcal{P}(A)|$（单射 $x \mapsto \{x\}$）。 假设存在双射 $f: A \to \mathcal{P}(A)$。令 $$B = \{x \in A \mid x \notin f(x)\}$$ 若 $B = f(a)$ 对某 $a \in A$，则 $$a \in B \Leftrightarrow a \notin f(a) = B$$ 矛盾！故不存在这样的双射。 $\square$ ===== 1.6 例题与习题 ===== ==== 例题 ==== **例 1.5** 证明：若 $A$ 是无限集，则存在 $A$ 的可数子集。 **证明** 由无限集定义，对任意有限集 $F$，$A \setminus F \neq \emptyset$。 归纳选取 $a_1 \in A$，$a_2 \in A \setminus \{a_1\}$，$a_3 \in A \setminus \{a_1, a_2\}$，...... 得到可数子集 $\{a_1, a_2, a_3, \ldots\}$。 $\square$ **例 1.6** 设 $\mathcal{A}$ 是 $\mathbb{R}$ 上互不相交的开区间族，证明 $\mathcal{A}$ 至多可数。 **证明** 每个开区间包含有理数。由不相交性，不同区间包含有理数不同。 选取每个区间中的有理数，得到到 $\mathbb{Q}$ 的单射，故 $|\mathcal{A}| \leq |\mathbb{Q}| = \aleph_0$。 $\square$ **例 1.7** 设 $E$ 为 $(0,1)$ 中十进制表示不含数字 7 的实数全体，证明 $E$ 具有连续统的基数。 **证明** 首先 $E \subset (0,1)$，故 $|E| \leq \mathfrak{c}$。 构造单射：对任意 $x \in (0,1)$，设其二进制表示为 $x = 0.a_1a_2a_3\cdots$。 定义 $f(x) = 0.b_1b_2b_3\cdots$（十进制），其中 $$b_n = \begin{cases} 1, & a_n = 0 \\ 2, & a_n = 1 \end{cases}$$ 则 $f(x) \in E$，且 $f$ 是单射。故 $|E| \geq \mathfrak{c}$。 由 Cantor-Bernstein 定理，$|E| = \mathfrak{c}$。 $\square$ ==== 习题 ===== **习题 1.1** 证明：$(A \setminus B) \cup B = A$ 当且仅当 $B \subset A$。 **习题 1.2** 设 $f: X \to Y$，$A_1, A_2 \subset X$，证明： $$f(A_1 \cap A_2) \subset f(A_1) \cap f(A_2)$$ 并举例说明等号一般不成立。 **习题 1.3** 证明：可数个有限集的并集至多可数。 **习题 1.4** 证明：代数数集可数。 **习题 1.5** 证明：$\mathbb{R}$ 上所有开集组成的集族具有连续统的基数。 **习题 1.6** 设 $A$ 为无限集，$B$ 为至多可数集，证明：$A \cup B \sim A$。 **习题 1.7** (Cantor集预备) 设 $C$ 为 $[0,1]$ 中三进制表示不含数字 1 的点全体： $$C = \left\{x = \sum_{n=1}^\infty \frac{a_n}{3^n} \mid a_n \in \{0, 2\}\right\}$$ 证明 $C$ 具有连续统的基数。 **习题 1.8** 证明：存在从 $[0,1]$ 到 $[0,1] \times [0,1]$ 的满射，但不能是单射。 **习题 1.9** 设 $\mathcal{F}$ 为 $\mathbb{N}$ 的有限子集全体，证明 $\mathcal{F}$ 可数。 **习题 1.10** 设 $A$ 是不可数集，$B$ 是 $A$ 的可数子集，证明：$A \setminus B \sim A$。