康托尔定理 · aiwiki.page

康托尔定理是集合论中的一项基本结果：任何集合 $A$ 的基数都严格小于其幂集 $\mathcal P(A)$ 的基数；幂集就是由该集合的所有子集组成的集合。等价地，不存在从 $A$ 到 $\mathcal P(A)$ 的满射。这一定理对有限集和无限集同样适用，并表明，取幂集会产生依次增大的无限基数，而不存在一个囊括一切的无限基数。(math.ucla.edu)

定理陈述与记号

集合 $A$ 的幂集定义为

\mathcal P(A)=\{B:B\subseteq A\},

其中， $B\subseteq A$ 表示 $B$ 是 $A$ 的子集。康托尔定理断言

|A|<|\mathcal P(A)|.

这里的“小于”指的是基数的大小，而非包含关系：两个集合的基数相等，当且仅当它们之间存在双射函数。上述不等式断言，从 $A$ 到 $\mathcal P(A)$ 存在单射函数，但两者之间不存在双射。这个单射很容易给出：

a\longmapsto\{a\}.

不同的元素对应不同的单元素子集。因此，定理的关键在于证明不可能存在满射函数 $A\to\mathcal P(A)$ 。(math.ucdavis.edu)

对于含有 $n$ 个元素的有限集，

|\mathcal P(A)|=2^n:

因为每个元素要么属于某个子集，要么不属于该子集。例如，

\mathcal P(\{a,b\}) =\{\varnothing,\{a\},\{b\},\{a,b\}\},

所以，含有两个元素的集合有四个子集。这一定理也适用于空集，因为

\mathcal P(\varnothing)=\{\varnothing\}, \qquad 0<1.

它的重要意义在于：对于无限集，基数也会同样严格增大。(whitman.edu)

对角线证明

设 $f:A\to\mathcal P(A)$ 是任意一个函数。定义

D=\{a\in A:a\notin f(a)\}.

这是 $A$ 的一个子集，因而是 $\mathcal P(A)$ 的一个元素。(math.ucla.edu)

对于每个 $a\in A$ ， $D$ 与 $f(a)$ 在是否包含元素 $a$ 这一点上不同：

若 $a\in f(a)$ ，则 $a\notin D$ 。
若 $a\notin f(a)$ ，则 $a\in D$ 。

因此，对每个 $a$ ，都有 $D\ne f(a)$ 。于是， $D$ 不在 $f$ 的像中，故 $f$ 不是满射。由于 $f$ 是任意选取的，从 $A$ 到其幂集不存在满射。(math.ucla.edu)

在通常的反证法中，先假设 $f$ 是满射。那么必有某个 $d\in A$ 满足 $f(d)=D$ ，但根据 $D$ 的定义，

d\in D \quad\Longleftrightarrow\quad d\notin f(d) \quad\Longleftrightarrow\quad d\notin D,

这就产生了矛盾。结合前述将元素映射到其单元素集的单射，便证明了基数之间的严格不等式。(math.ucla.edu)

这一证明是康托尔对角线论证的一个实例：面对一个声称已经列全的对象族，构造一个新对象，使它在每个索引所对应的位置上，都与该索引对应的对象不同，从而证明原来的对象族并未列全。这里不需要按数值顺序排列 $A$ 的元素。(math.ucla.edu)

二值函数表述

每个子集 $B\subseteq A$ 都唯一对应于它的示性函数

\chi_B:A\to\{0,1\}, \qquad \chi_B(a)= \begin{cases} 1,&a\in B,\\ 0,&a\notin B. \end{cases}

因此， $\mathcal P(A)$ 与函数集 $\{0,1\}^{A}$ 的基数相同，通常记为 $2^{|A|}$ 。康托尔定理因而可以写成

\kappa<2^\kappa.

这里的幂表示基数幂运算，是有限情形下计数公式的推广，而不是普通的实数幂运算。(plato.stanford.edu)

