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$
10
  • $\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, 2015 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, 2015 at 21:06
  • $\begingroup$ Yes, sorry about that $\endgroup$
    – AlexR
    May 26, 2015 at 21:07
  • $\begingroup$ Ehh... I just doesn't see why is the conclusion that $\mathcal M \vDash \psi$ $\endgroup$
    – Ranly
    May 26, 2015 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$ May 27, 2015 at 9:05

2 Answers 2

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .