Demostrar o refutar que para la teoría $T$ , $T \vdash (\phi \rightarrow \psi) \iff T \cup \{\phi\} \vdash \psi$ .

Question

Demostrar o refutar que para la teoría $T$ , $T \vdash (\phi \rightarrow \psi) \iff T \cup \{\phi\} \vdash \psi$ .

Esto parece bastante correcto, pero no sé cómo probarlo.

Así que vamos a empezar con $\Rightarrow$ : Así que si $\mathcal M \vDash T$ entonces $\mathcal M \vDash (\phi \rightarrow \psi)$ para cada estructura $\mathcal M$ . Así que $\mathcal M \vDash (\lnot \phi \lor \psi)$ . ¿Cómo puedo continuar desde aquí?

Gracias.

Answer 1

No estoy seguro de por qué quieres hablar de estructuras (o asumir la completitud, para el caso), así que aquí hay una prueba puramente sintáctica.

---

$T\vdash(\phi\to\psi)\Longrightarrow T\cup\left\{\phi\right\}\vdash\psi$

Dejemos que $T\vdash(\phi\to\psi)$ .

Entonces hay una deducción $D=\langle\gamma_1,\ldots,\gamma_n\rangle$ de $(\phi\to\psi)$ de $T$ , donde $\gamma_n=(\phi\to\psi)$ y para cada $\gamma_k$ ( $1\le k\le n$ ), $\gamma_k$ es un miembro de $T$ , un axioma lógico u obtenido por Modus Ponens a partir de dos enunciados anteriores $\gamma_i$ y $\gamma_j=(\gamma_i\to\gamma_k)$ (donde $i<j<k$ ).

Así, $D'=\langle\gamma_1,\ldots,\gamma_n,\phi\rangle$ es una deducción de $\psi$ de $T\cup\left\{\phi\right\}$ , donde $\phi\in T\cup\left\{\phi\right\}$ y $\psi$ se obtiene por Modus Ponens a partir de $(\phi\to\psi)$ .

Por lo tanto, $T\cup\left\{\phi\right\}\vdash\psi$ .

---

$T\cup\left\{\phi\right\}\vdash\psi\Longrightarrow T\vdash(\phi\to\psi)$

Esto se deduce inmediatamente si se asume el Teorema de la Deducción. Pero en aras de la exhaustividad, que por otra parte no asumo ( juego de palabras ), aquí hay una prueba.

Dejemos que $T\cup\left\{\phi\right\}\vdash\psi$ .

Entonces hay una deducción $D=\langle\gamma_1,\ldots,\gamma_n\rangle$ de $\psi$ de $T\cup\left\{\phi\right\}$ . Ahora trabajamos por inducción sobre la longitud de $D$ :

• $n=1$ : entonces, o bien $\psi\in T$ o $\psi=\phi$ o $\psi$ es un axioma lógico (o una generalización del mismo).
  • $\psi\in T$ Entonces $T\vdash\psi$ . Afirmamos que $\psi\to(\phi\to\psi)$ es una tautología de la lógica proposicional, por lo tanto una instancia del Axioma $1$ . Así, $T\vdash \psi\to(\phi\to\psi)$ . Por Modus Ponens: $T\vdash\phi\to\psi$ .
  • $\psi=\phi$ por la Ley de la Identidad, $\vdash\alpha\to\alpha$ . Así, $T\vdash\phi\to\psi$ .
  • $\psi$ es un axioma lógico : entonces $T\vdash\psi$ . Como en el caso anterior, podemos construir una tautología y aplicar el Modus Ponens para obtener $T\vdash\phi\to\psi$ .
• Hipótesis Inductiva : suponer que para todo $k<n$ , si $T\cup\left\{\phi\right\}\vdash\gamma_k$ entonces $T\vdash(\phi\to\gamma_k)$ .
• $n>1$ : $\psi=\gamma_n$ debe obtenerse entonces por Modus Ponens a partir de dos afirmaciones anteriores $\gamma_i$ y $\gamma_j=(\gamma_i\to\gamma_n)$ (donde $i<j<n$ ). Pero por IH, ya que $T\cup\left\{\phi\right\}\vdash\gamma_i$ y $T\cup\left\{\phi\right\}\vdash\gamma_j$ entonces $T\vdash(\phi\to\gamma_i)$ y $T\vdash(\phi\to\gamma_j)$ siendo este último equivalente a $T\vdash(\phi\to(\gamma_i\to\gamma_n))$ . Así, por Modus Ponens $T\vdash(\phi\to\psi)$ .

Por lo tanto (por el axioma de inducción) $T\vdash(\phi\to\psi)$ .

---

$$\therefore T\vdash(\phi\to\psi)\Longleftrightarrow T\cup\left\{\phi\right\}\vdash\psi$$

Answer 2

Si $\mathcal M\vDash T\cup \{\phi\}$ entonces $\mathcal M \vDash \phi$ Así que $\mathcal M\not\vDash \neg\phi$ (es decir $\phi$ es falso en $\mathcal M$ ). Esto implica $$\mathcal M \vDash (\neg \phi \vee \psi) \to \psi$$ Por supuesto, podemos decir que $\mathcal M \vDash \psi$ como se ha reclamado.