1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ If $\mathcal M \vDash T \cup \{\phi\}$, then $\mathcal M \vDash \phi$, thus $\mathcal M \not\vDash \neg \phi$ so $\mathcal M \vDash \psi$. $\endgroup$ – AlexR May 26 '15 at 21:04
  • $\begingroup$ What does $\lnot (\mathcal M \vDash \lnot \phi)$ actually mean? Does it mean $ \mathcal M \not \vDash \lnot \phi$? $\endgroup$ – Ranly May 26 '15 at 21:06
  • $\begingroup$ Yes, sorry about that $\endgroup$ – AlexR May 26 '15 at 21:07
  • $\begingroup$ Ehh... I just doesn't see why is the conclusion that $\mathcal M \vDash \psi$ $\endgroup$ – Ranly May 26 '15 at 21:09
  • 2
    $\begingroup$ But you are "mixing" derivability ($\vdash$) with logical implication ($\vDash$); in order to do so, you have to specify that for the proof system you are referring to the Completeness Thoerem holds (i.e., when you use $\mathcal M \vDash \psi$ to conclude that $T \cup \{ \phi \} \vdash \psi$). $\endgroup$ – Mauro ALLEGRANZA May 27 '15 at 9:05
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.