一、等势关系

1. 等势的定义

• 等势的定义：对于集合 $A, B$，如果存在 $A \to B$ 上的双射，则称 $A, B$ 等势，记为 $A \approx B$。

2. 等势的例子

1. 如果集合元素数目可数，显然元素数目相同的集合是等势的。下面研究的都是无穷集。

2. $\N$ 与 $\{ 1, 2, 4, 8, 16, \cdots \}$ 等势，因为存在双射 $f(n)=2^n$。

   • 后者感觉比前者疏松很多，但仍然等势。

3. $\N$ 与 $\Z$ 等势，这个双射如下：

   

4. $\N$ 与 $\N \times \N$ 等势，这个双射如下：

   

5. $\N$ 与 ${\mathbb Q}$ 等势，这个双射是可以构造的（需要避免重复元素）：

   

6. 区间 $(0, 1)$ 与 $\R$ 等势。比如构造 $(0, 1) \to\R$ 上的 $f(x) = \tan ((x-\frac 12)\pi)$。

   

7. 区间 $(0, 1)$ 与 $[0, 1]$ 等势。

   • 先介绍希尔伯特大酒店：在一个房间数量有限的旅店中，如果所有房间都被占用，那么新来的客人就没有房间了；但是对于一个有着无穷多个房间的旅店来说，这就不成问题——如果所有房间都住满了，那么当新来了一位客人时，只需要把每位客人的房间向下挪一个，把第一个房间空出来留给新来的客人就好了。

     

   • 因而，我们构造这样的 $(0, 1) \to [0, 1]$，先把 1/2 映射为 0、1/3 映射为 1，再把 1/4 映射为 1/2，1/5 映射为 1/3 ……以此来补偿，这还是一个双射：

     $$ f(x) = \begin{cases}

     0, & x = \frac 12 \\

     1, & x = \frac 13 \\

     \frac {1}{n-2}, & x = \frac 1n, \, n \in \N - \{0, 1, 2, 3 \} \\

     x, & {\rm otherwise}

     \end{cases} $$

     • 图示如下，不过下图阐述的是他的逆映射。

       

3. 等势的性质

• 等势关系满足如下性质：

  • 自反性：$A \approx A$（恒等关系 $I_A$ 就是一个 $A \to A$ 上的双射）
  • 对称性：$A \approx B \Rightarrow B \approx A$（双射的反函数必定存在，且是一个双射）
  • 传递性：$A \approx B \wedge B \approx C \Rightarrow A \approx C$（双射的复合存在，且是一个双射）

  因而等势关系是一种等价关系。

• 等价关系就构成等价类，每种等价类代表的就是具有不同基数的集合。

4. 康托定理

• 康托定理一：$\N$ 与 $\R$ 不等势。

  一个直观的证明：反证法。

  假设 $\N \approx \R \approx [0, 1]$，则存在双射 $f:[0, 1] \to \N$，这说明可以将所有的 $[0, 1 ]$ 数值排成一个表 $[0, 1] = \{ x^{(1)}, x^{(2)}, x^{(3)}, \cdots, x^{(m)}, \cdots \}$，再将他们每个进行数位展开，形如：

  $$ \begin{align*}

  x^{(1)} &= 0.a_1^{(1)} a_2^{(1)} a_3^{(1)} \cdots a_n^{(1)} \cdots \\

  x^{(2)} &= 0.a_1^{(2)} a_2^{(2)} a_3^{(2)} \cdots a_n^{(2)} \cdots \\

  x^{(3)} &= 0.a_1^{(3)} a_2^{(3)} a_3^{(3)} \cdots a_n^{(3)} \cdots \\

  & \ \ \vdots \\

  x^{(m)} &= 0.a_1^{(m)} a_2^{(m)} a_3^{(m)} \cdots a_n^{(m)} \cdots \\

  & \ \ \vdots \\

  \end{align*} $$

  但现在完全可以构造这样一个数 $y = b_1 b_2 b_3 \cdots b_n \cdots \in [0, 1]$，使得

  • $b_1$ 不等于 $a_1^{(1)}$；$b_2$ 不等于 $a_2^{(2)}$；$b_3$ 不等于 $a_3^{(3)}$……

  这样，$y$ 不等于列表 $\{ x^{(1)}, x^{(2)}, x^{(3)}, \cdots, x^{(m)}, \cdots \}$ 中的每一个数（因为每一个数而言，它们都至少有一位不一样），也就 $y \notin [0, 1]$；

  这里还有一个小问题，就是从任何一位数开始都可以有 $0.999\cdots = 1$，如 $0.78999\cdots = 0.79$；这里在构造时需要加个附加条件，就是出现这种模式需要强行修改进位。

