0
$\begingroup$

Suppose I wish to do a proof by contradiction the statement $Q$.

In proving $Q$ may I assume $\neg Q \land P$ (where $P$ is a statement known to be true) and show the implication $\neg Q \land P \Rightarrow P \land \neg P$ ?

That is in proving $P \land \neg P$, the statement $P$ follows directly from the assumption, so all that's left to get a contradiction is to prove $\neg P$. Then $\neg (\neg Q \land P)$ is true, which implies $Q$ must be true, since $\neg P$ is false.

$\endgroup$
  • $\begingroup$ You can use tautologies like : $A \to (\lnot A \to B)$ or $\lnot A \to (A \to B)$. If you have derived a contradiction (i.e. $A \land \lnot A$), you can use the above tautologies to derive "everything". $\endgroup$ – Mauro ALLEGRANZA Jan 12 '14 at 16:54
  • $\begingroup$ I think that the base of a "proof by contradiction" is the following rule : if $A \vdash B$ and $A \vdash \lnot B$, then $\vdash \lnot A$. So, why you want to assume also $P$ in order to get the contradiction ? $\endgroup$ – Mauro ALLEGRANZA Jan 12 '14 at 20:54
  • $\begingroup$ Consider the proof "No odd number can be written as the sum of three even numbers". Then proof by contradiction goes: Suppose $n$ is an odd number and $n = 2a + 2b + 2c$. Then $n$ is odd and $n$ is even, a contradiction. Here we assume $n$ is odd and $n$ is a sum of three even numbers, and get the contradiction that $n$ is odd and $n$ is even, where $n$ is odd was part of the assumption in this case $P$. $\endgroup$ – Shuzheng Jan 12 '14 at 21:32
  • $\begingroup$ Starting from $A$ = "$n$ is an odd number and $n=2a+2b+2c$" you have derived both $B$ = "$n$ is odd" and $\lnot B$" = "$n$ is even", i.e "$n$ is not odd". Using the above rule, you get $\lnot A$ that is "not [ ($n$ is odd) and ($n=2a+2b+2c$) ]. But $\lnot (P \land Q)$ is $(\lnot P \lor \lnot Q)$. So you have : ($n$ is even) or $n \neq 2a+2b+2c$. $\endgroup$ – Mauro ALLEGRANZA Jan 12 '14 at 21:43
  • $\begingroup$ But also, $(\lnot P\lor \lnot Q)$ is equivalent to $(P \to \lnot Q)$. So, in the end, we have : "if $n$ is an odd number then $n \neq 2a+2b+2c$" . $\endgroup$ – Mauro ALLEGRANZA Jan 13 '14 at 7:18
0
$\begingroup$

Yes you can, just start with the negation of what you want to proof and get to a contradiction (see also http://en.wikipedia.org/wiki/Proof_by_contradiction)

Here is a proof in natural deduction

 1 | . . (~Q & P) -> (P & ~P) . Premisse
 2 | . . P. . . . . . . . . . . Premisse
 . |------------------------------------- 
 3 | |__ ~Q . . . . . . . . . . Assumption (negated conclusion) 
 4 | | . ~Q & P . . . . . . . . 3,2 & Introduction
 5 | | . P & ~P . . . . . . . . 1,4 -> Elimination
 . | <---------------------------- end subproof
 6 | . . ~~Q. . . . . . . . . . 3-5 ~ Introduction
 7 | . . Q. . . . . . . . . . . 6 ~~ Elimination
 = | ========================================
 PS line 7 is not allowed in constructive logic 

to add another proof (so you can study the differences)

Proof P -> Q from (~Q & P) -> (P & ~P)

 1 | . . . (~Q & P) -> (P & ~P) . Premisse
 . |-------------------------------------
 2 | |____ P. . . . . . . . . . . Assumption (hypothesis)      
 3 | | |__ ~Q . . . . . . . . . . Assumption (negated conclusion) 
 4 | | | . ~Q & P . . . . . . . . 3,2 & Introduction
 5 | | | . P & ~P . . . . . . . . 1,4 -> Elimination
 . | | <---------------------------- end subproof
 6 | | . . ~~Q. . . . . . . . . . 3-5 ~ Introduction
 7 | | . . Q. . . . . . . . . . . 7 ~~ Elimination
 . | <------------------------------ end subproof
 8 | . . . P -> Q . . . . . . . . 2-7 -> Introduction
 = | ========================================
 PS line 7 is not allowed in constructive logic

Hope it helps

$\endgroup$
  • $\begingroup$ Why not ? Then a get an implication $T \rightarrow F$ ? $\endgroup$ – Shuzheng Jan 25 '14 at 7:33
  • $\begingroup$ sorry i meant P and Q both false edited answer $\endgroup$ – Willemien Jan 25 '14 at 10:06
  • $\begingroup$ But I know $P$ is a true statement. $P$ could be "$G$ is a graph with $2$ vertices" etc. $\endgroup$ – Shuzheng Jan 25 '14 at 11:20
  • $\begingroup$ If you know that P is true then you don't have to assume it (but treat it as premisse) assume ~Q instead, will edit answer again $\endgroup$ – Willemien Jan 25 '14 at 11:28
  • $\begingroup$ Ahh, so in doing a proof by contradiction I should not assume what I know is true ($P$), and then get a contradiction like $\neg Q$ implies $P \land \neg P$? $\endgroup$ – Shuzheng Jan 25 '14 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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