Teorema de la deducción


Teorema de la deducción

El teorema de la deducción es un metateorema de la lógica proposicional, la lógica de primer orden y otros sistemas lógicos, que es bastante utilizado para demostrar otros metateoremas.[1] Se trata de una formalización de la técnica de demostración ordinaria según la cual para demostrar que de A se sigue B, basta con suponer A y a partir de ello llegar a la conclusión de que B.

Más formalmente, el teorema establece que si una fórmula B es deducible (en un sistema deductivo S) a partir del conjunto de fórmulas \Gamma \cup \{A\}, entonces A → B es deducible a partir de Γ solamente.[1] En símbolos:

\Gamma \cup \{A\} \vdash_S B   implica   \Gamma \vdash_S A \to B

O alternativamente, en la notación del cálculo de secuentes:

\Gamma, A \vdash_S B   implica   \Gamma \vdash_S A \to B

En el caso especial donde Γ es el conjunto vacío, el teorema de la deducción dice que:[1]

A \vdash_S B   implica   \vdash_S A \to B

El teorema de la deducción parece haber sido demostrado por primera vez por Alfred Tarski en 1921, pero la primera demostración publicada es de Jacques Herbrand en 1930.[1]

Contenido

Converso del teorema de la deducción

A partir del teorema de la deducción, es fácil demostrar que si A → B es deducible (en un sistema deductivo S) a partir de Γ, entonces B es deducible a partir de \Gamma \cup \{A\}.[1] Simbólicamente:

\Gamma \vdash_S A \to B   implica   \Gamma \cup \{A\} \vdash_S B

Esto, junto con el teorema de la deducción, permite establecer el metateorema:[1]

\Gamma \cup \{A\} \vdash_S B   si y sólo si   \Gamma \vdash_S A \to B

Y cuando Γ es el conjunto vacío:

A \vdash_S B   si y sólo si   \vdash_S A \to B

El teorema en los sistemas de deducción natural

El teorema de la deducción se utiliza en los sistemas de deducción natural como regla de introducción del condicional material. La regla dice que si suponiendo A se llega a la conclusión de que B, entonces se puede afirmar que A → B, introduciendo así un condicional material. Por ejemplo, una demostración que hace uso de la regla de introducción del condicional material podría ser:

A demostrar: \phi \to \phi \,
Paso Fórmula Razón
1 \phi \, Supuesto.
2 \phi \or \phi Desde (1) por introducción de la disyunción.
3 (\phi \or \phi) \and \phi Desde (1) y (2) por introducción de la conjunción.
4 \phi \, Desde (3) por eliminación de la conjunción.
5 \phi \vdash \phi Resumen de (1) hasta (4).
6 \vdash \phi \to \phi Desde (5) por introducción del condicional. Q.E.D.

Véase también

Notas y referencias

  1. a b c d e f Hunter, Geoffrey (1971). «Sección 26». Metalogic: An Introduction to the Metatheory of Standard First-Order Logic. University of California Press. 

Wikimedia foundation. 2010.