Нет наивных множеств Теоретические модели полиморфного лямбда-исчисления?

В статье Филиппа Уодлера о теоремах для свободного он утверждает в разделе 2 о параметричности, что

нет наивных теоретико-множественных моделей полиморфного лямбда-исчисления

В наивной теоретико-множественной модели типы - это множества, а функции - теоретико-множественные функции, что представляется разумным. Так почему же он говорит, что нет наивных теоретико-множественных моделей полиморфного лямбда-исчисления?

functional-programming MK
источник

Хорошо, я только что наткнулся на этот документ: hal.inria.fr/inria-00076261/document . Мне придется пахать через это.

Эта статья Рейнольдса действительно подходит для чтения! Опуская много деталей, это подводит итог: рассмотреть data T = K ((T -> Bool) -> Bool). Тогда Tи ((T->Bool)->Bool)изоморфны. Если у них есть заданная модель, в которой ->обозначено пространство функций (как множество), последний имеет большую мощность, поэтому он не может быть изоморфен T. Итак, в модели нам нужно интерпретировать по- ->разному - например, как пространство непрерывных функций.

Чи

Я ответил слишком быстро и ответил на неправильный вопрос. Прости за это. Причина, по которой полиморфное лямбда-исчисление не имеет модели в наивной теории множеств, по-видимому, несколько отличается от той, которая существует для нетипизированного лямбда-исчисления.

Ответы:

Стандартная ссылка, которую вы ищете, - это действительно полиморфизм Рейнольда, а не теория множеств . Хотя совершенно очевидно, что вы не можете сформировать, например, произведение на все множества с использованием обычного теоретического произведения множеств, это законный и нетривиальный вопрос о том, есть ли более слабый Понятие продукта, который будет работать, сохраняя при этом обычный двоичный продукт и функциональное пространство . $\Pi_{S\in\mathrm{Set}}S$ $\times$ $\rightarrow$

Это также оказывается невозможным, так как, с одной стороны, довольно просто построить тип так, чтобы интерпретация имела как минимум 2 элемента, и показать, что интерпретация изоморфен , что невозможно для обычной интерпретации обычным канторским парадоксом. В этом смысле оно несколько похоже на доказательство для нетипизированного исчисления. $\bf 2$ $T=\Pi_X(X\rightarrow {\bf 2})\rightarrow{\bf 2}$ $(T\rightarrow {\bf 2})\rightarrow {\bf 2}$ $\rightarrow$

Отметим, что в следующей статье Эндрю Питтса « Полиморфизм теории множеств» конструктивно несколько опровергает этот вывод, показывая, что указанное противоречие возможно построить только в классической теории множеств и что существует несколько конструктивных теорий множеств, в которых полиморфизм может интерпретироваться с обычными интерпретациями пространств функций и произведений. В частности, эти «большие продукты» существуют в «Эффективных топосах», наиболее полное из представлений, которые дает Фоа .

Коди
источник