Contradiction vs contraposition

[Mr Davis 97]

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?

 

[mfb]

$\neg (p \rightarrow q) = \neg p \wedge q$

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.

 

[andrewkirk]

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.

 

[Edgardo]

You are asking about the difference between "Proof by contraposition" and "Proof by contradiction", and here is an example.


To prove $p \rightarrow q$:

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

- In proof by contradiction your start by assuming that the opposite of $p \rightarrow q$ is true. So you assume that $p \wedge \neg q$ 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.

 

[Svein]

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