自然数的表示

在 λ-Calculus 中表示自然数的方法并不唯一，其中我最喜欢的还是 Church 本人提出的 Church Encoding。

书接上文，在 λ-Calculus 我们当然是使用函数来表示自然数。而要使用函数表达式来表示某个数量的特征，有一个非常简洁的想法：多次复合该函数。

在大家已经熟悉 λ 之后，我们就没必要藏着掖着了，大家不妨先感受一下 $0, 1, 2, 3, 4$ 对应的 λ 表达式：

Zero = λf.λx.x

One = λf.λx.f x

Two = λf.λx.f (f x)

Three = λf.λx.f (f (f x))

Four = λf.λx.f (f (f (f x)))

简单来说，自然数 $n$ 对应的 λ 表达式相当于接受两个变量 f 和 x，然后将 f 复合 $n$ 次应用在 x 上。

皮亚诺公理

这时我们先打断一下，引入另一个话题。自然数是如何定义的呢？

皮亚诺用五条公理给出了一个归纳的定义，我们可以用下面两条规则来概括：

1. $0$ 是自然数。
2. 如果 $x$ 是自然数，那么 $x$ 的后继也是自然数。

TIP

什么是 $x$ 的后继呢？其实就是 $x + 1$。但是要注意的是，在定义自然数以前，我们没有关于加法的定义！因此我们不能使用加法来定义自然数。

加法的运算规则是依赖自然数而定义的，这会在后文讲到。

其实按照这样的规则，$1$ 表示的是 $0$ 的后继，$2$ 表示的是 $0$ 的后继的后继，以此类推。只不过这样说太麻烦，所以我们就采用阿拉伯数字和十进制表示来代替。

自然数的 Church Encoding

仿照皮亚诺公理，在 λ-Calculus 中我们首先给出 $0$ 的定义：

O = λf.λx.x

接下来我们给出后继（successor）的定义：

S = λn.λf.λx.f (n f x)

这个表达式可以看作 λn. (λf. λx. f (n f x))，它首先接受一个参数 n，表示一个自然数。 而将 n 带入后得到的结果，也就是后面括号里的表达式，显然也满足自然数的形式。

我们说 n 相当于接受两个变量 f 和 x，然后将 f 复合 $n$ 次应用在 x。 那么 f (n f x) 就相当于，在 $f(f(\cdots f(x)\cdots))$（$n$ 个 $f$）外面再套一层 $f$，也就变成了 $n + 1$ 对应的 λ。

于是，皮亚诺公里在 λ-Calculus 的形式如下：

1. O 是自然数。
2. 若 n 是自然数，那么 S n 也是自然数。

遵循这样定义的自然数也被称作邱奇数。 不妨试试化简下面的表达式：

化简顺序

你可能会注意到，我们有很多不同的化简顺序。在这里我推荐两种方式，都具有一定的启发意义：

1. 从外向内：首先化简为 S Two，然后保持 Two 不动把其他部分全部展开化简。然后展开 Two，保持 One 不动把其他部分化简，以此类推。
2. 从内向外：先化简为 S (S (S O))，然后先展开 O，再从最里面的 S 开始一个一个展开。

你可以以任意的顺序化简，最终的结果都是一样的。

重回小学一年级

学会了自然数，我们就可以学习加法了！

假设我们现在拿到了两个邱奇数 n 和 m，如何构造 $n + m$ 呢？很自然的想法是，在 m f x 的外面再套上 $n$ 个 f，而这恰好就是 n f 的含义，于是我们就写出了加法的定义：

Plus = λn.λm.λf.λx.n f (m f x)

后面的 λf.λx.n f (m f x) 代表的就是 $n + m$ 的邱奇数。尝试化简以下表达式：

可以发现，加法操作是基于邱奇数定义的，而邱奇数定义的核心就是 $0$——第一个自然数，和后继——自然数的归纳构造，相当于 $+1$。

加法就是由不断的 $+1$ 构成的。

