Take the 2-minute tour ×
Mathematics Educators Stack Exchange is a question and answer site for those involved in the field of teaching mathematics. It's 100% free, no registration required.

This question already has an answer here:

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).

share|improve this question

marked as duplicate by Matt F., JPBurke, JoeTaxpayer, Benjamin Dickman, Ilmari Karonen Jun 16 at 13:02

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
@MattF. Had forgotten about that one :-( –  vonbrand Jun 15 at 23:16
1  
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 at 0:19

3 Answers 3

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.

share|improve this answer
    
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 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 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.

share|improve this answer

Euclid's proof of the infitude of primes in generally considered a classic. I also think very fondly of proofs where one is to prove, say, $x \le y$, and assumes $x > y$.

share|improve this answer
4  
Euclid's original proof was not a proof by contradiction. Look it up, it's Book IX, Proposition 20. –  Dag Oskar Madsen Jun 15 at 22:40
3  
Hm, I see, that is a fairly common misconception, then. –  Andrew Thompson Jun 15 at 22:42

Not the answer you're looking for? Browse other questions tagged or ask your own question.