I had a very basic question about the logic behind proof by contradiction.
Firstly, I am trying to understand the rationale behind proof by contradiction. So, what we do is, negate the statement, assume the hypothesis and also assume the negation of the conclusion, and then reach a contradiction. Once we reach that contradiction, what we've done in essence, is show that the negation of the statement we wanted to prove is false, therefore, the statement itself must be true. Is this correct?
If this is correct, then please help me clear something up. Say we wanted to prove, by contradiction, a biconditional statement p<=>q. The negation of that is p/\~q \/ ~p/\q. I was taught we only need to show that one of these leads to a contradiction, and the proof is complete. But, since we're trying to show that this is false, wouldn't we need to show that BOTH sides are false? I thought that a disjunction is only false if BOTH sides are false, so wouldn't we need to show that both p/\~q and ~p/\q lead to contradiction in order to show its false, and hence, our original statement is true?
Thanks for any help!
To prove p by contradiction, we assume ~p and derive a contradiction. This means that we proved ~~p, and therefore p.
To prove p -> q by contradiction following the scheme above, we assume ~(p -> q), which is p /\ ~q. From this we derive a contradiction, thus proving ~(p /\ ~q), which is (equivalent to) p -> q. Here is another way to describe this: to prove p -> q, we assume p and then prove q by contradiction. I.e., we assume ~q (thus we assumed p and ~q so far), derive a contradiction, getting ~~q, i.e., q. Discharging p, we obtain p -> q.