# Nice examples of proof by contradiction? [duplicate]

The setting is undergraduate students in Computer Science, a course in Discrete Mathematics (first proof-oriented course they take, they had a mostly computation oriented first course in calculus).

As examples I need nice proofs using contradiction. The typical proof that $\sqrt{2}$ is irrational is standard fare, but they seem not to "see" the contradiction clearly, so any hints at making that one clearer would be appreciated.

The restriction is also that not much more than high-school algebra (and perhaps a dash of common sense) is required.

Bonus points for proofs that aren't obviously "mathematical" (i.e., no algebra, no formulas).

• @MattF. Had forgotten about that one :-( – vonbrand Jun 15 '14 at 23:16
• While the title of the question is the same as other one, I think a not insignificant difference is the mention of the audience being CS majors. While the accepted answer at the linked page lists a number of great proofs by contradiction, based on my experience teaching CS kids discrete math, you'll have a hard time convincing them of the value of the technique without making it relevant. I often motivate it through games like minesweeper, too. – ncr Jun 16 '14 at 0:19

Here's one that I use in an analogous course I teach: A lossless compression algorithm that makes some files smaller must make some (other) files larger.

• This is basically an application of the pigeonhole principle, and the proof-by-contradiction part is essentially about proving a particular case of this principle. I do agree, though, that if you goal is to illustrate proof by contradiction, it may be more effective to skip the pigeonhole principle as an intermediate step. – Ilmari Karonen Jun 16 '14 at 0:15
• Yes, I agree. However, I tend not to invoke the pigeonhole principle by name when I'm working out this proof. – ncr Jun 16 '14 at 0:49

If you don't mind probability-related problems, this one works pretty well.

Suppose $A$, and $B$ are sets in $S$. Then $A \cap B$, $A \cap B^C$, $A^C \cap B$ and $A^C \cap B^C$ partition $S$.

The proof by contradiction is in showing that the members of the partition are disjoint. Suppose, for example that $A \cap B$ and $A \cap B^C$ are not disjoint. Then there is some element $x \in S$ that belongs to both sets. But $x$ must be an element of both $B$ and $B^C$. The only such set is the null set. Therefore, $A \cap B$ and $A \cap B^C$ are disjoint. Note now that any pair of partition elements have at least one set and its complement, and so the partition members are disjoint.

That they jointly cover $S$ is obvious, for any $x \in S$ must belong to $A$ or $A^C$ by definition.

This can also be done with Boolean (set) algebra, but in teaching Bayes' rule I find that this argument is more persuasive.