¿Por qué termina este procedimiento de eliminación de corte (caso de contracción)?

En la encuesta de Melliès, Semántica categórica de la lógica lineal , se proporciona un procedimiento de eliminación de corte para la lógica lineal intuicionista que incluye el siguiente caso:

3.9.3 Promoción versus contracción
La prueba se transforma en la prueba $\frac{\frac{\frac{π_{1} ⋮}{! Γ ⊢ A}}{! Γ ⊢! A} Promotion \frac{\frac{π_{2} ⋮}{Υ_{1},! A,! A, Υ_{2} ⊢ B}}{Υ_{1},! A, Υ_{2} ⊢ B} Contraction}{Υ_{1},! Γ, Υ_{2} ⊢ B} Cut$ $\displaystyle\frac{ \displaystyle\frac{\displaystyle\frac{\pi_1\\\vdots}{!\Gamma \vdash A}}{!\Gamma \vdash !A} \text{ Promotion} \qquad \displaystyle\frac{\displaystyle\frac{\pi_2\\\vdots}{\Upsilon_1 , !A , !A , \Upsilon_2 \vdash B}}{\Upsilon_1 , !A , \Upsilon_2 \vdash B} \text{ Contraction} }{ \Upsilon_1 , !\Gamma , \Upsilon_2 \vdash B } \text{ Cut}$ $\frac{\frac{\frac{π_{1} ⋮}{! Γ ⊢ A}}{! Γ ⊢! A} Promotion \frac{\frac{\frac{π_{1} ⋮}{! Γ ⊢ A}}{! Γ ⊢! A} Promotion \frac{π_{2} ⋮}{Υ_{1},! A,! A, Υ_{2} ⊢ B}}{Υ_{1},! A,! Γ, Υ_{2} ⊢ B} Cut}{\frac{Υ_{1},! Γ,! Γ, Υ_{2} ⊢ B}{Υ_{1},! Γ, Υ_{2} ⊢ B} Series of Contractions and Exchanges} Cut$ $\displaystyle\frac{ \displaystyle\frac{\displaystyle\frac{\pi_1\\\vdots}{!\Gamma \vdash A}}{!\Gamma \vdash !A} \text{ Promotion} \qquad \displaystyle\frac{ \displaystyle\frac{\displaystyle\frac{\pi_1\\\vdots}{!\Gamma \vdash A}}{!\Gamma \vdash !A} \text{ Promotion} \qquad \displaystyle\frac{\pi_2\\\vdots}{\Upsilon_1 , !A , !A , \Upsilon_2 \vdash B} }{ \Upsilon_1 , !A , !\Gamma , \Upsilon_2 \vdash B } \text{ Cut} }{ \displaystyle\frac{\Upsilon_1 , !\Gamma , !\Gamma , \Upsilon_2 \vdash B}{\Upsilon_1 , !\Gamma , \Upsilon_2 \vdash B} \rlap{\;\text{ Series of Contractions and Exchanges}} } \text{ Cut}$

¿Por qué es un paso inductivo válido? Ni el tamaño de la fórmula de corte ni el tamaño de las derivaciones están disminuyendo. (En la prueba transformada, la rama derecha del corte inferior es potencialmente más grande después de eliminar inductivamente el corte superior). Por lo tanto, no está claro por qué este procedimiento debería terminar.

linear-logic Sebastien Zany
fuente

Acabo de echar un vistazo rápido y esto es mucho tiempo desde que no he leído tal formalismo, pero tengo la impresión de que el objetivo aquí es eliminar el corte después de una Promoción vs Contracción. En este caso, la transformación funciona ya que cada contracción está ahora debajo del corte, por lo que los cortes aumentan en el árbol de derivación y se eliminan inductivamente.

holf

El problema es que en la prueba transformada, la rama derecha del corte inferior es potencialmente más grande después de eliminar inductivamente el corte superior. (Agregaré esto como aclaración.)

Sebastien Zany

Sí, pero el número de contracciones se ha reducido en uno. Por lo que puedo decir (una vez más, no profundicé demasiado en los detalles), ninguna otra transformación aumenta el número de contracciones. Por lo tanto, si observa el valor (#contracción, lo que sea que necesite para el reposo), este valor siempre disminuye en el orden lexicográfico, por lo que terminará en algún momento.

holf

Además de lo que dijeron Holf y Neel, ¿no funciona una variación del argumento habitual (grado, rango)? Quiero decir, ¿cuál es la diferencia entre este paso y la eliminación habitual de un corte en una contracción en LJ? (Me refiero al cálculo secuencial intuitivo de Gentzen)

Damiano Mazza

Pero, ¿cómo eliminas el corte B? Lo único que parece que puede hacer en el caso de Promoción-Corte es intercambiar las posiciones de los dos cortes A y B. Pero luego, termina exactamente en la misma situación. Si elimina B (que ahora está arriba), puede aumentar el número de contracciones por encima de A.

Jérôme Fortier

Extiendo lo que escribí como comentario. Como hay una gran cantidad de casos en la prueba, solo doy una idea de por qué termina esta transformación. La respuesta corta es:

En el caso de promoción vs contracción, después de la transformación, el número de contracciones en la parte de la prueba que contiene cortes ha disminuido en uno.

Para entrar un poco más en detalles, diría que se equivocó porque pensó que el número de cortes o el tamaño de la prueba deberían disminuir para garantizar la terminación. Sin embargo, la terminación puede probarse observando otros parámetros de la prueba.

Si desea probar la terminación, solo tiene que mostrar que cada regla se aplicará un número finito de tiempo. Puede probar que la promoción de la regla de transformación frente a la contracción se aplicará la mayoría de las veces m, donde m es el número de contracciones en su prueba inicial. Para probar esto, solo debe observar que ninguna regla introduce una nueva contracción en el árbol de pruebas. Y este disminuye el número de contracciones en uno. Puede hacer este truco para cualquier otra regla "promoción vs sthg" para demostrar que esta se aplicará solo un número finito de veces.

holf
fuente

¿Por qué termina este procedimiento de eliminación de corte (caso de contracción)?

3.9.3 Promoción versus contracción

Respuestas: