# Mathematical Proof/Methods of Proof/Proof by Contradiction

The method of proof by contradiction is to assume that a statement is not true and then to show that that assumption leads to a contradiction. In the case of trying to prove $P\Rightarrow Q,$ this is equivalent to assuming that $P\land \lnot Q.$ That is, to assume that $P$ is true and $Q$ is false. This is known by its latin reductio ad absurdum (reduction to absurdity), since it ends with a statement that cannot be true.

## Rationale

Proof by contradiction is viewed as a logical consequence of the following series of steps to the question, "How can we show that P does not imply Q?"

1. We must show that the predicate $P$ not only not imply $Q$ but it cannot, or else logic breaks down.
To begin, we show that $P$ does not imply $Q$. This results in showing that $\neg(P \Rightarrow Q)$
2. The statement above is equivalent to the statement $P \land \lnot Q$
This actually only proves that an implication is not true.
3. Contradictions show that both statements cannot be true at the same time, or else logic breaks down by claiming a logical impossibility: $P \and \neg P$.
4. Thus, a proof by contradiction requires us to show, initially assuming that $P$ does not imply $Q$, either:
• $P \Rightarrow Q$
• $\neg Q \Rightarrow \neg P$
5. Which, when substituted back into the logical statement $P \land \lnot Q$ yields either
• $Q \land \lnot Q$
• $P \land \lnot P$

A contradiction proof is one of the strongest types of proof, since it proves not just that some given $P$ does not imply some $Q$, which does not discredit other attempts at proving a statement—only the one that shows your version of $P$ does not imply $Q$, but that $P$ can never imply $Q$; $P$ and $Q$ can never coexist together. If you are in mathematics, this type of proof is desired and sought after for exactly its quality of being such a strong argument.

## Method

It is straightforward to prove a contradiction and can be easily done by following the following steps:

1. Prove separately these two claims
1. $P \land \lnot Q$ is valid.
2. Either:
• $P \Rightarrow Q$ (The original claim)
• $\lnot Q \land \lnot P$ (The contrapositive of the original claim)
(whichever one is easier)
2. Put the two together; $P \and \neg P$. You have a contradiction. $\blacksquare$

Below are some examples where you see how this method is put into effect.

### Square root of 2

A good example of this is by proving that $\sqrt 2$ is irrational. Proving this directly (via constructive proof) would probably be very difficult (if not impossible). However, by contradiction we have a fairly simple proof.

Proposition 2.3.1. $\sqrt 2\notin \mathbb Q.$

Proof: Assume $\sqrt{2}$ is rational. Then $\sqrt{2}=\frac{a}{b}$, where $a$ and $b$ are relatively prime integers (a and b have no common factors).[1] and $b \ne 0$. So

$2=\frac{a^2}{b^2}.$

$2b^2=a^2.$

But since $a^2$ is even, $a$ must be even as well, since the square of an odd number is also odd. Then we have $a=2a_1$, or

$2b^2=4a_1^2,$ so $b^2=2a_1^2$.

The same argument can now be applied to $b$ to find $2b_1=b$. However, this contradicts the original assumption that a and b are relatively prime, and the above is impossible. Therefore, we must conclude that $\sqrt{2}$ is irrational.

Of course, we now note that there was nothing in this proof that was special about 2, except the fact that it was prime. That's what allowed us to say that $a$ was even since we knew that $a^2$ was even. Note that this would not work for 4 (mainly because $\sqrt 4 = 2\in \mathbb Q$) because $4|a^2$ does not imply that $4|a.$

## More Thoughts

In English, the procedure is this: Assert that a statement is false, and then prove yourself wrong. (Thereby proving the original statement was true.) This is a form of Modus Tollens.

For many students, the method of proof by contradiction is a tremendous gift and a trojan horse, both of which follow from how strong the method is. In fact, the apt reader might have already noticed that both the constructive method and contrapositive method can be derived from that of contradiction.

$P\land \lnot Q\ which\ implies\ P$ $Q\ (from\ P\ only)$ $Q\land \lnot Q$
$P\land \lnot Q\ which\ implies\ \lnot Q$ $\lnot P\ (from \lnot Q\ only)$ $P\land \lnot P$