En lógica matemática, Sistema U y Sistema U− son sistemas de tipos puros, es decir, formas especiales de un cálculo lambda tipado con un número arbitrario de géneros, axiomas y reglas (o dependencias entre los géneros). Jean-Yves Girard demostró que ambos eran inconsistentes en 1972.[1] Este resultado llevó a darse cuenta de que la teoría de tipos original de Martin-Löf de 1971 era inconsistente, ya que permitía el mismo comportamiento de «Tipo en tipo» que explota la paradoja de Girard.
Definición formal
editar
El Sistema U se define[2] : 352 como un sistema de tipo puro con
tres tipos ;
dos axiomas ; y
cinco reglas .
El Sistema U− se define igual con la excepción del regla.
los tipos y se denominan convencionalmente «Tipo» y «Tipo», respectivamente; el tipo no tiene un nombre específico. Los dos axiomas describen la contención de tipos en clases ( ) y tipos en ( ). Intuitivamente, los géneros describen una jerarquía en la naturaleza de los términos.
Todos los valores tienen un tipo, como un tipo base ( p. ej. se lee como " b es un booleano") o un tipo de función (dependiente) ( p. ej. se lee como “ f es una función de números naturales a booleanos”).
es el género de todos esos tipos ( se lee como “ t es un tipo”). De podemos construir más términos, como que es el tipo de operadores unarios de nivel de tipo ( p. ej. se lee como “ List es una función de tipos a tipos”, es decir, un tipo polimórfico). Las reglas restringen cómo podemos formar nuevos tipos.
es el tipo de todos esos tipos ( se lee como “ k es una especie”). De igual forma podemos construir términos relacionados, de acuerdo a lo que permitan las reglas.
es el género de todos esos términos.
Las reglas rigen las dependencias entre los géneros: dice que los valores pueden depender de los valores (funciones), permite que los valores dependan de los tipos (polimorfismo), permite que los tipos dependan de los tipos (operadores de tipo), y así sucesivamente.
Paradoja de Girard
editar
Las definiciones de Sistema U y U− permiten la asignación de tipos polimórficos a constructores genéricos de forma análoga a los tipos polimórficos de términos en cálculos lambda polimórficos clásicos, como Sistema F. Un ejemplo de un constructor genérico de este tipo podría ser[2]: 353 (donde k denota una especie de variable)
.
Este mecanismo es suficiente para construir un término con el tipo (equivale al tipo ), lo que implica que todo tipo está habitado. Por la correspondencia de Curry-Howard, esto es equivalente a que todas las proposiciones lógicas sean demostrables, lo que hace que el sistema sea inconsistente.
↑Girard, Jean-Yves (1972). «Interprétation fonctionnelle et Élimination des coupures de l'arithmétique d'ordre supérieur».
↑ abSørensen, Morten Heine; Urzyczyn, Paweł (2006). «Pure type systems and the lambda cube». Lectures on the Curry–Howard isomorphism. Elsevier. ISBN0-444-52077-5. doi:10.1016/S0049-237X(06)80015-7.