基数定义#

• 两个集合有相同的基数：如果它们之间存在双射
• 集合 $A$ 的基数小于等于集合 $B$ 的基数：如果存在 $A$ 到 $B$ 的某子集的单射
• 集合 $A$ 的基数小于集合 $B$ 的基数：如果存在 $A$ 到 $B$ 的某子集的单射，但不存在 $A$ 到 $B$ 的双射

有限集与无限集#

定义 1.5.1 集合 $A$ 是有限集，如果：

• $A = \emptyset$，或
• 存在自然数 $n$，使得 $\{1, \cdots, n\}$ 与 $A$ 有相同基数

性质：有限集不可能与其真子集有相同基数

重要结论：无限集可能与其真子集有相同基数（这是有限集与无限集的本质区别）

定义#

定义 1.5.2：

• 可数集：与 $\mathbb{N}$ 有相同基数的集合
• 至多可数集：有限集和可数集的统称

命题 1.5.1#

(1) 任何无限集必有一个可数子集（即任何无限集的基数 $\geq$ $\mathbb{N}$ 的基数）

(2) 至多可数集的子集是至多可数集

证明：

(1) 设 $A$ 是无限集，构造双射 $\varphi: \mathbb{N} \to A$ 的某个子集：

• 选择 $x_1 \in A$，令 $\varphi(1) = x_1$
• 假设已定义 $\varphi(1), \cdots, \varphi(n)$ 且互不相同
• 由于 $A$ 无限，$A \setminus \{\varphi(1), \cdots, \varphi(n)\} \neq \emptyset$
• 选择 $x_{n+1} \in A \setminus \{\varphi(1), \cdots, \varphi(n)\}$，令 $\varphi(n+1) = x_{n+1}$

由数学归纳法，$\varphi$ 是 $\mathbb{N}$ 到 $A$ 的某个子集的双射。

(2) 只需证明 $\mathbb{N}$ 的任何子集 $A$ 至多可数：

• 若 $A$ 有限，结论成立
• 若 $A$ 无限，定义映射 $\varphi: \mathbb{N} \to A$：
  • $\varphi(1) = \min A$
  • $\varphi(n+1) = \min(A \setminus \{\varphi(1), \cdots, \varphi(n)\})$

$\varphi$ 是严格递增的，且：

• $\forall n \in \mathbb{N}(n \leq \varphi(n))$
• $\varphi$ 是单射
• $\varphi$ 是满射（否则存在 $p \in A \setminus \varphi(\mathbb{N})$，则 $\forall n \in \mathbb{N}(n \leq \varphi(n) < p)$，取 $n = p$ 得矛盾）

命题 1.5.2#

可数个可数集之并是可数集

证明：

情况1：可数集 $A_n (n=1,2,3,\cdots)$ 两两不相交

将元素排列为：

按对角线法排序：$a_{11}; a_{12}, a_{21}; a_{13}, a_{22}, a_{31}; a_{14}, a_{23}, a_{32}, a_{41}; \cdots$

排序原则：双下标之和小的排在前，和相等时按第一下标大小排

这样就建立了 $\bigcup_{n=1}^{\infty} A_n$ 与 $\mathbb{N}$ 的双射。

情况2：可数集 $A_n$ 非两两不相交

构造两两不相交的集合 $B_n$：

$\bigcup_{n=1}^{\infty} B_n$ 可数，且与 $\bigcup_{n=1}^{\infty} A_n$ 的某个子集有双射，故 $\bigcup_{n=1}^{\infty} A_n$ 可数。

推论 1.5.1#

有限个可数集之并是可数集

证明：有限个可数集之并是可数个可数集之并的子集。

推论 1.5.2#

可数集与有限集之并是可数集

证明：可数集与有限集之并是两个可数集之并的子集。

推论 1.5.3#

设 $A$ 可数，$B$ 无限，$\varphi: A \to B$ 是满射，则 $B$ 可数

证明：

• $\forall y \in B, \varphi^{-1}(\{y\}) \neq \emptyset$
• 选择 $\psi(y) \in \varphi^{-1}(\{y\})$
• $B$ 与 $\psi(B)$ 有相同基数
• $\psi(B)$ 是 $A$ 的无限子集，故可数

推论 1.5.4#

正有理数全体是可数集

证明：

• $\{(m,n): m,n \in \mathbb{N}\}$ 可数
• 映射 $\phi((m,n)) = n/m$ 是满射
• 正有理数无限，由推论 1.5.3 可数

推论 1.5.5#

有理数全体是可数集

证明：正有理数、负有理数和 $\{0\}$ 的并集。

命题 1.5.3#

开区间 $(0,1)$ 是不可数的无限集

证明（Cantor对角线法）：

• 假设 $(0,1)$ 可数，可排成序列 $x_1, x_2, \cdots, x_n, \cdots$
• 每个 $x_n$ 有十进制表示 $x_n = 0.a_1^n a_2^n \cdots a_m^n \cdots$
• 构造 $y = 0.b_1 b_2 \cdots b_m \cdots$，其中 $$b_m = \begin{cases} 1, & \text{当 } a_m^m \neq 1 \text{ 时} \\ 2, & \text{当 } a_m^m = 1 \text{ 时} \end{cases}$$
• $\forall m \in \mathbb{N}(y \neq x_m)$，矛盾