令 $\#X = n$，则可以将 $X$ 等价写为

$$X = \{x_1, x_2, \ldots, x_n\}$$

($\Rightarrow$)
令 $f: X \to Y$ 为双射映射，满射性给出，$Y$ 可以被等价写为

$$Y = \{f(x_1), f(x_2), \ldots, f(x_n)\}$$

由单射性可知，$f(x_i) \neq f(x_j)$ 当且仅当 $i \neq j$，所以 $Y$ 也有且仅有 $n$ 个元素，故 $\#Y = n$。

($\Leftarrow$)
由于 $\#Y = n$，则可以将 $Y$ 等价写为

$$Y = \{y_1, y_2, \ldots, y_n\}$$

那么此时定义映射

$$f: X \to Y, \quad x_i \mapsto y_i$$

显然 $f$ 是双射映射。

$\square$

我们先证明对于 $a \lt b, c \lt d$，区间 $[a, b]$ 与 $[c, d]$ 等势
要证明两个集合等势，最关键的目标就是构造出双射映射
令映射

$$f : [a, b] \to [c, d], \quad x \mapsto c + \frac{(x - a)(d - c)}{b - a}$$

要证明这是双射，一个好办法是证明其可逆。定义

$$g : [c, d] \to [a, b], \quad y \mapsto a + \frac{(y - c)(b - a)}{d - c}$$

那么此时

$$\begin{aligned} (f \circ g)(y) &= f\left(a + \frac{(y - c)(b - a)}{d - c}\right) \\ &= c + \frac{\left(a + \frac{(y - c)(b - a)}{d - c} - a\right)(d - c)}{b - a} \\ &= c + \frac{(y - c)(b - a)}{d - c} \cdot \frac{d - c}{b - a} \\ &= c + (y - c) = y \\ (g \circ f)(x) &= g\left(c + \frac{(x - a)(d - c)}{b - a}\right) \\ &= a + \frac{\left(c + \frac{(x - a)(d - c)}{b - a} - c\right)(b - a)}{d - c} \\ &= a + \frac{(x - a)(d - c)}{b - a} \cdot \frac{b - a}{d - c} \\ &= a + (x - a) = x \end{aligned}$$

所以 g = f^

显然，对于这样的 $f$，可以知道

• 由 $[a,b)$ 到 $[c,d)$ 双射，所以 $|[a,b)| = |[c,d)|$
• 由 $(a,b]$ 到 $(c,d]$ 双射，所以 $|(a,b]| = |(c,d]|$
• 由 $(a,b)$ 到 $(c,d)$ 双射，所以 $|(a,b)| = |(c,d)|$

再简单取单调减少的一次函数，即可证明 $|[a,b)| = |(a,b]|$
至此所有区间的势都相等

$$|[a,b]| = |[a,b)| = |(a,b]| = |(a,b)| = |[c,d]| = |[c,d)| = |(c,d]| = |(c,d)|$$

接下来证明 $|[a,b]| = |\mathbb{R}|$，实际上我们只需要证明 $|(-\dfrac{\pi}{2}, \dfrac{\pi}{2})| = |\mathbb{R}|$ 即可
考虑正切函数

$$\tan : \left(-\frac{\pi}{2}, \frac{\pi}{2}\right) \to \mathbb{R}, \quad x \mapsto \tan x$$

其反函数为

$$\arctan : \mathbb{R} \to \left(-\frac{\pi}{2}, \frac{\pi}{2}\right), \quad y \mapsto \arctan y$$

显然 $\tan$ 与 $\arctan$ 互为逆映射，所以 $\tan$ 是双射映射
因此 $|(-\dfrac{\pi}{2}, \dfrac{\pi}{2})| = |\mathbb{R}|$ 成立
$\square$

($\Rightarrow$)
此时存在单射映射 $g : Y \to X$。给出限制其陪域的映射

$$\hat g : Y \to g(Y), \quad y \mapsto g(y)$$

显然 $\hat g$ 是双射映射

任取 $y_0 \in Y$，定义映射

$$f : X \to Y, \quad x \mapsto \begin{cases}\hat g^{-1}(x), & x \in g(Y) \\ y_0, & x \not\in g(Y)\end{cases}$$

