Cuán complejas son naturales de la deducción de las pruebas en comparación con secuente cálculo pruebas sin cortar?

Question

Lo que sobre con el corte?

Y puede el secuente cálculo considerarse como deducción natural, pero con la implicación/el cuantificador universal de la introducción de las reglas que se hizo más explícita con los contextos? Hay formas alternativas de hacer esas reglas explícitas?

Answer 1

Una respuesta completa a su pregunta es probable que dependen de los detalles de la deducción natural y sistema sequent prueba del sistema que tiene en mente. En general, el secuente sistemas con corte tienden a ser bastante similar a la de los sistemas de deducción natural. Concretamente, dado un sistema de deducción natural, se puede establecer una estrecha relación secuente de cálculo, en la que un secuente $\Gamma\implies\phi$ es comprobable si y sólo si el sistema de deducción natural tiene una prueba de $\phi$ abierto (es decir, no cumplidas o uncanceled, según su terminología) suposiciones $\Gamma$. En esta situación, yo esperaría que la complejidad de sequent de las pruebas y de deducción natural de las pruebas a ser muy similares. Una prueba, o incluso una cuidadosa formulación de ese hecho requeriría de mira de cerca a los axiomas y las reglas de ambos sistemas, para ver cómo de cerca cada uno simula el otro.

Corte de eliminación, por otro lado, puede aumentar en gran medida la duración de las pruebas. Así que yo esperaría natural de la deducción de las pruebas a ser mucho más eficiente, en general, de corte libre de sequent pruebas.