2
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ @MattF. Had forgotten about that one :-( $\endgroup$
    – vonbrand
    Commented Jun 15, 2014 at 23:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – ncr
    Commented Jun 16, 2014 at 0:19

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ilmari Karonen
    Commented Jun 16, 2014 at 0:15
  • $\begingroup$ Yes, I agree. However, I tend not to invoke the pigeonhole principle by name when I'm working out this proof. $\endgroup$
    – ncr
    Commented Jun 16, 2014 at 0:49
1
$\begingroup$

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.

Improve this answer
$\endgroup$

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