无最大集合的势

集合基数小于幂集基数

要证明任何集合 $A$ 的基数严格小于其幂集 $\mathcal{P}(A)$ 的基数（即 $|A| < |\mathcal{P}(A)|$），可以使用康托尔定理（Cantor's Theorem）。以下是详细证明步骤：

1. 定义幂集

幂集 $\mathcal{P}(A)$ 是集合 $A$ 的所有子集构成的集合。例如，若 $A = \{a, b\}$，则： $$ \mathcal{P}(A) = {\emptyset, {a}, {b}, {a, b}}. $$ 显然，当 $A$ 有 $n$ 个元素时，$\mathcal{P}(A)$ 有 $2^n$ 个元素。对于无限集合，幂集的基数更大。

2. 证明思路（反证法）

假设存在一个满射函数 $f: A \to \mathcal{P}(A)$，即 $f$ 将 $A$ 的每个元素映射到 $\mathcal{P}(A)$ 的某个子集。我们通过构造矛盾来推翻这一假设。

3. 构造矛盾的子集

定义集合 $B$ 为： $$ B = {x \in A \mid x \notin f(x)}. $$ 即，$B$ 包含所有“不属于自身在 $f$ 下的像”的 $A$ 的元素。

4. 分析集合 $B$

由于 $B \subseteq A$，显然 $B \in \mathcal{P}(A)$。
根据假设，$f$ 是满射，因此存在某个元素 $b \in A$，使得 $f(b) = B$。

5. 推导矛盾

问：$b \in B$ 吗？ - 若 $b \in B$：根据 $B$ 的定义，$b \notin f(b)$。但 $f(b) = B$，所以 $b \notin B$，矛盾。

若 $b \notin B$：根据 $B$ 的定义，$b \in f(b)$。但 $f(b) = B$，所以 $b \in B$，矛盾。

6. 结论

无论 $b$ 是否属于 $B$，都会导致矛盾。因此，原假设“存在满射 $f: A \to \mathcal{P}(A)$”不成立。进一步地： - $\mathcal{P}(A)$ 的基数严格大于 $A$ 的基数，即： $$ |A| < |\mathcal{P}(A)|. $$

直观理解

康托尔的证明展示了“幂集永远比原集合大”的核心思想： 1. 对角化思想：通过构造集合 $B$，使得 $B$ 无法被任何 $f(a)$ 覆盖，类似于实数不可数的对角线论证。 2. 自指矛盾：通过 $b$ 是否属于自身对应的集合 $B$，引发罗素悖论式的矛盾，表明“全集的映射”不可能存在。

补充说明

对无限集的意义：例如，自然数集 $\mathbb{N}$ 的基数为 $\aleph_0$，其幂集的基数为 $2^{\aleph_0}$，即连续统的基数。康托尔定理表明存在严格更大的无限基数。
广义结论：对任意基数 $\kappa$，有 $2^\kappa > \kappa$。这是集合论中“无最大基数”的基础。

通过这一证明，可以清晰地看到任何集合的幂集在基数上严格大于原集合。

自然数幂集与实数等势.

要证明自然数集 $\mathbb{N}$ 的幂集 $\mathcal{P}(\mathbb{N})$ 与实数集 $\mathbb{R}$ 等势（即 $|\mathcal{P}(\mathbb{N})| = |\mathbb{R}|$），可以通过以下步骤：

1. 幂集的基数

自然数集的幂集 $\mathcal{P}(\mathbb{N})$ 的基数为： $$ |\mathcal{P}(\mathbb{N})| = 2^{\aleph_0}, $$ 其中 $\aleph_0 = |\mathbb{N}|$。

2. 实数集的基数

实数集 $\mathbb{R}$ 的基数被称为连续统基数，记为 $\mathfrak{c}$。通过以下方法可证明 $\mathfrak{c} = 2^{\aleph_0}$：

方法一：二进制展开

每个实数 $x \in [0, 1)$ 可以唯一表示为二进制无限小数： $$ x = 0.b_1b_2b_3\dots \quad (b_i \in {0, 1}), $$ 其中排除以无限个 $1$ 结尾的表示（例如，$0.0111\dots$ 改写为 $0.1000\dots$）。
每个二进制序列 $\{b_i\}$ 对应 $\mathbb{N}$ 的一个子集 $S \subseteq \mathbb{N}$，其中： $$ n \in S \iff b_n = 1. $$ 因此，存在双射： $$ \mathcal{P}(\mathbb{N}) \leftrightarrow [0, 1) \subset \mathbb{R}. $$
由于 $[0, 1)$ 与 $\mathbb{R}$ 等势（例如，通过正切函数映射），得： $$ |\mathbb{R}| = |\mathcal{P}(\mathbb{N})| = 2^{\aleph_0}. $$

方法二：利用 Cantor-Schröder-Bernstein 定理

构造单射 $f: \mathcal{P}(\mathbb{N}) \to \mathbb{R}$：
对每个子集 $S \subseteq \mathbb{N}$，将其映射为实数： $$ f(S) = \sum_{n \in S} \frac{1}{10^n}. $$ 例如，$S = \{1, 3\}$ 对应 $0.101\dots$。此映射为单射。
构造单射 $g: \mathbb{R} \to \mathcal{P}(\mathbb{N})$：
对每个实数 $x \in \mathbb{R}$，将其二进制展开映射为 $\mathbb{N}$ 的子集： $$ g(x) = {n \in \mathbb{N} \mid \text{第 } n \text{ 位小数为 } 1}. $$ 需处理重复表示问题，例如规定优先选择不以无限个 $1$ 结尾的表示，以保证单射性。
应用定理：
存在单射 $f$ 和 $g$，因此由 Cantor-Schröder-Bernstein 定理： $$ |\mathcal{P}(\mathbb{N})| = |\mathbb{R}|. $$

3. 结论

自然数集的幂集与实数集等势： $$ \boxed{|\mathcal{P}(\mathbb{N})| = |\mathbb{R}|}. $$

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在协议之条款下提供，附加条款亦可能应用