那么

$$(f \circ g)(y) = f(g(y)) = \hat g^{-1}(g(y)) = y$$

所以 $f$ 是满射映射

($\Leftarrow$)
假设 $f : X \to Y$ 为满射映射，则存在映射 $g : Y \to X$，使得

$$f \circ g = \mathrm{id}_Y$$

那么对于任意 $y_1, y_2 \in Y$，若 $g(y_1) = g(y_2)$，则

$$y_1 = (f \circ g)(y_1) = (f \circ g)(y_2) = y_2$$

所以 $g$ 是单射映射，因此 $|X| \geq |Y|$ 成立
$\square$

假设 $|X| \leq |Y|, |Y| \leq |X|$
若其中一个集合为空集，根据定义可以得到 $X = Y = \emptyset$，所以 $|X| = |Y|$ 成立
所以不妨设 $X, Y$ 均非空

根据假设，存在单射映射

$$f : X \to Y, \quad g : Y \to X$$

令

$$Z = g(Y)$$

显然映射 $Y \to Z, y \mapsto g(y)$ 是双射映射，所以 $|Y| = |Z|$。接下来需要证明 $|X| = |Z|$。

令映射 $h = f \circ g$，注意 $Z \subset X$，归纳地定义以下集合列

$$\begin{cases} X_1 = X \\ X_2 = h(X_1) \\ X_3 = h(X_2) \\ \vdots \\ \end{cases},\qquad \begin{cases} Z_1 = Z \\ Z_2 = h(Z_1) \\ Z_3 = h(Z_2) \\ \vdots \\ \end{cases}$$

因为 $Z_1 \subset X_1$，所以 $Z_n \subset X_n$ 对任意 $n \in \mathbb N$ 成立
又因为

$$X_2 = g(f(X_1)) \subset g(Y) = Z = Z_1$$

所以 $X_{n+1} \subset Z_n$ 对任意 $n \in \mathbb N$ 成立

汇总可以得到以下交错的包含关系

$$X = X_1 \supset Z_1 \supset X_2 \supset Z_2 \supset X_3 \supset Z_3 \supset \cdots$$

因为 $h$ 是单射的，所以各个 $X_n$ 向着 $X_{n+1}$ 双射，并且各个 $Z_n$ 向着 $Z_{n+1}$ 双射，这样一来映射

$$h_n: X_n \setminus Z_n \to Z_{n+1} \setminus X_{n+1}, \quad x \mapsto h(x)$$

都是双射映射。

那么根据链式包含关系，可以知道对于任意的 $x \in X$，以下两种情况之一成立

• 要么仅存在唯一的 $n$，使得 $x \in X_n \setminus Z_n$
• 要么仅存在唯一的 $n$，使得 x \in Z_n \setminus X_

定义映射

$$\phi : X \to Z, \quad x \mapsto \begin{cases} h_n(x), & {}^\exists n: x \in X_n \setminus Z_n \\ x, & \text{otherwise} \end{cases}$$

那么 $\phi$ 是双射映射，因为逆映射可以按照如下给出

$$\phi^{-1} : Z \to X, \quad z \mapsto \begin{cases} h_n^{-1}(z), & {}^\exists n: z \in X_{n+1} \setminus Z_{n+1} \\ z, & \text{otherwise} \end{cases}$$

所以 $|X| = |Z|$ 成立
因此 $|X| = |Y|$ 成立
$\square$

需要利用选择公理。
记 $\Omega$ 为 $X$ 的全体无限子集所构成的集合，即

$$\Omega = \{A \subset X \mid A \text{ is infinite}\}$$

由于 $X$ 是无限集合，所以 $\Omega$ 非空。并且注意 $\emptyset \not\in \Omega$。

考虑集合族 $\{A\}_{A \in \Omega}$，与直积

$$\prod_{A \in \Omega} A = \{f : \Omega \to X \mid f(A) \in A, \forall A \in \Omega\}$$

由于各个 $A$ 非空，所以根据选择公理，直积非空

取直积中的元 $(f_A)_{A \in \Omega}$，归纳地定义序列

$$A_{n+1} = A_n \setminus \{f_{A_n}\},\quad A_1 = X$$

那么对于 $n \geq 2$ 有

