En el capítulo 1 y el Apéndice A del libro de Hott , se presentan varias familias de tipos primitivos (tipos de universo, tipos de funciones dependientes, tipos de pares dependientes, tipos de coproductos, tipo vacío, tipo de unidad, tipo de número natural y tipos de identidad) para formar la base para la teoría del tipo de homotopía.
Sin embargo, parece que, dados los tipos de universo y los tipos de función dependientes, puede construir todos estos otros tipos "primitivos". Por ejemplo, el tipo Vacío podría definirse como
ΠT:U.T
Supongo que los otros tipos también podrían construirse de manera similar a como están en CC puro (es decir, simplemente derivar el tipo de la parte inductiva de la definición).
Muchos de estos tipos se vuelven explícitamente redundantes por los tipos inductivos / W que se presentan en los capítulos 5 y 6. Pero los tipos inductivos / W parecen ser una parte opcional de la teoría ya que hay preguntas abiertas sobre cómo interactúan con HoTT (en al menos cuando salió el libro).
Así que estoy muy confundido acerca de por qué estos tipos adicionales se presentan como primitivos. Mi intuición es que una teoría fundamental debería ser lo más mínima posible, y redefinir un tipo vacío redundante como primitivo en la teoría parece muy arbitrario.
¿Se hizo esta elección?
- por algunas razones metateóricas que desconozco?
- por razones históricas, para hacer que la teoría de tipos se parezca a teorías de tipos pasadas (que no necesariamente intentaban ser fundamentales)?
- para la "usabilidad" de las interfaces de computadora?
- para obtener alguna ventaja en la búsqueda de pruebas que desconozco?
Similar a: Especificación mínima de la teoría de tipo Martin-Löf , /cs/82810/reducing-products-in-hott-to-church-scott-encodings/82891#82891
fuente
Respuestas:
Permítanme explicar por qué la codificación sugerida del tipo vacío no funciona. Necesitamos ser explícitos sobre los niveles del universo y no barrerlos debajo de la alfombra.
Cuando las personas dicen "el tipo vacío", pueden significar una de dos cosas:
Un solo tipo que está vacío con respecto a todos los tipos. Tal tipo tiene la regla de eliminación: por cada n y tipo de familia A : E → T n , hay un mapa e n , A : E → A .mi norte A : E→ Unorte minorte , A: E→ A
Una familia de tipos , uno para cada nivel de universo k , de modo que E k es "el tipo vacío de U k ". Tal tipo tiene que satisfacer E k : T k , obviamente, y también: para cada familia de tipo A : E k → U k , hay un mapa e k , A : E K → A .mik k mik Uk mik: Uk A : Ek→ Uk ek,A:Ek→A
Sin ninguna condición, cuando las personas dicen "tipo vacío" esperan el primer significado anterior.
¿Cómo podemos obtener ? Un primer intento podría ser algo como E = Π ( T : U )E
pero este es precisamente el tipo de barrido debajo de la alfombra que crea confusión. Debemos escribir niveles explícitos del universo. Si escribimos algo como
E k = Π ( T : U k )
Otro intento es pero ahora tienes que explicar quése supone que es" Π n ". Es posible que sienta la tentación de decir que hay un tipo L de niveles de universo, por lo que E = Π ( n : L )
Se pueden organizar universos impredecibles. Sin embargo, un famoso teorema de Thierry Coquand (si no me equivoco) muestra que tener dos universos impredecibles, uno contenido en el otro, conduce a una contradicción.
La moraleja de la historia es: simplemente axiomatiza el tipo vacío directamente y deja de codificar cosas.
fuente
Estás haciendo varias preguntas que son similares pero distintas.
¿Por qué el libro HoTT no usa codificaciones de la Iglesia para los tipos de datos?
Las codificaciones de la iglesia no funcionan en la teoría de tipo Martin-Löf, por dos razones.
En segundo lugar, incluso si definió tipos de datos como los números naturales con codificaciones de la Iglesia, para hacer pruebas con estos tipos, necesita principios de inducción para probar cosas sobre ellos. Para derivar los principios de inducción para las codificaciones de la Iglesia, debe utilizar un argumento basado en la parametricidad de Reynolds, y la cuestión de cómo internalizar los principios de parametricidad en la teoría de tipos aún no está completamente resuelta. (El estado del arte es Nuyts, Vezzosi y Devriese's ICFP 2017 Cuantificadores paramétricos para la teoría del tipo dependiente : ¡tenga en cuenta que esto es mucho después de que se escribió el libro HoTT!)
A continuación, se pregunta por qué la base no es mínima. Esta es en realidad una de las características sociológicas distintivas de los fundamentos de la teoría de los tipos: los teóricos de los tipos consideran que tener un pequeño conjunto de reglas es una conveniencia técnica, sin mucha importancia fundamental. Es mucho, mucho más importante tener el conjunto correcto de reglas, en lugar del conjunto más pequeño de reglas.
Desarrollamos teorías de tipo para ser utilizadas por matemáticos y programadores, y es muy, muy importante que las pruebas realizadas dentro de la teoría de tipo sean las que los matemáticos y programadores consideran que se hacen de la manera correcta. Esto se debe a que los argumentos que los matemáticos suelen considerar que tienen un buen estilo suelen estar estructurados utilizando los principios algebraicos y geométricos clave del dominio de estudio. Si tiene que usar codificaciones complicadas, se pierde u oculta mucha estructura.
Esta es la razón por la que incluso las presentaciones teóricas de tipo de lógica clásica proposicional invariablemente dan todos los conectivos lógicos, aunque sea formalmente equivalente a una lógica con solo NAND. Claro, todos los conectores booleanos se pueden codificar con NAND, pero esa codificación oculta la estructura de la lógica.
fuente