Teorema da dedução

Introdução e importância

O Teorema da dedução é um meta-teorema do cálculo proposicional. Seu enunciado é: Se $\Gamma\cup \{A\}\vdash B$, então $\Gamma\vdash A \implies B$.

Um enunciado mais humano seria: Se com os axiomas, um conjunto de hipóteses $\Gamma$ e com uma hipotese $A$ é possível deduzir $B$, então com o mesmo conjunto $\Gamma$ é possível deduzir $A \implies B$.

O Teorema da dedução é importante pois confirma a possibilidade de assumir uma hipótese $A$ e chegar em $B$ para demonstrar $A\implies B$. Por exemplo, se quisermos demonstrar $x \text{ primo} \implies x^2 \text{ primo}$, podemos assumir $x \text{ primo}$ e chegar usando os axiomas da aritmética que $x^2$ é primo e isso seria equivalente a demonstrar a implicação.

Demonstração

Queremos demonstrar: Se $\Gamma\cup \{A\}\vdash B$, então $\Gamma\vdash A \implies B$.

Para simplificar notação, vamos considerar que os axiomas da teoria estão contidos em $\Gamma$.

Primeiro, vamos analisar o que $\Gamma\cup \{A\}\vdash B$ significa. A nossa hipótese diz que existe uma demonstração de $B$ usando $\Gamma\cup \{A\}$ como hipótese. Ou seja, existe uma sequência $X_1,X_2,\cdots,X_n$ obedecendo (1) $X_n = B$ e (2) Para cada $X_i$, pelo menos um dos 3 ocorre:

• $X_i$ veio por M.P de dois anteriores;
• $X_i = A$ ;
• $X_i \in \Gamma$.

A demonstração será por indução completa no tamanho da sequência $X_1,X_2,\cdots,X_n$.

Caso $n=1$:

No caso $n=1$, temos uma sequência $X_1$ com uma fórmula só. Pela propriedade (1) da sequência, temos $X_1 = B$. Observe que $X_1$ não pode ter vindo por M.P de dois anteriores, portanto pela propriedade (2) ou $X_1 = A$ ou $X_1 \in \Gamma$.

Se $X_1 = A$, temos $X_1 = B = A$. Pelo Teorema 1 , temos $\Gamma \vdash A \implies A$. Como $A=B$, temos $\Gamma \vdash A \implies B$.

Se $X_1 \in \Gamma $, temos $X_1 = B \in \Gamma$. Logo $B$ é uma das hipóteses. Temos:

1. $\Gamma$ (Hipótese)
2. $B $ ($B \in \Gamma$)
3. $B \implies (A \implies B)$ ( Axioma 1 )
4. $A \implies B$ (MP 2,3)

Hipótese de indução

Supomos que se $\Gamma\cup \{A \} \vdash B$ e a demonstração de $B$ dada por $X_1,X_2,\cdots,X_n$ tiver tamanho menor ou igual a $k$, então $\Gamma \vdash A \implies B$.

Caso $n = k+1$:

Temos $\Gamma\cup \{A \} \vdash B$ e a demonstração de $B$ é dada por $X_1,X_2,\cdots,X_k, X_{k+1}$. Temos portanto $B = X_{k+1}$ e pelo menos um dos 3 ocorre:

• $X_{k+1}$ veio por M.P de dois anteriores;
• $X_{k+1} = A$ ;
• $X_{k+1} \in \Gamma$.

Se $X_{k+1} = A$ ou $X_{k+1} \in \Gamma$, a demonstração será análoga ao caso $n =1$.

Se $B = X_{k+1}$ veio por M.P de dois anteriores, existem $X_j$ ($1 \leq j \leq k$) e $X_q$ ($1 \leq q < j$) tal que $X_j = (X_q \implies B) $. Pela hipótese de indução $\Gamma \vdash A \implies X_j$ e $\Gamma \vdash A \implies X_q$. Temos:

1. $\Gamma$ (Hipótese)
2. $A \implies X_j$ (Hipótese de indução)
3. $A \implies X_q$ (Hipótese de indução)
4. $A \implies (X_q \implies B)$ (2 e $X_j = (X_q \implies B)$)
5. $ ( A \implies (X_q \implies B) ) \implies ((A \implies X_q) \implies (A \implies B) ) $ (Axioma 2)
6. $ (A \implies X_q) \implies (A \implies B) $ (MP 4,5)
7. $ A \implies B $ (MP 3,6)