如何证明阿列夫零上阿列夫零等势于二上阿列夫零？

要证明阿列夫零上阿列夫零等势于二上阿列夫零，这本质上是在讨论集合的基数（cardinality）问题。简单来说，我们是要证明自然数集合 ($mathbb{N}$) 的笛卡尔积 ($mathbb{N} imes mathbb{N}$) 和实数集合 ($mathbb{R}$) 的基数是相同的。

在集合论中，我们用阿列夫符号（$aleph$）来表示无穷集合的基数。$aleph_0$（阿列夫零）代表可数无穷集合的基数，也就是自然数集合的基数。而 $2^{aleph_0}$（二上阿列夫零）代表实数集合的基数。我们的目标是证明 $|mathbb{N} imes mathbb{N}| = |mathbb{R}|$。

要证明两个集合等势，我们需要找到一个从一个集合到另一个集合的双射（bijection），也就是一个既是单射（injection）又是满射（surjection）的函数。

第一步：证明 $|mathbb{N} imes mathbb{N}| = aleph_0$

首先，我们来看看自然数集合的笛卡尔积。它代表所有有序对 $(m, n)$ 的集合，其中 $m$ 和 $n$ 都是自然数（我们通常认为自然数从1开始，或者从0开始，这不影响基数）。例如，如果是从1开始：${(1,1), (1,2), (2,1), (1,3), (2,2), (3,1), (1,4), ldots }$。

我们需要证明这个集合是可数无穷的，也就是说，我们可以把这些有序对一一列举出来，并且不会遗漏任何一个。这里有一个经典的证明方法，通常被称为“康托尔对角线方法”（虽然这个名字更常用于证明实数不可数，但这里用于列举有序对）。

想象一个表格，行和列都用自然数标记：

| | 1 | 2 | 3 | 4 | ... |
|||||||
| 1 | (1,1) | (1,2) | (1,3) | (1,4) | ... |
| 2 | (2,1) | (2,2) | (2,3) | (2,4) | ... |
| 3 | (3,1) | (3,2) | (3,3) | (3,4) | ... |
| 4 | (4,1) | (4,2) | (4,3) | (4,4) | ... |
| ...| ... | ... | ... | ... | ... |

我们来尝试按照一个特定的顺序来遍历这些有序对，确保每个对都被访问到：

1. 从左上角开始，访问 (1,1)。
2. 然后转向右上方，访问 (1,2)。
3. 再转向左下方，访问 (2,1)。
4. 继续转向右上方，访问 (1,3)。
5. 再转向左下方，访问 (2,2)。
6. 再转向左下方，访问 (3,1)。
7. 继续……

这个遍历的顺序可以这样描述：首先访问所有 $m+n=2$ 的有序对，然后是所有 $m+n=3$ 的，再是所有 $m+n=4$ 的，以此类推。具体来说，我们可以按照“斜线”来访问：

第一条斜线（和为2）：(1,1)
第二条斜线（和为3）：(1,2), (2,1)
第三条斜线（和为4）：(1,3), (2,2), (3,1)
第四条斜线（和为5）：(1,4), (2,3), (3,2), (4,1)
依此类推……

这种方法可以给每一个有序对 $(m, n)$ 分配一个唯一的自然数作为其在列表中的位置。例如，我们可以定义一个函数 $f: mathbb{N} imes mathbb{N} o mathbb{N}$ 来实现这个映射。一个常见的函数是：

$f(m, n) = frac{(m+n2)(m+n1)}{2} + n$

