8
$\begingroup$

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

  • 4
    I think this is a good question, and I don't see why anyone would vote to close it as "not a real question".2012-12-13

3 Answers 3

8

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

  • 0
    Very nice derivation, thanks. When H is consistent then we cannot have H |- Q and H |- ~Q, therefore also not P |- Q.2012-12-13
  • 0
    Yes. And say no to intuitionstic logic! :-D2012-12-13
  • 0
    But we don't have $P \vdash Q$? so how does that apply here?2012-12-13
  • 1
    @amWhy: Assume by contradiction...2012-12-13
  • 0
    Asaf: Yes...I see now. Dahhh!2012-12-13
  • 0
    @amWhy: Oh, but it was a good remark. We all make those small jumps in our minds, it's good to have someone to set us back! (Well except Shelah, he makes huge leaps in his mind.)2012-12-13
4

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

4

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