Una pregunta sobre el teorema de la deducción

Question

El teorema de la deducción afirma que si $T \cup \{ \psi \} \vdash \varphi $ y la regla de generalización no se utiliza para demostrar $\varphi$ entonces $T \vdash \psi \rightarrow \varphi $ .

Si aplico la regla de la generalización, ¿en qué se equivoca exactamente si después aplico el teorema de la deducción? ¿Puede alguien dar un ejemplo?

Muchas gracias por su ayuda.

Answer 1

Lo importante es darse cuenta de que lo que está en el lado derecho de $\vdash$ tiene que ser un axioma (es decir, una fórmula universalmente verdadera). Por otro lado, en el LHS podemos suponer lo que queramos. Así, por ejemplo, si $T = \emptyset$ podemos demostrar que $\{ \varphi (x) \} \vdash \forall x \varphi(x)$ . Lo que no podemos hacer es demostrar que $\emptyset \vdash \varphi(x) \to \forall x \varphi (x)$ .

Para ver por qué no podemos, consideremos el ejemplo $\varphi (x) = (x = 1)$ :

Si asumimos ( $x = 1$ ) entonces obtenemos la siguiente prueba formal de $\{ x = 1 \} \vdash \forall x (x = 1)$ :

$(1) x = 1 ( \in T)$

$(2) \forall x (x = 1)$ (regla de generalización aplicada a ( $1$ ))

Por otro lado, si utilizamos la regla de la deducción sobre esto para obtener $\vdash (x = 1) \to \forall x (x = 1)$ entonces tenemos $\top \to \bot$ si sustituimos $x$ con $1$ donde es gratis. Pero esto es falso, de ahí que la fórmula del lado derecho no sea universalmente cierta.