这个公式稍微复杂一点，但它的作用是根据有序对的“对角线”位置来分配编号。我们可以验证一下：
$f(1,1) = frac{(1+12)(1+11)}{2} + 1 = frac{0 cdot 1}{2} + 1 = 1$
$f(1,2) = frac{(1+22)(1+21)}{2} + 2 = frac{1 cdot 2}{2} + 2 = 1 + 2 = 3$
$f(2,1) = frac{(2+12)(2+11)}{2} + 1 = frac{1 cdot 2}{2} + 1 = 1 + 1 = 2$
$f(1,3) = frac{(1+32)(1+31)}{2} + 3 = frac{2 cdot 3}{2} + 3 = 3 + 3 = 6$
$f(2,2) = frac{(2+22)(2+21)}{2} + 2 = frac{2 cdot 3}{2} + 2 = 3 + 2 = 5$
$f(3,1) = frac{(3+12)(3+11)}{2} + 1 = frac{2 cdot 3}{2} + 1 = 3 + 1 = 4$

这个函数 $f$ 是从 $mathbb{N} imes mathbb{N}$ 到 $mathbb{N}$ 的一个单射。为什么是单射？如果 $f(m_1, n_1) = f(m_2, n_2)$，那么可以证明 $(m_1, n_1) = (m_2, n_2)$。这是因为不同的有序对会落在不同的对角线或者在同一对角线上有不同的位置，这些信息都被函数编码了。

同时，这个函数也是满射到所有可能的自然数。也就是说，对于任何一个自然数 $k$，你都可以找到一对 $(m, n)$ 使得 $f(m, n) = k$。

因为我们找到了一个从 $mathbb{N} imes mathbb{N}$ 到 $mathbb{N}$ 的双射（或者说单射就足够了，因为我们可以从中构造一个双射，或者说 $mathbb{N} imes mathbb{N}$ 的基数小于等于 $mathbb{N}$ 的基数），所以 $mathbb{N} imes mathbb{N}$ 是可数无穷的，其基数就是 $aleph_0$。

即 $|mathbb{N} imes mathbb{N}| le |mathbb{N}|$。

第二步：证明 $|mathbb{N}| le |mathbb{R}|$

这一步相对容易。我们需要找到一个从自然数集合到实数集合的单射。这可以通过将自然数映射到实数的一个子集来完成。最简单的方法是将自然数 $n$ 映射到实数 $n.0$。例如：
$1 mapsto 1.0$
$2 mapsto 2.0$
$3 mapsto 3.0$
$ldots$

这个映射 $g: mathbb{N} o mathbb{R}$, $g(n) = n.0$ 是一个显然的单射。
因为存在一个单射，所以 $|mathbb{N}| le |mathbb{R}|$。

第三步：证明 $|mathbb{R}| le |mathbb{N} imes mathbb{N}|$

这一步通常是通过证明 $|mathbb{R}| le |{0, 1}^{mathbb{N}}|$（即所有由0和1组成的无穷序列的集合）然后证明 $|{0, 1}^{mathbb{N}}| = |{0, 1}^{aleph_0}| = |2^{aleph_0}| = |mathbb{R}|$，最后再结合之前的结论。但是，更直接的方法是证明 $|mathbb{R}| le |mathbb{N} imes mathbb{N}|$。

我们知道实数集合 $mathbb{R}$ 的基数等于 $2^{aleph_0}$。所以，我们实际上是要证明 $aleph_0 le 2^{aleph_0}$ 和 $2^{aleph_0} le aleph_0$，这两者结合起来才能证明等势。
第一步已经证明了 $|mathbb{N} imes mathbb{N}| = aleph_0$。
第二步证明了 $|mathbb{N}| le |mathbb{R}|$，即 $aleph_0 le 2^{aleph_0}$。

现在我们需要证明的是 $|mathbb{R}| le |mathbb{N} imes mathbb{N}|$, 也就是 $2^{aleph_0} le aleph_0$。这显然是不对的。

我在这里稍微修正一下思路。我们要证明的是 $|mathbb{N} imes mathbb{N}| = |mathbb{R}|$.
我们已经证明了：
1. $|mathbb{N} imes mathbb{N}| = aleph_0$
2. $|mathbb{N}| le |mathbb{R}|$, 即 $aleph_0 le 2^{aleph_0}$