$$A_n = X \setminus \{f_{A_1}, f_{A_2}, \ldots, f_{A_{n-1}}\}$$

对于 $f_{A_n}$ 来说，显然 $f_{A_n} \in A_n$，所以映射

$$g : \mathbb N \to X, \quad n \mapsto f_{A_n}$$

是单射映射，因此 $\aleph_0 \leq |X|$ 成立
$\square$

($\Rightarrow$)
假设 $X$ 是无限集合，根据 Aleph 零的最小性有 $\aleph_0 \leq |X|$
根据 Bernstein 定理，$|X| = \aleph_0$，所以 $X$ 是可数集

($\Leftarrow$)
若 $X$ 是可数集，根据定义有 $|X| = \aleph_0$
若 $X$ 是有限集，$X$ 为空集是按照定义显然有 $|X| \leq \aleph_0$ 成立
不妨设 $X$ 非空，只需要按照顺序排列

$$X = \{x_1, x_2, \ldots, x_n\}$$

那么定义映射

$$f : X \to \mathbb N, \quad x_i \mapsto i$$

显然 $f$ 是单射映射，所以 $|X| \leq \aleph_0$ 成立
$\square$

根据假设，存在单射映射

$$f : X \to Y$$

定义映射

$$\hat f : \mathcal{P}(X) \to \mathcal{P}(Y), \quad A \mapsto f(A) = \{f(a) \mid a \in A\}$$

任取 $A_1, A_2 \in \mathcal{P}(X)$
若 $\hat f(A_1) = \hat f(A_2)$，则对于任意 $a \in A_1$，都有

$$f(a) \in \hat f(A_1) = \hat f(A_2)$$

所以存在 $b \in A_2$，使得 $f(a) = f(b)$。由 $f$ 的单射性可知 $a = b$，所以 $a \in A_2$。

同理可证 $A_2 \subset A_1$，所以 $A_1 = A_2$。
因此 $\hat f$ 是单射映射，得到 $|\mathcal{P}(X)| \leq |\mathcal{P}(Y)|$
$\square$

若 $X$ 为空集，那么 $\mathcal{P}(X) = \{\emptyset\}$ 成为有限集合，并且显然 $\#X = 0 \lt 1 = \#\mathcal{P}(X)$
所以不妨设 $X$ 非空
考虑映射

$$f:X \to \mathcal{P}(X), \quad x \mapsto \{x\}$$

显然这是一个单射映射，所以得到 $|X| \leq |\mathcal{P}(X)|$。

接下来让我们证明 $|X| \neq |\mathcal{P}(X)|$，也就是说不存在从 $X$ 到 $\mathcal{P}(X)$ 的双射映射

任取由 $X$ 到 $\mathcal{P}(X)$ 的映射 $F$，定义集合 $Y \subset X$ 为

$$Y = \{x \in X \mid x \not\in F(x)\}$$

那么，对于任取的 $x \in X$，都有

• 若 $x \in Y$，则根据定义 $x \not\in F(x)$，所以 $F(x) \neq Y$
• 若 $x \not\in Y$，则根据定义 $x \in F(x)$，所以 $F(x) \neq Y$

无论如何 $F(x) \neq Y$ 成立，所以 $F$ 不是满射映射，因此不存在从 $X$ 到 $\mathcal{P}(X)$ 的双射映射
$\square$

任取 $A \in \mathcal{P}(X)$，定义映射

$$\chi_A:X \to \{0,1\}, \quad x \mapsto \begin{cases}1, & x \in A \\ 0, & x \not\in A\end{cases}$$

这样一来，实现了将各个 $A$ 映射到一个映射，所以得到

$$\chi:\mathcal{P}(X) \to \{0,1\}^X, \quad A \mapsto \chi_A$$

接下来证明 $\chi$ 是双射映射

任取 $f \in \{0,1\}^X$，定义集合

$$T(f) = f^{-1}(\{1\}) = \{x \in X \mid f(x) = 1\} \subset X$$

这样一来实现了映射

$$T:\{0,1\}^X \to \mathcal{P}(X), \quad f \mapsto T(f)$$

那么，对于任意的 $A \in \mathcal{P}(X)$，都有

