16 Teorema de la deduccion

Demostrar la validez de $\displaystyle\{p\rightarrow r\wedge s,r\rightarrow q\}\vdash p\rightarrow q\wedge s$ .

Demostrar la validez de $\displaystyle\{p\rightarrow r\wedge s,r\rightarrow q,p\}\vdash q\wedge s$ .

Sean $\displaystyle n\geq 1$ y $\displaystyle\varphi_{1},\varphi_{2},\ldots,\varphi_{n},\varphi$ una coleccion de formulas. Entonces

\displaystyle\{\varphi_{1},\varphi_{2},\ldots,\varphi_{n}\}\vdash\varphi

si y solo si

\displaystyle\{\varphi_{1},\varphi_{2},\ldots,\varphi_{n-1}\}\vdash\varphi_{n}\rightarrow\varphi

$\displaystyle\Rightarrow)$ Si tengo una demostracion

\displaystyle\begin{array}[]{c}\varphi_{1}\\ \vdots\\ \varphi_{n}\\ \alpha_{1}\\ \vdots\\ \alpha_{m}\\ \varphi\end{array}\Rightarrow\begin{array}[]{c}\varphi_{1}\\ \vdots\\ \varphi_{n-1}\\ \varphi_{n}\text{ \small Pr aux}\\ \alpha_{1}\\ \vdots\\ \alpha_{m}\\ \varphi\\ \varphi_{n}\rightarrow\varphi\\ \text{Demostracion del 2}\end{array}

$\displaystyle\Leftarrow)$

\displaystyle\begin{array}[]{c}\varphi_{1}\\ \vdots\\ \varphi_{n-1}\\ \beta\\ \vdots\\ \beta_{m}\\ \varphi_{n}\rightarrow\varphi\end{array}\Rightarrow\begin{array}[]{c}\varphi_{% 1}\\ \vdots\\ \varphi_{n-1}\\ \varphi_{n}\\ \beta_{1}\\ \vdots\\ \beta_{m}\\ \varphi_{n}\rightarrow\varphi\\ \varphi E\rightarrow a,b\end{array}

∎

No se puede demostrar que un razonamiento es incorrecto con Gentzen.

El teorema de la deduccion permite transformar cualquier razonamiento valido del sistema de Gentzen en un teorema de ese sistema. Por ejemplo, si

\displaystyle\{\varphi_{1},\varphi_{2}\}\vdash\varphi

es un razonamiento valido, entonces

\displaystyle\vdash\varphi_{1}\rightarrow(\varphi_{2}\rightarrow\varphi)

es un teorema.