1. Mar 20, 2004

### Jin314159

Hi folks. Long-time lurker, first-time poster. Anyways, my question regards the legitimacy of a contradiction-contrapositive hybrid method of proving.

Let's say we need to prove P implies Q. Contradiction says: If P implies Q_not leads to a contradiction, then we are done. Contrapositive says: If Q_not implies P_not, then we are done.

So a Contradiction-Contrapositive hybrid consists of first applying contradition, and then applying contrapositive. For example: To prove P implies Q by contradiction, we need to show P implies Q_not leads to a contradiction. But if we can also show that P_not implies Q leads to a contradiction, then are we done?

Is this method of proving legit?

2. Mar 21, 2004

### HallsofIvy

Staff Emeritus

This is wrong. "If P implies Q_not leads to a contradiction" then P does NOT imply Q_not. That says nothing about what P DOES imply: in particular it does not prove that P implies Q.

"(A implies B)_not" is equivalent to "A and B_not" not "A implies B_not" as you seem to think.

In proof by contradiction we do not assume that "P implies Q_not" and then show that we get a contradiction. We assume P and Q_not and show that that leads to a contradiction. In the simplest cases the contradiction is to show that from Q_not we can arrive at P_not (which contradicts P)- that is the same as proving the contrapositive.

Finally, "If we can also show that P_not implies Q leads to a contradiction, then are we done?"

No, "P_not implies Q leads to a contradiction" is equivalent to "(P and Q_not)_not" which is the same as "P and Q" not "P implies Q".

3. Mar 21, 2004

### matt grime

not( P and notQ) is the same as [(notP) or (Q)] which is the same as P=>Q, assuming I can read it correctly which is by no means certain.

But the rest (of HoI's post) seems right as much as my befuddled brain can be bothered to figure out.

Last edited: Mar 21, 2004
4. Mar 22, 2004

### Jin314159

I'm a bit confused at the difference between "P implies Q" and "P and Q." Understanding this discrepancy will help me understand your explanation.

5. Mar 22, 2004

### Jin314159

Actually, let me take a stab at what the difference between "P and Q" and "P implies Q" is.

P and Q means that it is possible for P and Q to both occur. For example, it's possible to be both fat and bald.

But P implies Q means that if the former is true, it's for certain that the later is true. So taking our previous example, being fat does not imply being bald.

6. Mar 23, 2004

### metacristi

Jin314159

From the definition of implication [symbol -> ;where p -> q is logically equvalent with (not)p OR q] can be derived the so called modus ponendo ponens and modus tollendo tollens:

If p -> q and p=true (or 1) then q=1 (true) modus ponendo ponens

If p -> q and q=false (0) then p=0 (false) modus tollendo tollens

From the modus tollendo tollens we can derive the following logical equivalence (<->):

p -> q <-> (not)q -> (not)p

This is exactly the contraposition rule you mentioned above and from the defintion of equivalence results that if we prove that (non)q implies (non)p then we have also proved that p -> q.

But the fact that p does not imply (non)q [or that (not)p does not imply q] does not mean that p must imply with necessity q.

Last edited: Mar 24, 2004