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

I Contradiction vs contraposition

  1. Sep 21, 2017 #1
    Say I have the theorem ##p \rightarrow q##. What is the difference between proving that ##\neg q \rightarrow \neg p## is true and showing that ##\neg (p \rightarrow q) = \neg p \wedge q## leads to a contradiction?
  2. jcsd
  3. Sep 21, 2017 #2


    User Avatar
    2017 Award

    Staff: Mentor

    That should be ##\neg (p \rightarrow q) = \neg q \wedge p##. If you are careful with statements like "for all" and "there exists", then they are all the same thing.
  4. Sep 21, 2017 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That last formula should be ##p\wedge \neg q##.

    Subject to that, the two approaches are logically equivalent in classical first-order predicate logic, which is all that mathematicians that don't specialise in logic worry about.

    In intuitionist logic and other logics where some of the basic axioms such as ##\neg\neg p\leftrightarrow p## are not accepted, the approaches may give different results.
  5. Sep 26, 2017 #4
    You are asking about the difference between "Proof by contraposition" and "Proof by contradiction", and here is an example.

    To prove [itex]p \rightarrow q[/itex]:

    - In proof by contraposition you start by assuming that [itex]\neg q[/itex] is true and derive the statement [itex]\neg p[/itex]. Here, the path is clear, i.e. you start at [itex]\neg q[/itex] and arrive at [itex]\neg p[/itex].

    - In proof by contradiction your start by assuming that the opposite of [itex]p \rightarrow q[/itex] is true. So you assume that [itex]p \wedge \neg q[/itex] is true and derive some contradiction. Here the path is not clear, nobody is going to tell you what the contradiction is and what it looks like.
  6. Sep 26, 2017 #5


    User Avatar
    Science Advisor

    The trouble with "proof by contradiction" is that if you make a mistake somewhere, you can easily end up in a contradiction without actually proving anything.

    Another point against "proof by contradiction" is that it does not help you in solving anything, it just says that the assumption is proved (but not how).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted