¿MLTT es efectivamente pCiC sin Prop?

11

¿Es la teoría de tipo Martin-Löf básicamente el cálculo predicativo de construcciones inductivas sin impredicative ?Prop

Si están estrechamente relacionados pero con más diferencias que solo , ¿cuáles son esas diferencias?Prop

type-theory calculus-of-constructions usuario
fuente
En mi libro, MLTT es una teoría de tipo dependiente intuitiva (antigua y establecida), mientras asocio el cálculo de construcciones con el asistente de prueba Coq. Pero puedo estar equivocado.
Thomas Klimpel
1
MLTT utiliza tipos de identidad para lidiar con la igualdad. ¿Cuál sería la igualdad en el fragmento predicativo de la CiC?
Martin Berger
2
@MartinBerger: ¡CiC también tiene tipos de identidad!
cody
1
Esto es como preguntar si el Reino Unido es UE sin los otros 27 estados miembros :-)
Andrej Bauer
3
@AndrejBauer Si fuera lo suficientemente ingenioso, inventaría un chiste brexit, pero desafortunadamente no lo soy. :-P
usuario

Respuestas:

17

La respuesta corta es sí, MLTT se puede equiparar razonablemente con CIC sin ninguna imprecisión Prop.

El principal problema técnico es que hay docenas de variantes cuando se habla de la teoría de tipos de Martin-Löf y, quizás más sorprendentemente, cuando se habla de CIC. Por ejemplo, tomando la versión de CIC definida en la tesis de Benjamin Werner, ni siquiera tiene sentido eliminarla Prop, ya que uno no tiene ninguno Seto universos de Type.

Las principales variaciones que uno puede considerar en cualquiera de estas teorías son:

  1. Universos : cuántos y cómo se definen (Palmgren, On Universes in Type Theory , discute muchas variaciones no equivalentes) y si se admite o no el polimorfismo universal .

  2. Qué tipos / familias inductivas : Agda admite tipos inductivos-recursivos, pero hay muchas más variaciones mundanas dependiendo de cuán "grandes" estén permitidos los tipos en los constructores y eliminadores, los parámetros de manejo frente a los índices, etc.

  3. Inyectividad de constructores tipo . Esto lleva a un sistema inconsistente con EM en Agda. Por supuesto, Epigram tiene una "Teoría del tipo de observación" más extrema, pero esto puede considerarse algo completamente diferente.

  4. Axioma K : esto viene gratis con ciertas versiones de coincidencia de patrones dependientes.

  5. Intencional vs Extensional : esta es una gran diferencia, donde esencialmente se agrega una nueva regla de conversión en los sistemas extensionales Lo que hace que la verificación de tipo sea indecidible (¡pero mucho más poderosa!). El propio Martin-Löf parece haber considerado ambos tipos de sistemas.

    Γ⊢t:IdType A BΓ⊢A = B

  6. La presencia de tipos coinductivos y principios de eliminación asociados.

Todas las variaciones anteriores (excepto OTT) se han considerado en la literatura y se han asociado con el nombre "Teoría del tipo Martin-Löf" o "Cálculo de construcciones inductivas", principalmente debido a su asociación con los sistemas Agda y Coq, respectivamente.

Entonces, la respuesta larga es que no hay consenso sobre cuál es la definición exacta de ninguno de estos sistemas.

cody
fuente