康托尔定理（综述）

贡献者：待更新

　　本文根据 CC-BY-SA 协议转载翻译自维基百科相关文章。

图 1：集合 $\{x, y, z\}$ 的基数是 3，而它的幂集中有 8 个元素（$3 < 2^3 = 8$），如下图按包含关系排列。

　　在数学的集合论中，康托尔定理是一个基本结论，它指出：对于任意集合 $A$，其幂集（即包含 $A$ 所有子集的集合）具有严格大于 $A$ 本身的基数。

　　对于有限集合，康托尔定理可以通过对子集数量的直接枚举来验证。将空集也算作一个子集，若一个集合含有 $n$ 个元素，则它共有 $2^n$ 个子集。而由于对所有非负整数都有 $2^n > n$，因此定理在有限情形下成立。

　　更为重要的是，康托尔发现了一种适用于任意集合的论证方法，表明该定理对无限集合同样成立。因此，实数集的基数（它与整数集的幂集具有相同基数）严格大于整数集的基数；详细内容见 “连续统的基数”。

　　该定理以格奥尔格·康托尔命名，他在 19 世纪末首次提出并证明了这一命题。康托尔定理对数学哲学产生了直接而深远的影响。例如，通过对一个无限集合不断取幂集并应用康托尔定理，可以得到一个无尽的无限基数层级，每一层的基数都严格大于前一层。因此，该定理意味着：不存在 “最大的” 基数（通俗地说，就是 “没有最大的无穷大”）。

1. 证明

　　康托尔的论证既优雅又极其简洁。完整的证明如下，随后将附上详细解释。

　　 定理（康托尔） — 设 $f$ 是一个从集合 $A$ 到其幂集 $\mathcal{P}(A)$ 的映射，即 $ f: A \to \mathcal{P}(A)$，那么 $f$ 不是满射。因此，对于任意集合 $A$，都有： $\operatorname{card}(A) < \operatorname{card}(\mathcal{P}(A))$ 即集合 $A$ 的基数严格小于其幂集的基数。

　　证明

　　定义集合 $B = \{x \in A \mid x \notin f(x)\}$ 该集合根据外延公理模式是合法的，且由于 $B \subseteq A$，所以 $B \in \mathcal{P}(A)$。假设 $f$ 是一个满射。

　　那么存在某个 $\xi \in A$ 使得 $f(\xi) = B$。

　　根据定义，对于 $A$ 中任意 $x$，都有：$x \in B \iff x \notin f(x)$ 将 $x = \xi$ 代入可得：$\xi \in B \iff \xi \notin f(\xi)$ 但由于 $f(\xi) = B$，上述推理得到形式为 $\varphi \Leftrightarrow \lnot \varphi$ 的矛盾。

　　因此，依据反证法，$f$ 不可能是满射。我们已经知道从 $A$ 到 $\mathcal{P}(A)$ 的单射是存在的，例如函数：$g: A \to \mathcal{P}(A), \quad g(x) = \{x\}$ 因此可得：$\operatorname{card}(A) < \operatorname{card}(\mathcal{P}(A)) \quad \blacksquare$

　　根据基数的定义，对于任意两个集合 $X$ 和 $Y$，当且仅当存在一个从 $X$ 到 $Y$ 的单射而不存在双射时，才有：$\operatorname{card}(X) < \operatorname{card}(Y)$ 我们只需证明：不存在从 $X$ 到 $Y$ 的满射，就能得出这一不等式。这正是康托尔定理的核心：不存在从任意集合 $A$ 到其幂集 $\mathcal{P}(A)$ 的满射。为证明这一点，只需展示：任意一个函数 $f$（从 $A$ 映射到其子集）都无法覆盖所有可能的子集。也就是说，我们只需要构造出一个子集 $B \subseteq A$，使得对于任意 $x \in A$，都有 $f(x) \neq B$。回顾每个 $f(x)$ 都是 $A$ 的一个子集，我们定义如下集合 $B$，有时称为 $f$ 的康托尔对角集合：$^\text{[1][2]}$ $$ B = \{x \in A \mid x \notin f(x)\}~ $$ 也就是说，对于所有 $x \in A$，有：$x \in B \iff x \notin f(x)$ 对于每个 $x$，集合 $B$ 和 $f(x)$ 不可能相等，因为 $B$ 是从那些在其像 $f(x)$ 中不包含自身的元素构造而成的。对每个 $x \in A$，只有两种情况：若 $x \in f(x)$，那么根据定义 $x \notin B$，因此 $f(x) \neq B$，因为 $f(x)$ 包含 $x$ 而 $B$ 不包含；若 $x \notin f(x)$，那么根据定义 $x \in B$，因此同样 $f(x)\neq B$，因为 $B$ 包含 $x$，而 $f(x)$ 不包含。综上所述，对于任意 $x \in A$，都有 $f(x) \neq B$。因此，$B$ 并不是 $f$ 的像，这就证明了：不存在从 $A$ 到 $\mathcal{P}(A)$ 的满射。

　　换句话说，更形式化地表达，我们刚刚证明了：若存在某个 $\xi \in A$ 使得 $f(\xi) = B$，则会导致如下矛盾： $$ \begin{aligned} \xi \in B &\iff \xi \notin f(\xi) \quad &&\text{（根据 } B \text{ 的定义）}; \\ \xi \in B &\iff \xi \in f(\xi) \quad &&\text{（由于假设 } f(\xi) = B \text{）}. \end{aligned}~ $$ 因此，依据反证法，该假设必为错误。$^\text{[3]}$ 也就是说，不存在任何 $\xi \in A$ 使得 $f(\xi) = B$；换句话说，集合 $B$ 不属于函数 $f$ 的像集，而 $f$ 并未映射到集合 $A$ 的所有子集，即：$f$ 不是满射。

　　最后，为了完成整个证明，我们还需要给出一个从集合 $A$ 到其幂集的单射函数。构造这样的函数是显而易见的：只需将每个元素 $x$ 映射到单元素集合 $\{x\}$。至此，论证完成，我们得出了对于任意集合 $A$ 都成立的严格不等式：$\operatorname{card}(A) <\operatorname{card}(\mathcal{P}(A))$

　　另一种理解该证明的方法是：集合 $B$，无论是空集还是非空集，始终属于集合 $A$ 的幂集 $\mathcal{P}(A)$。若函数 $f$ 是满射，则必须存在某个 $A$ 中的元素映射到 $B$。但这会导致矛盾：没有哪个 $B$ 中的元素能映射到 $B$，因为那会违反 $B$ 中元素的判定标准；因此，映射到 $B$ 的那个元素不能属于 $B$，这又意味着它满足了属于 $B$ 的标准，形成另一个矛盾。因此，假设某个 $A$ 中的元素映射到 $B$ 是错误的，故函数 $f$ 不可能是满射。

　　由于表达式 “$x \in f(x)$” 中变量 $x$ 出现了两次，这属于对角线式论证。对于一个可数（或有限）集合，可以通过构造如下的表格来说明上述证明的论证过程：

表格的每一行以集合 $A = \{x_1, x_2, \ldots\}$ 中的唯一元素 $x$ 作为行标，按照该顺序排列。这里假设集合 $A$ 是线性有序的，以便可以构造出这样的表格。
表格的每一列以集合 $A$ 的幂集中唯一的元素 $y$ 作为列标；列的顺序由函数 $f$ 的参数决定，即列标按 $f(x_1), f(x_2), \ldots$ 的顺序排列。
每一行 $x$ 与每一列 $y$ 的交点记录一个真/假的布尔值，用以表示 $x \in y$ 是否成立。

　　根据为行标和列标所选定的顺序，该表格的主对角线 $D$ 记录了每个 $x \in A$ 是否满足 $x \in f(x)$ 的情况。这样的一个表格示例如下：

图 2

　　在前文中构造的集合 $B$，正好对应于主对角线 $D$ 上那些表格记录为 $x \in f(x)$ 为假的行标（在上面的示例中，这些条目被标为红色）。表格的每一行记录了该行所代表元素 $x$ 是否属于每一列所对应集合的指示函数的值。而集合 $B$ 的指示函数，正好对应于主对角线条目的逻辑否定（即将 “真” 与 “假” 互换）。因此，集合 $B$ 的指示函数在至少一个条目上与任意一列都不一致。这就意味着，没有任何一列可以代表集合 $B$。