重回小学二年级

学会了加法，我们就可以学习乘法了！

如何定义 $n \times m$？我们可以用加法来定义：$n \times m$ 等于 $n$ 个 $m$ 相加。 也就是说，我们对 $0$ 进行 $n$ 次的 $+m$，就得到了 $n\times m$。 对应到邱奇数上，$n\times m$ 对应的邱奇数是将 $f$ 复合 $n\times m$ 次应用于 $x$。

• 将 $f$ 复合 $m$ 次对应的 λ 是 m f。
• 将 “$f$ 复合 $m$ 次” 复合 $n$ 次对应的 λ 是 n (m f)。

于是我们就可以写出乘法的定义：

Mul = λn.λm.λf.λx.n (m f) x

尝试化简以下表达式：

重回小学三年级

学会了乘法，我们就可以学习乘方了！尝试理解下面乘方的表达式：

Exp = λn.λm.n (Mul m) One

并化简以下表达式：

自然之道

其实当我自己在学习 λ-Calculus 的这部分内容时，总是被它既玄妙却又浅显的矛盾感一次次震撼。写下来的 λ 表达式仅仅只由三条规则支配，但却似乎可以代表一切。

表示自然数的方法有很多。比如我们可以仿照现代计算机的硬件，采用二进制的方式，这种表示同样只由一组进位规则支配，也可以做到很简洁，但是它不够“自然”。我想，自然数成为一个抽象的，公认的数学概念，起源于当人们想要表示某种事物的数量。对于当时的古人，他们不关心进制，不关心推导，他们只想写下不同的符号，代表不同的数量，也因此自然数本身没有别的深意。它本身的存在性就是它的意义。

λ-Calculus 中，函数为第一要义。我们不会采用不同的符号代表自然数，因为符号始终有限。我们需要一种记号，一种媒介，使得我们能够基于简单的表达式定义，刻画出一种逻辑上“自然”的表示方法。而函数的复合（也就是“应用”）做为函数最基本的组合方式，也是 λ-Calculus 中函数唯一的组合方式（“抽象” 是函数的构造方式），成为了唯一的选择。很自然地想到，复合的次数对应了我们想表示的数量。至于将什么带入这个表达式，并不重要，给它取一个名字叫做 x 就可以了。

在 λ-Calculus 的世界里，与其说邱奇数是在表示某种东西的数量，不如说邱奇数是在表示多次进行某个相同的操作（可以理解为运算，变换等）。不要忘了，自然数的后继 S 本身也是一个函数！也就是说，一个邱奇数 n 的构造过程实际上是对 O 求 $n$ 次后继。

使用 Church Encoding 表述这句话，将会是：n S O。

尝试化简以下表达式，看看结果和 Three 本身有什么关系：

直觉上，如果我们说 A 可以做到 B，那么潜台词就是：A 不仅仅能做到 B，它能做的事比 B 更多。

n S O 仿佛是在说，一个邱奇数可以自己构造自己。n 可以将任何函数复合 $n$ 次应用到某个变量 $x$ 上，那么 n 能做的事绝不仅仅是像上面这样构造邱奇数。不要忘了，加法、乘法和乘方的定义，都用到了邱奇数的性质，它可以成为更多概念的基点。

另一方面，直觉上，如果我们说 B 代表的事情就是 A 能做的事情，那么我们认为 A 做到的事情不可能比 B 多。

邱奇数，它是 λ-Calculus 中的自然数。它一开始存在的意义是什么？不妨回去看看引言中的最后一句话： “简单来说，自然数 $n$ 对应的 λ 表达式相当于接受两个变量 f 和 x，然后将 f 复合 $n$ 次应用在 x 上。” 因此，n 只是一个邱奇数。它能做的事被邱奇数的概念完全包含在内。

于是我们得到的结果是 A=B。邱奇数=邱奇数。它能做的所有事构成了它本身的概念。

还有什么能比这样的存在更“自然”呢？