现在，我们需要证明的是 $|mathbb{R}| le |mathbb{N} imes mathbb{N}|$, 也就是 $2^{aleph_0} le aleph_0$。
这个方向是不正确的。事实上，我们想要证明的是 $|mathbb{N} imes mathbb{N}| = 2^{aleph_0}$。

让我们换一个角度来证明。我们需要找到一个从 $mathbb{N} imes mathbb{N}$ 到 $mathbb{R}$ 的双射，或者从 $mathbb{R}$ 到 $mathbb{N} imes mathbb{N}$ 的双射。

重新组织证明思路：

我们要证明 $|mathbb{N} imes mathbb{N}| = |mathbb{R}|$.
我们知道 $|mathbb{N} imes mathbb{N}| = aleph_0$.
所以，我们要证明 $|mathbb{R}| = aleph_0$.
这是错误的！ 实数集合的基数是 $2^{aleph_0}$，它比 $aleph_0$ 要大。康托尔对角线证明了实数是不可数的。

因此，原问题陈述“证明阿列夫零上阿列夫零等势于二上阿列夫零”可能存在误解。

“阿列夫零上阿列夫零” 通常是指 $(aleph_0)^{aleph_0}$。
“二上阿列夫零” 是指 $2^{aleph_0}$。

我们实际上是要证明 $(aleph_0)^{aleph_0} = 2^{aleph_0}$.

让我们来证明这一点：

证明 $(aleph_0)^{aleph_0} = 2^{aleph_0}$

首先，我们理解 $(aleph_0)^{aleph_0}$ 的含义。它代表的是所有从自然数到自然数的函数的集合的基数。
也就是 $| ext{Map}(mathbb{N}, mathbb{N}) |$.

我们需要找到一个双射函数，将这样的函数映射到实数或者 $2^{aleph_0}$ 的集合。

1. 证明 $2^{aleph_0} le (aleph_0)^{aleph_0}$

我们需要从实数（或者其子集，比如 $[0, 1]$）找到一个单射到从 $mathbb{N}$ 到 $mathbb{N}$ 的函数集合。
考虑实数在 $[0, 1]$ 区间内的表示。我们可以用二进制小数来表示 $[0, 1]$ 中的实数。例如，$0.101101...$

每个这样的二进制小数都可以看作是一个由0和1组成的无穷序列，例如 $(1, 0, 1, 1, 0, 1, ldots)$。
这样的序列可以被看作是函数 $f: mathbb{N} o {0, 1}$。
例如，序列 $(b_1, b_2, b_3, ldots)$ 可以被看作是函数 $f(n) = b_n$。

这个集合 ${ f: mathbb{N} o {0, 1} }$ 的基数就是 $2^{aleph_0}$。

现在，我们需要一个从 ${ f: mathbb{N} o {0, 1} }$ 到 ${ g: mathbb{N} o mathbb{N} }$ 的单射。
我们可以将一个函数 $f: mathbb{N} o {0, 1}$ 映射到一个函数 $g: mathbb{N} o mathbb{N}$。

一个简单的方法是：
对于任意一个函数 $f: mathbb{N} o {0, 1}$, 定义一个函数 $g_f: mathbb{N} o mathbb{N}$ 如下：
$g_f(n) = f(n) + 1$

这样，对于每个 $f$, 我们得到一个 $g_f$，其值域是 ${1, 2}$。
这个映射 $F: { f: mathbb{N} o {0, 1} } o { g: mathbb{N} o mathbb{N} }$ 定义为 $F(f) = g_f$ 是一个单射。
因为 $F(f_1) = F(f_2)$ 意味着 $g_{f_1} = g_{f_2}$，即 $f_1(n) + 1 = f_2(n) + 1$ 对所有 $n$ 成立，所以 $f_1(n) = f_2(n)$，也就是 $f_1 = f_2$。

因此，我们证明了 $2^{aleph_0} le (aleph_0)^{aleph_0}$.

