不可数集是既不是有限集,也不是可数无限集的集合:它的全部元素无法用一个以自然数为索引的序列列出。等价地说,不存在从该集合到 的单射函数。实数集是典型的例子。不可数性描述的是集合的大小,即基数,而不是它在几何上占据的范围、稠密程度,或其元素是否容易描述。
定义及与可数性的比较
如果一个集合是有限集,或者它与 之间存在双射函数,就称它为可数集。有些作者只用“可数”指可数无限集,而用“至多可数”涵盖有限集和可数无限集;无论采用哪种约定,“不可数”的含义都相同。
对于非空集合 ,不可数性也可以表述为:不存在一个序列
包含 的每个元素。这一表述允许元素重复出现:即使允许重复,也无法列尽不可数集的全部元素。
在包含选择公理的通常集合论框架下,不可数集的基数严格大于
即可数无限集的基数。因此,不可数性区分的是不同大小的无穷,而不只是无限集与有限集。
为什么实数集不可数
最广为人知的证明使用康托尔对角线论证。用反证法,假设区间 中的所有实数都能列成一个序列:
将每个数写成十进制小数,并统一选取不会从某一位起全为 的展开形式:
定义一个新数
其中,当 时令 ,否则令 。数 属于 ,但对于每个 ,它的小数点后第 位都与 的相应位不同。由于它的各位数字只有 和 ,有限小数与末尾无限循环 的展开形式之间的歧义不会造成问题。
因此, 不在那个假定已列尽所有实数的序列中。这样的序列并不存在,所以 不可数,进而 也不可数。
这一论证不仅说明某一种具体的列举方式行不通,还给出了一种方法,可以针对任何提出的列举方式构造出一个遗漏的元素。
主要例子
具有连续统基数的集合
实数集的基数记为 ,称为连续统基数。一些看似不同的集合都具有相同的大小:
- 任何包含两个不同点的实数区间。
- 全体无理数组成的集合。
- 全体复数组成的集合。
- 任何有限维欧几里得空间 ,其中 为正整数。
- 康托尔集。
- 全体无限二进制序列组成的集合 。
- 幂集 ,即自然数集的所有子集组成的集合。
最后两个例子之间存在自然的双射:用一个二进制序列表示 的一个子集,其中第 项记录 是否属于该子集。它们与实数集之间的关系给出
虽然某些实数有两种二进制展开形式,但在证明上述基数相等时,可以妥善处理这种歧义。
相比之下,有理数集是可数的。每个实数区间中都有有理数,并不意味着有理数集不可数。
第一个不可数序数
序数 是所有可数序数组成的集合。它是最小的不可数序数,其基数记为 ,即最小的不可数基数。
的存在提供了一个基本例子,说明不可数性也可以源自序结构,而不一定源自实数轴。
比连续统更大的集合
康托尔定理指出,每个集合的基数都严格小于其幂集的基数:
因此,
反复取幂集可以得到不断增大的无限基数。因此,不可数集并非只有一种大小,也不存在最大的基数。
基本性质与证明方法
利用几条标准原理,可以证明集合不可数,而不必每次都构造对角线论证。
包含关系。 任何包含不可数子集的集合都是不可数集。更一般地,如果存在从一个已知不可数集到另一个集合的单射,就能证明后者不可数。
满射。 如果存在从 到不可数集 的满射函数,那么 不可数,因为可数集的像仍是可数集。
去掉可数多个元素。 如果 不可数,而 可数,那么 仍不可数。否则, 就是两个可数集的并,从而自身也可数。
可数并。 在包含选择公理的标准集合论中,可数多个可数集的并仍是可数集。因此,如果一个不可数集被表示为可数多个集合的并,那么这些集合中至少有一个不可数。
积。 如果一个笛卡尔积的一个因子不可数,另一个因子非空,那么该积不可数,因为固定另一个因子中的一个元素,就能得到从不可数因子到该积的单射。
这些原理经常用于数学分析及数学的其他分支。
不可数性、测度与拓扑
不可数性必须与数学中其他关于大小的概念区分开来。
测度
在测度论中, 的每个可数子集的勒贝格测度都为零。因此,任何勒贝格测度为正的子集都是不可数集。
反过来则不成立。康托尔集不可数,但其测度为零。因此,一个集合所含的点可以与整条实数轴一样多,却在测度论意义上不占据任何正的长度。
概率中也有类似的区别。在 上的均匀分布下,每个单独结果的概率都是零,而整个区间的概率为一。这并不矛盾:概率测度具有可数可加性,而不是对任意不可数族都具有可加性。
拓扑结构
在拓扑学中,不可数性并不意味着一个集合包含区间或具有非空内部。康托尔集同样是一个反例。
反过来,稠密集也不一定不可数。有理数集在实数轴中稠密,但它是可数的。实数轴虽然自身不可数,却有一个可数稠密子集,因此也是可分空间。
连续统假设
由于 不可数,
连续统假设断言
等价地说,不存在基数严格介于自然数集与实数集的基数之间的集合。
假定策梅洛—弗兰克尔集合论的标准公理加上选择公理(合称 ZFC)是一致的,那么这一断言独立于这些公理。因此,必须区分“不可数”与“具有连续统基数”:前者表示大小超出可数范围。ZFC 不能证明 的每个不可数子集的基数都是 。
历史发展与基础层面的注意事项
格奥尔格·康托尔在 1874 年发表的工作中证明了实数集的不可数性。他最初的证明不同于后来在 1891 年发表的对角线论证。这些结果推动无限基数研究成为集合论的核心内容之一。
大多数标准论述都以 ZFC 为基础。如果没有选择公理,关于无限集的一些熟知结论就需要附加条件。特别是,可数多个可数集的并不一定可数,无限集也不一定包含可数无限子集。用“不存在到 的单射”定义不可数性仍然有意义,但若要将它对应到良序基数层级中的某个位置,就需要更加谨慎。
不可数性也与集合论模型内部有哪些集合和函数有关。一个从外部看是可数的模型,内部可能包含一个被该模型视为不可数的集合,因为模型中不存在枚举该集合的函数。这一区别是与勒文海姆—斯科伦定理相关的表面悖论的根源;它并不会使不可数性的定义产生矛盾。