Proof by Contradiction

Method

• Assume that ~S (not S) is true
• Based on this, use known facts and theorems to arrive at a logical contradiction.
• Since every step of the argument thus far is logically correct, the problem must lie in the assumption (that ~S is true)
• Thus, it can be concluded that ~S is false, that is, S is true

Example

Prove that $\sqrt{2}$ is irrational

1. Suppose not, that $\sqrt{2}$ is rational 1.1. Then, $\exists a,b\in \mathbb{Z},b\ne 0$ s.t. $\sqrt{2}=\frac{a}{b}$ (by definition of rational numbers) 1.2. Convert $\frac{a}{b}$ to its lowest term, $\frac{m}{n}$ 1.3. $m^2=2n^2$ (by basic algebra) (note: this is done by squaring both sides of $\sqrt{2}=\frac{m}{n}$) 1.4. Hence, $m^2$ is even (by definition of even numbers, as $n^2$ is an integer by closure) 1.5. Hence, $m$ is even (by Proposition 4.6.4 (has been proved somewhere else)) 1.6. Let $m=2k$; Substituting into 1.3: $4k^2=2n^2$, or $n^2=2k^2$ 1.7. Hence, $n^2$ is even (by definition of even numbers) 1.8. Hence, $n$ is even (by Proposition 4.6.4) 1.9. So both $m$ and $n$ are even, but this contradicts that $\frac{m}{n}$ is in its lowers term
2. Therefore, the assumption that $\sqrt{2}$ is rational is false
3. Hence $\sqrt{2}$ is irrational