　　尽管上述证明看起来很简单，但对自动定理证明器来说，生成这个证明其实相当困难。其主要难点在于如何自动发现康托尔对角线集合。Lawrence Paulson 在 1992 年指出，Otter 无法完成这个任务，而 Isabelle 可以做到，不过需要一定程度的战术引导，这在某种意义上或许可以视为 “作弊”。

2. 当 $A$ 是可数无限集时

　　让我们来看一个特例，即当 $A$ 是可数无限集合的情况。我们不失一般性地取 $A = \mathbb{N} = \{1, 2, 3, \ldots\}$，即自然数集合。

　　假设 $\mathbb{N}$ 与其幂集 $\mathcal{P}(\mathbb{N})$ 等势。我们来看一下 $\mathcal{P}(\mathbb{N})$ 的一个样例： $$ \mathcal{P}(\mathbb{N}) = \{\varnothing, \{1,2\}, \{1,2,3\}, \{4\}, \{1,5\}, \{3,4,6\}, \{2,4,6,\dots\}, \dots\}~ $$ 实际上，$\mathcal{P}(\mathbb{N})$ 包含了 $\mathbb{N}$ 的无限子集，例如所有正偶数的集合 $\{2, 4, 6, \ldots\} = \{2k : k \in \mathbb{N} \}$，以及空集 $\varnothing$。

　　现在我们已经了解了 $\mathcal{P}(\mathbb{N})$ 中元素的大致形式，让我们尝试将 $\mathbb{N}$ 中的每个元素与 $\mathcal{P}(\mathbb{N})$ 中的每个元素配对，以期证明这两个无限集合是等势的。换句话说，我们将尝试把 $\mathbb{N}$ 中的每个元素与 $\mathcal{P}(\mathbb{N})$ 中的一个元素配对，使得两个集合中都没有未配对的元素。这样一种配对可能如下所示： $$ \mathbb{N} \quad \begin{Bmatrix} 1 & \longleftrightarrow & \{4, 5\} \\ 2 & \longleftrightarrow & \{1, 2, 3\} \\ 3 & \longleftrightarrow & \{4, 5, 6\} \\ 4 & \longleftrightarrow & \{1, 3, 5\} \\ \vdots & \vdots & \vdots \end{Bmatrix} \quad \mathcal{P}(\mathbb{N})~ $$ 在这样的配对中，有些自然数与包含它们本身的子集配对。例如，在这个例子中，数字 2 被配对到子集 $\{1, 2, 3\}$，而这个子集中确实包含 2。我们称这样的数字为自私的。其他自然数则被配对到不包含它们本身的子集。例如，数字 1 被配对到子集 $\{4, 5\}$，该子集中不包含数字 1。我们称这类数字为非自私的。同样地，数字 3 和 4 也是非自私的。

　　借助这个想法，让我们构造一个特殊的自然数集合。这个集合将为我们提供所需的矛盾。设 $B$ 为所有非自私自然数的集合。根据定义，幂集 $\mathcal{P}(\mathbb{N})$ 包含所有自然数的子集，因此它也包含这个集合 $B$。如果映射是双射（即一一对应），那么集合 $B$ 必然会与某个自然数 $b$ 配对。然而，这就产生了问题：如果 $b \in B$，那么根据配对关系，$b$ 属于它所对应的集合（即 $B$），因此是自私的，这与它属于 $B$（即非自私）矛盾。如果 $b \notin B$，那么它不是自私的，即是非自私的，那它就应该属于 $B$，同样产生矛盾。因此，不存在这样一个自然数 $b$ 能够与集合 $B$ 配对。

　　既然不存在与 $B$ 配对的自然数，我们就推翻了最初的假设：即存在 $\mathbb{N}$ 与 $\mathcal{P}(\mathbb{N})$ 之间的双射。这说明这两个集合不等势。

　　注意，集合 $B$ 可能是空集。这意味着每个自然数 $x$ 都被映射到一个包含 $x$ 本身的自然数子集上。也就是说，每个数都映射到了一个非空集合，没有任何一个数被映射到空集上。但空集是 $\mathcal{P}(\mathbb{N})$ 的元素之一，因此这种映射依然未能覆盖整个 $\mathcal{P}(\mathbb{N})$。

