Prove $\Sigma \vdash \lnot(\phi \rightarrow \psi)$ iff $\Sigma \vdash \phi$ and $\Sigma \vdash \lnot \psi.$

87 Views Asked by At

$\Sigma$ is a set of sentences, the set $ L$ consists of all axioms of the forms:

A1) $ \ \phi \rightarrow (\psi \rightarrow \phi)$

A2) $\ (\phi \rightarrow (\psi \rightarrow \theta)) \rightarrow ((\phi \rightarrow \psi) \rightarrow (\phi \rightarrow \theta))$

A3) $\ ((\lnot \phi \rightarrow \psi) \rightarrow (( \lnot \phi \rightarrow \lnot \psi) \rightarrow \phi))$

I can only use → with modus ponens to make any deductions.

I'm having a tough time dealing with $\Sigma \vdash \lnot(\phi \rightarrow \psi)$. I can't use $\land$ or $\lor$ so I can't use DeMorgan's law. I assume I have to use axiom A3 with $\phi$ as $(\phi \rightarrow \psi)$ or something. Any hints?