7: Proof strategies (direct, contrapositive, contradiction)

Proof Strategies: Direct, Contrapositive, Contradiction

Mastering proof techniques is fundamental in discrete mathematics and computer science. For implications of the form "If $P$, then $Q$" ($P \to Q$), three core strategies exist: direct proof, proof by contrapositive, and proof by contradiction. Understanding when and how to apply each is crucial.

1. Direct Proof:
This is the most straightforward approach. You start by assuming the premise $P$ is true. Using logical deductions, definitions, axioms, and previously established results, you then demonstrate that the conclusion $Q$ must also be true.
Example: Prove "If integer $n$ is even, then $n^2$ is even."
Proof: Assume $n$ is even. By definition, $n = 2k$ for some integer $k$. Then, $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$. Since $2k^2$ is an integer, $n^2$ is even. ∎

2. Proof by Contrapositive:
This method leverages the logical equivalence of $P \to Q$ and its contrapositive: $\neg Q \to \neg P$. Instead of proving $P \to Q$ directly, you prove that if $Q$ is false, then $P$ must also be false. This is often useful when the negation of $Q$ provides a more workable starting point.
Example: Prove "If $n^2$ is odd, then integer $n$ is odd."
Contrapositive: "If $n$ is not odd (i.e., even), then $n^2$ is not odd (i.e., even)." This is exactly the direct proof shown above. Since the contrapositive is true, the original statement is true. ∎

3. Proof by Contradiction:
Here, you assume the negation of the statement you want to prove and show this assumption leads to a logical contradiction – a statement that is always false (like $0=1$ or violating a known fact). Since the assumption caused an impossibility, the original statement must be true.
Example: Prove "If $a$ and $b$ are integers and $a \cdot b$ is even, then at least one of $a$ or $b$ is even."
Proof by Contradiction: Assume the negation: "$a \cdot b$ is even AND both $a$ AND $b$ are odd." If $a$ and $b$ are odd, then $a = 2m+1$, $b = 2n+1$ for integers $m$, $n$. Then $a \cdot b = (2m+1)(2n+1) = 4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1$, which is odd. This contradicts our assumption that $a \cdot b$ is even. Therefore, the original statement holds. ∎

Choosing a Strategy:

• Use direct proof when you can construct a clear chain of reasoning from $P$ to $Q$.
• Use contrapositive when the negation of $Q$ ($\neg Q$) seems easier to work with as a premise than $P$.
• Use contradiction when the negation of the entire statement provides useful assumptions, especially for statements that are not simple implications (e.g., "There are infinitely many primes").