Teoría de tipos intuicionista

ImprimirCitar

Fundamento alternativo de las matemáticas

Teoría de tipos intuicionista (también conocida como teoría de tipos constructiva, o teoría de tipos de Martin-Löf) es una teoría de tipos y una base alternativa de las matemáticas La teoría de tipos intuicionista fue creada por Per Martin-Löf, un matemático y filósofo sueco, quien la publicó por primera vez en 1972. Existen múltiples versiones de la teoría de tipos: Martin-Löf propuso variantes tanto intensionales como extensionales de la teoría y versiones impredicativas tempranas, mostrado ser inconsistente por la paradoja de Girard, dio paso a versiones predicativas. Sin embargo, todas las versiones mantienen el diseño central de la lógica constructiva utilizando tipos dependientes.

Diseño

Martin-Löf diseñó la teoría de tipos sobre los principios del constructivismo matemático. El constructivismo requiere que cualquier prueba de existencia contenga un 'testigo'. Entonces, cualquier prueba de "existe un número primo mayor que 1000" debe identificar un número específico que sea tanto primo como mayor que 1000. La teoría de tipos intuicionista logró este objetivo de diseño al internalizar la interpretación de BHK. Una consecuencia interesante es que las demostraciones se convierten en objetos matemáticos que se pueden examinar, comparar y manipular.

Los constructores tipo teoría de tipo intuitionista fueron construidos para seguir una correspondencia única con los conectores lógicos. Por ejemplo, el conector lógico llamado implicación ( ${displaystyle Aimplies B}$ ) corresponde al tipo de función ( $Ato B$ ). Esta correspondencia se llama el isomorfismo Curry-Howard. Las teorías del tipo anterior también habían seguido este isomorfismo, pero el de Martin-Löf fue el primero en extenderlo a la lógica predicada introduciendo tipos dependientes.

Teoría de tipos

La teoría de tipos intuicionista tiene 3 tipos finitos, que luego se componen usando 5 constructores de tipos diferentes. A diferencia de las teorías de conjuntos, las teorías de tipos no se construyen sobre una lógica como la de Frege. Por lo tanto, cada característica de la teoría de tipos cumple una doble función como característica tanto de las matemáticas como de la lógica.

Si no está familiarizado con la teoría del tipo y conoce la teoría del conjunto, un resumen rápido es: Los tipos contienen términos como conjuntos contienen elementos. Los términos pertenecen a uno y sólo un tipo. Términos como $2+2$ y ${displaystyle 2cdot 2}$ compute ("reduce") a términos canónicos como 4. Para más, vea el artículo sobre la teoría del tipo.

Tipo 0, tipo 1 y tipo 2

Hay 3 tipos finitos: El tipo 0 contiene 0 términos. El tipo 1 contiene 1 término canónico. Y el tipo 2 contiene 2 términos canónicos.

Porque... 0 tipo contiene 0 términos, también se llama el tipo vacío. Se utiliza para representar cualquier cosa que no pueda existir. También está escrito $bot$ y representa cualquier cosa inproviable. (Es decir, una prueba de ello no puede existir.) Como resultado, la negación se define como una función a ella: ${displaystyle neg A:=Ato bot }$ .

Del mismo modo, 1 tipo contiene 1 término canónico y representa la existencia. También se llama el tipo de unidad. A menudo representa propuestas que pueden ser probadas y es, por lo tanto, a veces escritas $top$ .

Finalmente, el tipo 2 contiene 2 términos canónicos. Representa una elección definitiva entre dos valores. Se utiliza para valores booleanos pero para proposiciones no. Las proposiciones se consideran del tipo 1 y se puede probar que nunca tienen una prueba (el tipo 0), o no se puede probar de ninguna manera. (La Ley del Medio Excluido no se cumple para las proposiciones en la teoría de tipo intuicionista).

Constructor de tipo Σ

