Jak stworzyć kombinator K w zaczarowanym lesie? (Aby wyśmiać przedrzeźniacz)

Question

Przypomnij sobie, że kombinator K jest stałą funkcją. To zawsze wraca swój pierwszy argument:

Kxy = x for all y 

W książce drwić drozda autor przedstawia przykład zaczarowanym lesie zawierającym ptaki rozmawiają. Ptaki mają zachowanie:

Biorąc pod uwagę wszystkie ptaki A i B, jeśli wywołasz imię B do A, wtedy A odpowie, wytykając ci imię jakiegoś ptaka: ten ptak zostanie oznaczony przez AB.

Załóżmy, że las składa się z trzech ptaków: A, B i C. Czy przynajmniej jedno z ptaków zachowuje się jak kombinator K?

Poniżej znajduje się tabela przedstawiająca możliwy zestaw zachowań ptaków w zaczarowanym lesie. Pierwsza kolumna ma nazwę każdego ptaka w lesie. Górny rząd ma nazwy, które mogą być wywołane do każdego ptaka. Ciało jest odpowiedzią ptaka na imię. Na przykład, jeśli wywołasz nazwę A do ptaka A, ptak A odpowie C (patrz wiersz 2, kolumna 2). Zwięźle, AA = C. Jeśli wywołasz nazwę B do ptaka A, ptak A odpowie odpowiedzią B (patrz wiersz 2, kolumna 3). Zwięźle, AB = B. Jaką wartość powinien przejść do pustego gniazda AC?

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

Zobaczmy, czy możemy sprawić, by ptak A zachowywał się jak kombinator K. Powyższy zestaw wartości wygląda obiecująco:

• AA = C i Cy = A dla wszystkich y. To znaczy (AA) y = A dla wszystkich y.

• AB = B i By = B dla wszystkich y. Oznacza to, że (AB) y = B dla wszystkich y.

Jakie wartości powinny być umieszczone w pustym gnieździe (AC)? Rozważyć wszystkie przypadki:

• Jeśli AC = A wtedy wartość Ay C musi być dla wszystkich y, która jest wyraźnie fałszywe. Dlatego A nie może być poprawną wartością pustego gniazda.

• Jeśli AC = B, wówczas wartość By musi być C dla wszystkich y, co jest oczywiste, że fałsz. Dlatego B nie może być poprawną wartością pustego gniazda.

• Jeśli AC = C, wartość Cy musi być równa C dla wszystkich y, co jest oczywiste, że fałsz. Dlatego C nie może być poprawną wartością pustego gniazda.

Dlatego żadna wartość nie może być umieszczona w pustym gnieździe, aby spełnić warunek (AC) y = C, dla każdego y.

O ile wiem, niemożliwe jest, aby jakikolwiek ptak zachowywał się jak kombinator K. Mam nadzieję, że mi się nie uda.

Answer 1

Ja lubię odpowiedź sędziego Mental, więc dla tych, którzy mają problemy z jej uzyskaniem, będę pisał dalej.

---

Niech G będzie zbiorem wszystkich funkcji.

Niech F będzie podzbiorem G takim, że | F | > 1 i ∀f ∈ F (f: F → F). (F odbiornik ptaków).

Niech 1 _F być funkcja tożsamości F.

Załóżmy sprzeczności że ∃k ∈ F (∀ (F, G) ∈ (F x F) (kfg = f)). Napraw takie k. Innymi słowy, ∀f ∈ F (kf jest stałe). Z definicji ∀f ∈ F (kkf = k). Tak więc ∀f ∈ F (kf = 1 _F, ponieważ k ma lewą odwrotność według Lemma poniżej). Tak więc mamy ∀f ∈ F (kf jest stała i kf = 1 _F), co jest ewidentnie absurdalne, ponieważ | F | > 1.

Lemma: Niech (f, g) ∈ (F × F) takie, że kf = kg. Z definicji k, ∀h ∈ F (kfh = f). Więc ∀h ∈ F (f = kfh = (kf) h = (kg) h = kgh = g). Może się to zdarzyć tylko wtedy, gdy f = g. Tak więc k iniekcyjne. Zatem k musi mieć lewą odwrotność.

Answer 2

Masz rację. Niemożliwa jest skończona liczba ptaków większa niż 1.

Prostym argumentem jest to, że gdyby był taki ptak K, każdy ptak na obrazku K byłby stały (z definicji), a każdy ptak byłby na obrazku K (argumentem liczności), w tym K sam w sobie, co oczywiście jest niestałe.