# Proof by contradiction: May I assume $P$ (true) in $\neg Q \land P \Rightarrow P \land \neg P$ to prove $Q$ by contradiction

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.

• 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". – Mauro ALLEGRANZA Jan 12 '14 at 16:54
• 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 ? – Mauro ALLEGRANZA Jan 12 '14 at 20:54
• 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$. – Shuzheng Jan 12 '14 at 21:32
• 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$. – Mauro ALLEGRANZA Jan 12 '14 at 21:43
• 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$" . – Mauro ALLEGRANZA Jan 13 '14 at 7:18

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

• Why not ? Then a get an implication $T \rightarrow F$ ? – Shuzheng Jan 25 '14 at 7:33
• sorry i meant P and Q both false edited answer – Willemien Jan 25 '14 at 10:06
• But I know $P$ is a true statement. $P$ could be "$G$ is a graph with $2$ vertices" etc. – Shuzheng Jan 25 '14 at 11:20
• 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 – Willemien Jan 25 '14 at 11:28
• 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$? – Shuzheng Jan 25 '14 at 11:33