2. 证明 $(aleph_0)^{aleph_0} le 2^{aleph_0}$

我们需要从从 $mathbb{N}$ 到 $mathbb{N}$ 的函数集合找到一个单射到 $2^{aleph_0}$ 的集合（或者说，到 ${ f: mathbb{N} o {0, 1} }$ 的集合）。

我们知道 $aleph_0$ 等于 $|mathbb{N}|$.
所以 $(aleph_0)^{aleph_0} = |mathbb{N}|^{aleph_0}$.
而 $|mathbb{N}|^{aleph_0}$ 等于 $aleph_0^{aleph_0}$.

现在我们来处理 $aleph_0^{aleph_0}$.
我们可以将自然数集 $mathbb{N}$ 看作是 ${0, 1, 2, ldots }$.
而 ${0, 1, 2, ldots }^{mathbb{N}}$ 代表的是所有从 $mathbb{N}$ 到 ${0, 1, 2, ldots }$ 的函数的集合。

我们需要找到一个单射从 ${ g: mathbb{N} o mathbb{N} }$ 到 ${ f: mathbb{N} o {0, 1} }$.

这个证明的关键在于，我们可以利用一种“编码”技术。
考虑一个函数 $g: mathbb{N} o mathbb{N}$.
我们可以将这个函数的图像 ${ (n, g(n)) mid n in mathbb{N} }$ 进行编码。

一个更直接的方法是利用格奥尔格·康托尔的另一个发现：
我们知道，任意一个自然数 $n$ 可以唯一地分解成质因数。
对于一个函数 $g: mathbb{N} o mathbb{N}$, 我们可以构造一个实数 $x_g in [0, 1]$ 如下：

将质数序列 $p_1=2, p_2=3, p_3=5, ldots$。
对于一个函数 $g$，定义一个无穷序列 $a_n = g(n)$。
然后我们可以考虑序列 $(a_1, a_2, a_3, ldots)$, 其中 $a_n in mathbb{N}$.

为了将其映射到 ${0, 1}$ 的序列，我们需要更精细的编码。
考虑将自然数 $g(n)$ 用质数幂次来编码。
对于函数 $g: mathbb{N} o mathbb{N}$, 我们可以构造一个实数 $x_g$ 如下：
$x_g = sum_{n=1}^{infty} frac{g(n)}{2^{p_n}}$

其中 $p_n$ 是第 $n$ 个质数。
例如：
如果 $g(1)=0, g(2)=1, g(3)=0, g(4)=1, ldots$ (即 $g(n) = (n+1) mod 2$)
那么 $x_g = frac{0}{2^2} + frac{1}{2^3} + frac{0}{2^5} + frac{1}{2^7} + ldots$

这个构造存在一个问题：不同的函数可能映射到同一个实数，因为实数表示的唯一性问题（例如，0.1000... 和 0.0111... 表示同一个数）。不过，我们可以通过使用一个“标准”的表示（例如，避免出现无限个9的表示）来解决。

更关键的是，我们需要一个映射到 ${0, 1}$ 的序列，而这里我们映射到了实数。

让我们回到 $(aleph_0)^{aleph_0} = aleph_0^{aleph_0}$。
我们知道 $aleph_0 = |mathbb{N}|$.
那么 $aleph_0^{aleph_0} = |mathbb{N}|^{aleph_0}$.

我们可以利用一个事实：
对于任意集合 $A$ 和 $B$，如果 $|A| le |B|$, 那么 $|C^A| le |C^B|$.

我们知道 $aleph_0 le 2^{aleph_0}$.
因此，如果我们考虑 $C=aleph_0$, 那么 $aleph_0^{aleph_0} le aleph_0^{2^{aleph_0}}$. 这不是我们想要的。

我们需要证明 $(aleph_0)^{aleph_0} le 2^{aleph_0}$.
这是要证明 $| ext{Map}(mathbb{N}, mathbb{N})| le | ext{Map}(mathbb{N}, {0, 1})|$.

