If $\Phi \vdash \phi \to \psi$, show that $\Phi, \phi, \neg\psi$ is inconsistent.

Question

If $\Phi \vdash \phi \to \psi$, show that $\Phi, \phi, \neg\psi$ is inconsistent.

I am stuck on my proof.

Assume that $\Phi \vdash \phi \to \psi$. Then $\Phi, \neg(\phi \to \psi)$ is inconsistent or $\Phi, \phi \wedge \neg \psi$ is inconsistent. Then $\sigma(\phi \wedge \neg \psi) = F$.

I am not sure where to go from here since the falsity can be made in three ways and I just wanted one way, where $\sigma(\phi)=\sigma(\neg\psi)=F$.

Answer 1

Use the deduction theorem.

$\Phi\vdash \phi\to\psi$, so $\Phi,\phi\vdash\psi$. Hence $\Phi,\phi,\lnot\psi$ syntactically entails both $\psi$ (coming from $\Phi,\phi$) and $\lnot\psi$ (from $\lnot\psi\vdash\lnot\psi$), so is inconsistent.

Or with valuations: Let $v$ be a valuation that assigns $\top$ to all of $\Phi,\phi,\lnot\psi$. From $\Phi\vdash\phi\to\psi$, we have $v(\phi\to\psi)=\top$. Also, by supposition $v(\phi)=\top$, so we must have $v(\psi)=\top$, contradicting $v(\lnot\psi)=\top$.

Answer 2

Assume that $\Phi \vdash \phi \to \psi$. Then $\Phi, \neg(\phi \to \psi)$ is inconsistent or $\Phi, \phi \wedge \neg \psi$ is inconsistent.

If you are allowed to use those substitution equivalences, you're done.

When $\{x, y\land z\}$ is inconsistent, so too $\{x,y,z\}$ is inconsistent, because $\nu(y\land z)=\mathrm T$ iff $\nu(y)\land\mathrm T$ and $\nu(z)\land\mathrm T$.

So $\{x, y, z\}$ cannot be satisfied by any evaluation exactly when $\{x, y\land z\}$ cannot be satisfied.

---

...

---

But more simply, use deduction theorem: When $\Phi\vdash \phi\to \psi$, then we may infer that $\Phi, \phi\vdash \psi$ and so...