基数¶

Question

如何比较两个集合的大小？有穷集能数出元素个数，那无穷集呢？——关键看两集合的映射关系

等势¶

等势: 若存在从集合 $A$ 到集合 $B$ 的双射，则称 $A$ 和 $B$ 等势，记作 $A \sim B$

有穷集合: 集合是有穷的，当且仅当它与某个自然数等势 (可以证明: 任意有穷集合唯一地与一个自然数等势)

抽屉原理: 任何有限集都不能与它的真子集等势

基数¶

有穷集合的基数: 对于任意有穷集合 $A$ ，存在唯一的自然数 $n$ ，使得 $A \sim n$ ，称 $n$ 为 $A$ 的基数，记为 $# A$

无穷集的基数用特殊的记号，例如: $# (N) = ℵ_{0}$ (阿列夫零)

基数比较:

若 $A \sim B$ ，则记 $# (A) = # (B)$
若存在从 $A$ 到 $B$ 的单射，则记 $# (A) ⩽ # (B)$

双射就是 " $=$ " ，单射就是 " $⩽$ "

定理 $# (B) ⩽ # (A) ⟺$ 存在从 $A$ 到 $B$ 的满射

可数与无穷¶

可数无穷集合: 任何与自然数等势的集合称为可数无穷集合

可数集合: 有穷 / 可数无穷

不可数集合: 无穷且不可数

无穷集的等价条件:

$A$ 为无穷集
$A$ 有可数无穷子集
$A$ 有与它等势的真子集

证明:

(1) $\to$ (2): 因为 $A$ 无穷，所以可以不断地从其中取元素，我们给这些元素赋以 $0, 1, 2, . . ., i, . . .$ 这样的下标，就能和 $N$ 等势

(2) $\to$ (3): 我们把取出的第一个元素 $a_{0}$ 从 $A$ 中去掉，得真子集 $A^{'}$ ，可以通过错位构造出 $A$ 到 $A^{'}$ 的双射

(3) $\to$ (1): 抽屉原理反证

构造双射¶

构造从 $A = (0, 1)$ 到 $B = [0, 1]$ 的双射:

$(0, 1) = {a_{0}, a_{1}, a_{2}, \dots, a_{i}, \dots} \cup ((0, 1) - C)$

$[0, 1] = {0, 1, a_{0}, \dots, a_{i - 2}, \dots} \cup ((0, 1) - C)$

幂集的基数¶

定理 对每个集合 $A$ ，皆有 $# (A) < # P (A)$

证明:

$⩽$ : 对任意 $a \in A$ ，令 $f (a) = {a}$ ，构造出了 $A \to P (A)$ 的单射

$\neq$ :

$B$ 的元素映射后得到的集合不包含自身

我们记 $# P (N) = ℵ$

R不可列——Cantor的对角线法¶

思路: $(0, 1)$ 无法与 $N$ 构成双射

设 $f : N \to R$ 是双射， $f (i) = s_{i}$ ，我们把所有“映射对”排好:

s_{1} = 0. x_{11} x_{12} x_{13} x_{14} \dots

s_{2} = 0. x_{21} x_{22} x_{23} x_{24} \dots

s_{3} = 0. x_{31} x_{32} x_{33} x_{34} \dots

s_{4} = 0. x_{41} x_{42} x_{43} x_{44} \dots

\dots

再找一个新的实数 $x^{*} = 0. x_{11}^{*} x_{22}^{*} x_{33}^{*} x_{44}^{*} \dots$

$x_{11}^{*}$ 表示 $0$ ~ $9$ 内与 $x_{11}$ 不等的任意数

这样的话， $x^{*}$ 是实数，但是它排不进我们构造的映射里，则无法构成双射

R的基数¶

$# (R) = ℵ$

证明:

$[0, 1] \sim (0, 1) \sim R$ ，现证 $[0, 1] \sim P (N)$

$f ({0, 1, 2, . . .}) = \frac{1}{2} + \frac{1}{2^{2}} + \frac{1}{2^{3}} + \dots$ ，极限为 $1$

$[0, 1]$ 之间的任意的数都有二进制表示，所以 $f$ 是满射

$g ({0, 1, 2, . . .}) = \frac{1}{3} + \frac{1}{3^{2}} + \frac{1}{3^{3}} + \dots$ ，极限为 $\frac{1}{2}$ ，不是满射

连续统假设¶

连续统假设 (Continuum Hypothesis, CH) 由康托尔提出，关于无穷集的大小，有

不存在一个基数绝对大于可数集而绝对小于实数集的集合

Reference

维基百科｜连续统假设

2024/12/04