考虑一个函数 $g: mathbb{N} o mathbb{N}$.
我们可以将 $g(n)$ 的值进行编码。
例如，我们知道 $mathbb{N}$ 可以分解为有限个集合的并集（虽然这句有点陈述不清）。

一个更常见的证明方式是：
对于任意一个函数 $g: mathbb{N} o mathbb{N}$, 我们想将其映射到一个二元序列（即 $0$ 或 $1$ 组成的无穷序列）。

我们可以将每个自然数 $k$ 写成二进制：$k = sum_{i=0}^m b_i 2^i$, 其中 $b_i in {0, 1}$.
这个表示是唯一的。

我们可以将函数 $g$ 映射到一个二元序列，但不是直接的。
考虑康托尔配对函数 $J(m, n) = frac{1}{2}(m+n)(m+n+1) + n$.
这个函数将 $mathbb{N} imes mathbb{N}$ 双射到 $mathbb{N}$.

关键的等式是：

$aleph_0^{aleph_0} = (2^{aleph_0})^{aleph_0}$? 不对。
$aleph_0^{aleph_0}$ 是从 $mathbb{N}$ 到 $mathbb{N}$ 的函数的基数。
$2^{aleph_0}$ 是实数的基数。

我们需要证明 $(aleph_0)^{aleph_0} = 2^{aleph_0}$.

我们已经证明了 $2^{aleph_0} le (aleph_0)^{aleph_0}$.

现在证明 $(aleph_0)^{aleph_0} le 2^{aleph_0}$.

我们知道 $aleph_0 le 2^{aleph_0}$.
由于 $aleph_0$ 是无限集合，对于任何无限集合 $X$, 我们有 $|X| le |X imes X|$.
所以 $aleph_0 le aleph_0 imes aleph_0 = aleph_0$.

还有重要的基数性质：
对于任何集合 $A, B$, 如果 $|A| le |B|$, 则 $|2^A| le |2^B|$.
对于任何集合 $A, B$, 如果 $|A| le |B|$, 则 $|C^A| le |C^B|$.

我们有 $aleph_0 le 2^{aleph_0}$.
那么我们应该尝试构造一个从 ${g: mathbb{N} o mathbb{N}}$ 到 ${h: mathbb{N} o {0,1}}$ 的单射。

考虑一个函数 $g: mathbb{N} o mathbb{N}$.
我们可以将其分解为一些“步骤”。

一个非常巧妙的方法是利用施罗德伯恩斯坦定理 (Schröder–Bernstein theorem)。
这个定理说：如果存在从集合 $A$ 到集合 $B$ 的单射，并且存在从集合 $B$ 到集合 $A$ 的单射，那么存在从集合 $A$ 到集合 $B$ 的双射。

我们已经证明了：
1. 存在从 ${ f: mathbb{N} o {0, 1} }$ 到 ${ g: mathbb{N} o mathbb{N} }$ 的单射 (记作 $phi$).
这意味着 $2^{aleph_0} le (aleph_0)^{aleph_0}$.

现在我们需要证明：
2. 存在从 ${ g: mathbb{N} o mathbb{N} }$ 到 ${ f: mathbb{N} o {0, 1} }$ 的单射 (记作 $psi$).
这意味着 $(aleph_0)^{aleph_0} le 2^{aleph_0}$.

如何构造 $psi$?
考虑一个函数 $g: mathbb{N} o mathbb{N}$.
我们可以定义一个函数 $f_g: mathbb{N} o {0, 1}$.
这个映射需要“编码” $g$ 的信息。

构造 $psi$：

我们知道每个自然数 $n$ 可以写成一个唯一的质数幂次乘积：$n = p_1^{a_1} p_2^{a_2} ldots p_k^{a_k}$.
一个函数 $g: mathbb{N} o mathbb{N}$ 给出了一个序列 $(g(0), g(1), g(2), ldots)$.

