Как показать, что тип в системе с зависимыми типами не заселен (то есть формула не доказуема)?

Для систем без зависимых типов, таких как система типов Хиндли-Милнера, типы соответствуют формулам интуиционистской логики. Там мы знаем, что ее модели являются гейтинговыми алгебрами, и, в частности, чтобы опровергнуть формулу, мы можем ограничиться одной гейтинговой алгеброй, где каждая формула представлена открытым подмножеством . $\mathbb{R}$

Например, если мы хотим показать, что не заселен, мы строим отображение из формул для открытия подмножеств , определяя: Затем Это показывает, что исходная формула не может быть доказуема, так как у нас есть модель, в которой она не соответствует действительности, или эквивалентно (изоморфизмом Карри-Говарда) тип не может быть обитаемым. $\forall\alpha.\alpha\lor(\alpha\rightarrow\bot)$ $\phi$ $\mathbb{R}$

\begin{aligned} φ (α) & знак равно (- \infty, 0) \end{aligned}

$\begin{align} \phi(\alpha) &= (-\infty, 0) \end{align}$

\begin{aligned} φ (α \to ⊥) & знак равно ИНТ ([0, \infty)) \\ знак равно (0, \infty) \\ φ (α \lor (α \to ⊥)) & знак равно (- \infty, 0) \cup (0, \infty) \\ знак равно р ∖ 0, \end{aligned}

$\begin{align} \phi(\alpha\rightarrow\bot) &= \mbox{int}( [0, \infty) ) \\ & = (0,\infty) \\ \phi(\alpha\lor(\alpha\rightarrow\bot)) &= (-\infty, 0) \cup (0,\infty) \\ &= \mathbb{R} \setminus {0}. \end{align}$

Другая возможность - использовать рамки Kriepke .

Существуют ли аналогичные методы для систем с зависимыми типами? Как какое-то обобщение гейтинговых алгебр или фреймов Крипке?

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

lo.logic dependent-type model-theory calculus-of-constructions Петр Пудлак
источник

То, что формула не доказуема, может быть сделано двумя способами. Если повезет, мы сможем показать в рамках теории типов, что формула подразумевает те, которые, как известно, уже не доказуемы. Другой способ - найти модель, в которой формула неверна, и это может быть довольно сложно. Например, потребовалось очень много времени, чтобы найти группоидную модель теории зависимых типов, которая первой сделала недействительной уникальность доказательств идентичности .

Вопрос "что такое модель теории зависимого типа?" имеет несколько сложный ответ. Если вы игнорируете некоторые свойства замещения, модель является локально декартовой замкнутой категорией , и это может быть самым простым ответом. Если вам нужна «реальная» модель, есть несколько вариантов, см. Страницу nLab по категориальным моделям теории зависимых типов . В любом случае, ответ всегда немного сложен, потому что теория зависимых типов является довольно сложной формальной системой.

Если бы я предложил одну статью на эту тему, я бы, вероятно, рекомендовал бы оригинальную статью Роберта Сили «Локально декартовы замкнутые категории и теория типов» . Если бы я предложил другой вариант, он, вероятно, объяснил бы, что необходимо исправить в статье Сили, например, в статье Мартина Хоффмана «Об интерпретации теории типов в локально декартовых замкнутых категориях» .

Важным недавним достижением в этой области является осознание того, что теоретико-гомотопические модели также являются моделями теории зависимых типов, см. Ссылки на homotopytypetheory.org . Это предоставляет множество возможностей, но теперь нужно изучить теорию гомотопии, чтобы получить доступ к моделям.

Андрей Бауэр
источник

Этот ответ довольно приятный, хотя он игнорирует, пожалуй, самый простой из возможных способов доказать, что тип не заселен: индукция в нормальных формах! В частности, легко доказать, что исключенная середина не может быть заселена в исчислении конструкций такой индукцией. Конечно, вам нужно показать, что каждый член может быть преобразован в нормальную форму того же типа, и это включает в себя построение модели ...

cody

@ Cody: хорошая мысль, нормальные формы могут быть очень полезны.

Андрей Бауэр

@cody: «тогда вам нужно показать, что каждый термин может быть представлен в нормальной форме того же типа»: разве это не стандартная часть метатеории для «хорошей» системы типов (если вы этого не сделаете есть аксиомы) или "хорошая" логика (где это исключение среза)? Таким образом, вы можете просто использовать существующее доказательство, верно?

Blaisorblade

@Blaisorblade: конечно, вам нужно только один раз доказать уничтожение среза. Можно сказать, что использование индукции в нормальных формах вместо построения моделей было способом задать вопрос: вы уже строите модель, чтобы показать, что каждый член может быть приведен в нормальную форму. В некотором смысле вы работаете в «нормальной модели формы», а не выполняете строго синтаксическую работу.

Коди

Понятно - я думал об «усилиях по доказательству», хотя, думаю, вы рассуждаете о том, как реализовано все доказательство Но вы снова заставили меня усомниться в разнице между синтаксическим и семантическим подходами, учитывая такие конструкции, как терминовые модели. Поэтому я задал отдельный вопрос по этому поводу

Blaisorblade

Как показать, что тип в системе с зависимыми типами не заселен (то есть формула не доказуема)?

Ответы: