lambda - 如何在魔法森林中创建K组合器？ ( mock 一只知更鸟)

Question

回想一下，K 组合器是一个常数函数。它总是返回其第一个参数:

Kxy = x for all y

在《模仿一只知更鸟》一书中，作者展示了一个包含会说话的鸟儿的魔法森林的例子。鸟儿有以下行为:

给定任何鸟 A 和 B，如果你向 A 喊出 B 的名字，那么 A 会向你喊出某种鸟的名字来回应:我们将用 AB 来指定这只鸟。

假设森林由三只鸟 A、B 和 C 组成。是否有可能至少其中一只鸟的行为类似于 K 组合器？

下表显示了魔法森林中鸟类的一组可能的行为。第一列有森林中每只鸟的名字。最上面一行有每只鸟的名字。 body 是鸟儿对名字的 react 。例如，如果你对鸟 A 喊出 A 的名字，那么鸟 A 就会用 C 来回应(见第 2 行第 2 列)。简而言之，AA = C。如果你对鸟 A 喊出 B 的名字，那么鸟 A 就会用 B 来回应(见第 2 行第 3 列)。简而言之，AB = B。AC 的空槽应填入什么值？

   | A    B    C
------------------
A  | C    B
B  | B    B    B
C  | A    A    A

让我们看看是否能让鸟 A 表现得像 K 组合器。上述一组值看起来很有希望:

• 对于所有 y，AA = C 且 Cy = A。也就是说，对于所有 y，(AA)y = A。

• 对于所有 y，AB = B 且 By = B。也就是说，对于所有 y，(AB)y = B。

空槽(AC)中应该放置什么值？考虑所有情况:

• 如果 AC = A，则对于所有 y，Ay 的值必定为 C，这显然是 错误的。因此 A 不可能是空槽的正确值。

• 如果 AC = B，则对于所有 y，By 的值必定为 C，这显然是 错误的。因此 B 不可能是空槽的正确值。

• 如果 AC = C，则对于所有 y，Cy 的值必定为 C，这显然是 错误的。因此，C 不可能是空槽的正确值。

因此，对于每个 y，空槽中不能放置任何值来满足条件 (AC)y = C。

据我所知，不可能让任何鸟表现得像 K 组合器。我希望你能证明我错了。

Answer 1

我喜欢 Mental 法官的回答，因此对于那些无法理解的人，我会详细说明。

<小时/>

设 G 为所有函数的集合。

令 F 为子集 G，使得 |F| > 1 且 ∀f ∈ F (f : F → F)。 (F 是您的鸟组。)

设 1_F 为 F 的恒等函数。

假设矛盾存在∃k ∈ F (∀(f,g) ∈ (F×F) (kfg = f))。修复这样一个k。换句话说，∀f ∈ F(kf 是常数)。根据定义，∀f ∈ F (kkf = k)。所以 ∀f ∈ F(kf = 1_F 因为 k 有一个由下面的引理得出的左逆)。因此我们有 ∀f ∈ F(kf 是常数并且 kf = 1_F)，这显然是荒谬的，因为 |F| > 1.

引理: 令 (f,g) ∈ (F×F) 使得 kf = kg。根据 k 的定义，∀h ∈ F (kfh = f)。所以 ∀h ∈ F (f = kfh = (kf)h = (kg)h = kgh = g)。这只有在 f = g 时才会发生。因此 k 单射。因此 k 必须有一个左逆。