Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the difference between a "proof by contradiction" and "proving the contrapositive"? Intuitive, it feels like doing the exact same thing. And when I compare an exercise, one person proves by contradiction, and the other proves the contrapositive, the proofs look almost exactly the same.

For example, say I want to prove: $P \implies Q$ When I want to prove by contradiction, I would say assume this is not true. Assume $Q$ is not true, and $P$ is true. Blabla, but this implies $P$ is not true, which is a contradiction.

When I want to prove the contrapositive, I say. Assume $Q$ is not true. Blabla, this implies $P$ is not true.

The only difference in the proof is that I assume $P$ is true in the beginning, when I want to prove by contradiction. But this feels almost redundant, as in the end I always get that this is not true. The only other way that I could get a contradiction is by proving that $Q$ is true. But this would be the exact same things as a direct proof.

Can somebody enlighten me a little bit here ? For example: Are there proofs that can be proven by contradiction but not proven by proving the contrapositve?

share|improve this question
    
Also related: math.stackexchange.com/questions/71245/… and more importantly, math.stackexchange.com/questions/227109/… –  Asaf Karagila Dec 20 '12 at 19:06
6  
Excellent question, +1. –  Matt N. Dec 20 '12 at 19:16
4  
Andrej Bauer had a recent blog post about this. "I am discovering that mathematicians cannot tell the difference between “proof by contradiction” and “proof of negation”. " –  MJD Dec 20 '12 at 22:39
2  
@MJD: Nearly three years is not very recent in terms of the internet. Just to get some perspective, Google+ was not yet conceived when Andrej posted this. –  Asaf Karagila Dec 21 '12 at 1:10
    
@asaf: I thought it was recent because I hadn't seen it when it was new, or perhaps because I saw it when it was new, forgot it, and saw it again last week. –  MJD Dec 21 '12 at 1:24

3 Answers 3

up vote 3 down vote accepted

There is a useful rule of thumb, when you have a proof by contradiction, to see whether it is "really" a proof by contrapositive.

In a proof of by contrapositive, you prove $P \to Q$ by assuming $\lnot Q$ and reasoning until you obtain $\lnot P$.

In a "genuine" proof by contradiction, you assume both $P$ and $\lnot Q$, and deduce some other contradiction $R \land \lnot R$.

So, at then end of your proof, ask yourself: Is the "contradiction" just that I have deduced $\lnot P$, when the implication was $P \to Q$? Did I never use $P$ as an assumption? If both answers are "yes" then your proof is a proof by contraposition, and you can rephrase it in that way.

For example, here is a proof by "contradiction":

Proposition: Assume $A \subseteq B$. If $x \not \in B$ then $x \not \in A$.

Proof. We proceed by contradiction. Assume $x \not \in B$ and $x \in A$. Then, since $A \subseteq B$, we have $x \in B$. This is a contradiction, so the proof is complete.

That proof can be directly rephrased into a proof by contrapositive:

Proposition: Assume $A \subseteq B$. If $x \not \in B$ then $x \not \in A$.

Proof. We proceed by contraposition. Assume $x \in A$. Then, since $A \subseteq B$, we have $x \in B$. This is what we wanted to prove, so the proof is complete.

Proof by contradiction can be applied to a much broader class of statements than proof by contraposition, which only works for implications. But there are proofs of implications by contradiction that cannot be directly rephrased into proofs by contraposition.

Proposition: If $x$ is a multiple of $6$ then $x$ is a multiple of $2$.

Proof. We proceed by contradiction. Let $x$ be a number that is a multiple of $6$ but not a multiple of $2$. Then $x = 6y$ for some $y$. We can rewrite this equation as $1\cdot x = 2\cdot (3y)$. Because the right hand side is a multiple of $2$, so is the left hand side. Then, because $2$ is prime, and $1\cdot x $ is a multiple of $2$, either $x$ is a multiple of $2$ or $1$ is a multiple of $2$. Since we have assumed that $x$ is not a multiple of $2$, we see that $1$ must be a multiple of $2$. But that is impossible: we know $1$ is not a multiple of $2$. So we have a contradiction: $1$ is a multiple of $2$ and $1$ is not a multiple of $2$. The proof is complete.

Of course that proposition can be proved directly as well: the point is just that the proof given is genuinely a proof by contradiction, rather than a proof by contraposition. The key benefit of proof by contradiction is that you can stop when you find any contradiction, not only a contradiction directly involving the hypotheses.

share|improve this answer
1  
It'd be very helpful if you also explicitly addressed the relationship between nonessential proof by contradicton vs. direct proof in proofs like Euclid's proof that there are infinitely many primes. Then we could refer to this answer as a canonical answer for eliminating such nonessential uses of contradiction. I don't think that will be clear to beginners from what is written above. it is addressed briefly in passing in Hardy and Woodgold's intelligencer article (and, iirc, also mentioned in passing in some answers here). –  Bill Dubuque Mar 17 at 4:20
    
