This article was published in Scientific American’s former blog network and reflects the views of the author, not necessarily those of Scientific American
If you don’t know what to do, do something. That’s one of my mottos when I teach math (and it’s probably good life advice too). Last year, I taught introductory analysis (basically calculus with the juicy bits left in), one of the first proof-oriented classes students take. Writing proofs is hard, and sometimes the hardest part is starting. After you write down the hypothesis, what comes next? What is the something my students should do?
If they don’t have any better ideas, sometimes the best way to start is by contradiction. Proof by contradiction is one of the major proof techniques in mathematics. To prove the statement “A implies B,” a proof by contradiction assumes that both A and “not B” are true, and then shows that this is impossible.
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
For example, how do you show that there are infinitely many prime numbers? One way to start, often attributed to Euclid, is to assume you have a finite list of all the prime numbers and work until you have a contradiction. Specifically, you multiply all your primes together, add 1, and show that this resulting number is not divisible by any primes on the list. That means your list was incomplete, so there must be infinitely many primes.
Another commonly given example of proof by contradiction is Cantor’s diagonalization argument showing that the set of real numbers is “bigger” than the set of counting numbers. See Vi Hart's video about different sizes of infinity for a good explanation of diagonalization.
The funny thing is, neither the proof of the infinitude of primes nor the diagonalization proof is really a proof by contradiction. (For an interesting analysis of the widespread myth that Euclid’s proof is a proof by contradiction, see the disappointingly paywalled article Prime Simplicity by Michael Hardy and Catherine Woodgold.) In the case of primes, the proof works perfectly well on any old finite list of prime numbers. You don’t need to assume that the list is complete to run the argument. Similarly, in the case of diagonalization, the proof shows that any function from the counting numbers to the real numbers won’t hit all of the real numbers. We don’t have to assume there is a function that will hit all the real numbers in the first place. The difference is subtle and fun to roll around in your head.
If I didn’t already know how to prove that there are infinitely many prime numbers or that the cardinality of the counting numbers is smaller than the cardinality of the real numbers, I would try contradiction first. It's a little hard for me to see how to find these proofs without starting from contradiction, even though contradiction is not necessary for either argument.
I often encourage my students to try contradiction if they get stuck on a proof. I think it helps get ideas flowing. Why? I'm not really sure, but maybe it gives us something concrete to hold onto. When we're first working with a new mathematical idea, it can seem hopelessly abstract. But by trying a proof by contradiction, we have in some sense a tangible "villain" to fight against. Of course, contradiction can't always help us find a proof, but it's better to do something, to write down some ideas and whittle away at them until you get to the heart of an argument, than to sit around twiddling your thumbs because you don’t know where to start.