定义 1.1 集合是由确定的、互不相同的对象组成的整体。这些对象称为集合的元素。

我们用大写字母 $A, B, C, \ldots$ 表示集合，用小写字母 $a, b, c, \ldots$ 表示元素。

记号：

1. $a \in A$ 表示 $a$ 是集合 $A$ 的元素
2. $a \notin A$ 表示 $a$ 不是集合 $A$ 的元素

定义 1.2 不包含任何元素的集合称为空集，记作 $\emptyset$ 或 $\varnothing$。

列举法: 直接列出集合的所有元素。 $$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\}$$（有理数集）

设 $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.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$。

设 $\{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 设 $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$：

1. 若 $f(X) = Y$，称 $f$ 为满射（surjective）
2. 若 $f(x_1) = f(x_2)$ 蕴含 $x_1 = x_2$，称 $f$ 为单射（injective）
3. 若 $f$ 既是单射又是满射，称 $f$ 为双射或一一对应（bijective）

设 $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 原像运算保持集合运算：

1. $f^{-1}(A \cup B) = f^{-1}(A) \cup f^{-1}(B)$
2. $f^{-1}(A \cap B) = f^{-1}(A) \cap f^{-1}(B)$
3. $f^{-1}(A^c) = (f^{-1}(A))^c$

注意: 像运算只满足包含关系：

1. $f(A \cup B) = f(A) \cup f(B)$
2. $f(A \cap B) \subset f(A) \cap f(B)$（等号一般不成立）

定义 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.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|$。

性质: 对等关系满足

1. 自反性: $A \sim A$
2. 对称性: $A \sim B \Rightarrow B \sim A$
3. 传递性: $A \sim B, B \sim C \Rightarrow A \sim C$

定义 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.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.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.10 与 $(0,1)$ 对等的集合称为具有连续统的基数，记作 $\mathfrak{c}$ 或 $2^{\aleph_0}$。

定理 1.8 以下集合具有连续统的基数：

1. 任意区间 $(a,b)$, $[a,b]$, $(a,b]$, $[a,b)$
2. 实数集 $\mathbb{R}$
3. 无理数集
4. 超越数集
5. $\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.11 设 $A, B$ 为集合：

1. 若存在 $B$ 的子集与 $A$ 对等，称 $|A| \leq |B|$
2. 若 $|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.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$。