康托尔定理与幂集

集合 (A) 的幂集 (\mathcal P(A)) 是由 (A) 的全部子集组成的集合，其中包括空集与 (A) 本身。若 (A) 有 (n) 个元素，每个元素在构造子集时都有“选入”或“不选入”两种独立选择，所以：

[ |\mathcal P(A)|=2^n. ]

例如五元集合有 (1+5+10+10+5+1=32) 个子集。这里的加数是按子集大小分层得到的二项式系数；空集是 (A) 的子集，即使它不是 (A) 的元素。

康托尔定理断言，对任何集合 (A)，幂集的基数都严格大于原集合：

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

证明的核心是对角论证。假设有函数 (f:A\to\mathcal P(A))，构造

[ D={a\in A\mid a\notin f(a)}. ]

对任意 (a)，(D) 是否包含 (a) 都与 (f(a)) 相反，因此 (D\neq f(a))；没有从 (A) 到其幂集的满射。

当 (A=\mathbb N) 时，(\mathcal P(\mathbb N)) 不可数，其基数写作 (2^{\aleph_0})，并与实数集等势。有限集合的幂集仍是有限的，因此“幂集不可数”只在特定无限基数的语境中成立；普遍成立的是幂集的基数严格大于原集合。

与此密切相关的对角论证可以直接证明区间 ((0,1)) 中的实数不可数。假设这些数能排成序列，并把第 (n) 个数的小数第 (n) 位记作 (a_{nn})。构造一个新数，使它的第 (n) 位在 (a_{nn}\neq5) 时取 5，在 (a_{nn}=5) 时取 6。这个新数在第 (n) 位上不同于序列中的第 (n) 个数，所以不可能出现在原序列中。只使用 5 和 6 还能避开以无穷多个 9 结尾所造成的十进制双重表示问题。

这一证明是反证法：先假定实数可数，再由该假定构造出遗漏项。它不需要预先假定“实数不可数”，因此不是循环论证。

《研讨班 XVI》在枚举子集时使用了同一基数增长事实：含 \(n\) 个元素的有限集合有 \(2^n\) 个子集，因而子集总数会迅速超过元素数。不过工作底本的口头写法有时省略花括号，容易把元素 \(1\)、单元素集合 \({1}\)、空集以及幂集本身混在一起。数学上应先恢复这些层级，再讨论拉康怎样把子集的“多出”转接到大他者与 Un-en-plus；基数定理本身并不证明这一精神分析解释。

来源

• Cantor theorem（英文；《数学百科全书》）
• Cardinal number（英文；《数学百科全书》）
• Set Theory（英文；《斯坦福哲学百科全书》）
• 《研讨班 XVI》第二十三课 s16-23-0045—s16-23-0053（法文；元素／单元素集合、空集、子集枚举及指数增长）

关联

戴德金无限与伽利略悖论 集合划分、二分与补集对 乔治·安东尼亚德斯-梅特里奥斯《康托尔错了》 空集、单元素集合与 Un-en-plus：数学事实与拉康的借用

s16-23-0045 s16-23-0053 s19b-06-0227 s19b-06-0254 s19b-07-0265