¿Eliminación de corte para cálculo con nats u otro tipo de datos inductivo?

14

¿Alguien me dirige a un artículo que detalla un teorema de eliminación de cortes para la lógica intuicionista proposicional, que incluye un tipo de datos inductivo como los números naturales (las listas o los árboles también estarían bien)? Un ejemplo del tipo de sistema que me interesa es la T de Godel, que tiene tipos dados por la gramática . No estoy muy interesado en cuantificadores sobre números naturales o predicados indexados por números naturales.UN:: =norteEl |UNUN

Sé cómo probar la normalización beta para la versión de deducción natural de estos sistemas utilizando un argumento de relaciones lógicas (o técnicas relacionadas como NbE), pero me gustaría saber si existen referencias estándar sobre cómo adaptar estos métodos a los cálculos posteriores.

La razón por la que pregunto es que estoy estudiando agregar operadores de punto fijo para la recursión protegida a un idioma. La idea denotacional es bastante antigua: interpretar los tipos como espacios ultramétricos y puntos fijos a través del teorema de Banach, pero las técnicas puramente sintácticas que conozco para probar la eliminación de cortes no parecen adaptarse tan bien.

Neel Krishnaswami
fuente

Respuestas:

10

¿Qué tal el trabajo de Ulrich Berger? Por ejemplo, fuerte normalización para cálculos lambda aplicados . La parte de "constantes definidas recursivamente" obtiene tipos inductivos, más o menos. Y no se desanime por la palabra "sin tipo", también obtiene resultados para los sistemas con tipo.

Andrej Bauer
fuente
¡Esta es una idea muy interesante! Estoy interesado en agregar (por ejemplo) constantes para puntos fijos que no son necesariamente reglas de izquierda o derecha, por lo que este parece un buen lugar para buscar.
Neel Krishnaswami
10

Puede echar un vistazo a Cut-Elimination de McDowell y Miller para una lógica con definiciones e inducción , que muestra cómo adoptar el método de Tait a un cálculo secuencial intuitivo de primer orden con un predicado de números naturales inductivamente definido.

Noam Zeilberger
fuente
Gracias, leí este artículo hace un tiempo, pero lo olvidé. Echaré otro vistazo.
Neel Krishnaswami