　　通过上述反证法，我们已经证明了 $\mathbb{N}$ 与其幂集 $\mathcal{P}(\mathbb{N})$ 的基数不可能相等。而且我们也知道，$\mathcal{P}(\mathbb{N})$ 的基数不可能小于 $\mathbb{N}$ 的基数，因为 $\mathcal{P}(\mathbb{N})$ 按定义包含所有单元素集合（singletons），而这些单元素集合就在 $\mathcal{P}(\mathbb{N})$ 中构成了 $\mathbb{N}$ 的一个 “拷贝”。

　　因此，只剩下一种可能性，那就是 $\mathcal{P}(\mathbb{N})$ 的基数严格大于 $\mathbb{N}$ 的基数，从而证得康托尔定理。

3. 相关悖论

　　康托尔定理及其证明与集合论中的两个悖论密切相关。

　　康托尔悖论是一个从康托尔定理与 “存在一个包含所有集合的集合” 这一假设（即所谓的全集 $V$）共同推出的矛盾。为了将这个悖论与下文将要讨论的另一个悖论区分开来，我们需要明确这一矛盾的具体内容：根据康托尔定理，对于任意集合 $X$，都有 $|\mathcal{P}(X)| > |X|$，即其幂集的基数严格大于它本身的基数。但另一方面，$\mathcal{P}(V)$ 的所有元素都是集合，因此也应属于全集 $V$，这意味着 $|\mathcal{P}(V)| \leq |V|$$^\text{[1]}$。

　　另一个悖论可以从康托尔定理的证明中导出，方法是将函数 $f$ 取为恒等函数；这会将康托尔的对角线集合转化为在给定集合 $A$ 上构造的所谓罗素集合：$^\text{[1]}$ $$ R_A = \{ x \in A : x \notin x \}.~ $$ 康托尔定理的证明可以直接改写来说明：如果假设存在一个包含所有集合的集合 $U$，那么考虑其对应的罗素集合 $R_U$ 会导致以下矛盾： $$ R_U \in R_U \iff R_U \notin R_U.~ $$ 这个论证就是著名的罗素悖论 $^\text{[1]}$。值得注意的是，这里我们呈现的罗素悖论实际上是策梅洛提出的一个定理 $^\text{[4]}$。由该矛盾我们可以得出结论：必须否定假设 $R_U \in U$，从而反证了 “存在一个包含所有集合的集合” 这一假设。这之所以成为可能，是因为我们在上面定义 $R_A$ 时使用了受限的理解公理，正是 ZFC 公理系统中的做法。这导致我们实际上得到了以下逻辑关系： $$ R_U \in R_U \iff (R_U \in U \land R_U \notin R_U).~ $$ 而如果我们采用的是不受限制的理解公理，比如在弗雷格系统中那样，直接将罗素集合定义为：$R = \{ x : x \notin x \}$,那么这个矛盾将由公理系统自身推出，无需任何额外假设。这也正是弗雷格系统崩溃的根源之一。$^\text{[4]}$

　　尽管罗素集合（无论哪种变体）在语法结构上与康托尔对角线集合相似，阿隆佐·邱奇指出，罗素悖论是独立于基数及其相关概念（如一一对应）的，与它们无关。$^\text{[5]}$

4. 历史背景

　　康托尔在 1891 年发表的论文《论多样性理论中的一个初等问题》中基本上给出了这一证明 $^\text{[6]}$，这篇论文中首次出现了用于证明实数不可数性的对角线论证（此前他已通过其他方法证明了实数的不可数性）。他在该论文中给出的论证版本是以集合上的指示函数而非子集为表述形式的 $^\text{[7]}$。他证明了：若 $f$ 是定义在集合 $X$ 上的函数，且值域是定义在 $X$ 上的二值函数（即指示函数），那么函数 $G(x) = 1 - f(x)(x)$ 不属于 $f$ 的值域。

　　伯特兰·罗素在其《数学原理》, 1903，第 348 节）中也给出了一个非常相似的证明，在那里他展示了命题函数的数量多于对象的数量。“假设所有对象与某些命题函数之间建立了一个对应关系，并设 $\phi_x$ 为 $x$ 的对应命题函数。那么命题‘非 $\phi_x(x)$’，即‘$\phi_x$ 不适用于 $x$’，是一个不包含在该对应关系中的命题函数；因为它对 $x$ 的真假取决于 $\phi_x$ 对 $x$ 的真假，因此对所有 $x$ 它都不同于 $\phi_x$。” 他将这一证明思想归功于康托尔。