Los tipos de la RAZ contienen pares ordenados. Al igual que con los tipos típicos de pareja ordenada (o 2 trompas), un tipo de la ega puede describir el producto cartesiano, $Atimes B$ , de otros dos tipos, $A$ y $B$ . Lógicamente, un par ordenado tendría una prueba de $A$ y una prueba de $B$ , por lo que uno puede ver tal tipo escrito como $Awedge B$ .

Los tipos Σ son más poderosos que los tipos de pares ordenados típicos debido a la tipificación dependiente. En el par ordenado, el tipo del segundo término puede depender del valor del primer término. Por ejemplo, el primer término del par podría ser un número natural y el tipo del segundo término podría ser un vector de longitud igual al primer término. Tal tipo se escribiría:

sum_{n mathbin{:} {mathbb N}} operatorname{Vec}({mathbb R}, n)

Utilizando la terminología de la teoría de conjuntos, esto es similar a una unión descomunal indexada de conjuntos. En el caso de parejas ordenadas habituales, el tipo de segundo término no depende del valor del primer término. Así el tipo de describir el producto cartesiano ${mathbb N} times {mathbb R}$ está escrito:

sum_{n mathbin{:} {mathbb N}} {mathbb R}

Es importante señalar aquí que el valor del primer mandato, $n$ , no se depende del tipo de segundo mandato, ${mathbb R}$ .

Los tipos Σ se pueden usar para crear tuplas de tipos dependientes más largas que se usan en matemáticas y los registros o estructuras que se usan en la mayoría de los lenguajes de programación. Un ejemplo de una tupla de 3 tipos dependientes son dos enteros y una prueba de que el primer entero es más pequeño que el segundo entero, descrito por el tipo:

