Proof Techniques

Direct Proof

To prove $p \rightarrow q$: Assume $p$ is true, then show $q$ must be true.

Structure

1. Assume the hypothesis $p$
2. Use definitions, known theorems, and logical reasoning
3. Conclude $q$

Example

Theorem: If $n$ is odd, then $n^2$ is odd.

Proof:

• Assume $n$ is odd
• Then $n = 2k + 1$ for some integer $k$
• $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$
• Let $m = 2k^2 + 2k$, which is an integer
• Then $n^2 = 2m + 1$, which is odd $\square$

Proof by Contraposition

To prove $p \rightarrow q$: Prove the contrapositive $\neg q \rightarrow \neg p$.

$p \rightarrow q \equiv \neg q \rightarrow \neg p$

When to Use

Use when assuming $\neg q$ gives useful information.

Example

Theorem: If $n^2$ is even, then $n$ is even.

Proof (by contraposition):

• We prove: If $n$ is odd, then $n^2$ is odd
• Assume $n$ is odd, so $n = 2k + 1$
• $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$
• Thus $n^2$ is odd $\square$

Proof by Contradiction

To prove $p$: Assume $\neg p$ and derive a contradiction.

Structure

1. Assume $\neg p$ (the negation of what we want to prove)
2. Derive a statement that is always false
3. Conclude $p$ must be true

Example

Theorem: $\sqrt{2}$ is irrational.

Proof:

• Assume $\sqrt{2}$ is rational
• Then $\sqrt{2} = \frac{a}{b}$ where $a, b \in \mathbb{Z}$, $b \neq 0$, $\gcd(a,b) = 1$
• $2 = \frac{a^2}{b^2}$, so $a^2 = 2b^2$
• Thus $a^2$ is even, so $a$ is even (by contraposition of previous theorem)
• Let $a = 2c$, then $4c^2 = 2b^2$, so $b^2 = 2c^2$
• Thus $b^2$ is even, so $b$ is even
• But if both $a$ and $b$ are even, $\gcd(a,b) \geq 2$
• This contradicts $\gcd(a,b) = 1$
• Therefore $\sqrt{2}$ is irrational $\square$

Proof by Cases

When proving $p \rightarrow q$ and $p$ can be split into cases: $(p_1 \lor p_2 \lor \cdots \lor p_n) \rightarrow q$

Prove each case: $p_1 \rightarrow q$, $p_2 \rightarrow q$, etc.

Example

Theorem: $|xy| = |x| \cdot |y|$

Proof: Consider all combinations of signs of $x$ and $y$:

• Case 1: $x \geq 0$ and $y \geq 0$: $|xy| = xy = |x||y|$ ✓
• Case 2: $x \geq 0$ and $y < 0$: $|xy| = -xy = x(-y) = |x||y|$ ✓
• Case 3: $x < 0$ and $y \geq 0$: $|xy| = -xy = (-x)y = |x||y|$ ✓
• Case 4: $x < 0$ and $y < 0$: $|xy| = xy = (-x)(-y) = |x||y|$ ✓ $\square$

Existence Proofs

Constructive Proof

Explicitly find an example that satisfies the condition.

Example: Prove there exists an irrational number $r$ such that $r^{\sqrt{2}}$ is rational.

Consider $r = \sqrt{2}^{\sqrt{2}}$. Either it's rational or irrational.

• If rational, we're done
• If irrational, let $r = \sqrt{2}^{\sqrt{2}}$, then $r^{\sqrt{2}} = (\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{2}^2 = 2$ ✓

Nonconstructive Proof

Prove existence without finding a specific example.

Uniqueness Proofs

Existence and Uniqueness

Prove $\exists! x \, P(x)$:

1. Existence: Show $\exists x \, P(x)$
2. Uniqueness: Show if $P(a)$ and $P(b)$, then $a = b$

Example

Theorem: There is a unique real number $x$ such that $x + 3 = 5$.

Proof:

• Existence: $x = 2$ satisfies $2 + 3 = 5$ ✓
• Uniqueness: Suppose $a + 3 = 5$ and $b + 3 = 5$
  • Then $a + 3 = b + 3$
  • Thus $a = b$ $\square$

Common Mistakes to Avoid

1. Circular reasoning: Using what you're trying to prove
2. Assuming the converse: Proving $q \rightarrow p$ instead of $p \rightarrow q$
3. Proof by example: One example doesn't prove "for all"
4. Incomplete case analysis: Missing cases in proof by cases