基数¶
Question
如何比较两个集合的大小？有穷集能数出元素个数，那无穷集呢？——关键看两集合的映射关系
等势¶
等势: 若存在从集合 \(A\) 到集合 \(B\) 的双射，则称 \(A\) 和 \(B\) 等势，记作 \(A \sim B\)
有穷集合: 集合是有穷的，当且仅当它与某个自然数等势 (可以证明: 任意有穷集合唯一地与一个自然数等势)
抽屉原理: 任何有限集都不能与它的真子集等势
基数¶
有穷集合的基数: 对于任意有穷集合 \(A\)，存在唯一的自然数 \(n\)，使得 \(A \sim n\)，称 \(n\) 为 \(A\) 的基数，记为 \(\#A\)
无穷集的基数用特殊的记号，例如: \(\# (N) = \aleph_0\) (阿列夫零)
基数比较:
- 若 \(A \sim B\)，则记 \(\# (A) = \# (B)\)
- 若存在从 \(A\) 到 \(B\) 的单射，则记 \(\# (A) \leqslant \#(B)\)
双射就是 "\(=\)" ，单射就是 "\(\leqslant\)"
定理 \(\#(B) \leqslant \#(A) \iff\) 存在从 \(A\) 到 \(B\) 的满射
可数与无穷¶
可数无穷集合: 任何与自然数等势的集合称为可数无穷集合
可数集合: 有穷 / 可数无穷
不可数集合: 无穷且不可数
无穷集的等价条件:
- \(A\) 为无穷集
- \(A\) 有可数无穷子集
- \(A\) 有与它等势的真子集
证明:
(1) \(\rightarrow\) (2): 因为 \(A\) 无穷，所以可以不断地从其中取元素，我们给这些元素赋以 \(0,1,2,...,i,...\) 这样的下标，就能和 \(N\) 等势
(2) \(\rightarrow\) (3): 我们把取出的第一个元素 \(a_0\) 从 \(A\) 中去掉，得真子集 \(A'\)，可以通过错位构造出 \(A\) 到 \(A'\) 的双射
(3) \(\rightarrow\) (1): 抽屉原理反证
构造双射¶
构造从 \(A = (0,1)\) 到 \(B = [0,1]\) 的双射:
\((0,1) = \{a_0, a_1, a_2, \cdots ,a_i, \cdots\} \cup ((0,1)-C)\)
\([0,1] = \{0, 1, a_0, \cdots,a_{i-2},\cdots\}\cup ((0,1)-C)\)
幂集的基数¶
定理 对每个集合 \(A\)，皆有 \(\#(A) < \# \mathcal{P}(A)\)
证明:
\(\leqslant\) : 对任意 \(a \in A\)，令 \(f(a) = \{a\}\)，构造出了 \(A \rightarrow \mathcal{P}(A)\) 的单射
\(\neq\) :
\(B\) 的元素映射后得到的集合不包含自身
我们记 \(\# \mathcal{P}(N) = \aleph\)
R不可列——Cantor的对角线法¶
思路: \((0,1)\) 无法与 \(N\) 构成双射
设 \(f:N \rightarrow R\) 是双射，\(f(i) = s_i\)，我们把所有“映射对”排好:
再找一个新的实数 \(x^{*} = 0.x_{11}^*x_{22}^*x_{33}^*x_{44}^*\cdots\)
\(x_{11}^*\) 表示 \(0\)~\(9\) 内与 \(x_{11}\) 不等的任意数
这样的话，\(x^*\) 是实数，但是它排不进我们构造的映射里，则无法构成双射
R的基数¶
\(\#(R) = \aleph\)
证明:
\([0,1] \sim (0,1) \sim R\)，现证 \([0,1]\sim \mathcal{P}(N)\)
\(f(\{0,1,2,...\}) = \frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \cdots\)，极限为 \(1\)
\([0,1]\) 之间的任意的数都有二进制表示，所以 \(f\) 是满射
\(g(\{0,1,2,...\}) = \frac{1}{3} + \frac{1}{3^2} + \frac{1}{3^3} + \cdots\)，极限为 \(\frac{1}{2}\)，不是满射
连续统假设¶
连续统假设 (Continuum Hypothesis, CH) 由康托尔提出，关于无穷集的大小，有
不存在一个基数绝对大于可数集而绝对小于实数集的集合
Reference
2024/12/04