Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Contradiction-Contrapositive hybrid

  1. Mar 20, 2004 #1
    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. jcsd
  3. Mar 21, 2004 #2


    User Avatar
    Science Advisor

    "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".
  4. Mar 21, 2004 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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
  5. Mar 22, 2004 #4
    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.
  6. Mar 22, 2004 #5
    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.
  7. Mar 23, 2004 #6

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook