Proof Techniques

Why This Matters

Proof techniques are the backbone of discrete mathematics and 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.

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

A direct proof assumes the hypothesis and derives the conclusion. It's the most straightforward approach for statements of the form "If $P$, then $Q$."

The process looks like this:

1. Assume $P$ is true.
2. Unpack what $P$ means using definitions (e.g., if $P$ says "$n$ is even," write $n = 2k$ for some integer $k$).
3. Apply logical steps, algebraic manipulation, or known theorems.
4. Arrive at the conclusion $Q$.

Best choice when the path forward is clear. If you can see how to get from hypothesis to conclusion, don't overcomplicate it by reaching for an indirect method.

Proof by Construction

This technique explicitly builds the object whose existence you're claiming. It's used for statements like "There exists an $x$ such that $P(x)$."

Rather than arguing abstractly that something must exist, you provide a concrete example or an algorithm that produces the desired object. This is common in combinatorics and algorithm design. For instance, to prove there exists a graph with 5 vertices where every vertex has degree 2, you'd just draw a 5-cycle and verify it works.

Proof by Equivalence

This technique proves two statements are logically equivalent by showing both $P \Rightarrow Q$ and $Q \Rightarrow P$. It establishes "if and only if" (often written "iff") relationships, and both directions must be proven separately.

The two directions often call for different strategies. You might use a 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

This technique 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.

Here's the structure:

1. Assume, for the sake of contradiction, that the statement you want to prove is false.
2. Reason logically from that assumption.
3. Arrive at a statement that contradicts a known fact, a given hypothesis, or the assumption itself.
4. Conclude the original statement must be true.

The classic example is proving $\sqrt{2}$ is irrational: you assume it is rational, write it as $\frac{a}{b}$ in lowest terms, and eventually show both $a$ and $b$ must be even, contradicting "lowest terms."

This technique is especially powerful for "there is no..." or uniqueness claims, where the negation gives you a concrete object to manipulate.

Proof by Contraposition

This technique proves "If $P$, then $Q$" by instead proving "If $\neg Q$, then $\neg P$." These two statements are logically equivalent: $P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$.

It's ideal when the negation gives you more to work with. For example, proving "if $n^2$ is even, then $n$ is even" directly is awkward, but the contrapositive "if $n$ is odd, then $n^2$ is odd" flows naturally: write $n = 2k + 1$, square it, and factor out the 2.

---

Case-Based Proofs

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

Proof by Cases

This technique partitions the problem into exhaustive, mutually exclusive scenarios and proves the statement holds in each case separately. For example, proving a property for all integers by handling even and odd cases separately.

Two requirements are non-negotiable:

• Exhaustive: Your cases must cover every possibility. If you miss a case, the proof is incomplete.
• Each case must be proven: You need a valid argument within every case, not just a claim.

Proof by Exhaustion

This technique checks every single instance when the total number of cases is finite and small. It guarantees completeness through brute force.

This is common in proofs involving small sets or specific numerical bounds (e.g., verifying a property for all integers between 1 and 10). For larger case counts, exhaustion is often computer-assisted. The Four Color Theorem famously required exhaustive computer verification of hundreds of configurations.

---

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

Every induction proof has two parts:

1. Base case: Verify the statement holds for your starting value (usually $n = 1$ or $n = 0$, depending on the problem).
2. Inductive step: Assume $P(n)$ is true (this assumption is called the inductive hypothesis), and use it to prove $P(n+1)$.

The inductive hypothesis is your leverage. You're not assuming what you're trying to prove; you're assuming one case to establish the next, like pushing over one domino to topple the next.

Variants:

• Strong induction assumes $P(k)$ for all $k \leq n$ (not just $k = n$) when proving $P(n+1)$. Use this when $P(n+1)$ depends on multiple previous cases, not just the immediate predecessor. For example, proving every integer $\geq 2$ has a prime factorization requires strong induction because you might factor $n+1$ into parts much smaller than $n$.
• Structural induction applies to recursively defined objects like trees, strings, or formulas. The base case handles the simplest structure, and the inductive step shows the property is preserved by each recursive construction rule.

---

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

A single specific instance where a universal claim fails is enough to destroy it. If someone claims "all primes are odd," just point to $2$.

Your counterexample must genuinely satisfy the hypothesis while violating the conclusion. Be precise: clearly state the example, verify it meets the conditions of the claim, and show where the claimed conclusion breaks down.

Proof by Diagonalization

This technique constructs an element guaranteed to differ from every item in a supposed complete list. It's used to show certain sets are uncountable or certain problems are undecidable.

Cantor's diagonal argument is the classic example. Suppose you could list all real numbers between 0 and 1. Cantor constructs a new real number by changing the $n$th digit of the $n$th number in the list, guaranteeing this new number differs from every listed number in at least one decimal place. This contradicts the assumption that the list was complete, proving the reals are uncountable.

The same core idea 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.