(N.B. this blog post is mainly directed at my undergraduate students for their first year Mathematics for Computing module!)
The square root of 2 (, root 2) is the positive algebraic number that, when multiplied by itself, gives the number 2. Geometrically, the square root of 2 is the length of a diagonal across a square with sides of one unit of length; this follows from the Pythagorean theorem. A quick approximation for the square root of two is (despite having a denominator of only 70, it differs from the correct value by less than ).
In the first few lectures we have covered the basics of logic and the propositional calculus, including the idea of reductio ad absurdum, or more specifically, proof by contradiction (indirect proof). One of the examples given in the lecture was proving that the square root of 2 is irrational using infinite descent:
Assume that is rational; this means that we can represent it as the ratio of two integers:
Then can be written as an irreducible fraction such that and are co-prime integers:
It follows that:
Therefore is even because it is equal to ( is necessarily even because it is 2 times another whole number and even numbers are multiples of 2); it follows that must be even (as squares of odd integers are never even). Because a is even, there exists an integer that fulfils:
Substituting in for in the earlier equation:
Because is divisible by 2 and therefore even, and because , it follows that is also even which means that is even. As we have shown that and are both even, this contradicts that is irreducible.
Because there is a contradiction, the original assumption that is a rational number must be false. By the law of excluded middle, the opposite is proven: is irrational.
This proof was hinted at by Aristotle, in his Analytica Priora, but it appeared first as a full proof in Euclid‘s Elements (as proposition 117 of Book X). There are a number of other methods of proving that the square root of 2 is irrational, including a simple geometric proof and proof by unique factorisation (using that fact that every integer greater than 1 has a unique factorisation into powers of primes). Check them out!
Here’s another geometric proof using infinite descent on the (great) Futility Closet blog.