Как создать K комбинатор в заколдованном лесу? (Издеваться над пересмешником)

Напомним, что комбинатор K является постоянной функцией. Он всегда возвращает свой первый аргумент:

Kxy = x for all y

В книге " Чтобы издеваться над пересмешником" автор представляет пример заколдованного леса с говорящими птицами. Птицы имеют поведение:

Если для любых птиц A и B вы назовете имя B на A, то A ответит, назвав вам имя какой-нибудь птицы: эту птицу мы обозначим AB.

Предположим, что лес состоит из трех птиц, A, B и C. Может ли хотя бы одна из птиц вести себя как комбинатор K?

Ниже приведена таблица, в которой показан один из возможных вариантов поведения птиц в заколдованном лесу. В первом столбце есть название каждой птицы в лесу. В верхнем ряду есть имена, которые могут быть вызваны для каждой птицы. Тело - это ответ птицы на имя. Например, если вы называете имя А птице А, тогда птица А ответит буквой С (см. Строку 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

Давайте посмотрим, сможем ли мы заставить птицу А вести себя как комбинатор К. Приведенный выше набор значений выглядит многообещающе:

  • AA = C и Cy = A для всех y. То есть (AA)y = A для всех y.

  • AB = B и By = B для всех y. То есть (AB)y = B для всех y.

Какое значение следует поместить в пустой слот (AC)? Рассмотрим все случаи:

  • Если AC = A, то значение Ay должно быть C для всех y, что явно ложно. Поэтому A не может быть правильным значением для пустого слота.

  • Если AC = B, то значение By должно быть C для всех y, что явно неверно. Поэтому B не может быть правильным значением для пустого слота.

  • Если AC = C, то значение Cy должно быть C для всех y, что явно неверно. Поэтому C не может быть правильным значением для пустого слота.

Поэтому никакое значение не может быть помещено в пустой слот, чтобы удовлетворять условию (AC)y = C, для каждого y.

Насколько я могу судить, невозможно заставить любую птицу вести себя как комбинатор К. Я надеюсь, что вы докажете, что я неправ.

Источник

2 ответа

Решение

Мне нравится ответ судьи Ментала, поэтому для тех, у кого возникли проблемы с его получением, я изложу его подробнее.

Пусть G - множество всех функций.

Пусть F подмножество G такое, что |F| > 1 и ∀f ∈ F (f: F → F). (F ваш набор птиц.)

Пусть 1F - единичная функция F.

Предположим для противоречия, что существует ∈k ∈ F (∀(f,g) ∈ (F×F) (kfg = f)). Исправить такой к. Другими словами, ∀f ∈ F (kf постоянна). По определению ∀f ∈ F (kkf = k). Таким образом, ∈f ∈ F (kf = 1F, так как k имеет левый обратный по лемме ниже). Таким образом, имеем ∀f ∈ F (kf постоянна и kf = 1F), что явно абсурдно, потому что |F| > 1.

Лемма. Пусть (f, g) ∈ (F × F) такое, что kf = kg. По определению k ∀h ∈ F (kfh = f). Итак, ∈h ∈ F (f = kfh = (kf) h = (кг) h = kgh = g). Это может произойти, только если f = g. Таким образом, k инъективно. Таким образом, k должно иметь левое обратное.

Источник

Ты прав. Это невозможно для любого конечного числа птиц больше 1.

Простой аргумент состоит в том, что если бы существовала такая птица K, каждая птица в изображении K была бы постоянной (по определению), и каждая птица была бы в изображении K (по аргументу мощности), включая саму K, которая является очевидно непостоянный.

Источник
Другие вопросы по тегам