无穷集合 | Dale 的花园 ^

type

status

date

slug

summary

一一对应

比较有限集合的大小很简单, 数一数就行. 但无穷集合怎么数？康托尔的想法是：

两个集合“一样大”（等势）, 当且仅当它们的元素之间能建立一一对应

这意味着：

集合 A 的每个元素都对应集合 B 的唯一元素

集合 B 的每个元素都恰好对应集合 A 的一个元素

无穷集合的神奇性质：整体和部分可以一样大

自然数集 N = {0, 1, 2, 3, 4, … }

偶数集 E = {0, 2, 4, 6, 8, … }

平方数集 Q = {0, 1, 4, 9, 16, … }

整数集 Z = {…, -3, -2, -1, 0, 1, 2, 3… }

从康托尔的”一一对应”角度看, 我们可以说上面四个集合都是一样大的

自然数集与偶数集一样大, 因为其可以建立一一对应的双射：

自然数集与平方数集一样大, 因为有

自然数集与整数集一样大, 因为能找到双射：

这表明：无穷集合可以与自己的子集一样大

可数集与不可数集

如果一个无穷集合能与自然数集建立一一对应, 那么称此类集合为可数无穷集

显然, 整数集、平方数集、偶数集都是可数无穷集, 下面我们证明有理数集 Q 也是可数无穷集:

有理数可以写成 p/q 的形式, 其中 p 和 q 为整数, 且 q ≠ 0. 为了方便安排顺序, 我们先只考虑分子分母都是正整数的分数. 尝试给所有正有理数排一个队: 按照分子和分母的和从小到大来分组. 比如, 分子分母和为 2 的只有 1/1；和为 3 的有 1/2 和 2/1；和为 4 的有 1/3、2/2、3/1；和为 5 的有 1/4、2/3、3/2、4/1 … 依此类推. 在每一组内部, 我们按分子从小到大排列. 这样, 我们就得到了一个长长的列表：1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, … 这个列表包含了所有形如 p/q 的正分数, 但其中有些是重复的, 比如 1/1 和 2/2 实际上是同一个有理数. 为了避免重复, 我们在读这个列表的时候, 跳过那些已经出现过的分数. 具体来说, 只保留分子和分母互质（即不能再约分）的分数. 这样, 每一个正的有理数都会在某个时刻出现, 且只出现一次. 前面是按“分子加分母”的和逐步推进的, 任何一个最简分数 a/b 都会在第 a+b 步或之前被考虑到, 因此它一定会出现在这个去重后的序列中的某个有限位置上. 这就说明, 所有的正有理数可以排成一列, 每个都在有限步内出现. 所以说, 正有理数集合是可以被编号的. 接下来, 我们把零和负的有理数也加进来. 零只有一个, 直接放在最前面. 而每一个负的有理数, 都对应一个正的有理数（比如 -3/5 对应 3/5）, 所以负有理数也可以按照正有理数的顺序一一列出. 我们可以这样排队：0, 1/1, -1/1, 1/2, -1/2, 2/1, -2/1, 1/3, -1/3, 3/1, -3/1, 2/3, -2/3, 3/2, -3/2, 1/4, -1/4, 4/1, -4/1 … 显然, 任意一个有理数都会在队伍中占据一个确定的、有限的位置. 因此, 整个有理数集合 Q 可以被自然数编号：第 1 个、第 2 个、第 3 个… 每个元素都能被数到.

证明某个无穷集合是可数集, 其实不需要写出它与自然数集的双射公式, 只需要证明存在一种排队秩序, 能将集合内所有元素排成一个序列, 每一个元素都恰好出现在某一个被安排的位置上. 简单地说：一个无穷集合里的元素只要能找到排队规律, 就是可数的. 可数性的本质就是能被自然数编号.

有些无穷集无法与自然数集建立一一对应, 这些称为不可数集, 康托尔用对角线法证明了(0, 1)间的实数集无法与自然数集一一对应.

此外, 所有自然数的子集的集合也是一个不可数集.

康托尔证明了并非所有无穷集合都一样大, 实际上, 可数集是最小的无穷, 康托尔定义其基数为 (阿列夫零), 而实数集、复数集、的基数都是