slide 16: 势 Cardinality（无限集）

伽利略悖论 Galileo's Paradox

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

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

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

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

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

例如：与下列集合都是等势的：

如果一个集合与等势，那么是一个可数集。通常，记作，读作 aleph-null。

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

对于集合的超集（superset）（所有整数）。

的势也是，即。因为从到的函数是双射的。证明：

其实就是把负数映射到了正偶数，正数映射到了更大的正奇数。也就是：

上面的证明方法，是证明了，到的双射关系。其实也可以反过来。比如集合，要证明是可数的，不方便从到建立双射，但是可以比较轻松的从到搞一个双射出来，如：

这样就搞出来了一个的双射

考虑集合。

这个集合，铺成正方形，每一行每一列都是无限个…但是如果从左上角开始，斜着计数，就可以列出这种形式：…看起来依然是可以数出来的吼

那么如何计算这个集合的势？

不妨定义函数。由于和都是质数，由唯一分解定理得知，是双射的，即每个都能通过映射到某个整数，而那个整数也只能分解成的形式。于是，就与建立了双射关系。故，的势还是，这个集合是可数集。

扩展一步，如果是，甚至是更多维数，依然是可数的。二维的，用前两个质数，三维的就用前三个，维的就用前个质数，就好了。比如，就可以映射到。

再拓展一下，对于有理数集，也是可数集。因为有理数可以与双射，这就回到了刚才的二维问题。

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