Opposing arrows, a common "punctuation mark" at the end a proof by contradiction.

If you dont know what to do, do something. Thats one of my mottos when I teach math (and its 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 dont 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.

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 Cantors 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 Euclids 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 dont 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 wont hit all of the real numbers. We dont 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 didnt 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 dont know where to start.