如何在魔法森林中创建一个K组合器？(模拟一只知更鸟)

Question

回想一下,K组合器是一个常数函数.它总是返回它的第一个参数:

Kxy = x for all y

在To Mock a Mockingbird这本书中,作者提供了一个含有说话鸟类的魔法森林的例子.这些鸟有行为:

鉴于任何鸟类A和B,如果您将B的名称称为A,那么A将通过向您呼叫某只鸟的名称来回应:这只鸟我们将由AB指定.

假设森林由三只鸟A,B和C组成.至少有一只鸟可能像K组合一样吗？

下面的表格显示了魔法森林中鸟类的一组可能行为.第一列包含森林中每只鸟的名称.顶行的名称可以调用每只鸟.身体是鸟对名字的反应.例如,如果您将A的名称称为鸟A,则鸟A将以C响应(请参阅第2行第2列).简洁地说,AA = C.如果你把B的名字叫做鸟A,那么鸟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 法官的回答，所以对于那些无法理解的人，我会详细说明。

\n\n\n\n

令 G 为所有函数的集合。

\n\n

令 F 为子集 G，使得 |F| > 1 和 \xe2\x88\x80f \xe2\x88\x88 F (f : F \xe2\x86\x92 F)。（F 是你的鸟组。）

\n\n

让_1F为 F 的恒等函数。

\n\n

假设有一个矛盾 \xe2\x88\x83k \xe2\x88\x88 F (\xe2\x88\x80(f,g) \xe2\x88\x88 (F\xc3\x97F) (kfg = f)) 。修复这样一个k。换句话说，\xe2\x88\x80f \xe2\x88\x88 F（kf 是常数）。根据定义，\xe2\x88\x80f \xe2\x88\x88 F (kkf = k)。所以 \xe2\x88\x80f \xe2\x88\x88 F （kf = 1 _F因为 k 通过下面的引理有一个左逆）。因此我们有 \xe2\x88\x80f \xe2\x88\x88 F （kf 是常数并且 kf = 1 _F），这显然是荒谬的，因为 |F| > 1.

\n\n

引理：\n设 (f,g) \xe2\x88\x88 (F\xc3\x97F) 使得 kf = kg。根据 k 的定义，\xe2\x88\x80h \xe2\x88\x88 F (kfh = f)。所以 \xe2\x88\x80h \xe2\x88\x88 F (f = kfh = (kf)h = (kg)h = kgh = g)。这只有在 f = g 时才会发生。因此 k 单射。因此 k 必须有一个左逆。

\n