Proof Writing Playbook

Generalizable proof patterns with worked examples

This document is a procedural guide to proof writing. It covers the common argument structures.

For each major pattern:

• the logical structure is stated,
• the components are identified,
• and a simple example proof is given.

1. Quantifiers & Logical Form (Foundation of All Proofs)

Core Quantifier Patterns

Example: Correct Handling of Nested Quantifiers

Claim For every real number , there exists a real number such that .

Proof Let be arbitrary. Choose . Then . Since was arbitrary, the claim holds for all .

Key components

• arbitrary choice of ,
• explicit construction of ,
• conclusion restated universally.

Negation Rules (Used to Construct Counterexamples)

Example: Negating a Universal Bound

Claim For all vectors , .

Negation There exists a vector such that .

This negated form is exactly what a counterexample must satisfy.

2. Direct Proof (Most Common Pattern)

Template

1. State assumptions
2. Apply definitions
3. Apply known results
4. Derive conclusion

Example: Direct Proof

Claim If and , then .

Proof Assume and . Since both are positive, their sum satisfies . Thus the claim holds.

Key components

• assumptions restated explicitly,
• no hidden steps,
• conclusion follows immediately.

3. Proof by Contrapositive

Structure

Instead of proving

prove

Example: Contrapositive Proof

Claim If a number is even, then is even.

Contrapositive If is odd, then is odd.

Proof Assume is odd. Then , so is odd. Thus the contrapositive holds, and so does the original claim.

Key components

• reformulated statement,
• proof proceeds forward,
• no contradiction invoked.

4. Proof by Contradiction

Structure

1. Assume negation of the claim
2. Deduce an impossibility
3. Conclude the claim is true

Example: Contradiction Proof

Claim There is no largest integer.

Proof Assume there exists a largest integer . Then is an integer and . This contradicts the assumption that is largest. Therefore, no largest integer exists.

Key components

• explicit negation,
• contradiction is concrete,
• conclusion follows logically.

5. Existence Proofs

Constructive Existence

Pattern

• Explicitly define an object
• Verify it satisfies the required property

Example: Constructive Existence

Claim There exists an integer that is divisible by both 2 and 3.

Proof Let . Then is divisible by both 2 and 3. Thus such an integer exists.

Non-Constructive Existence

Pattern

• Assume no such object exists
• Derive contradiction

Example: Non-Constructive Existence

Claim There exist irrational numbers such that is rational.

Proof Consider . If is rational, we are done. Otherwise, let . Then

which is rational. Thus such numbers exist.

6. Uniqueness Proofs

Template

1. Assume two objects satisfy the property
2. Show they are equal

Example: Uniqueness Proof

Claim There is a unique real number such that .

Proof Existence: satisfies the equation. Uniqueness: Suppose and . Then . Thus the solution is unique.

7. Inequality Proofs (General Pattern)

Template

1. Start from one side
2. Apply valid inequalities
3. Reach the bound

Example: Inequality Proof

Claim For all real numbers ,

Proof By definition,

In both cases, . Thus the claim holds for all .