Teorema de la deducción

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 \Gamma 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 \Gamma 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]

Converso del teorema de la deducción[editar]

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 \Gamma, 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 \Gamma 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[editar]

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[editar]

Notas y referencias[editar]

  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.