Puede dependiente de las sumas que ser codificada como dependiente de productos?

Question

Por favor perdonen si no ortodoxa de la notación o errores evidentes aquí... estoy tratando de conseguir una intuición para la dependencia escribió idiomas, así que estoy empezando a cabo por ver qué analogías que se pueden tomar desde el mecanografiada mundo. En una ML-como el lenguaje nos puede codificar existencial tipos en términos de universales tipos:

$\exists a.T(a) \equiv \forall x.(\forall a.T(a) \rightarrow x) \rightarrow x$

Del mismo modo, también podemos definir la suma de los tipos en términos de universales tipos y tipos de producto:

$a + b \equiv \forall x.(a \rightarrow x)\times(b \rightarrow x) \rightarrow x$

Esta correspondencia tiene sentido para mí, ya existencial tipos son como infinito sumas y universal tipos son como infinita de productos.

En un dependiente de lenguaje escrito, también va a ser posible definir dependiente de sumas de dinero en términos de dependiente de productos? Esto parece cerrar:

$\Sigma(b:B).T(b) \equiv \forall x.(\Pi(b:B).T(b) \rightarrow x) \rightarrow x$

$(a,t) : \Sigma(b:B).T(b) \equiv \lambda f. f\ a\ t$

$\text{fst}\ p \equiv p_B\ (\lambda(b:B).\lambda(\_:T(b)).b)$

$\text{snd}\ p \equiv p_{T (\text{fst}\ p)}\ (\lambda(b:B).\lambda(t:T(b)).t)$

Sin embargo, yo no puedo convencerme de que la definición de snd está bien escrito porque no puedo demostrar que $t : T (\text{fst}\ p)$. Hay alguna manera de hacer este trabajo?

Answer 1

Mi entendimiento es que el dependiente de la eliminación no puede ser derivada a partir de impredicative codificaciones, pero no puedo encontrar una referencia aparte de una mención en El Implícito Cálculo de Construcciones.

Answer 2

La declaración "para cualquier tipo de indexado de la familia de proposiciones, existe una proposición isomorfo a su subproducto" es inconsistente con impredicative tipo de teoría (CC); esto conduce a Girard de la Paradoja.

La declaración "para cualquier proposición-indexado de la familia de proposiciones, existe una proposición isomorfo a su subproducto" es independiente de impredicative tipo de teoría (CC). Es decir, CC tiene modelos en los que esto es falso. Para la prueba, ver T Streicher, la Independencia de los resultados de los cálculos de los tipos de dependientes en la Categoría de la Teoría y Ciencia de la computación, 1989.

Por lo tanto, si lo que estás buscando fuera posible, creo que habría que incluir algún tipo de "gotcha" que hizo incompatible con $B:Prop\ \&\ T:(B\to Prop)\Rightarrow(\Sigma b:B.T(b)):Prop$. Me imagino que este tipo de gotcha (si existe) sería algo como la necesidad de $(\Sigma b:B.T(b)):Type$ - que dependen de las sumas son un universo de sus coordenadas.

Como Russell menciona, Coq consigue todo esto mediante el uso de una más fuerte de la teoría (CiC) de que la declaración contenida en el segundo párrafo no es independiente.

Answer 3

Ciertamente, esto no es lo que la pregunta fue después, pero debido a que las respuestas parecen ser algo a lo largo de las líneas de sí, a veces, pero no menos...

Multi-ordenan la lógica de primer orden (es decir, la lógica clásica) puede ser considerada como una realización de tipo dependiente de la teoría a enriquecer el universo de los términos que contienen la suficiente estructura para el modelo requiere de reglas de inferencia, que son más ricos, porque de De Morgan de la dualidad. Lo que es más importante, necesita de Hilbert epsilon operador modelo de la eliminación de la regla de dependiente de sumas. La teoría resultante es no constructiva —en un sentido fuerte: la equivalencia de la teoría en términos es indecidible— pero puede ser dado una sencilla interpretación en ZFC. Dependiente de la suma y el producto son, a continuación, existencial y universal de la cuantificación, por lo que cualquiera puede ser codificada en términos de los otros.

No he pesar cuidadosamente acerca de esta materia en más de diez años, pero es esencialmente la misma que una observación debido, CREO, a la Factura de Tait, que la teoría de conjuntos ZFC pone de relieve una debilidad de la utilización de la BHK interpretación a la revisión de la noción de lógica constructiva - si la noción de la construcción es de izquierda no interpretada, entonces ZFC proporciona una noción de "construcción" sobre los que puede basarse una BHK interpretación de la lógica clásica. Corolario: el BHK interpretación no hacer el trabajo que mucha gente piensa.

Answer 4

Eche un vistazo a hoq Coq define dependiente de sumas de dinero en términos de productos del dependiente en la biblioteca estándar. Específicamente, usted debe buscar en http://coq.inria.fr/stdlib/Coq.Init.Specif.html.