<math alttext="{displaystyle sum _{m{mathbin {:}}{mathbb {Z} }}{sum _{n{mathbin {:}}{mathbb {Z} }}((m.. m:Z.. n:Z()()m.n)=Cierto.){displaystyle sum _{m{mathbin {fnMithbb} {Z}}{sum _{n{mathbin {:} {fnMitbb {}} {fnMicrosoft Sans Serif}}}}}}<img alt="{displaystyle sum _{m{mathbin {:}}{mathbb {Z} }}{sum _{n{mathbin {:}}{mathbb {Z} }}((m

Tipoteo dependiente permite Tipos de la ONUDI para servir el papel del cuantificador existencial. La declaración "hay una $n$ tipo ${displaystyle {mathbb {N} }}$ , tal que $P(n)$ es probado" se convierte en el tipo de pares ordenados donde el primer artículo es el valor $n$ tipo ${displaystyle {mathbb {N} }}$ y el segundo artículo es una prueba de $P(n)$ . Observe que el tipo de segundo artículo (pruebas de $P(n)$ ) depende del valor en la primera parte del par ordenado ( $n$ ). Su tipo sería:

{displaystyle sum _{n{mathbin {:}}{mathbb {N} }}P(n)}

Π constructor de tipos

Los tipos Π contienen funciones. Al igual que con los tipos de función típicos, consisten en un tipo de entrada y un tipo de salida. Sin embargo, son más potentes que los tipos de función típicos, ya que el tipo de retorno puede depender del valor de entrada. Las funciones en la teoría de tipos son diferentes de la teoría de conjuntos. En la teoría de conjuntos, buscas el valor del argumento en un conjunto de pares ordenados. En la teoría de tipos, el argumento se sustituye por un término y luego se aplica el cálculo ("reducción") al término.

Como ejemplo, el tipo de función que, dada un número natural $n$ , devuelve un vector que contiene $n$ números reales está escrito:

prod_{n mathbin{:} {mathbb N}} operatorname{Vec}({mathbb R}, n)

Cuando el tipo de salida no depende del valor de entrada, el tipo de función es a menudo simplemente escrito con un $to$ . Así, ${mathbb N} to {mathbb R}$ es el tipo de funciones de números naturales a números reales. Estos tipos de LOG corresponden a implicación lógica. La proposición lógica ${displaystyle Aimplies B}$ corresponde al tipo $Ato B$ , que contiene funciones que toman pruebas de A y devuelven pruebas de B. Este tipo podría ser escrito más consistentemente como:

{displaystyle prod _{a{mathbin {:}}A}B}

Los tipos de LOG también se utilizan en la lógica para la cuantificación universal. La declaración "por cada uno $n$ tipo ${displaystyle {mathbb {N} }}$ , $P(n)$ es probado" se convierte en una función $n$ tipo ${displaystyle {mathbb {N} }}$ a las pruebas de $P(n)$ . Así pues, dado el valor $n$ la función genera una prueba de que $P()$ sostiene ese valor. El tipo sería

{displaystyle prod _{n{mathbin {:}}{mathbb {N} }}P(n)}

= constructor de tipos

Los tipos se crean a partir de dos términos. Dados dos términos como $2+2$ y ${displaystyle 2cdot 2}$ , puede crear un nuevo tipo ${displaystyle 2+2=2cdot 2}$ . Los términos de ese nuevo tipo representan pruebas que el par reduce al mismo término canónico. Así pues, desde ambos $2+2$ y ${displaystyle 2cdot 2}$ computar al término canónico $4$ , habrá un término del tipo ${displaystyle 2+2=2cdot 2}$ . En la teoría del tipo intuitionista, hay una única manera de hacer términos de tipos = y que es por la reflexividad:

operatorname{refl} mathbin{:} prod_{a mathbin{:} A} (a = a).

Es posible crear tipos como: ${displaystyle 1=2}$ donde los términos no se reducen al mismo término canónico, pero usted será incapaz de crear términos de ese nuevo tipo. De hecho, si usted fue capaz de crear un término de ${displaystyle 1=2}$ , usted podría crear un término $bot$ . Poner eso en una función generaría una función de tipo ${displaystyle 1=2to bot }$ . Desde ${displaystyle ldots to bot }$ es cómo la teoría del tipo intuitionista define la negación, usted habría ${displaystyle neg (1=2)}$ o, finalmente, ${displaystyle 1neq 2}$ .

La igualdad de pruebas es un área de investigación activa en la teoría de pruebas y ha llevado al desarrollo de la teoría de tipos de homotopía y otras teorías de tipos.

Tipos inductivos

Los tipos inductivos permiten la creación de tipos complejos y auto-referenciales. Por ejemplo, una lista enlazada de números naturales es una lista vacía o un par de un número natural y otra lista enlazada. Los tipos inductivos se pueden utilizar para definir estructuras matemáticas sin límites como árboles, gráficos, etc. De hecho, el tipo de números naturales se puede definir como un tipo inductivo, ya sea siendo ${displaystyle 0}$ o el sucesor de otro número natural.

Tipos inductivos definen nuevas constantes, como cero $0 mathbin{:} {mathbb N}$ y la función sucesora ${displaystyle S{mathbin {:}}{mathbb {N} }to {mathbb {N} }}$ . Desde $S$ no tiene una definición y no se puede evaluar mediante sustitución, términos como ${displaystyle S0}$ y ${displaystyle SSS0}$ convertirse en los términos canónicos de los números naturales.

Las pruebas de los tipos inductivos son posibles por inducción. Cada nuevo tipo inductivo viene con su propia regla inductiva. Para probar un predicado $P()$ para cada número natural, utiliza la siguiente regla:

{displaystyle {operatorname {{mathbb {N} }-elim} },{mathbin {:}}P(0),to left(prod _{n{mathbin {:}}{mathbb {N} }}P(n)to P(S(n))right)to prod _{n{mathbin {:}}{mathbb {N} }}P(n)}

Los tipos inductivos en la teoría de tipos intuicionista se definen en términos de tipos W, el tipo de árboles bien fundados. El trabajo posterior en la teoría de tipos generó tipos coinductivos, inducción-recursión e inducción-inducción para trabajar en tipos con tipos más oscuros de autorreferencialidad. Los tipos inductivos superiores permiten definir la igualdad entre términos.

Tipos de universo

Los tipos del universo permiten que las pruebas se escriban sobre todos los tipos creados con los otros constructores de tipo. Cada término en el tipo del universo $mathcal{U}_0$ se puede mapear a un tipo creado con cualquier combinación de ${displaystyle 0,1,2,SigmaPi=,}$ y el constructor de tipo inductivo. Sin embargo, para evitar paradojas, no hay término en $mathcal{U}_0$ que mapas a $mathcal{U}_0$ .

Para escribir pruebas sobre todos los "tipos pequeños" y $mathcal{U}_0$ , debes usar ${displaystyle {mathcal {U}}_{1}}$ , que contiene un término para $mathcal{U}_0$ , pero no por sí mismo ${displaystyle {mathcal {U}}_{1}}$ . Del mismo modo, ${displaystyle {mathcal {U}}_{2}}$ . Hay una jerarquía predicativa de universos, para cuantificar una prueba sobre cualquier constante fija $k$ universos, puedes usar ${displaystyle {mathcal {U}}_{k+1}}$ .

Los tipos de universo son una característica engañosa de las teorías de tipos. La teoría de tipos original de Martin-Löf tuvo que cambiarse para dar cuenta de la paradoja de Girard. Investigaciones posteriores cubrieron temas como 'superuniversos', 'universos de Mahlo' y universos impredicativos.

Sentencias

La definición formal de la teoría del tipo intuitionista está escrita usando juicios. Por ejemplo, en la declaración "si $A$ es un tipo y $B$ es un tipo entonces ${displaystyle textstyle sum _{a:A}B}$ es un tipo" hay juicios de "es un tipo", "y", y "si... entonces...". La expresión ${displaystyle textstyle sum _{a:A}B}$ no es un juicio; es el tipo que se define.

Este segundo nivel de la teoría del tipo puede ser confuso, especialmente en lo que se refiere a la igualdad. Existe una sentencia de igualdad de término, que podría decir ${displaystyle 4=2+2}$ . Es una declaración que dos términos reducen al mismo término canónico. También hay una sentencia de igualdad de tipo, decir que $A=B$ , lo que significa cada elemento de $A$ es un elemento del tipo $B$ y viceversa. En el nivel de tipo, hay un tipo ${displaystyle 4=2+2}$ y contiene términos si hay una prueba de que $4$ y $2+2$ reducir al mismo valor. (Los términos de este tipo se generan utilizando el criterio de calidad.) Por último, hay un nivel de igualdad en inglés, porque usamos la palabra "cuatro" y el símbolo " $4$ "para referirse al término canónico ${displaystyle SSSS0}$ . Sinónimos como estos son llamados "definitivamente iguales" por Martin-Löf.

La descripción de los juicios a continuación se basa en la discusión en Nordström, Petersson y Smith.

La teoría formal trabaja con tipos y objetos.

Un tipo es declarado por:

$A mathsf{Type}$

Did you mean:

An object exists and is in a type of:

$a mathbin{:} A$

Los objetos pueden ser iguales

$a=b$

y los tipos pueden ser iguales

$A=B$

Se declara un tipo que depende de un objeto de otro tipo

$(x mathbin{:} A)B$

y eliminado por sustitución

$B[x / a]$ , sustitución de la variable $x$ con el objeto $a$ dentro $B$ .

Did you mean:

An object that depends on an object from another type can be done two ways. If the object is "abstracted#34;, then it is written

$[x]b$

y eliminado por sustitución

$b[x / a]$ , sustitución de la variable $x$ con el objeto $a$ dentro $b$ .

El objeto que depende del objeto también se puede declarar como una constante como parte de un tipo recursivo. Un ejemplo de un tipo recursivo es:

$0 mathbin{:} mathbb{N}$
${displaystyle S{mathbin {:}}mathbb {N} to mathbb {N} }$

Aquí, $S$ es un objeto-dependiente-en-objeto constante. No se asocia con una abstracción. Constantes como $S$ se puede eliminar definiendo la igualdad. Aquí la relación con la adición se define utilizando la igualdad y el uso de patrón que coincida para manejar el aspecto recursivo de $S$ :

{displaystyle {begin{aligned}operatorname {add} &{mathbin {:}} (mathbb {N} times mathbb {N})to mathbb {N} \operatorname {add} (0,b)&=b\operatorname {add} (S(a),b)&=S(operatorname {add} (a,b)))end{aligned}}}

$S$ se manipula como una constante opaca - no tiene estructura interna para la sustitución.

Entonces, los objetos y tipos y estas relaciones se usan para expresar fórmulas en la teoría. Los siguientes estilos de juicios se utilizan para crear nuevos objetos, tipos y relaciones a partir de los existentes:

$Gammavdash sigma mathsf{Type}$	σ es un tipo bien formado en el contexto de Dimensiones.
$Gammavdash t mathbin{:} sigma$	t es un término bien formado de tipo σ en contexto
$Gammavdash sigma equiv tau$	σ y τ son tipos iguales en el contexto Dimension.
$Gammavdash t equiv u mathbin{:} sigma$	t y u son términos juzgados iguales de tipo σ en contexto
$vdash Gamma mathsf{Context}$	Dimensiones es un contexto bien formado de hipótesis de clasificación.

Por convención, hay un tipo que representa a todos los demás tipos. Se llama ${mathcal {U}}$ (o $operatorname {Set}$ ). Desde ${mathcal {U}}$ es un tipo, los miembros de ella son objetos. Hay un tipo dependiente $operatorname{El}$ que mapea cada objeto a su tipo correspondiente. En la mayoría de los textos $operatorname{El}$ Nunca está escrito. Desde el contexto de la declaración, un lector casi siempre puede decir si $A$ se refiere a un tipo, o si se refiere al objeto en ${mathcal {U}}$ que corresponde al tipo.

Esta es la base completa de la teoría. Todo lo demás es derivado.

Para implementar la lógica, cada propuesta se da su propio tipo. Los objetos de esos tipos representan las diferentes formas posibles de probar la proposición. Si no hay pruebas para la proposición, entonces el tipo no tiene objetos en ella. Operadores como "y" y "o" que trabajan en proposiciones introducen nuevos tipos y nuevos objetos. Así que... $A times B$ es un tipo que depende del tipo $A$ y el tipo $B$ . Los objetos de ese tipo dependiente se definen para existir por cada par de objetos en $A$ y $B$ . Si $A$ o $B$ no tiene prueba y es un tipo vacío, entonces el nuevo tipo que representa $Atimes B$ también está vacía.

Esto se puede hacer para otros tipos (booleanos, números naturales, etc.) y sus operadores.

Modelos categóricos de la teoría de tipos

Usando el lenguaje de la teoría de categorías, R. A. G. Seely introdujo la noción de una categoría cerrada localmente cartesiana (LCCC) como el modelo básico de la teoría de tipos. Esto ha sido refinado por Hofmann y Dybjer a Categorías con Familias o Categorías con Atributos basado en trabajos anteriores de Cartmell.

Una categoría con familias es una categoría C de contextos (en la que los objetos son contextos, y los morfismos de contexto son sustituciones), junto con un funtor T: C^op → Fam(Set ).

Fam()Set) es la categoría de familias de conjuntos, en los cuales los objetos son pares $(A,B)$ de un "index set" A y una función B: X → A, y los morfismos son pares de funciones f: A → A ' y g: X → X ' , tal que B ' _° g = f _° B - en otras palabras, f mapas B_a a B_g()a).

El functor T asigna a un contexto G un conjunto ${displaystyle Ty(G)}$ de tipos, y para cada ${displaystyle A:Ty(G)}$ , un conjunto ${displaystyle Tm(G,A)}$ de términos. Los axiomas para un functor requieren que estos jueguen armoniosamente con la sustitución. La sustitución suele ser escrito en la forma Af o af, donde A es un tipo en ${displaystyle Ty(G)}$ y a es un término en ${displaystyle Tm(G,A)}$ , y f es una sustitución desde D a G. Aquí. ${displaystyle Af:Ty(D)}$ y ${displaystyle af:Tm(D,Af)}$ .

La categoría C debe contener un objeto terminal (el contexto vacío), y un objeto final para una forma de producto llamado comprensión, o extensión contextual, en el que el elemento derecho es un tipo en el contexto del elemento izquierdo. Si G es un contexto, y ${displaystyle A:Ty(G)}$ , entonces debe haber un objeto ${displaystyle (G,A)}$ final entre contexts D con asignaciones p: D → G, q: T m()D,Ap).

Un marco lógico, como el de Martin-Löf, toma la forma de condiciones de cierre en los conjuntos de tipos y términos dependientes del contexto: que debería haber un tipo llamado Conjunto, y para cada conjunto un tipo, que los tipos deben cerrarse bajo formas de suma dependiente y producto, y así sucesivamente.

Una teoría como la de la teoría predicativa de conjuntos expresa condiciones de cierre sobre los tipos de conjuntos y sus elementos: que deben cerrarse bajo operaciones que reflejen suma y producto dependientes, y bajo diversas formas de definición inductiva.

Did you mean:

Extensional vs intensional

Una distinción fundamental es la teoría de tipo extensional versus intensional. En la teoría de tipo extensional, la igualdad definitoria (es decir, computacional) no se distingue de la igualdad proposicional, que requiere demostración. Como consecuencia, la verificación de tipos se vuelve indecidible en la teoría de tipos extensional porque los programas en la teoría podrían no terminar. Por ejemplo, tal teoría permite dar un tipo al combinador Y; se puede encontrar un ejemplo detallado de esto en Nordstöm y Petersson Programming in Martin-Löf's Type Theory. Sin embargo, esto no impide que la teoría de tipos extensionales sea la base de una herramienta práctica; por ejemplo, NuPRL se basa en la teoría de tipo extensional.

En contraste, en la teoría de tipos intensionales, la verificación de tipos es decidible, pero la representación de conceptos matemáticos estándar es un poco más engorrosa, ya que el razonamiento intensional requiere el uso de setoides o construcciones similares. Hay muchos objetos matemáticos comunes con los que es difícil trabajar o que no se pueden representar sin esto, por ejemplo, números enteros, números racionales y números reales. Los números enteros y racionales se pueden representar sin setoides, pero es difícil trabajar con esta representación. Los números reales de Cauchy no se pueden representar sin esto.

La teoría del tipo de homotopía funciona para resolver este problema. Permite definir tipos inductivos superiores, que no solo definen constructores de primer orden (valores o puntos), sino constructores de orden superior, es decir, igualdades entre elementos (caminos), igualdades entre igualdades (homotopías), ad infinitum.

Implementaciones de la teoría de tipos

Se han implementado diferentes formas de teoría de tipos como los sistemas formales subyacentes de varios asistentes de prueba. Si bien muchos se basan en las ideas de Per Martin-Löf, muchos tienen características adicionales, más axiomas o antecedentes filosóficos diferentes. Por ejemplo, el sistema NuPRL se basa en la teoría de tipos computacional y Coq se basa en el cálculo de construcciones (co)inductivas. Los tipos dependientes también aparecen en el diseño de lenguajes de programación como ATS, Cayenne, Epigram, Agda e Idris.

Teorías tipo Martin-Löf

Per Martin-Löf construyó varias teorías de tipos que fueron publicadas en varios momentos, algunas de ellas mucho más tarde que cuando los preprints con su descripción se hicieron accesibles a los especialistas (entre otros, Jean-Yves Girard y Giovanni Sambin). La lista a continuación intenta enumerar todas las teorías que se han descrito en forma impresa y esbozar las características clave que las distinguen entre sí. Todas estas teorías tenían productos dependientes, sumas dependientes, uniones disjuntas, tipos finitos y números naturales. Todas las teorías tenían las mismas reglas de reducción que no incluían η-reducción ni para productos dependientes ni para sumas dependientes, excepto MLTT79 donde se suma la η-reducción para productos dependientes.

MLTT71 fue la primera teoría de tipos creada por Per Martin-Löf. Apareció en una preimpresión en 1971. Tenía un universo, pero este universo tenía un nombre en sí mismo, es decir, era una teoría de tipos con, como se llama hoy, 'Tipo en tipo'. Jean-Yves Girard ha demostrado que este sistema era inconsistente y la preimpresión nunca se publicó.

MLTT72 se presentó en una preimpresión de 1972 que ahora se ha publicado. Esa teoría tenía un universo V y ningún tipo de identidad. El universo era "predicativo" en el sentido de que el producto dependiente de una familia de objetos de V sobre un objeto que no estaba en V como, por ejemplo, el propio V, no se suponía que estaba en V. El universo era a la Russell's Principia Mathematica, es decir, uno escribiría directamente "T∈V" y "t∈T" (Martin-Löf usa el signo "∈" en lugar del moderno ":") sin el constructor adicional como "El".

MLTT73 fue la primera definición de una teoría de tipos que publicó Per Martin-Löf (se presentó en el Logic Colloquium '73 y se publicó en 1975). Hay tipos de identidad que él llama "proposiciones" pero como no se introduce una distinción real entre las proposiciones y el resto de los tipos, el significado de esto no está claro. Está lo que luego adquiere el nombre de J-eliminator pero aún sin nombre (ver pp. 94-95). Hay en esta teoría una secuencia infinita de universos V₀,..., V_n,... . Los universos son predicativos, a la Russell y no acumulativos. De hecho, el Corolario 3.10 en la p. 115 dice que si A∈V_m y B∈V_n son tales que A y B son convertibles entonces m = n. Esto significa, por ejemplo, que sería difícil formular la univalencia en esta teoría: hay tipos contráctiles en cada uno de los V_i pero no está claro cómo declararlos iguales ya que no hay tipos de identidad que conectan V_i y V_j para i ≠ j .

MLTT79 se presentó en 1979 y se publicó en 1982. En este artículo, Martin-Löf introdujo los cuatro tipos básicos de juicio para la teoría del tipo dependiente que desde entonces se ha vuelto fundamental en el estudio de la meta -teoría de tales sistemas. También introdujo contextos como un concepto separado en él (ver p. 161). Hay tipos de identidad con el J-eliminator (que ya apareció en MLTT73 pero no tenía este nombre allí) pero también con la regla que hace que la teoría sea "extensional" (pág. 169). Hay tipos W. Hay una secuencia infinita de universos predicativos que son acumulativos.

Bibliopolis: hay una discusión sobre una teoría de tipos en el libro Bibliopolis de 1984, pero es algo abierto y no parece representar un conjunto particular de opciones y, por lo tanto, no hay una teoría de tipo específica asociada con él.

Contenido relacionado

Más resultados...

Teoría de tipos intuicionista

Diseño

Teoría de tipos

Tipo 0, tipo 1 y tipo 2

Constructor de tipo Σ

Π constructor de tipos

= constructor de tipos

Tipos inductivos

Tipos de universo

Sentencias

Modelos categóricos de la teoría de tipos

Extensional vs intensional

Implementaciones de la teoría de tipos

Teorías tipo Martin-Löf

Contenido relacionado

Cálculo secuencial

Matriz Hessiana

Función Weierstrass