Почему рекурсивные типы необходимы в качестве примитивов для доказательств в системах зависимых типов?

Я относительно новичок в теории типов и зависимом программировании. Я изучал исчисление конструкций (CoC) и других систем чистого типа. Я особенно заинтересован в том, чтобы использовать его в качестве промежуточного представления для сохранения системы компиляции.

Я понимаю , что (со) рекурсивные типы представимы , вычислительно , используя в качестве единственного типа конструктора. Я читал, однако, что они не могут быть использованы для создания доказательств по индукции (простите меня, я не могу найти где сейчас!), Например, что я не мог доказать, что в простом CoC (хотя можно печатать как ). $\Pi$ $0\neq 1$ $\texttt{Nat}$ $\Pi(\mathbb{N}:*).\Pi(S:\mathbb{N}\rightarrow\mathbb{N}).\Pi(Z:\mathbb{N}).\mathbb{N}$

Я предполагаю, что именно поэтому они построили исчисление индуктивных конструкций (CIC). Это правильно? Но почему? Я не смог найти никакого материала, объясняющего, почему такие доказательства не могут быть представлены без использования (со) индуктивных типов в качестве примитивов. Если это не так, то зачем добавлять их как примитивы в CIC?

type-theory dependent-types coq paulotorrens
источник

Я не эксперт, но я поделюсь тем, что я до сих пор понял, с примером.

Давайте рассмотрим логический тип в CoC, используя его стандартную кодировку: Можно ожидать, что мы сможем доказать Действительно, это быстро следует из принцип зависимого исключения / индукции, который мы имеем, например, в CiC

\begin{array}{l} B = Π_{τ : *} τ \to τ \to τ \\ t t = λ τ : *, x : τ, y : τ . x \\ f f = λ τ : *, x : τ, y : τ . y \end{array}

$\begin{array}{l} \mathbb{B} = \Pi_{\tau:*} \tau \to \tau \to \tau \\ \mathsf{tt} = \lambda \tau:*,x:\tau,y:\tau.\ x \\ \mathsf{ff} = \lambda \tau:*,x:\tau,y:\tau.\ y \end{array}$

Π_{b : B} b = t t \lor b = f f (*)

$\Pi_{b : \mathbb{B}} b={\sf tt} \lor b = {\sf ff} \qquad(*)$

B_{i n d} : Π_{P : B \to *} P (t t) \to P (f f) \to Π_{b : B} P (b)

$\mathbb{B}_{ind} : \Pi_{P:\mathbb{B}\to*} P({\sf tt}) \rightarrow P({\sf ff}) \rightarrow \Pi_{b:\mathbb{B}} P(b)$

Тем не менее, мы не можем ожидать (*) для всех моделей CoC! Интуитивно понятно, что значение в должно быть приблизительно семейством функций присваивающих каждому типу значение в интерпретации . Но это не заставляет находиться между значениями . Мы могли бы иметь, например (неофициально) $\mathbb{B}$ $\{f_\tau\}_{\tau}$ $\tau$ $\tau\to\tau\to\tau$ $f_\tau$ $\sf tt,ff$

f_{N} (n) (m) = n + m

$f_{\mathbb{N}}(n)(m) = n+m$

Чтобы быть уверенным, что значения $\sf tt,ff$ являются единственно возможными значениями, нам нужно ограничиться параметрическими моделями. Действительно (я думаю) свойство может быть доказано из свободной теоремы , связанной с политипом . $(*)$ $\mathbb{B}$

Однако, насколько я понимаю, CoC не исключает специальных моделей, в которых параметричность не выполняется. В некоторых из них просто ложно. Надежно, в присутствии контрмодели, мы заключаем, что не заселен в CoC. Следовательно, в CoC также нет термина . $(*)$ $(*)$ $\mathbb{B}_{ind}$

чи
источник

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

, Есть много способов, которыми я мог бы сделать конструкторы для Nat, но, в конечном счете, разве они не были бы созданы из

или

(λ (N a t : *) . (. . .)) (Π (N : *) . Π (S : N \to N) . Π (Z : N) . N)

$(\lambda(Nat:*).(...)) (\Pi(\mathbb{N}:*).\Pi(S:\mathbb{N}\rightarrow\mathbb{N}).\Pi(Z:\mathbb{N}).\mathbb{N})$

S

$S$

Z

$Z$

@paulotorrens В логике, да, я считаю, что это единственные варианты. Но в модели УПС (модели одноранговой), могут быть значения

, которые не могут быть определены через

. Подумайте о натуральном значении

таком что

для всех типов

кроме

где вместо

N a t

$Nat$

S, Z

$S,Z$

n

$n$

n (T) (S_{T}) (Z_{T}) = Z_{T}

$n(T)(S_T)(Z_T) = Z_T$

T

$T$

T = B

$T=\mathbb{B}$

. Значение

ведет себя как «ноль» в большинстве типов и как «один» для логических значений. Мы не можем написать

в УПСчтобы определитьчто значение

, но в одноранговой модели, значение может присутствоватьтем не менее.

n (B) (S) (Z) = S (Z)

$n(\mathbb{B})(S)(Z) = S(Z)$

n

$n$

λ T : * . i f T = B t h e n \dots

$\lambda T:*. {\sf if}\ T=\mathbb{B}\ {\sf then}\ \ldots$

n

$n$

Чи

@paulotorrens Может быть , вы можете понять проблему легче , если вы думаете о

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

для всех типов

но для

где

Π_{T : *} T \to T

$\Pi_{T:*} T\to T$

v (T) (x) = x

$v(T)(x) = x$

T

$T$

T = N

$T=\mathbb{N}$

v (N) (x) = x + 1

$v(\mathbb{N})(x) = x+1$

чи

Почему рекурсивные типы необходимы в качестве примитивов для доказательств в системах зависимых типов?

Ответы: