Discrete Structures: Proof by Contradiction Margaret Fleck, University of Illinois

When teaching discrete structures, it's very tempting to exhaustively cover all proof methods (except perhaps induction) right at the start. This seems intellectually tidy. However, it's more helpful to the students to leave this method until late in the course, after they have a solid grasp of more basic proof methods.

What is proof by contradiction?

It is traditional in mathematics to divide (non-inductive) proofs into two types: direct and indirect. Indirect proof includes two proof methods: proof by contrapositive and proof by contradiction. In both, you start from the negated conclusion of the original claim. However, in proof by contrapositive, you end at the negated hypothesis whereas proof by contradiction ends at some contradiction that may not be closely related to the statement of the original claim.

Many proofs can be written in either style, with minimal changes. I teach these as "proof by contrapositive." This method is presented very early in the course, as a simple modification of direct proof. In what follows, "proof by contradiction" refers only to proofs that cannot easily be rewritten as proof by contrapositive. That is, the contradiction at the end is not the negation of the original hypothesis or, perhaps, an obvious piece of the original hypothesis.

Under this restrictive definition, there are very few examples of proof by contradiction in elementary math courses. Contrapositive may not be sufficiently powerful, e.g. proving that the real numbers aren't countable or that there are an infinite number of primes. Adirect/contrapositive proof may be possible but awkward, e.g. showing that \(\sqrt{2}\) is irrational. Finally, there are some debatable cases where contradiction might or might not be useful. But all of these are uncommon. So it's possible to do large amounts of mathematics without introducing contradiction.

Why teach it late?

The main reason to delay contradiction is that students tend to misuse it. They see contradiction as a "get out of jail free" card that they can play whenever they have no clue how to outline their proof. The classical method is to write out the hypothesis and the negated conclusion, write several paragraphs of math that go around in circles, and then declare success when some mistake (e.g. in the algebra) creates a contradiction. In almost all cases, they should have chosen a more appropriate outline.

This behavior highlights a major disadvantage of contradication. Other proof techniques provide a clear goal to reach at the end of the proof. Contradiction does not. If the goal was obvious from the start, you could probably have written it as contrapositive. So beginners who launch into a proof by contradiction. have absolutely no idea where they are going.

By delaying contradiction, I force them to spend more time learning how to build a solid direct proof. That is, put statements into logical order, substitute definitions correctly, and so forth. I also push them to learn the classic outlines for specific types of proofs, when showing that a function is one-to-one, use the the contrapositive form of the definition. By the time we get to contradiction, hopefully they will have learned to mechanically build the obvious outline in simple situations and reach for more interesting tools only when the simpler ones aren't working.

A more subtle form of misuse involves proofs that demand a a counter-example. Beginners tend to see these as too simple to be a "real" proof. So, if they know about contradiction, they are tempted to use it in place of the counter-example. This is typically both wrong and overly complex. Delaying contradiction gives us more time to teach them when to use counter-examples, and to teach them to use very simple concrete ones that are easy for the reader to verify.