Methods of Proof — Contradiction by Jeremy Kun.
From the post:
In this post we’ll expand our toolbox of proof techniques by adding the proof by contradiction. We’ll also expand on our knowledge of functions on sets, and tackle our first nontrivial theorem: that there is more than one kind of infinity.
Impossibility and an Example Proof by Contradiction
Many of the most impressive results in all of mathematics are proofs of impossibility. We see these in lots of different fields. In number theory, plenty of numbers cannot be expressed as fractions. In geometry, certain geometric constructions are impossible with a straight-edge and compass. In computing theory, certain programs cannot be written. And in logic even certain mathematical statements can’t be proven or disproven.
In some sense proofs of impossibility are hardest proofs, because it’s unclear to the layman how anyone could prove it’s not possible to do something. Perhaps this is part of human nature, that nothing is too impossible to escape the realm of possibility. But perhaps it’s more surprising that the main line of attack to prove something is impossible is to assume it’s possible, and see what follows as a result. This is precisely the method of proof by contradiction:
Assume the claim you want to prove is false, and deduce that something obviously impossible must happen.
There is a simple and very elegant example that I use to explain this concept to high school students in my guest lectures.
I hope you are following this series of posts but if not, at least read the example Jeremy has for proof by contradiction.
It’s a real treat.