我们可以尝试将每个 $g(n)$ 的二进制表示拼接起来，形成一个大的二进制序列。
然而，直接拼接可能会导致歧义。例如，如果 $g(0)=1$ (二进制 $1$)， $g(1)=0$ (二进制 $0$)，得到的序列是 $10$.
但如果 $g(0)=10$ (二进制 $1010$)，则得到的序列是 $1010$.

我们需要一种无歧义的编码方式。
考虑对于每一个自然数 $n$, 我们可以将 $g(n)$ 的值编码成一个有限的二元串。
比如，我们可以先编码数字的长度，然后再编码数字本身。

一个标准的方法是使用哥德尔数 (Gödel numbering) 的思想。
对于函数 $g: mathbb{N} o mathbb{N}$, 我们可以定义一个二元序列 $f_g = (b_1, b_2, b_3, ldots)$ 如下：

对于每个 $n in mathbb{N}$, $g(n)$ 是一个自然数。
我们可以将 $g(n)$ 表示成一个二元串。
然后，我们在这些二元串之间插入一个分隔符（例如，一个特定的模式，比如 010101010101...，然后跟随 $g(n)$ 的二进制表示，然后是另一个分隔符）。

例如，如果 $g(0) = 3$ (二进制 11), $g(1) = 5$ (二进制 101), $g(2) = 2$ (二进制 10).
我们可以设计一个编码。

一种更直接的方法是利用康托尔配对函数的性质：
我们知道 $mathbb{N} imes mathbb{N}$ 可以双射到 $mathbb{N}$.
那么 $(mathbb{N} imes mathbb{N})^{mathbb{N}}$ 的基数是什么？

回到 $(aleph_0)^{aleph_0}$.
我们知道 $aleph_0 = |mathbb{N}|$.
$(aleph_0)^{aleph_0} = |mathbb{N}|^{aleph_0}$.
这表示从 $mathbb{N}$ 到 $mathbb{N}$ 的函数的基数。

我们还需要 $aleph_0 le 2^{aleph_0}$ 和 $2^{aleph_0} le aleph_0$. 显然后者不对。

正确的证明思路应该是 $(aleph_0)^{aleph_0} = 2^{aleph_0}$：

1. 证明 $2^{aleph_0} le (aleph_0)^{aleph_0}$ (已完成，通过 $f: mathbb{N} o {0, 1}$ 到 $g(n) = f(n)+1$ 的映射)

2. 证明 $(aleph_0)^{aleph_0} le 2^{aleph_0}$

我们需要证明存在从 ${ g: mathbb{N} o mathbb{N} }$ 到 ${ f: mathbb{N} o {0, 1} }$ 的单射。

考虑一个函数 $g: mathbb{N} o mathbb{N}$.
我们知道 $mathbb{N} = {0, 1, 2, ldots}$.
我们可以将 $mathbb{N}$ 分成偶数和奇数。
$mathbb{N} = E cup O$, 其中 $E = {0, 2, 4, ldots }$ 和 $O = {1, 3, 5, ldots }$.
$|E| = aleph_0$, $|O| = aleph_0$.

我们可以定义一个映射 $psi$ 如下：
对于任意一个函数 $g: mathbb{N} o mathbb{N}$, 我们构造一个函数 $f_g: mathbb{N} o {0, 1}$.
这个映射的目的是将关于 $g$ 的信息编码到 $f_g$ 的值中。

一个标准的构造是：
我们将每个自然数 $n$ 进行质因数分解。
$n = p_1^{a_1} p_2^{a_2} ldots p_k^{a_k}$.

对于函数 $g: mathbb{N} o mathbb{N}$, 定义 $f_g: mathbb{N} o {0, 1}$ 如下：
对于每个 $m in mathbb{N}$, $f_g(m)$ 的值取决于 $g(m)$ 的某些属性。

更简洁且易于理解的证明方式：

