WikiDer > Система U

System U

В математическая логика, Система U и Система U находятся системы чистого типа, т.е. особые формы типизированное лямбда-исчисление с произвольным количеством сортирует, аксиомы и правила (или зависимости между сортами). Оба они оказались несостоятельными. Жан-Ив Жирар в 1972 г.[1] Этот результат привел к осознанию того, что Мартин-Лёфоригинальный Теория типов 1971 года был непоследователен, поскольку допускал то же поведение «Тип в типе», которое использует парадокс Жирара.

Формальное определение

Система U определена[2]:352 как система чистого типа с

  • три сортирует ;
  • две аксиомы ; и
  • пять правил .

Система U определяется так же, за исключением правило.

Сорта и условно называются «Тип» и «вид", соответственно; вид не имеет конкретного названия. Две аксиомы описывают содержание типов в видах () и виды в (). Интуитивно сортировки описывают иерархию в природа условий.

  1. Все значения имеют тип, например базовый тип (например читается как «б является логическим ») или (зависимым) типом функции (например читается как «ж является функцией от натуральных чисел до логических »).
  2. это разновидность всех таких типов ( читается как «т это тип »). Из мы можем создать больше терминов, например какой своего рода унарных операторов уровня типа (например читается как «Список - функция от типов к типам », то есть полиморфный тип). Правила ограничивают то, как мы можем формировать новые виды.
  3. есть разновидность всех таких ( читается как «k вид »). Точно так же мы можем построить связанные термины в соответствии с тем, что позволяют правила.
  4. это разновидность всех таких терминов.

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

Парадокс Жирара

Определения систем U и U разрешить назначение полиморфный виды к универсальные конструкторы по аналогии с полиморфными типами термов в классических полиморфных лямбда-исчислениях, таких как Система F. Примером такого универсального конструктора может быть[2]:353 (куда k обозначает переменную типа)

.

Этого механизма достаточно, чтобы построить терм с типом , откуда следует, что каждый тип обитаемый. Посредством Переписка Карри – Ховарда, это эквивалентно доказуемости всех логических предложений, что делает систему непоследовательной.

Парадокс Жирара это теоретико-типичный аналог Парадокс Рассела в теория множеств.

Рекомендации

  1. ^ Жирар, Жан-Ив (1972). "Interprétation fonctionnelle et Élimination des coupures de l'arithmétique d'ordre supérieur" (PDF). Цитировать журнал требует | журнал = (помощь)
  2. ^ а б Соренсен, Мортен Гейне; Уржичин, Павел (2006). «Системы чистых типов и лямбда-куб». Лекции об изоморфизме Карри – Ховарда. Эльзевир. ISBN 0-444-52077-5.

дальнейшее чтение