Contradiction

Proof by contradiction (which is also known as indirect proof or the method of reductio ad absurdum) is a common proof technique that is based on a very simple principle: something that leads to a contradiction can not be true.

When we want to prove a statement by contradiction, we start by assuming that the statement is false or incorrect. Then we show that the consequences of this are absurd and impossible. That means the statement can not be false and has to be true.

G.H. Hardy called proof by contradiction "one of a mathematician's finest weapons," saying, "It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game."

When you attempt a proof by contradiction, the first thing you do is to negate the conclusion. Negating the conclusion sometimes leads to scenarios that are easier to work with. Sometimes tackling something head-on doesn't work well. When it isn't immediately clear how to approach a problem directly, it is always a good idea to ask questions like "what would happen if the statement were not true?" If you negate the conclusion and then are able to derive a contradiction from it, you are done!

We start with the very classic proof of the irrationality of \(\sqrt{2}\).

Prove that \(\sqrt{2}\) is irrational.

---

We are going to attempt a proof by contradiction. So the first thing we do is to assume that our conclusion is not true and see what happens after that.

We assume that \(\sqrt{2}\) is rational. Now if it were rational we would be able to express it as the ratio of two co-prime integers \(p\) and \(q\). Since \(p\) and \(q\) are co-prime, both of them can not be even.

Now if \(\sqrt{2}=\dfrac{p}{q}\), then \(2q^2=p^2\). Since the left hand side is even, so is the right hand side. We know that the square of an odd number can't be even. So, this means \(p\) is even.

Now if \(p\) is even, \(p^2\) is a multiple of \(4\). This in turn means \(2q^2\) is a multiple of \(4,\) or in other words, \(q^2\) is a multiple of \(2\). By the same reasoning as above, we conclude that \(q\) is even.

But that's a contradiction! Didn't we just say that both \(p\) and \(q\) can't be even?

So assuming that \(\sqrt{2}\) is rational led to a contradiction. That means \(\sqrt{2}\) can't be rational. We've proved that \(\sqrt{2}\) is irrational. \(_\square\)

Here's another example.

Prove that there is no least positive rational number.

---

We start by assuming the contrary that there is a least positive rational number. Let's call it \(k\).

Now \(\frac{k}{2}\) is a positive rational strictly less than \(k\). But this contradicts \(k\) being the smallest positive rational number. That means we were wrong to begin with. \(k\) in fact doesn't exist. In other words, there is no such thing as the least positive rational. \(_\square\)

Note: This result gives an intuition that any dense subset of R cannot have a least positive element.

One final example before we sign off.

If \(a\), \(b\) and \(c\) are all odd integers, prove that \(ax^2+bx+c=0\) can't have a rational solution.

---

We begin, just as we have been, by assuming that a rational number \(\frac{p}{q}\) is the solution to \(ax^2+bx+c=0\). Without loss of generality, we can assume that \(p\) and \(q\) are co-prime. Very much like the first example, this means that both of \(p\) and \(q\) can't be even. At least one of them has to be odd.

If \(\frac{p}{q}\) is indeed a solution to the quadratic, we must have:

\[\begin{align} a\left(\frac{p}{q}\right)^2+b\frac{p}{q}+c&=0\\ ap^2+bpq+cq^2&=0. \end{align}\]

Now the right hand side is even, so the left hand side has to be even too. But since \(a\), \(b\), \(c\) are all odd, that can happen only if both \(p\) and \(q\) are even and we made it very clear that they aren't.

So like every example we've done so far, our initial assumption was wrong.

Therefore, a rational number \(\frac{p}{q}\) can't be a solution to \(ax^2+bx+c=0\) if \(a\), \(b\) and \(c\) are all odd. \(_\square\)