Proof Techniques

Why This Matters

Proof techniques are the backbone of discrete mathematics—and honestly, of all rigorous mathematical thinking. You're not just being tested on whether you can recite definitions; you're being tested on whether you can construct valid arguments and recognize which proof strategy fits which situation. Every theorem you encounter in this course was established using one of these techniques, and exam questions frequently ask you to either write proofs yourself or identify the method being used in a given argument.

The key insight here is that different proof techniques exploit different logical structures. Some work by building forward from assumptions, others by working backward from contradictions, and still others by systematic case analysis. Don't just memorize the names—know when each technique is your best tool and why. If you can identify the logical structure of a claim, you can select the right proof strategy almost automatically.

---

Forward-Building Proofs

These techniques work by starting from what you know and logically progressing toward what you want to prove. They follow the natural direction of implication.

Direct Proof

• Assumes the hypothesis and derives the conclusion—the most straightforward approach for statements of the form "If $P$, then $Q$"
• Requires solid command of definitions; you'll unpack what $P$ means and use logical steps to show $Q$ must follow
• Best choice when the path forward is clear—if you can see how to get from hypothesis to conclusion, don't overcomplicate it

Proof by Construction

• Explicitly builds the object whose existence you're claiming—used for statements like "There exists an $x$ such that $P(x)$"
• Demonstrates existence non-abstractly; you provide a concrete example or algorithm that produces the desired object
• Common in combinatorics and algorithm design—if asked to prove something exists, showing how to make it is often the cleanest approach

Proof by Equivalence

• Proves two statements are logically equivalent by showing $P \Rightarrow Q$ and $Q \Rightarrow P$
• Establishes "if and only if" relationships; both directions must be proven separately
• Often combines multiple proof techniques—you might use direct proof for one direction and contraposition for the other

---

Indirect Proofs

When the direct path is blocked, these techniques take a detour. They leverage logical equivalences or the impossibility of contradictions.

Proof by Contradiction

• Assumes the negation of what you want to prove and derives a logical impossibility—if $\neg Q$ leads to absurdity, then $Q$ must be true
• Powerful for "there is no" or uniqueness claims—classic examples include proving $\sqrt{2}$ is irrational
• Watch for the moment of contradiction; you need to clearly identify which established fact or assumption you've violated

Proof by Contraposition

• Proves "If $P$, then $Q$" by proving "If $\neg Q$, then $\neg P$"—logically equivalent but often easier
• Exploits the contrapositive equivalence; $P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$
• Ideal when the negation gives you more to work with—if $Q$ involves existence and $\neg Q$ gives a concrete condition, contraposition simplifies things

---

Case-Based Proofs

These techniques handle complexity by breaking it into manageable pieces. They ensure no scenario is overlooked.

Proof by Cases

• Partitions the problem into exhaustive, mutually exclusive scenarios—proves the statement holds in each case separately
• Essential when conditions vary; for example, proving something for all integers by handling even and odd cases
• Must cover all possibilities—if you miss a case, the proof is incomplete

Proof by Exhaustion

• Checks every single instance when the total number of cases is finite and small
• Guarantees completeness through brute force—common in proofs involving small sets or specific numerical bounds
• Often computer-assisted for larger case counts—the Four Color Theorem famously required exhaustive computer verification

---

Inductive Reasoning

Mathematical induction is a specialized technique for proving statements about infinite sequences, particularly those indexed by natural numbers. It works by establishing a domino effect.

Mathematical Induction

• Two-step structure: base case and inductive step—first verify the statement for $n = 1$ (or your starting value), then prove that $P(n) \Rightarrow P(n+1)$
• The inductive hypothesis is your leverage; you assume $P(n)$ is true and use it to prove $P(n+1)$
• Variants include strong induction (assume $P(k)$ for all $k \leq n$) and structural induction (for recursively defined objects like trees)

---

Disproving and Limiting Claims

Not every proof establishes truth—sometimes you need to show a claim is false or reveal fundamental limitations.

Proof by Counterexample

• Provides a single specific instance where a universal claim fails—one counterexample destroys "for all" statements
• Requires precision in selection; your example must genuinely satisfy the hypothesis while violating the conclusion
• Quick and decisive—if someone claims "all primes are odd," just point to $2$

Proof by Diagonalization

• Constructs an element guaranteed to differ from every item in a list—used to show certain sets are uncountable
• Cantor's diagonal argument is the classic example; it proves the real numbers cannot be enumerated
• Reveals fundamental limits on enumeration—appears in computability theory to prove the Halting Problem is undecidable

---

Quick Reference Table

---

Self-Check Questions

1. You need to prove "If $n^2$ is even, then $n$ is even." Would direct proof or contraposition be more efficient, and why?

2. What do Proof by Contradiction and Proof by Contraposition have in common, and what's the key difference in how they reach their conclusions?

3. A classmate claims "All functions from $\mathbb{N}$ to $\{0, 1\}$ can be listed." Which proof technique would you use to refute this, and what's the core idea?

4. When proving a statement about all natural numbers using induction, what happens to your proof if you establish the inductive step but forget the base case?

5. Compare Proof by Cases and Proof by Exhaustion: give an example of a claim where you'd use cases and another where exhaustion would be necessary.