Introduction to Proof by Contradiction

Return to Course Outline

Previous Lecture

Misc

I’m out of town from this afternoon through Friday, specifically including Friday’s class.

Prof. Johannes will teach Friday’s class, looking at some “mind stretching” examples of proof by contradiction.

Questions?

Proof by Contradiction

Section 3.3.

Warm-Up

Prove that for all integers d ≥ 2, if n is an integer such that d divides n, then d does not divide n+1.

A proof by contradiction appears in the first proof in this solution, whose LaTeX source is here.

An Interesting Application

Prove that there must be an infinite number of prime numbers.

Helpful background: every natural number greater than 1 is either prime or a product of primes.

The key idea is to assume the theorem is false, then arrive at a contradiction. In particular, the key contradiction is that if the number of primes is finite, then you can multiply them all together to get a natural number P. But then as proven above, none of the primes can divide P+1, so P+1 must be prime, contradicting the assumption that you had all of them earlier.

A detailed and formal proof based on this argument appear as the second proof in this solution, and its LaTeX source.

Key Point

The basic strategy of proof by contradiction: assume that a claim is false, and from that assumption derive some impossibility.

Next

Prof. Johannes on more uses of proof by contradiction.

Then (Monday) proof in cases.

Read section 3.4 for Monday.

Next Lecture