Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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". –  Asaf Karagila Dec 13 '12 at 23:33

3 Answers 3

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|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. –  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
1  
@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|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|improve this answer

Your Answer

 
discard

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.