我们知道 $mathbb{N}$ 是可数无穷的，可以写成 $mathbb{N} = {0, 1, 2, ldots}$.
我们知道实数集 $mathbb{R}$ 的基数是 $2^{aleph_0}$.
实数集可以通过二进制小数表示。一个在 $[0, 1]$ 的实数可以表示为 $0.b_1 b_2 b_3 ldots$, 其中 $b_i in {0, 1}$.
这个集合的基数是 $2^{aleph_0}$.

证明 $(aleph_0)^{aleph_0} = 2^{aleph_0}$:

我们已经证明了 $2^{aleph_0} le (aleph_0)^{aleph_0}$。

现在证明 $(aleph_0)^{aleph_0} le 2^{aleph_0}$.
我们知道 $aleph_0 = |mathbb{N}|$.
$aleph_0^{aleph_0} = |mathbb{N}|^{aleph_0}$.
这是所有从 $mathbb{N}$ 到 $mathbb{N}$ 的函数的集合的基数。

我们需要找到一个从 ${ g: mathbb{N} o mathbb{N} }$ 到 ${ f: mathbb{N} o {0, 1} }$ 的单射。

考虑一个函数 $g: mathbb{N} o mathbb{N}$.
我们可以将 $g$ 的“值”编码到二元序列中。
例如，我们可以利用哥德尔编码的思想。

我们可以将 $mathbb{N}$ 看作是自然数集合。
而 ${0, 1}^{mathbb{N}}$ 是所有由0和1组成的无穷序列的集合。

一个直接的方法：
将 $mathbb{N}$ 看作是 ${ldots, 2, 1, 0, 1, 2, ldots}$ 的子集。
或者我们直接考虑函数 $g: mathbb{N} o mathbb{N}$.
我们可以将 $mathbb{N}$ 的每一个元素都映射到一个有限的二元串。
例如，$n$ 的二进制表示 $b_k b_{k1} ldots b_1 b_0$.

考虑函数 $g: mathbb{N} o mathbb{N}$.
我们可以将函数 $g$ 映射到一个二元序列 $f_g$ 如下：
对于每一个 $n in mathbb{N}$, 我们将 $g(n)$ 的二进制表示进行编码。
例如，我们可以用一个特定模式来分隔每个 $g(n)$ 的编码。

一个经典的证明是利用有限长度的二元串。
每个自然数 $n$ 都可以唯一地表示为二进制形式：$n = (b_k b_{k1} ldots b_1 b_0)_2$.
这个表示的长度是 $k+1$.

对于函数 $g: mathbb{N} o mathbb{N}$, 我们定义一个二元序列 $f_g$。
为了无歧义地编码 $g(n)$ 的值，我们可以先编码 $g(n)$ 的长度，然后编码 $g(n)$ 本身。
比如，用 $g(n)$ 的长度加一（表示长度的长度）来分隔。

一个更简单的视角：
我们知道 $aleph_0 = |mathbb{N}|$.
我们知道 $2^{aleph_0} = |mathbb{R}|$.
实数在 $[0, 1]$ 区间内的表示，我们可以将其与所有 $0/1$ 无穷序列一一对应。

那么 $(aleph_0)^{aleph_0}$ 是什么？ 是 $mathbb{N}^{mathbb{N}}$ 的基数。
可以证明 $mathbb{N}^{mathbb{N}}$ 和 ${0, 1}^{mathbb{N} imes mathbb{N}}$ 是等势的。
而 ${0, 1}^{mathbb{N} imes mathbb{N}}$ 的基数是 $2^{|mathbb{N} imes mathbb{N}|} = 2^{aleph_0}$.

证明 $mathbb{N}^{mathbb{N}}$ 和 ${0, 1}^{mathbb{N} imes mathbb{N}}$ 等势

1. 证明 $|{0, 1}^{mathbb{N} imes mathbb{N}}| le |mathbb{N}^{mathbb{N}}|$
因为 $|mathbb{N} imes mathbb{N}| = aleph_0$, 所以 ${0, 1}^{mathbb{N} imes mathbb{N}}$ 可以看作是 ${0, 1}^{aleph_0}$ 的集合。
我们知道 $2 le aleph_0$.
对于基数 $a le b$ 和集合 $C$, $|C^a| le |C^b|$.
所以 $|{0, 1}^{aleph_0}| le |{0, 1}^{mathbb{N}}|$. 这似乎也不是正确的方向。

回到核心等式 $(aleph_0)^{aleph_0} = 2^{aleph_0}$

我们已经证明了 $2^{aleph_0} le (aleph_0)^{aleph_0}$.

证明 $(aleph_0)^{aleph_0} le 2^{aleph_0}$:
考虑函数 $g: mathbb{N} o mathbb{N}$.
我们可以将 $mathbb{N}$ 看作是所有 $0/1$ 的有限序列的集合（二进制表示）。
每个自然数 $n$ 都有一个唯一的二进制表示，例如 $n = (b_k b_{k1} ldots b_0)_2$.

我们可以定义一个映射 $psi$ 如下：
对于每一个函数 $g: mathbb{N} o mathbb{N}$, 我们构造一个函数 $f_g: mathbb{N} o {0, 1}$.
这个映射 $psi: mathbb{N}^{mathbb{N}} o {0, 1}^{mathbb{N}}$ 是一个单射。

构造 $psi$ 的关键在于编码 $g(n)$ 的信息：
我们将自然数 $g(n)$ 的二进制表示，然后用一个特殊的模式（比如一串0）来分隔，然后是下一个 $g(n+1)$ 的二进制表示，以此类推。
例如，如果 $g(0) = 3$ (二: $11$), $g(1) = 5$ (二: $101$).
我们可以构造一个二元序列：$110010100ldots$
这里用两个0来分隔每个 $g(n)$ 的二进制表示。
例如：$g(0)$ 的二制表示，后跟两个0，然后是 $g(1)$ 的二制表示，后跟两个0，……

这个编码是无歧义的。任何一个以这种方式构造的二元序列，我们都可以唯一地将其解析回一个函数 $g: mathbb{N} o mathbb{N}$.
例如，我们从序列的开头开始，读取二进制数字，直到遇到两个0。这个数字就是 $g(0)$。然后我们继续从两个0之后读取下一个数字，直到再次遇到两个0，这就是 $g(1)$，以此类推。

这个映射 $psi$ 将每一个 $g in mathbb{N}^{mathbb{N}}$ 映射到一个唯一的 $f_g in {0, 1}^{mathbb{N}}$.
所以 $psi$ 是一个单射。

因此，我们证明了 $(aleph_0)^{aleph_0} le 2^{aleph_0}$.

总结：
我们已经证明了：
1. $2^{aleph_0} le (aleph_0)^{aleph_0}$
2. $(aleph_0)^{aleph_0} le 2^{aleph_0}$

根据施罗德伯恩斯坦定理，我们可以得出结论：
$(aleph_0)^{aleph_0} = 2^{aleph_0}$.

也就是，“阿列夫零上阿列夫零”等势于“二上阿列夫零”。

这里的关键在于理解符号的含义以及如何利用基数运算的性质和编码技巧来构造单射和利用定理。
“阿列夫零上阿列夫零”是指所有从自然数到自然数的函数的集合的基数，即 $|mathbb{N}^{mathbb{N}}|$.
“二上阿列夫零”是指所有从自然数到 ${0, 1}$ 的函数的集合的基数，即 $|{0, 1}^{mathbb{N}}|$, 这也是实数集合的基数 $|mathbb{R}|$.

整个证明的核心是通过构造一个将“从 $mathbb{N}$ 到 $mathbb{N}$ 的函数”编码为“从 $mathbb{N}$ 到 ${0, 1}$ 的函数（或序列）”的单射来实现。

一方面由 得到

另外一方面由 得到