在这一表述中，若试图用 $a\mapsto g_a$ 为 $A$ 上的所有二值函数建立索引，就必然会遗漏函数

h(a)=1-g_a(a).

对于每个 $a$ ， $h$ 与 $g_a$ 在自变量为 $a$ 时的函数值不同。这仍是同一个对角线构造，只是用函数值来表达，而不是用元素是否属于子集来表达。(math.bu.edu)

无限基数与连续统

将定理应用于自然数，可得

|\mathbb N|<|\mathcal P(\mathbb N)|.

因此， $\mathcal P(\mathbb N)$ 不是可数集：不存在一个序列能够列出自然数集的所有子集。等价地，所有无限二进制序列组成的集合是不可数的。(math.ucdavis.edu)

$\mathbb N$ 的幂集与实数集的基数相同，所以

|\mathbb R|=2^{\aleph_0}>\aleph_0, \qquad \aleph_0=|\mathbb N|.

反复应用这一定理，可得

|\mathbb N| < |\mathcal P(\mathbb N)| < |\mathcal P(\mathcal P(\mathbb N))| < \cdots.

更一般地，每个集合的幂集都具有严格更大的基数。因此，不存在最大的基数。(math.ucdavis.edu)

康托尔定理并未确定基数 $2^\kappa$ 比 $\kappa$ 大多少。尤其是，它并不能解决连续统假设，该假设断言

2^{\aleph_0}=\aleph_1,

其中， $\aleph_1$ 是最小的不可数基数。假定相关公理相容，连续统假设独立于加入选择公理的策梅洛—弗兰克尔集合论；而康托尔的严格不等式则是这一公理系统中的定理。(plato.stanford.edu)

公理基础及与悖论的关系

这一证明不需要选择公理。其中的构造都是明确给出的：将元素映射到其单元素集的映射提供了一个单射，而分离公理则从已有集合 $A$ 中，选出恰好满足 $a\notin f(a)$ 的那些元素，构成 $D$ 。幂集公理保证 $\mathcal P(A)$ 作为一个集合存在。这些构造在不含选择公理的策梅洛—弗兰克尔集合论中都可以完成。(plato.stanford.edu)

定义 $D$ 的条件与罗素悖论中涉及集合是否属于自身的条件相似，但两者的作用不同。罗素悖论揭示了不受限制的集合概括原则所导致的矛盾。康托尔的构造则是从一个已有集合中选取子集，符合分离公理；这里的矛盾所否定的是所假设的满射的存在。(math.ucla.edu)

这一定理也有助于解释为什么标准集合论中不存在全集。若有一个集合 $U$ 包含所有集合，那么 $U$ 的每个子集本身也都属于 $U$ ，于是得到包含关系 $\mathcal P(U)\subseteq U$ ，这与康托尔的基数不等式不相容。因此，标准的公理化处理会区分集合与那些大到无法成为集合的汇集，例如所有集合的汇集。(plato.stanford.edu)

历史发展

格奥尔格·康托尔在1874年发表的论文中证明了实数集不可数。他在1891年提出的对角线论证提供了一种一般方法：对于任意集合 $M$ ，从 $M$ 到一个二元素集合的所有函数所组成的集合，其基数严格大于 $M$ 的基数。通过子集与二值函数之间的对应关系，这一结果就是现代的幂集定理。与早先关于实数的论证不同，这一一般性结果不依赖于实数直线的序结构或拓扑性质。(math.bu.edu)

参考来源

Introduction to Analysismath.ucdavis.edu
Cantor’s Paradoxical Theoremmath.uci.edu
10 Cantor's Theoremwhitman.edu
The Notation in Principia Mathematicaplato.stanford.edu
Set Theoryplato.stanford.edu
The Continuum Hypothesisplato.stanford.edu
Alternative Axiomatic Set Theoriesplato.stanford.edu
The Continuum Hypothesisplato.stanford.edu