　　恩斯特·策梅洛在 1908 年发表的论文《集合论基础的研究（一）》中给出了一条定理（他称之为 “康托尔定理”），其形式与上述内容一致。这篇论文构成了现代集合论的基础。参见策梅洛集合论。

5. 推广

　　劳维尔的固定点定理为康托尔定理提供了一个广泛的推广，适用于任何具有有限积的范畴，具体方式如下 $^\text{[8]}$：

　　设 $\mathcal{C}$ 是这样一个范畴，且 $1$ 是 $\mathcal{C}$ 中的终对象。假设 $Y$ 是 $\mathcal{C}$ 中的一个对象，并且存在一个自同态 $\alpha : Y \to Y$，且该自同态没有固定点；也就是说，没有一个态射 $y : 1 \to Y$ 满足 $\alpha \circ y = y$。那么，$\mathcal{C}$ 中就不存在一个对象 $T$，使得有一个态射 $f : T \times T \to Y$ 可以对所有的态射 $T \to Y$ 进行参数化。换句话说，对于每个对象 $T$ 和每个态射 $f : T \times T \to Y$，尝试将 $T \to Y$ 写成形如 $f(-,x) : T \to Y$ 的映射时，必须漏掉至少一个 $T \to Y$ 的映射。

6. 另见

施罗德–伯恩斯坦定理
康托尔的第一次不可数性证明
关于康托尔理论的争议

7. 参考文献

Abhijit Dasgupta (2013). *Set Theory: With an Introduction to Real Point Sets*. Springer Science & Business Media. 第 362–363 页. ISBN 978-1-4614-8854-5.
Lawrence Paulson (1992). *Set Theory as a Computational Logic* (PDF). Cambridge University Computer Laboratory. 第 14 页.
Graham Priest (2002). *Beyond the Limits of Thought*. Oxford University Press. 第 118–119 页. ISBN 978-0-19-925405-7.
Heinz-Dieter Ebbinghaus (2007). *Ernst Zermelo: An Approach to His Life and Work*. Springer Science & Business Media. 第 86–87 页. ISBN 978-3-540-49553-6.
Church, A. [1974] "Set theory with a universal set." in *Proceedings of the Tarski Symposium*. *Proceedings of Symposia in Pure Mathematics* XXV, 编辑 L. Henkin, Providence RI, 第二版带补充，1979 年，第 297–308 页. ISBN 978-0-8218-7360-1. 也刊登在 *International Logic Review* 15，第 11–23 页.
Cantor, Georg (1891). "Über eine elementare Frage der Mannigfaltigskeitslehre", *Jahresbericht der Deutschen Mathematiker-Vereinigung* (德文), 1: 75–78, 也见于 Georg Cantor, *Gesammelte Abhandlungen mathematischen und philosophischen Inhalts*, E. Zermelo, 1932.
A. Kanamori, "The Empty Set, the Singleton, and the Ordered Pair", 第 276 页. *Bulletin of Symbolic Logic* vol. 9, no. 3, (2003). 访问日期: 2023 年 8 月 21 日.
F. William Lawvere; Stephen H. Schanuel (2009). *Conceptual Mathematics: A First Introduction to Categories*. Cambridge University Press. 第 29 章. ISBN 978-0-521-89485-2.

Halmos, Paul，《朴素集合论》（*Naive Set Theory*），新泽西州普林斯顿：D. Van Nostrand 公司，1960 年。由 Springer-Verlag 于 1974 年在纽约再版，ISBN 0-387-90092-6（Springer-Verlag 版）。由 Martino Fine Books 于 2011 年再版，ISBN 978-1-61427-131-4（平装版）。
Jech, Thomas（2002），《集合论》（*Set Theory*），*Springer 数学专著系列*（第三千禧年版），Springer 出版社，ISBN 3-540-44085-2。

8. 外部链接

“Cantor theorem”，《数学百科全书》，EMS Press，2001 年 [1994 年版]
Weisstein, Eric W. “Cantor's Theorem”，MathWorld（数学世界）

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。