Thread: Question about proof by contradiction

Hi all!

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!
James

Originally Posted by james121515

Hi all!

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!
James

So, you are saying that the biconditional is the conclusion of an argument? If so, then you'll need to let p be false and q true, and then try to avoid contradiction in the premises with the truth values under each main operator being true. You will then have to let q be false and p be false and the same...

Originally Posted by james121515

So, what we do is, negate the statement, assume the hypothesis and also assume the negation of the conclusion, and then reach a contradiction.

That's correct, though the statement does not need to be an implication. For example, below you are trying to prove a biconditional.

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.

Originally Posted by james121515

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?

You are absolutely right . We need to prove that a disjunction p/\~q \/ ~p/\q implies a contradiction. Now, for any formulas a, b, and c, (a \/ b) -> c is equivalent to (a -> c) /\ (b -> c). That's what reasoning by cases means: if we know a \/ b and want to prove c, we need to consider two cases, a and b, and prove c in both of them.

Originally Posted by james121515

Hi all!

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!
James

No. The statement "p and q are both true" is false if either of p and q is false.

Originally Posted by HallsofIvy

No. The statement "p and q are both true" is false if either of p and q is false.

I think VonNemo was talking about the disjunction p/\~q \/ ~p/\q. To prove that it is false, one needs to show that both p/\~q and ~p/\q lead to contradiction.