Some statements, like "$\sqrt{2}$ is irrational" from the real number system, say that something does not exist. There is nothing to start a direct proof from. Proof by contradiction supplies a starting point: assume the opposite and watch it fall apart. It is a cousin of proof by contrapositive.
Key idea
To prove $S$ by contradiction, assume $\neg S$ and reason until you reach something impossible, a statement and its negation together. Since $\neg S$ leads to a contradiction, $\neg S$ is false, so $S$ is true. The assumption must be the exact negation of $S$; to prove "if $P$, then $Q$," assume $P$ and $\neg Q$.
Why it works
If $\neg S \to (R \wedge \neg R)$ is true, then $\neg S$ must be false, because $R \wedge \neg R$ is false in every row, and a true conditional with a false conclusion must have a false hypothesis. This is why the negation must be exact: a contradiction reached from the wrong assumption only shows that the wrong assumption is false, which tells you nothing about $S$. The rules for negating quantifiers are the tool for getting it right.
Worked examples
Worked example: $\sqrt{2}$ is irrational
Prove that $\sqrt{2}$ is irrational.
- Suppose not: $\sqrt{2} = \frac{a}{b}$ for integers $a$, $b$ with $b \ne 0$, and the fraction in lowest terms (any fraction can be reduced).
- Square: $2 = \frac{a^{2}}{b^{2}}$, so $a^{2} = 2b^{2}$. Then $a^{2}$ is even, so $a$ is even (the contrapositive lesson proved this). Write $a = 2c$.
- Substitute: $4c^{2} = 2b^{2}$, so $b^{2} = 2c^{2}$. Now $b^{2}$ is even, so $b$ is even.
- Both $a$ and $b$ are even, so $\frac{a}{b}$ was not in lowest terms: a contradiction. So $\sqrt{2}$ is irrational.
Answer: The assumption forces $a$ and $b$ both even, contradicting lowest terms.
Worked example: There are infinitely many primes
Prove that there are infinitely many primes.
- Suppose not: the primes are exactly $p_{1}, p_{2}, \ldots, p_{k}$.
- Let $N = p_{1}p_{2}\cdots p_{k} + 1$. Dividing $N$ by any $p_{i}$ leaves remainder $1$, so no $p_{i}$ divides $N$.
- But $N > 1$, so $N$ has some prime factor, and that prime is not on the list. This contradicts "the list has every prime."
- Note that $N$ itself need not be prime: $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30{,}031 = 59 \cdot 509$. The proof only needs a prime factor that is new.
Answer: Any finite list of primes misses a prime factor of $N$.
Worked example: No largest even integer
Prove that there is no largest even integer.
- Suppose there is one, $N$.
- Then $N + 2$ is even (it is $2(k + 1)$ if $N = 2k$) and larger than $N$.
- That contradicts "$N$ is the largest." So no largest even integer exists.
Answer: $N + 2$ beats any proposed largest even integer.
Common mistake
Starting from a wrong negation. To prove "if $n^{2}$ is even, then $n$ is even," the assumption must be "$n^{2}$ is even and $n$ is odd." Assuming "$n^{2}$ is odd" or "$n$ is even" negates the wrong thing, and any contradiction you reach proves nothing about the original claim. Check: write the claim in symbols, negate it with the rules ($\neg(P \to Q) \equiv P \wedge \neg Q$, $\neg \forall \equiv \exists \neg$), and start from exactly that.