Using proof by contradiction vs proof of the contrapositive

Solution 1:

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 (P \land \lnot Q) \equiv P \rightarrow Q$

Solution 2:

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.

Solution 3:

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.

Solution 4:

One difference is that proof by contrapositive only applies to propositions of the form $A \to B$ ("if-then propositions"). However not every proposition is a "if-then proposition", for example, consider the proposition, exist x real for all p,q integer, x != p/q, there is no $\to$ inside that proposition, so it is not feasible to prove it by contrapositive.

Proof by contrapositive:

$(\neg B \to \neg A) \to (A \to B)$

Proof by contradiction:

$(\neg A \to (B \land\neg B)) \to A $