Friday, 25 January 2008

We Hold These Truths to be Self-evident

Mathematical proof is the closest thing you can get to absolute certainty. The idea of mathematically proving something seemed alien to me when I first encountered it. I was amazed that no amount of brute force can invalidate a mathematical truth. It doesn't depend on the amount of evidence in support of it like physics for example. Take Golbach's conjecture, which states that every even number greater than 2 can be expressed as a sum of two primes, has been verified for hundreds of trillions of numbers but that still does not prove the conjecture to be true since there are infinitely many numbers. A proof must demonstrate that a proposition is true in all cases to which it applies, without a single exception. One of my favourite proofs is Georg Cantor's demonstration that there is a whole hierarchy of infinities, a mind boggling idea.
There are a lot of ways to prove things, here I have listed some of the methods mathematicians use.

Direct Proof

In direct proof, the conclusion is established by logically combining the axioms, definitions, and earlier theorems. For example, direct proof can be used to establish that the sum of two even integers is always even: For any two even integers x and y we can write x = 2a and y = 2b for some integers a and b, since both x and y are multiples of 2. But the sum x + y = 2a + 2b = 2(a + b) is also a multiple of 2, so it is therefore even by definition. This proof uses definition of even integers, as well as distribution law.

Proof by Induction

Proof by induction is applicable to integers. If you have a theorem which holds true for some value of n, for example n = k, you then deduce that if this is true it will also be true for n = k + 1. Finally establish that it is true when n = 1. We then know it will be true for n = 2, 3, 4...
A subset of induction is infinite descent, which can be used to prove the irrationality of the square root of two.

Proof by Contradiction

Also known as reductio ad absurdum, you can prove a statement is true by assuming it is false, and if a contradiction arises then your original statement has to be true. A classical example is Euclid's proof of the irrationality of square root of two:

Let: SQRT(2) = a/b where a and b are both integers.
Now we repeatedly apply rule (3) to a/b until the fraction can no longer be simplified. This gives us:
SQRT(2) = p/q where p and q do not share any common factors.
If we square both sides then: 2 = p2/q2
This can be rearranged to give: 2q2 = p2
Now from point (1) we know that p2 must be even. Futhermore, from point (2) we know that p itself must be even. Since p is even it can be re-written in the form p = 2m, where m is some other whole number. This follows from point (1). Plug this back into the equation and we get:
2q2 = (2m)2 = 4m2
Divide both sides by 2 to get: q2 = 2m2
But, by the same arguments we used before, we know that q2 must be even, and so q itself must also be even. If this is the case, then q can be written as 2n where n is some other integer. If we go back to the beginning, then:
SQRT(2) = p/q = 2m/2n
However this contradicts the original condition that p and q do not share any common factors, and therefore there cannot exist two integers a and b where SQRT(2) = a/b
Therefore SQRT(2) is irrational. QED.

Proof by Transposition

Proof by Transposition establishes the conclusion "if p then q" by proving the equivalent contrapositive statement "if not q then not p".

Proof by Construction

Something can be proven to exist by giving an example of or a method to find it it. Such an example is showing that there is at least one square number which is also a cube number, 64 is the square of 8 and is also the cube of 4.

Combinatorial proof

A combinatorial proof establishes the equivalence of different expressions by showing that they count the same object in different ways. Usually a bijection is used to show that the two interpretations give the same result.

Nonconstructive Proof

This is the opposite to proof by construction, something can be shown to exist indirectly without providing any examples. Often, this takes the form of a proof by contradiction in which the non-existence of the object is proven to be impossible.

There are also things in mathematics that cannot be proven true or false using the current system, an example of this is Cantor's continuum hypothesis which has been shown to be undecidable using only the ZFC.



Post a Comment