如何在魔法森林中創建K combinator？ （模擬一隻知更鳥）

Question

回想一下K組合函數是一個常量函數。它總是返回第一個參數：

Kxy = x for all y 

在書中嘲笑一隻知更鳥作者提出含說話的鳥兒的魔法森林的一個例子。這些鳥的行爲如下：

給定鳥類A和鳥類B，如果你將B的名字叫做A，那麼A將通過向你呼叫某隻鳥的名字作出迴應：這隻鳥我們將由AB指定。

假設森林由三隻鳥類A，B和C組成。是否有可能至少有一隻鳥的行爲像K combinator？

下面是一個表格，顯示了一個可能的一組可能的行爲，用於迷人森林中的鳥類。第一欄有森林裏每隻鳥的名字。最上面一行的名字可能會被呼叫給每隻鳥。身體是鳥類對名稱的迴應。例如，如果您向鳥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然後Ay的值必須是下所有的Y，這顯然是 假。因此A不能是空槽的正確值。

• 如果AC = B，則對於所有y，By的值必須是C，這顯然是 false。因此B不能是空槽的正確值。

• 如果AC = C，則對於所有y，Cy的值必須是C，這顯然是錯誤的 。因此C不能是空槽的正確值。

因此，對於每個y，沒有值可以置於空槽中以滿足條件（AC）y = C。

據我所知，這是不可能的，使任何鳥類行爲像一個K combinator。我希望你能證明我錯了。

Answer 1

我喜歡Judge 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必須有一個左逆。

Answer 2

你是對的。對於任何有限數量的大於1的鳥是不可能的。

簡單的說法是，如果有這樣一隻鳥K，那麼K圖像中的每隻鳥將是恆定的（根據定義），並且每隻鳥都將以K的形象出現（通過基數論證），包括K本身，這顯然是不恆定的。