• 康托定理二：任意集合 $A$ 与 ${\mathscr P}(A)$ 不等势。

  证明：有限集合由于数目上的差异（$|{\mathscr P}(A)| = 2^{|A|}$）肯定不可能，下面证明无限集合也不会出现，通过反证法。

  

  

  • 假设存在双射 $f:A \to {\mathscr P}(A)$，即 $A$ 的所有元素一一映射为 $A$ 的所有子集。
  • 定义「好元素」和「坏元素」：
    • 对于任何 $x \in A$，如果 $x \in f(x)$，即元素自身在其映射到的子集内，那么称 $x$ 是「好元素」；
    • 否则 $x \notin f(x)$，元素自身不在其映射到的子集内，称为「坏元素」。
      • 虽然这里不需要讨论坏元素存不存在，但显然是存在的，因为 $\emptyset \in {\mathscr P}(A)$，那么存在原像即 $\exist e \in A, \, f(e) = \empty$，而显然 $e \notin \empty$。
  • 构造所有坏元素构成的集合 $B = \{ x \in A \, | \, x \notin f(x)\}$，有 $B \in {\mathscr P}(A)$。那么存在原像即 $\exist b \in A, \, f(b) = B$。
    • 如果 $b$ 是好元素即 $b \in B$，根据坏元素集合 $B$ 定义有 $b \notin f(b)=B$，矛盾；
    • 如果 $b$ 是坏元素即 $b \notin B$，根据坏元素集合 $B$ 定义有 $b \in B$，也矛盾。

• 康托伯恩斯坦定理：$\R$ 与 ${\mathscr P} (\N)$ 等势；$\R$ 与 $2^{\N}$（$\N$ 到 $2$ 上的全体函数）等势。

  证明

  • 核心要义：将实数 $r \in [0, 1]$ 表示为一个二进制小数串 $r=0.b_1b_2b_3\cdots$（同理将某位后无穷的一算成进位）。
  • 思路一：
    • 定义 $S_r = \{ n\in \N \, | \, r 的第 n+1 位二进制数 b_n(r)=1 \}$，比如 0.101 对应 $S_{0.101} = \{ 0, 2 \}$，显然 $S_r \subseteq \N$ 即 $S_r \in {\mathscr P}(\N)$。
    • 可以证明所有 $r$ 与所有 $S_r$ 存在一一对应，因而 $\R$ 与 ${\mathscr P} (\N)$ 等势。
  • 思路二：
    • $\R \approx (0, 1)$，$2 \approx \{ 0, 1 \}$（按照自然数定义，其实 $2 = \{ 0, 1 \}$，笑死）。
    • 能够构造一个单射 $H: (0, 1) \to \{ 0, 1 \}^\N$。留意设 $r \in (0, 1)$ 的话 $H(r)$ 是一个 $\N$ 到 $\{ 0, 1 \}$ 的函数，记为 $H(r, n)$，$H(r, n)$ 定义为 $r$ 的二进制表示中第 $n+1$ 位小数。
    • 能够构造一个单射 $G: \{ 0, 1 \}^\N \to [0, 1]$，其中 $G(f) = 0. f(0)f(1) f(2)\cdots$。

二、有穷性、基数、可数性