$$(T \circ \chi)(A) = T(\chi_A) = \chi_A^{-1}(\{1\}) = A$$

所以 $T \circ \chi = \mathrm{id}_{\mathcal{P}(X)}$。再任取 $f \in \{0,1\}^X$，都有

$$(\chi \circ T)(f) = \chi_{T(f)} = \chi_{f^{-1}(\{1\})} = f$$

所以 $\chi \circ T = \mathrm{id}_{\{0,1\}^X}$。因此 $\chi$ 是双射映射
$\square$

首先根据上述结论有 $|\mathcal{P}(\mathbb N)| = |\{0,1\}^{\mathbb N}|$。
并且 $|\mathbb R| = |[0.1)|$，所以只需要证明 $|\{0,1\}^{\mathbb N}| = |[0,1)|$

首先证明 $|[0,1)| \leq |\{0,1\}^{\mathbb N}|$
任取 $x \in [0,1)$，考虑其二进制小数表示（对于有限小数，总是取无限个 0 的表示）

$$x = 0.x_1 x_2 x_3 \ldots,\qquad x_i \in \{0,1\}$$

这是合法的操作，例如

$$\begin{aligned} \frac{1}{2} &= 0.1 = 0.1000\ldots \\ \frac{1}{3} &= 0.011\ldots \end{aligned}$$

定义映射

$$\varphi_x: \mathbb N \to \{0,1\}, \quad i \mapsto x_i$$

来得到映射

$$\varphi: [0,1) \to \{0,1\}^{\mathbb N}, \quad x \mapsto \varphi_x$$

任取 $x, y \in [0,1)$，假设 $\varphi(x) = \varphi(y)$
那么对于任意的 $i \in \mathbb N$，都有

$$x_i = \varphi_x(i) = \varphi_y(i) = y_i$$

所以

$$x = 0.x_1 x_2 x_3 \ldots = 0.y_1 y_2 y_3 \ldots = y$$

因此 $\varphi$ 是单射映射，所以 $|[0,1)| \leq |\{0,1\}^{\mathbb N}|$。

接下来证明 $|\{0,1\}^{\mathbb N}| \leq |[0,1)|$
对于各个映射 $f \in \{0,1\}^{\mathbb N}$，定义三进制表示下的实数

$$\lambda_f = 0.f(1) f(2) f(3) \ldots$$

那么可以知道 $0 \leq \lambda_f \lt 1$
这可以导出映射

$$\lambda : \{0,1\}^{\mathbb N} \to [0,1), \quad f \mapsto \lambda_f$$

任取 $f, g \in \{0,1\}^{\mathbb N}$，假设 $\lambda(f) = \lambda(g)$，那么有

$$0.f(1) f(2) f(3) \ldots = 0.g(1) g(2) g(3) \ldots$$

将等式两边变为 $3$ 倍，即

$$f(1).f(2) f(3) \ldots = g(1).g(2) g(3) \ldots$$

因为各个 $f(i) \leq 1$，所以小数部分

$$0.f(2) f(3) \ldots = \frac{f(2)}{3} + \frac{f(3)}{3^2} + \ldots = \sum_{i=1}^{\infty} \frac{f(i)}{3^i} \lt \sum_{i=1}^{\infty} \frac{1}{3^i} = \frac{1/3}{1 - 1/3} = \frac{1}{2}$$

同理可得

$$0.g(2) g(3) \ldots \lt \frac{1}{2}$$

这意味着，对于等式

$$f(1).f(2) f(3) \ldots = g(1).g(2) g(3) \ldots$$

来说，整数部分必然相等，所以 $f(1) = g(1)$。再将等式两边减去整数部分，得到

$$0.f(2) f(3) \ldots = 0.g(2) g(3) \ldots$$

重复上述论证，可以得到 $f(i) = g(i)$ 对任意 $i \in \mathbb N$ 成立，所以 $f = g$。
因此 $\lambda$ 是单射映射，所以 $|\{0,1\}^{\mathbb N}| \leq |[0,1)|$。
综上，依据 Bernstein 定理，得到 $|\{0,1\}^{\mathbb N}| = |[0,1)|$，所以 $|\mathcal{P}(\mathbb N)| = |\mathbb R|$ 成立
$\square$