Proof by contradiction ( M381-NT#2 )

M381 Unit 1 Foundations is about
- number patterns,
- proof by mathematical induction,
- divisibility and the division algorithm
- GCD and LCM ( greatest common divisor and least common multiple )
- the Euclidean algorithm
- solving linear Diophantine equations

Unit 1 also contains the proof of the method of mathematical induction. 'The proof of proof by induction'. This post is part 1 of a forthcoming series with an in-depth explanation of this proof. We begin with the concept of proof by contradiction.

Proof by contradiction

If finding a direct proof fails we can try proving by contradiction. If we have to prove a proposition P we then assume ~P and show that this assumption implies a contradiction and thus ~P is false or P is true.

Example

Show that $\sqrt{2}$ is irrational ( can not be expressed as a fraction ).

We assume that $\sqrt{2}$ is rational ( not irrational ) and can thus write it as follows: $$\sqrt{2} = \frac{p}{q}$$ where $(p,q)=1$ ( have no common divisors, are relatively prime ).

Then:
$\sqrt{2} = \frac{p}{q}$
$2 = \frac{p^2}{q^2}$
$p^2 = 2q^2$
So $p^2$ is even. Since the square of an odd number is always odd and the square of an even number is always even, we know that $p$ must be even and can thus be factorized to $2r$.

Then:
$\sqrt{2} = \frac{2r}{q}$
$2 = \frac{4r^2}{q^2}$
$q^2 = 2r^2$
So q can be factorized further as well to $2s$.

Then:
$(p,q) = (2r,2s) = 2(r,s) > 1$.
This is clearly a contradiction and thus proves that $\sqrt{2}$ must be irrational.