Tag Archives: Proofs

The beauty of a good mathematical proof

Throughout his life, John von Neumann, the Hungarian-American polymath, leaned towards pure mathematics, or pure mathematics with recognised applications. In his 1947 essay entitled The Mathematician, he described his personal concept of mathematics, showing him to be thoughtful and original concerning the philosophical underpinnings of the discipline. One word von Neumann repeatedly uses is aesthetical; he defends mathematics for mathematics’ sake, consciously posting analogies to the visual arts. For example, in listing the qualities of a good mathematical proof:

One also expects “elegance” in its “architectural,” structural make-up. Ease in stating the problem, great difficulty in getting hold of it and in all attempts at approaching it, then again some surprising twist by which the approach, or some part of the approach, becomes easy, etc. Also, if the deductions are lengthy or complicated, there should be some simple general principle involved, which ”explains” the complications and detours, reduces the apparent arbitrariness to a few simple guiding motivations, etc. These criteria are clearly those of any creative art, and the existence of some underlying empirical, worldly motif in the background — overgrown by aestheticizing developments and followed by a multitude of labyrinthine variants — all this is much more akin to the atmosphere of art pure and simple than to that of the empirical sciences.

Nevertheless, von Neumann insisted that the best mathematics was usually inspired by practical problems, perhaps in partial defence of game theory from fellow mathematicians who at the time deprecated it as an applied field.

(also see: Feynman, Bethe and the beauty of mathematics)

Tagged , , ,

Proof that the square root of 2 is irrational

(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 (\sqrt{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 \tfrac{99}{70} (despite having a denominator of only 70, it differs from the correct value by less than \tfrac{1}{10000}).

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 \sqrt{2} is rational; this means that we can represent it as the ratio of two integers:

\dfrac{a}{b} = \sqrt{2}

Then \sqrt{2} can be written as an irreducible fraction \tfrac{a}{b} such that a and b are co-prime integers:

\left(\dfrac{a}{b}\right)^2 = 2

It follows that:

\dfrac{a^2}{b^2} = 2
a^2 = 2b^2

Therefore a^2 is even because it is equal to 2b^2 (2b^2 is necessarily even because it is 2 times another whole number and even numbers are multiples of 2); it follows that a must be even (as squares of odd integers are never even). Because a is even, there exists an integer k that fulfils:

a = 2k

Substituting in 2k for a in the earlier equation:

2b^2 = (2k)^2
2b^2 = 4k^2
b^2 = 2k^2

Because 2k^2 is divisible by 2 and therefore even, and because 2k^2 = b^2, it follows that b^2 is also even which means that b is even. As we have shown that a and b are both even, this contradicts that \tfrac{a}{b} is irreducible. \square

Because there is a contradiction, the original assumption that \sqrt{2} is a rational number must be false. By the law of excluded middle, the opposite is proven: \sqrt{2} 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!

Tagged ,