跳转至

slide 16: 势 Cardinality（无限集）

伽利略悖论 Galileo's Paradox

伽利略悖论的大意是，所有的自然数，要么是完全平方数，要么不是完全平方数。因此，所有的自然数的数量，应该比所有的完全平方数的数量，要多。

但是，每个自然数都会有一个与之对应的平方数。从这个角度来看，完全平方数个数并不比所有的自然数个数要少。

所以，无限集之间，是不能比较所含元素个数的多少的。

无限集的定义

对于一个集合 $S$，若它的一个真子集 $T$ 与之有双射关系，则集合 $S$ 是无限集。

无限集的势

两个集合，无论是无限集还是有限集，只要它们之间是双射的，势就相等。

例如：$\mathbb{N}$ 与下列集合都是等势的：

  • $\{\text{大于零的整数}\}$，因为 $(\lambda x \in \mathbb{N} \cdot x+1)$ 双射
  • $\{\text{大于 } k \text{ 的整数}\}$，因为 $(\lambda x \in \mathbb{N} \cdot x+k+1)$ 双射
  • $\{\text{偶数}\}$，因为 $(\lambda x \in \mathbb{N} \cdot 2x)$ 双射
  • $\{\text{奇数}\}$，因为 $(\lambda x \in \mathbb{N} \cdot 2x+1)$ 双射
  • $\{k \text{ 的正整数倍}\}$，因为 $(\lambda x \in \mathbb{N} \cdot kx)$ 双射

可数集 countable set

如果一个集合 $S$ 与 $\mathbb{N}$ 等势，那么 $S$ 是一个可数集。通常，$\# \mathbb{N}$ 记作 $\aleph_0$，读作 aleph-null。

在集合 $\mathbb{N}$ 当中删除元素（删一个、删 k 个、每隔两个删一个，等等删法），不会改变 $\mathbb{N}$ 的势。

整数的势

对于集合 $\mathbb{N}$ 的超集（superset）$\mathbb{Z} = \{\dots, -3, -2, -1, 0, 1, 2, 3, \dots\}$（所有整数）。

$\mathbb{Z}$ 的势也是 $\aleph_0$，即 $\# \mathbb{Z} = \# \mathbb{N}$。因为从 $\mathbb{Z}$ 到 $\mathbb{N}$ 的函数 $f$ 是双射的。证明： $$f(x)= \begin{cases}-2x, & \text { if } x \leq 0 \ 2x-1, & \text { if } x>0\end{cases}$$ 其实就是把负数映射到了正偶数，正数映射到了更大的正奇数。也就是：$\{\ldots,(-3,6),(-2,4),(-1,2),(0,0),(1,1),(2,3),(3,5), \ldots\}$

上面的证明方法，是证明了，$\mathbb{Z}$ 到 $\mathbb{N}$ 的双射关系。其实也可以反过来。比如集合 $S \triangleq\{n \in \mathbb{Z} \mid(n<-7) \vee(n>9) \bullet n\}$，要证明 $S$ 是可数的，不方便从 $S$ 到 $\mathbb{N}$ 建立双射，但是可以比较轻松的从 $\mathbb{N}$ 到 $S$ 搞一个双射出来，如： $$f(x) = \begin{cases} -\frac{x}{2}-8 & \text{if } x \text{ is even} \ \frac{x + 1}{2} + 9 & \text{if } x \text { is odd} \end{cases}$$ 这样就搞出来了一个 $\{(0,8), (1,10), (2,-9), (3,11), (4,-10), \dots\}$ 的双射

更大的无限集？

考虑集合 $\mathbb{N} \times \mathbb{N}$。 $$ \begin{array}{ccccc} (0,0) & (1,0) & (2,0) & (3,0) & \cdots \\ (0,1) & (1,1) & (2,1) & (3,1) & \cdots \\ (0,2) & (1,2) & (2,2) & (3,2) & \cdots \\ (0,3) & (1,3) & (2,3) & (3,3) & \cdots \\ \vdots & \vdots & \vdots & \vdots \end{array} $$

这个集合，铺成正方形，每一行每一列都是无限个…但是如果从左上角开始，斜着计数，就可以列出这种形式：$\{(0,0),(1,0),(0,1),(0,2),(1,1),(2,0),(3,0),(2,1),(1,2),(0,3), \ldots\}$…看起来依然是可以数出来的吼

那么如何计算这个集合 $\mathbb{N} \times \mathbb{N}$ 的势？

不妨定义函数 $f((i,j)) = 2^i \times 3^j$。由于 $2$ 和 $3$ 都是质数，由唯一分解定理得知，$f$ 是双射的，即每个 $(i,j)$ 都能通过 $f$ 映射到某个整数，而那个整数也只能分解成 $2^i\times 3^j$ 的形式。于是，$\mathbb{N} \times \mathbb{N}$ 就与 $\mathbb{N}$ 建立了双射关系。故，$\mathbb{N} \times \mathbb{N}$ 的势还是 $\aleph_0$，这个集合是可数集。

扩展一步，如果是 $\mathbb{N} \times \mathbb{N} \times \mathbb{N}$，甚至是更多维数，依然是可数的。二维的，用前两个质数，三维的就用前三个，$k$ 维的就用前 $k$ 个质数，就好了。比如，$(3,4,2,0,2,1)$ 就可以映射到 $2^3 \times 3^4 \times 5^2 \times 7^0 \times 11^2 \times 13^1$。

再拓展一下，对于有理数集 $\mathbb{Q}$，也是可数集。因为有理数 $\frac{p}{q}$ 可以与 $(p,q)$ 双射，这就回到了刚才的二维问题。

希尔伯特旅馆悖论 Hilbert’s Hotel

参考 Wikipedia，参考知乎，房间永远够用…

  • $k$ 个新客人：之前在第 $i$ 个房间的客人移动到 $i+k$ 号房间，腾出来了 $k$ 个房间
  • 无限个新客人：之前在第 $i$ 个房间的客人移动到 $2i$ 号房间，腾出来了无限个房间
  • 一辆公交车，车上有无限个新客人：之前在第 $i$ 个房间的客人移动到 $2i$ 号房间，腾出来了无限个房间
  • $k$ 辆公交车，每辆车都有无限个新客人：之前在第 $i$ 个房间的客人移动到 $2^i$ 号房间，第 $1$ 辆车上的第 $j$ 个乘客进入 $3^j$ 号房间，第 $2$ 辆车呃第 $j$ 个乘客进入 $5^j$ 号房间，以此类推，第 $k$ 辆车上的乘客，分配到第 $k+1$ 个质数的幂的房间，腾出来了无限个房间
  • 无限多辆公交车，每辆车都有无限个新客人：类似上面的办法，用无限个质数，腾出来了无限个房间