Primary reference: Chapter 5 (Contrapositive Proof) and Chapter 6 (Proof by Contradiction) of Book of Proof by Richard Hammack

richardhammack.github.io

Content covered in this unit includes:

• The contrapositive and converse of a mathematical statement

• The recipe for writing a proof by contrapositive:

  <aside>

  Proposition. If $P$, then $Q$.

  Proof. We will prove the contrapositive. Suppose $\mathord{\sim} Q$.

  …

  Therefore $\mathord{\sim} P$.

  </aside>

• The recipe for writing a proof by contradiction:

  <aside>

  Proposition. $P$.

  Proof. Suppose for the sake of contradiction that $\mathord{\sim} P$.

  …

  Therefore $C$ and $\mathord{\sim} C$, which is a contradiction. We conclude that $P$.

  </aside>

• The recipe for proving a conditional statement by contradiction

  <aside>

  Proposition. If $P$, then $Q$.

  Proof. Suppose for the sake of contradiction that $P$ and $\mathord{\sim} Q$.

  …

  Therefore $C$ and $\mathord{\sim} C$, which is a contradiction. We conclude that $P \implies Q$.

  </aside>

• The precise definitions of the terms congruent modulo $n$, rational, irrational