From Mathematics to Generic Programming

Appendix B. Common Proof Techniques

There are a few standard proof techniques that occur frequently in mathematics and computer science, and which we use in this book. If you are having trouble understanding the proofs in the main text, you may want to review this section.

B.1 Proof by Contradiction

Many things we want to prove have the form “if p, then q” (also sometimes written “p q”), where p and q are two propositions. We always start with the premise that p is true; otherwise, we would be solving a different problem. The idea of proof by contradiction is to assume the opposite of what the original conjecture concludes (i.e., assume that ...