Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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{ ?} $$


share|cite|improve this question
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
up vote 8 down vote accepted

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

share|cite|improve this answer
Very nice derivation, thanks. When H is consistent then we cannot have H |- Q and H |- ~Q, therefore also not P |- Q. – j4n bur53 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$.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.