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