Contradiction-Contrapositive hybrid

[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?

[HallsofIvy]

"Contradiction says: If P implies Q_not leads to a contradiction, then we are done."

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".

[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.

[Jin314159]

Originally posted by HallsofIvy
"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.


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.

[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.

[metacristi]

Jin314159

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?

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.