6

回想一下，K 组合子是一个常数函数。它总是返回它的第一个参数：

Kxy = x for all y

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

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

假设森林由三只鸟 A、B 和 C 组成。是否有可能至少有一只鸟表现得像 K 组合子？

下表显示了魔法森林中鸟类可能的一组行为。第一列是森林中每只鸟的名字。最上面一行有可以叫到每只鸟的名字。身体是鸟对名字的反应。例如，如果你向鸟 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 组合子。我希望你能证明我错了。

4

2 回答 2

1

你是对的。任何大于 1 的有限数量的鸟都是不可能的。

简单的论点是，如果有这样一只鸟 K，K 的形象中的每只鸟都将是常数（根据定义），并且每只鸟都将在 K 的形象中（通过基数论证），包括 K 本身，即显然是非恒定的。

于 2012-06-04T05:49:14.740 回答
1

我喜欢心理法官的回答，所以对于那些有问题的人，我会详细说明。

令 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 必须有一个左逆。

于 2012-06-06T06:56:51.593 回答