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

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

• Can't you just use the contrapositive to show $\phi\implies \psi$ is equivalent to $\neg\psi\implies\neg\phi$? Then you have both $\phi$ and $\neg\phi$ as theorems. Commented Nov 5, 2018 at 22:59
• @JohnDouma This is what I got: Assume that $\Phi, \phi, \neg \psi$ is consistent. Then $\sigma(\phi) = \sigma(\neg \psi) = T$. Then $\sigma(\phi \wedge \neg \psi) = T$ or $\sigma(\neg (\phi \to \psi)) = T$. Then $\Phi, \neg (\phi \to \psi)$ is consistent. If $\Phi \vdash \phi \to \psi$, then $\Phi, \neg(\phi \to \psi)$ is inconsistent, which forms a contradiction. How is this?
– user482939
Commented Nov 5, 2018 at 23:09
• I don't understand why you aren't done after $\sigma(\neg (\phi \to \psi)) = T$ because you have a statement and its negative both true. Commented Nov 5, 2018 at 23:17

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

• (That's using modus ponens at the first step, not the deduction theorem!) Commented Nov 6, 2018 at 15:13
• It is deduction theorem: $\Phi\vdash p\to q$ iff $\Phi,p\vdash q$. Modus ponens is $\phi,\phi\to\psi\vdash\psi$. Commented Nov 6, 2018 at 15:18
• No, the label "deduction theory" is standardly used just for the direction if $\Phi,p\vdash q$ then $\Phi \vdash p \to q$. Commented Nov 6, 2018 at 15:22
• (The other direction relies on the modus ponens inference taking us from $\Phi \vdash p \to q$ and the triviality $\Phi, p \vdash p$ to $\Phi, p \vdash q$.) Commented Nov 6, 2018 at 17:05

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