@Bill Dubuque: that is a good idea, but I don't know if it fits into this question very well. I wrote something at math.stackexchange.com/a/715438/630 –  Carl Mummert Mar 17 at 12:49
1  
Thanks, that should prove very helpful to many readers. However, it doesn't seem to address the point I raised above, which perhaps was not clear. What I meant was that many proofs of Euclid's proposition P by contradiction are simply proofs of P that have prepended an unused assumption of $\,\lnot$ P. Thus, similar to above, deleting that unused assumption yields a direct proof of P. $\ \ $ –  Bill Dubuque Mar 17 at 23:35

To prove $P \rightarrow Q$, you can do the following:

  1. Prove directly, that is assume $P$ and show $Q$;
  2. Prove by contradiction, that is assume $P$ and $\lnot Q$ and derive a contradiction; or
  3. Prove the contrapositive, that is assume $\lnot Q$ and show $\lnot P$.

Sometimes the contradiction one arrives at in $(2)$ is merely contradicting the assumed premise $P$, and hence, as you note, is essentially a proof by contrapositive $(3)$. However, note that $(3)$ allows us to assume only $\lnot Q$; if we can then derive $\lnot P$, we have a clean proof by contrapositive.

However, in $(2)$, the aim is to derive a contradiction: the contradiction might not be arriving at $\lnot P$, if one has assumed ($P$ and $\lnot Q$). Arriving at any contradiction counts in a proof by contradiction: say we assume $P$ and $\lnot Q$ and derive, say, $Q$. Since $Q \land \lnot Q$ is a contradiction (can never be true), we are forced then to conclude it cannot be that both $(P \land \lnot Q)$.

But note that $\lnot (P \land \lnot Q) \equiv \lnot P \lor Q\equiv P\rightarrow Q.$

So a proof by contradiction usually looks something like this ($R$ is often $Q$, or $\lnot P$ or any other contradiction):

  • $P \land \lnot Q$ Premise
    • $P$
    • $\lnot Q$
    • $\vdots$
    • $R$
    • $\vdots$
    • $\lnot R$
    • $\lnot R \land R$ Contradiction

$\therefore \lnot (\lnot P \land Q) \equiv P \rightarrow Q$


share|improve this answer
    
"We are forced then to conclude $¬P$, since $Q∧¬Q$ is a contradiction." But this is essentially proving directly $(1)$, right ? –  Kasper Dec 20 '12 at 19:11
4  
No, this is not the same as proving directly: To prove P, one uses step by step implications to arrive directly at $Q$, without assuming $\lnot Q$. (2) Note that the contradiction obtained may may be that assuming P and $\lnot Q$ leads to both $R \land \lnot R$ (R may happen to be Q)$. –  amWhy Dec 20 '12 at 19:18
2  
Yes, Kasper, usually. It's just that in longer proofs, we may find a point were some other statement AND its negation follow from assuming both $P\land \lnot Q$. (e.g., P may imply R, and $\lnot Q$ may imply $\lnot R$, in which we have to conclude that we cannot have both $P$ and $\lnot Q$, which is equivalent to proving $P\rightarrow Q$). –  amWhy Dec 20 '12 at 19:44
2  
Okay, I understand. I've one other question if you don't mind :). Does a problem like the following exist? You're assuming: $P∧¬Q$ (to prove a contradiction). And in this problem it's impossible to prove $Q∧¬Q$ or $P∧¬P$ from this assumption. But it's possible to prove another contradiction $R∧¬R$. –  Kasper Dec 20 '12 at 20:02
1  
Yes, I'll try to find an example. There are many...usually longer proofs, where we assume $P \land \lnot Q$...then show $\lnot Q \rightarrow q_i ....\rightarrow...q_j....\rightarrow R$ and $P \rightarrow ...p_i....\rightarrow...p_j \rightarrow \lnot R$, giving $R \land \lnot R$. When I have a little time to look through some texts, for a shortish proof using this, I'll post here, or we can go through it in chat...either way, I'll let you know. –  amWhy Dec 20 '12 at 20:09

It's not the same.

If $P$ and $Q$ are statements about instances that (a priori independently) are true for some instances and false for others then proving $P\Rightarrow Q$ is the same as proving the contrapositive $\neg Q\ \Rightarrow \neg P$. Both mean the same thing: The set of instances for which $P$ is true is contained in the set of instances where $Q$ is true.

Proving a statement $A$ by contradiction is something else: You add $\neg A$ to your list of axioms, and using the rules of logic arrive at a contradiction, e.g., at $1=0$. Then you say: My axiom system was fine before adding $\neg A$. Since this addition has spoiled it, in reality $A$ has to be true.

An example: You want to prove the statement $$A:\quad {\rm "The\ number}\ \sqrt{2}\ {\rm is\ irrational."}$$ Then you add $\sqrt{2}={p\over q}$ to your list of axioms about rational numbers and arrive at a contradiction.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.