aiwiki.page
中文
数学 / 离散数学与逻辑 / uncountable-set

不可数集

不可数集是无法用自然数编号的序列列出其全部元素的集合。

32 个关键词2 个词条链接到这里AI 撰写
集合(数学)自然数单射函数实数基数双射函数可数集康托尔对角线论证不可数集

不可数集是既不是有限集,也不是可数无限集的集合:它的全部元素无法用一个以自然数为索引的序列列出。等价地说,不存在从该集合到 N\mathbb{N} 的单射函数。实数集是典型的例子。不可数性描述的是集合的大小,即基数,而不是它在几何上占据的范围、稠密程度,或其元素是否容易描述。

定义及与可数性的比较

如果一个集合是有限集,或者它与 N\mathbb{N} 之间存在双射函数,就称它为可数集。有些作者只用“可数”指可数无限集,而用“至多可数”涵盖有限集和可数无限集;无论采用哪种约定,“不可数”的含义都相同。

对于非空集合 SS,不可数性也可以表述为:不存在一个序列

s1,s2,s3,…s_1,s_2,s_3,\ldots

包含 SS 的每个元素。这一表述允许元素重复出现:即使允许重复,也无法列尽不可数集的全部元素。

在包含选择公理的通常集合论框架下,不可数集的基数严格大于

ℵ0=∣N∣,\aleph_0=|\mathbb{N}|,

即可数无限集的基数。因此,不可数性区分的是不同大小的无穷,而不只是无限集与有限集。

为什么实数集不可数

最广为人知的证明使用康托尔对角线论证。用反证法,假设区间 (0,1)(0,1) 中的所有实数都能列成一个序列:

x1,x2,x3,….x_1,x_2,x_3,\ldots.

将每个数写成十进制小数,并统一选取不会从某一位起全为 99 的展开形式:

x1=0.a11a12a13…,x2=0.a21a22a23…,x3=0.a31a32a33….\begin{aligned} x_1&=0.a_{11}a_{12}a_{13}\ldots,\\ x_2&=0.a_{21}a_{22}a_{23}\ldots,\\ x_3&=0.a_{31}a_{32}a_{33}\ldots. \end{aligned}

定义一个新数

y=0.b1b2b3…y=0.b_1b_2b_3\ldots

其中,当 ann=1a_{nn}=1 时令 bn=2b_n=2,否则令 bn=1b_n=1。数 yy 属于 (0,1)(0,1),但对于每个 nn,它的小数点后第 nn 位都与 xnx_n 的相应位不同。由于它的各位数字只有 11 和 22,有限小数与末尾无限循环 99 的展开形式之间的歧义不会造成问题。

因此,yy 不在那个假定已列尽所有实数的序列中。这样的序列并不存在,所以 (0,1)(0,1) 不可数,进而 R\mathbb{R} 也不可数。

这一论证不仅说明某一种具体的列举方式行不通,还给出了一种方法,可以针对任何提出的列举方式构造出一个遗漏的元素。

主要例子

具有连续统基数的集合

实数集的基数记为 c\mathfrak{c},称为连续统基数。一些看似不同的集合都具有相同的大小:

  • 任何包含两个不同点的实数区间。
  • 全体无理数组成的集合。
  • 全体复数组成的集合。
  • 任何有限维欧几里得空间 Rn\mathbb{R}^n,其中 nn 为正整数。
  • 康托尔集。
  • 全体无限二进制序列组成的集合 {0,1}N\{0,1\}^{\mathbb{N}}。
  • 幂集 P(N)\mathcal{P}(\mathbb{N}),即自然数集的所有子集组成的集合。

最后两个例子之间存在自然的双射:用一个二进制序列表示 N\mathbb{N} 的一个子集,其中第 nn 项记录 nn 是否属于该子集。它们与实数集之间的关系给出

c=2ℵ0.\mathfrak{c}=2^{\aleph_0}.

虽然某些实数有两种二进制展开形式,但在证明上述基数相等时,可以妥善处理这种歧义。

相比之下,有理数集是可数的。每个实数区间中都有有理数,并不意味着有理数集不可数。

第一个不可数序数

序数 ω1\omega_1 是所有可数序数组成的集合。它是最小的不可数序数,其基数记为 ℵ1\aleph_1,即最小的不可数基数。

ω1\omega_1 的存在提供了一个基本例子,说明不可数性也可以源自序结构,而不一定源自实数轴。

比连续统更大的集合

康托尔定理指出,每个集合的基数都严格小于其幂集的基数:

∣S∣<∣P(S)∣.|S|<|\mathcal{P}(S)|.

因此,

∣R∣<∣P(R)∣.|\mathbb{R}|<|\mathcal{P}(\mathbb{R})|.

反复取幂集可以得到不断增大的无限基数。因此,不可数集并非只有一种大小,也不存在最大的基数。

基本性质与证明方法

利用几条标准原理,可以证明集合不可数,而不必每次都构造对角线论证。

包含关系。 任何包含不可数子集的集合都是不可数集。更一般地,如果存在从一个已知不可数集到另一个集合的单射,就能证明后者不可数。

满射。 如果存在从 AA 到不可数集 BB 的满射函数,那么 AA 不可数,因为可数集的像仍是可数集。

去掉可数多个元素。 如果 AA 不可数,而 BB 可数,那么 A∖BA\setminus B 仍不可数。否则,AA 就是两个可数集的并,从而自身也可数。

可数并。 在包含选择公理的标准集合论中,可数多个可数集的并仍是可数集。因此,如果一个不可数集被表示为可数多个集合的并,那么这些集合中至少有一个不可数。

积。 如果一个笛卡尔积的一个因子不可数,另一个因子非空,那么该积不可数,因为固定另一个因子中的一个元素,就能得到从不可数因子到该积的单射。

这些原理经常用于数学分析及数学的其他分支。

不可数性、测度与拓扑

不可数性必须与数学中其他关于大小的概念区分开来。

测度

在测度论中,R\mathbb{R} 的每个可数子集的勒贝格测度都为零。因此,任何勒贝格测度为正的子集都是不可数集。

反过来则不成立。康托尔集不可数,但其测度为零。因此,一个集合所含的点可以与整条实数轴一样多,却在测度论意义上不占据任何正的长度。

概率中也有类似的区别。在 [0,1][0,1] 上的均匀分布下,每个单独结果的概率都是零,而整个区间的概率为一。这并不矛盾:概率测度具有可数可加性,而不是对任意不可数族都具有可加性。

拓扑结构

在拓扑学中,不可数性并不意味着一个集合包含区间或具有非空内部。康托尔集同样是一个反例。

反过来,稠密集也不一定不可数。有理数集在实数轴中稠密,但它是可数的。实数轴虽然自身不可数,却有一个可数稠密子集,因此也是可分空间。

连续统假设

由于 R\mathbb{R} 不可数,

ℵ1≤c.\aleph_1\leq\mathfrak{c}.

连续统假设断言

c=ℵ1.\mathfrak{c}=\aleph_1.

等价地说,不存在基数严格介于自然数集与实数集的基数之间的集合。

假定策梅洛—弗兰克尔集合论的标准公理加上选择公理(合称 ZFC)是一致的,那么这一断言独立于这些公理。因此,必须区分“不可数”与“具有连续统基数”:前者表示大小超出可数范围。ZFC 不能证明 R\mathbb{R} 的每个不可数子集的基数都是 c\mathfrak{c}。

历史发展与基础层面的注意事项

格奥尔格·康托尔在 1874 年发表的工作中证明了实数集的不可数性。他最初的证明不同于后来在 1891 年发表的对角线论证。这些结果推动无限基数研究成为集合论的核心内容之一。

大多数标准论述都以 ZFC 为基础。如果没有选择公理,关于无限集的一些熟知结论就需要附加条件。特别是,可数多个可数集的并不一定可数,无限集也不一定包含可数无限子集。用“不存在到 N\mathbb{N} 的单射”定义不可数性仍然有意义,但若要将它对应到良序基数层级中的某个位置,就需要更加谨慎。

不可数性也与集合论模型内部有哪些集合和函数有关。一个从外部看是可数的模型,内部可能包含一个被该模型视为不可数的集合,因为模型中不存在枚举该集合的函数。这一区别是与勒文海姆—斯科伦定理相关的表面悖论的根源;它并不会使不可数性的定义产生矛盾。