Diferencia entre Gentzen y cálculos de Hilbert

Question

¿Cuál es la diferencia entre Gentzen y cálculos de Hilbert?

De mi comprensión de la lectura de concisa introducción de Rautenberg a lógica matemática, cálculo de Gentzen se basa en cálculo de Hilbert, en tautologías y sequents.

¿Pero no cada siguiente de Gentzen una tautológica modus ponens?

¿Por ejemplo, el siguiente $X\vdash a \wedge b |X \vdash a,b$ puede ser escrito como la tautología $\forall X \forall a \forall b\:( X\vdash a \wedge b \rightarrow X \vdash a,b$), no puede él?

Answer 1

Usted puede ver una descripción detallada en : Francisco Pelletier & Allen Hazen, Deducción Natural :

Sequent Cálculo fue inventado por Gerhard Gentzen (1934), que la utilizan como un escalón para avanzar en su caracterización de deducción natural [...]. Es muy general la caracterización de una prueba; los básicos de la notación de ser $ϕ_1,\ldots,ϕ_n ⊢ ψ_1,\ldots,ψ_m$, lo que significa que es una consecuencia de las premisas $ϕ_1,\ldots,ϕ_n$ que al menos uno de $ψ_1,\ldots,ψ_m$ mantiene.

Si $\Gamma$

Answer 2

En realidad, Gentzen introdujo dos familias de cálculos, de los cuales el más importante quizás son la deducción natural de los cálculos (que Bruno Bentzen se refiere en su respuesta). Sequent cálculos son bastante diferentes de ambos deducción natural de los cálculos y de Hilbert de los cálculos. El segundo son dos formas de construir argumentos a partir de proposiciones (wffs en el correspondiente idioma lógico) a las proposiciones; sequent cálculos en lugar de manipular sequents (que puede ser leído como metalingüísticos reclamaciones acerca de lo siguiente de lo que en la lengua de que se trate).

Lo que usted realmente necesita para llegar a entender es que, en primer lugar, la relación entre Hilbert cálculos y Gentzen deducción natural de los cálculos: ver, por ejemplo, este folleto de la mina en diversas pruebas de estilos.

Y, a continuación, en segundo lugar, usted necesita para comprender la relación entre la deducción natural de los cálculos y sequent cálculos: ver cap. 1 de la espléndida Estructurales de la Prueba de Teoría por Sara Negri y Jan von Platón, disponible aquí.

Answer 3

Ambos sistemas son equivalentes en el sentido de que la prueba de los mismos teoremas.

Una de Hilbert-estilo de la deducción sistema utiliza el enfoque axiomático a prueba la teoría. En este tipo de cálculo, una prueba formal se compone de una secuencia finita de fórmulas de $\alpha_1, ..., \alpha_n$, donde cada una de las $\alpha_n$ es o bien un axioma o se obtiene a partir de las fórmulas anteriores, a través de una aplicación del modus ponens.

Por supuesto, muchos de los teoremas de la apariencia de Gentzen de la deducción natural reglas de inferencia, si el de la mejora de la relación ha de ser representado en el objeto de idioma a través de la implicación material:

• $\vdash(A\land B) \rightarrow A $ $\ \ \ \ $ y $ \ \ \ $ $\displaystyle \frac{A \land B}{A} $
• $\vdash((A \rightarrow \bot) \rightarrow \neg A) $ $\ \ \ \ $ y $ \ \ \ $ $\displaystyle \frac{\frac{A}{\bot} }{\neg A} $
• $\vdash A \rightarrow (A \lor B) $ $\ \ \ \ $ y $ \ \ \ $ $\displaystyle \frac{A}{A \lor B} $

De izquierda a derecha, Hilbert y Genzten estilo respectivamente.

Pero esto tiene un montón de inconvenientes técnicos. Hilbert-estilo de las pruebas son bastante artificial y más difícil de realizar en comparación a Gentzen estilo de las pruebas: A ver esto por ti mismo, tratamos de ofrecer una axiomática de la prueba de $A \rightarrow B,B \rightarrow C \vdash A \rightarrow C$ y, a continuación, un Gentzen de estilo prueba de ello. En su axiomática de la prueba, considerar como un ejercicio para probar con y sin utilizar el teorema de la deducción en su prueba.

Has notado la diferencia? Esto es parcialmente debido al hecho de que en Hilbert-estilo de cálculo uno no está permitido hacer hipotético razonamiento, es decir, argumentos como "vamos a $P$ ... a la conclusión de $Q$, por lo tanto $P$ implica $Q$" (ver la implicación de la introducción de la regla), que es parte de la práctica diaria de un matemático. El teorema de la deducción tipo de compensa, pero este es todavía un gran inconveniente.