Types of Mathematical Proofs

Why This Matters

In abstract mathematics, proofs aren't just about showing something is true—they're about understanding why it's true and communicating that reasoning with precision. You're being tested on your ability to select the right proof technique for a given problem and execute it correctly. The difference between a direct proof and proof by contradiction isn't just stylistic; it reflects fundamentally different logical strategies that work better in different situations.

Mastering these proof types means understanding logical equivalence, negation, quantifiers, and the structure of mathematical arguments. When you encounter a theorem, you should immediately start asking: Can I prove this directly? Would assuming the opposite lead somewhere useful? Is there a natural case structure? Don't just memorize the names—know when and why each technique is your best tool.

---

Direct Logical Arguments

These proof techniques work by building a logical chain from what you know to what you want to show. The key mechanism is forward reasoning: start with hypotheses and definitions, then deduce the conclusion step by step.

Direct Proof

• Starts with known facts—definitions, axioms, and established theorems—and logically deduces the target statement through valid inference steps
• Most natural for proving implications of the form $P \rightarrow Q$: assume $P$ is true, then show $Q$ must follow
• First technique to attempt because it produces the clearest, most intuitive arguments when it works

Proof by Contraposition

• Proves $P \rightarrow Q$ by instead proving $\neg Q \rightarrow \neg P$—the contrapositive, which is logically equivalent to the original statement
• Particularly useful when the conclusion $Q$ gives you little to work with, but assuming $\neg Q$ provides concrete information
• Relies on the logical equivalence $P \rightarrow Q \equiv \neg Q \rightarrow \neg P$, so no contradiction is needed—just direct reasoning on the contrapositive

---

Indirect and Negation-Based Arguments

These techniques work by assuming something false and showing it leads to problems. The underlying principle is that contradictions cannot exist in consistent mathematics, so any assumption leading to contradiction must be false.

Proof by Contradiction

• Assumes the negation of the statement to be proven and derives a logical contradiction, forcing the original statement to be true
• Works for any statement type, not just implications—making it more versatile than contraposition
• Go-to technique for proving irrationality (like $\sqrt{2}$) and impossibility results where direct approaches hit dead ends

Proof by Counterexample

• Disproves universal statements by exhibiting a single specific case where the statement fails
• Only requires one example—if someone claims "all primes are odd," the number $2$ is a complete refutation
• Highlights the precision required in mathematical claims; a counterexample often reveals exactly which hypothesis was missing

---

Structured Case Analysis

When a problem naturally splits into distinct scenarios, these techniques ensure you've covered all possibilities. The mechanism is partitioning the domain: if you prove the statement holds in every case, it holds universally.

Proof by Cases

• Divides the proof into exhaustive, mutually exclusive scenarios and proves the statement separately for each case
• Essential when different conditions require different arguments—such as proving a property for all integers by handling positive, negative, and zero separately
• Requires careful justification that your cases truly cover all possibilities with no gaps

Proof by Exhaustion

• Checks every single possibility when the domain is finite and small enough to enumerate completely
• Guarantees certainty by leaving no case unexamined—famously used in the computer-assisted proof of the Four Color Theorem
• Practical only for limited cases; becomes infeasible as the number of possibilities grows

---

Inductive Arguments

Mathematical induction handles statements about infinite collections (typically natural numbers) through a clever finite process. The principle is the domino effect: if the first domino falls, and each falling domino knocks down the next, all dominoes fall.

Proof by Induction

• Establishes truth for all natural numbers using two components: a base case (prove for $n = 1$ or $n = 0$) and an inductive step (prove $P(k) \rightarrow P(k+1)$)
• The inductive hypothesis—assuming $P(k)$ is true—is not circular reasoning; it's the key tool you use to prove $P(k+1)$
• Extends to strong induction (assume $P(1), P(2), \ldots, P(k)$ all hold) and structural induction for recursively defined objects

---

Existence and Uniqueness Arguments

These techniques address fundamental questions about mathematical objects: Does something with these properties exist? If so, is it the only one? The underlying logic involves existential and universal quantifiers and how to prove or leverage them.

Existence Proof

• Demonstrates that at least one object satisfying given conditions exists—proves $\exists x : P(x)$
• May be non-constructive, using indirect methods (like contradiction) without revealing which object works
• Critical for establishing that definitions are meaningful—you can't study "the solution" if you haven't shown solutions exist

Constructive Proof

• Explicitly builds or identifies the object whose existence is being claimed, providing a concrete witness
• Stronger than mere existence proofs because it answers "which one?" not just "does one exist?"
• Preferred in computational contexts where you need an algorithm, not just assurance that an answer exists somewhere

Uniqueness Proof

• Shows that at most one object satisfies the given conditions—often combined with existence to prove "exactly one"
• Standard technique: assume two objects $x$ and $y$ both satisfy the conditions, then prove $x = y$
• Essential for well-defined functions and operations; without uniqueness, expressions like "the inverse" are meaningless

---

Quick Reference Table

---

Self-Check Questions

1. You need to prove "if $n^2$ is odd, then $n$ is odd." Which two proof techniques are most natural here, and why might one be easier than the other?

2. What distinguishes proof by contradiction from proof by contraposition? Give an example of a statement where contradiction is necessary but contraposition wouldn't apply.

3. A classmate claims "all continuous functions are differentiable." What proof technique would you use to address this claim, and what would you need to provide?

4. Compare and contrast constructive existence proofs with non-constructive existence proofs. Why might a computer scientist prefer one over the other?

5. You're asked to prove that $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ for all positive integers $n$. Which proof technique is required, and what are the two components you must establish?