Я читаю книгу HoTT, и мне тяжело с индукцией пути.
Когда я смотрю на тип в разделе 1.12.1 : у меня нет проблем с пониманием того, что это значит (я просто написал тип из памяти, чтобы проверить это).
У меня возникла следующая проблема:
Мое первое впечатление состояло в том, что это последнее выражение не определяет результирующую функцию
а просто заявляет ее недвижимость .
Это в отличие от предыдущих примеров принципов индукции , или \ text {ind} _ \ mathbb {N} - там являются определение уравнения для этих элементов - мы на самом деле знаем , как построить результирующую функцию, учитывая помещение. Что согласуется с «конструктивностью» теории типов, изложенной в этой главе.
Возвращаясь к , я с подозрением отнесся к тому факту, что (похоже) он не определен. Заявление о том, что элемент просто существует, казалось, не соответствует остальной части главы. И действительно, раздел 1.12.1, кажется, подчеркивает, что мое впечатление неверно, и мы на самом деле определили
... функция F: \ prod_ {х, у: А} \ prod_ {р: х = _Ay} С (х, у, р), определяется индукцией пути из C: \ prod_ {х: A} C ( x, x, \ text {refl} _x) , который, кроме того, удовлетворяет f (x, x, \ text {refl} _x): \ эквивалент c (x) ...
Это оставляет меня в замешательстве, но я чувствую, что этот момент очень важен для всех дальнейших событий. Так с каким из двух чтений для я должен идти? Или, возможно, мне не хватает какой-то важной тонкости, и ответ «нет»?
Ответы:
Это иллюзия, что правила вычислений «определяют» или «конструируют» объекты, о которых они говорят. Вы правильно заметили, что уравнение для не «определяет» его, но не заметило, что то же самое верно и в других случаях. Рассмотрим принцип индукции для единицы типа , который представляется особенно явно «детерминированным». В соответствии с разделом 1.5 книги HoTT у нас есть с уравнение Это "определить" или "построить"ind=A 1
Разве это не тот случай, когда каждый замкнутый член типа существу равен ? На самом деле это зависит от неприятных деталей и сложных доказательств нормализации. В случае HOTT ответ «нет» , потому что е не может содержать экземпляры унивалентностью Axiom, и это не ясно , что делать , чтобы об этом (это открытая проблема в HOTT).e 1 ⋆ e
Мы можем обойти проблемы с univalance, рассматривая вариант теории типа , который действительно имеет хорошие свойства , так что каждые замкнутые термы типа является субъективно равны ⋆ . В этом случае было бы справедливо сказать , что мы действительно знаем , как вычислить с I п д 1 , но:1 ⋆ ind1
То же самое будет иметь место для типа идентичности, потому что каждый замкнутый член типа идентичности будет равняться субъективно некоторой , и так , то уравнение для я п д = будет сказать нам , как вычислить.refl(a) ind=A
Просто потому, что мы знаем, как вычислять с закрытыми членами типа, это не значит, что мы на самом деле что-то определили, потому что есть нечто большее, чем тип с закрытыми членами , как я пытался объяснить однажды.
Например, теорию типа Мартин-Лёф (без типов идентичности) можно интерпретировать домен теоретически таким образом , что содержит два элемента ⊥ и ⊤ , где ⊤ соответствует к ⋆ и ⊥ к не-прекращению. Увы, поскольку в теории типов нет способа записать не заканчивающееся выражение, ⊥ не может быть названо. Следовательно, уравнение для я п d 1 ничего не говорят нам , как вычислить на ⊥ (два очевидных варианта бытия «охотно» и «ленивую»).1 ⊥ ⊤ ⊤ ⋆ ⊥ ⊥ ind1 ⊥
С точки зрения разработки программного обеспечения, я бы сказал, у нас есть путаница между спецификацией и реализацией . Аксиомы HoTT для типов идентичности являются спецификацией . Уравнение не говорит нам, как вычислить или как построить i n d = C , а скорее что однако я нind=C(C,c,x,x,refl(x))≡c(x) ind=C "реализовано", мы требуем, чтобы оно удовлетворяло уравнению. Это отдельный вопрос, можно ли получить такое i n d = C конструктивным образом.ind=C ind=C
Наконец, я немного устал от того, как вы используете слово «конструктивный». Похоже, вы думаете, что «конструктивный» такой же, как «определенный». В соответствии с этой интерпретацией Оракул Остановки является конструктивным, поскольку его поведение определяется требованием, которое мы к нему предъявляем (а именно, что он выдает 1 или 0 в зависимости от того, останавливается ли данная машина). Вполне возможно описать объекты, которые существуют только в неконструктивной обстановке. И наоборот, вполне возможно конструктивно говорить о свойствах и других вещах, которые на самом деле не могут быть вычислены. Вот один из них: отношение определенное как H ( n , d )H⊆N×{0,1}
конструктивно, т. е. нет ничего плохого в этом определении с конструктивной точки зрения. Так уж сложилось, что конструктивно нельзя показать, что H является тотальным отношением, а его характеристическое отображение χ H : N × { 0 , 1 } → P r o p не учитывается через b o o l
Приложение: Название вашего вопроса "Является ли индукция пути конструктивной?" Уточнив разницу между «конструктивным» и «определенным», мы можем ответить на вопрос. Да, индукция пути известна как конструктивная в определенных случаях:
Если мы ограничимся теорией типов без однолистности, чтобы мы могли показать сильную нормализацию, то индукция пути и все остальное будет конструктивным, поскольку существуют алгоритмы, выполняющие процедуру нормализации.
Существуют модели реализуемости теории типов, которые объясняют, как каждый замкнутый член в теории типов соответствует машине Тьюринга. Однако эти модели удовлетворяют аксиоме Штрейхера K, которая исключает однолистность.
Существует перевод теории типов (опять же без однолистности) в конструктивную теорию множеств CZF. Еще раз, это подтверждает аксиому К. Штрейхера.
Внутри моделей реализуемости есть группоидная модель, которая позволяет нам интерпретировать теорию типов без К. Стрейхера. Это предварительная работа Стива Аводи и меня.
Нам действительно нужно разобраться в конструктивном статусе Univalence.
источник
Я не HoTT человек, но я добавлю свои два цента.
Предположим , что мы хотели , чтобы сделать функцию Как мы это делаем? Хорошо, предположим, что нам даны любые x , y : A и доказательство их равенства p : x = A y . Поскольку я ничего не знаю о произвольном типе A , я ничего не знаю о «структуре» x , y
Избавление от подписчиков приводит к общему индуктивному определению.
Надеюсь, это поможет!
источник
Итак, вы видите, что определение элиминатора для индуктивного типа с данными конструкторами происходит в 2 этапа:
источник