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

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

• We have to produce a lot of preliminary work ... : use A1) and A2) to prove B1) $\vdash \phi \to \phi$. – Mauro ALLEGRANZA Sep 21 '18 at 7:56
• With B1) prove the Deduction Theorem. – Mauro ALLEGRANZA Sep 21 '18 at 7:57
• With the DT prove the "auxiliary" rule : B2) $\phi \to \psi, \psi \to \chi \vdash \phi \to \chi$. – Mauro ALLEGRANZA Sep 21 '18 at 7:57
• Prove Double Negation laws : B3) $\lnot \lnot \phi \vdash \phi$ and B4) $\phi \vdash \lnot \lnot \phi$. – Mauro ALLEGRANZA Sep 21 '18 at 7:59
• Now we can prove a useful "variant" of A3) : B5) $\vdash (\phi \to \psi) \to ((\phi \to \lnot \psi) \to \lnot \phi)$. – Mauro ALLEGRANZA Sep 21 '18 at 8:01