Prove or disprove that for theory $T$, $T \vdash (\phi \rightarrow \psi) \iff T \cup \{\phi\} \vdash \psi$.

Question

Prove or disprove that for theory $T$, $T \vdash (\phi \rightarrow \psi) \iff T \cup \{\phi\} \vdash \psi$.

This seems quite right, but I don't know how to prove it.

So lets start with $\Rightarrow$: So if $\mathcal M \vDash T$ then $\mathcal M \vDash (\phi \rightarrow \psi)$ for every structure $\mathcal M$. So $\mathcal M \vDash (\lnot \phi \lor \psi)$. How can I continue from here?

Thank you!

Answer 1

If $\mathcal M\vDash T\cup \{\phi\}$ then $\mathcal M \vDash \phi$, so $\mathcal M\not\vDash \neg\phi$ (i.e. $\phi$ is false in $\mathcal M$). This implies $$\mathcal M \vDash (\neg \phi \vee \psi) \to \psi$$ By assumption we can then say $\mathcal M \vDash \psi$ as claimed.

Answer 2

I'm not sure why you want to talk about structures (or assume completeness, for that matter), so here's a purely syntactic proof.

---

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

Let $T\vdash(\phi\to\psi)$.

Then there is a deduction $D=\langle\gamma_1,\ldots,\gamma_n\rangle$ of $(\phi\to\psi)$ from $T$, where $\gamma_n=(\phi\to\psi)$ and for each $\gamma_k$ ($1\le k\le n$), $\gamma_k$ is either a member of $T$, a logical axiom or obtained by Modus Ponens from two earlier statements $\gamma_i$ and $\gamma_j=(\gamma_i\to\gamma_k)$ (where $i<j<k$).

Thus $D'=\langle\gamma_1,\ldots,\gamma_n,\phi\rangle$ is a deduction of $\psi$ from $T\cup\left\{\phi\right\}$, where $\phi\in T\cup\left\{\phi\right\}$ and $\psi$ is obtained by Modus Ponens from $(\phi\to\psi)$.

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

---

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

This follows immediately if you assume the Deduction Theorem. But for the sake of completeness, which I am not otherwise assuming (pun), here's a proof.

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

Then there is a deduction $D=\langle\gamma_1,\ldots,\gamma_n\rangle$ of $\psi$ from $T\cup\left\{\phi\right\}$. We now work by induction on the length of $D$:

• $n=1$ : then either $\psi\in T$, or $\psi=\phi$, or $\psi$ is a logical axiom (or generalization thereof).
  • $\psi\in T$ : then $T\vdash\psi$. We claim that $\psi\to(\phi\to\psi)$ is a tautology of propositional logic, hence an instance of Axiom $1$. Thus $T\vdash \psi\to(\phi\to\psi)$. By Modus Ponens: $T\vdash\phi\to\psi$.
  • $\psi=\phi$ : by the Law of Identity, $\vdash\alpha\to\alpha$. Thus $T\vdash\phi\to\psi$.
  • $\psi$ is a logical axiom : then $T\vdash\psi$. As above, we can build a tautology and apply Modus Ponens to yield $T\vdash\phi\to\psi$.
• Inductive Hypothesis : assume that for all $k<n$, if $T\cup\left\{\phi\right\}\vdash\gamma_k$ then $T\vdash(\phi\to\gamma_k)$.
• $n>1$ : $\psi=\gamma_n$ must then be obtained by Modus Ponens from two earlier statements $\gamma_i$ and $\gamma_j=(\gamma_i\to\gamma_n)$ (where $i<j<n$). But by IH, since $T\cup\left\{\phi\right\}\vdash\gamma_i$ and $T\cup\left\{\phi\right\}\vdash\gamma_j$, then $T\vdash(\phi\to\gamma_i)$ and $T\vdash(\phi\to\gamma_j)$, the latter being equivalent to $T\vdash(\phi\to(\gamma_i\to\gamma_n))$. Thus by Modus Ponens $T\vdash(\phi\to\psi)$.

Therefore (by the axiom of induction) $T\vdash(\phi\to\psi)$.

---

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