Proof Strategies

Types of Statements to Prove

Universal Statements

"For all $x$, $P(x)$" — $\forall x \, P(x)$

Strategy: Take an arbitrary element and prove it satisfies $P$.

Existential Statements

"There exists $x$ such that $P(x)$" — $\exists x \, P(x)$

Strategy: Find a specific example, or prove indirectly.

Conditional Statements

"If $P$ then $Q$" — $P \rightarrow Q$

Strategy: Direct proof, contraposition, or contradiction.

Biconditional Statements

"$P$ if and only if $Q$" — $P \leftrightarrow Q$

Strategy: Prove both directions: $P \rightarrow Q$ and $Q \rightarrow P$.

Existence Proofs

Constructive Proofs

Explicitly exhibit an object satisfying the property.

Example: Prove there exist irrational numbers $a, b$ such that $a^b$ is rational.

Proof: Let $a = \sqrt{2}$ and $b = 2\log_2 3$. Then $a^b = \sqrt{2}^{2\log_2 3} = 2^{\log_2 3} = 3$, which is rational.

Actually, we need to verify $b$ is irrational, which requires more work. Alternative:

Consider $\sqrt{2}^{\sqrt{2}}$.

• If it's rational, take $a = b = \sqrt{2}$
• If it's irrational, take $a = \sqrt{2}^{\sqrt{2}}$ and $b = \sqrt{2}$ Then $a^b = (\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{2}^2 = 2$ ✓

Non-Constructive Proofs

Prove existence without finding a specific example.

Example: Prove there exist two irrational numbers whose sum is rational.

Proof: Consider $\sqrt{2}$ and $-\sqrt{2}$. Both are irrational, but $\sqrt{2} + (-\sqrt{2}) = 0$ is rational. $\square$

(This is actually constructive, but serves as a simple example.)

Uniqueness Proofs

Method 1: Direct Uniqueness

Assume two elements satisfy the property, then show they're equal.

Template: Suppose $a$ and $b$ both satisfy property $P$. $$Show that $a = b$$$

Method 2: Uniqueness via Contradiction

Assume two different elements satisfy the property and derive a contradiction.

Example

Theorem: If $ax = b$ with $a \neq 0$, then $x$ has a unique solution.

Proof:

• Existence: $x = \frac{b}{a}$ is a solution
• Uniqueness: Suppose $x_1$ and $x_2$ both satisfy $ax = b$
  • Then $ax_1 = b$ and $ax_2 = b$
  • So $ax_1 = ax_2$
  • Since $a \neq 0$, we get $x_1 = x_2$ $\square$

Counter-Examples

To disprove $\forall x \, P(x)$, find one counter-example where $P(x)$ is false.

Claim: Every prime number is odd.

Counter-example: 2 is prime but even. $\square$

Proof by Construction

Build an object with desired properties.

Example: Prove that for any $n \geq 1$, there exists a binary string of length $n$ with more 1s than 0s.

Proof: Construct the string of $n$ ones: $11\ldots1$. It has $n$ ones and 0 zeros. $\square$

The Pigeonhole Principle in Proofs

If $n+1$ objects are placed in $n$ boxes, at least one box contains two or more objects.

Generalized Version

If $N$ objects are placed in $k$ boxes, some box contains at least $\lceil N/k \rceil$ objects.

Example

Theorem: Among any 5 integers, two have the same remainder when divided by 4.

Proof: There are 4 possible remainders: 0, 1, 2, 3 (boxes). With 5 integers (pigeons), by pigeonhole principle, at least two must have the same remainder. $\square$

Proof by Minimum Counter-Example

To prove $\forall n \geq n_0, P(n)$:

1. Assume there exists a counter-example
2. Let $m$ be the smallest counter-example
3. Use properties of $m$ being minimal to derive a contradiction

Example

Theorem: Every positive integer can be written as a sum of distinct powers of 2.

Proof: Suppose not. Let $m$ be the smallest positive integer that cannot be written this way.

• $m > 1$ (since $1 = 2^0$)

• Let $2^k$ be the largest power of 2 with $2^k \leq m$

• Consider $m - 2^k$:

  • $m - 2^k < m$ (since $2^k > 0$)
  • $m - 2^k \geq 0$ (by choice of $k$)
  • $m - 2^k < 2^k$ (otherwise $2^{k+1} \leq m$)

• By minimality of $m$, $m - 2^k$ can be written as distinct powers of 2

• None of these powers is $2^k$ (since their sum $< 2^k$)

• So $m = 2^k + (m - 2^k)$ is a sum of distinct powers of 2 ✗

Contradiction! $\square$

Diagonalization Arguments

Used to prove uncountability or non-existence.

Cantor's Diagonal Argument

Theorem: The real numbers in $(0,1)$ are uncountable.

Proof: Assume we can list all reals in $(0,1)$: $r_1, r_2, r_3, \ldots$

Construct a new number $d$ where the $i$-th digit differs from the $i$-th digit of $r_i$.

Then $d \neq r_i$ for all $i$ (differs in $i$-th digit), but $d \in (0,1)$.

Contradiction! The reals are uncountable. $\square$