# How to deduce that something does not follow?

Assume I have formulas $H$, $P$ and $Q$. Assume further that I can show in classical logic that $P$ follows from $H$:

$$H \vdash P$$

And that the negation of $Q$ follows from $H$:

$$H \vdash \neg Q$$

Can I then jump to the conclusion that $Q$ does not follow from $P$:

$$P\not\vdash Q \text{ ?}$$

Bye

-
I think this is a good question, and I don't see why anyone would vote to close it as "not a real question". –  Asaf Karagila Dec 13 '12 at 23:33

If $H$ is consistent then yes. Assume towards contradiction that this is not the case, then $P\vdash Q$.

1. $P\vdash Q$ implies $\vdash P\rightarrow Q$ using the deduction theorem.
2. Therefore $H\vdash P\land P\rightarrow Q$.
3. And so $H\vdash Q$.

If $H$ is inconsistent (e.g. $0=1$ or $\varnothing\in\varnothing$ sort of thing) then the principle of explosion says that everything is provable from $H$.

-
Very nice derivation, thanks. When H is consistent then we cannot have H |- Q and H |- ~Q, therefore also not P |- Q. –  Cookie Monster Dec 13 '12 at 23:34
Yes. And say no to intuitionstic logic! :-D –  Asaf Karagila Dec 13 '12 at 23:36
But we don't have $P \vdash Q$? so how does that apply here? –  amWhy Dec 13 '12 at 23:36
@amWhy: Assume by contradiction... –  Asaf Karagila Dec 13 '12 at 23:37
Asaf: Yes...I see now. Dahhh! –  amWhy Dec 13 '12 at 23:39

No. If $H$ is $0=1$, then you can deduce both $P$ and the negation of $Q$ from $H$, even if, say, $P=Q$.

-

What you can deduce is $$H \vdash (P \land \lnot Q),\quad\text{that is}\;\;\; H\vdash \lnot(P \rightarrow Q)$$

since $(P \land \lnot Q)\equiv \lnot(\lnot P \lor Q) \equiv \lnot (P\rightarrow Q)$

-