Introduction

http://i.imgur.com/2XGVw1T.jpg

Kurt Gödel - one of the most significant logicians in history.

Image credit.

Gödel’s famous incompleteness theorem was one of the great triumphs of twentieth century mathematics, and places an unexpected limitation on what we might be able to know in mathematics. Indeed, it's quite an unnerving theorem as it says there may be conjectures out there, perhaps about numbers, for example, such as Golbach's conjecture (which supposes that every even number is the sum of two primes) for which there is no proof within the axiomatic system we have constructed for mathematics.

This was a big revelation for mathematics, as it was previously believed that every true statement has a proof. Even though some statements, such as the Poincare conjecture are devilishly difficult to prove, we would expect that all true statements do have a valid proof, but Gödel showed that there is a fundamental gap between truth, and proof.

Paradoxes

Suppose we have an ordinary piece of paper, and on one side of the paper, is written "the statement on the other side of this card is false". Let’s suppose that this is true, and that the statement on the other side of the card is indeed false, as we have been told. When we turn the card over, we find that it says, "the statement on the other side of this card is true". The more iterations of this you work through, the further and further down the regressive rabbit hole you descent, into an infinite nonsensical loop! The existence of verbal paradoxes is not something we should be worried about, because we don't expect every syntactical object to have some objective truth value attached to it.

Before Gödel

We would expect that we should be able to prove that mathematics is consistent, and that mathematics does not give rise to logical contradictions. This school of thought was solidified and inspired by the great paradoxes that Bertrand Russell brought to the fore in the twentieth century. A classic example of one of these paradoxes is the question of whether this set is in that set, or not, for the set of all sets which don’t contain themselves. One of the big problems that David Hilbert proposed to mathematicians in the twentieth century was to prove that mathematics, itself is consistent. Gödel brought about a fundamental paradigm shift in his work by showing that there are true statements out there that cannot be proven, within any mathematical system.

Axioms

How does mathematics work? We set down these things which we call axioms which are the kind of things we believe govern the way that numbers and geometry work. For example, we don't expect the 1 + 2 to be different from the number 2 + 1. We have rules which allow us to make logical deductions from these axioms. Indeed, we can add new axioms if we feel we haven't captured the essence and logical core of mathematics. Now, the pipe dream is to have a set of axioms which are strong enough so that we can deduce all the current axioms, and expand what we can prove within mathematics. There will be a set of axioms which can explain all of mathematics.

What did Gödel do?

He did something very novel, by essentially formulating a way for mathematics to talk about itself. He invented this concept which is now referred to as the Gödel coding. The key idea is that every statement about mathematics has its own particular code number. So, every statement about mathematics could be turned into a number, for example the axioms of mathematics have code numbers, true statements have code numbers, as well as false statements.

As you might expect, these numbers are typically huge, but the code number corresponding to each statement is unique. Every code number can be worked back into a mathematical statement, but not every code number is a meaningful statement. The more interesting situation is to study the fact that every true mathematical statement has a code number associated with it, which allows us to talk about the concept of proof using these numbers. Simply put, every code number that is divisible by the axioms is provable from the axioms.

Gödel’s challenge

Now, Gödel challenges you with the following statement: "this statement cannot be proved from the axioms of mathematics". This has a code number, and we can change it into a mathematical equation, so by necessity it has to be either true or it is false, because that’s how maths works! What if it's false? Then the statement is provable from the axioms, but a provable statement must be true. So, we have a contradiction. We are assuming that mathematics is consistent so we can't have contradictions. We arrive at the conclusion that the statement must be true! To reiterate, it says that this statement cannot be proved from the axioms, so we have a true statement which cannot be proved true from the axioms of mathematics.

What we have done is, within a system of mathematics, we have found a true statement that cannot be proved within that system - we have proved it from an outside perspective, looking in. We can then just add the statement as an axiom to the system. It's a sort of infinite regression thing. As much as you expand mathematics, adding axioms, you will always be missing something.

Link to Riemann hypothesis

http://i.imgur.com/7lKGEGn.gif

The Riemann Zeta function.

Gödel talked about the famous Riemann hypothesis, which is a conjecture that states the Riemann zeta function has its zeros only at the negative and even integers, and complex numbers with real part ½. We may be having trouble proving it just because we haven't expanded the axioms of mathematics to such a level where it is provable! If the Riemann hypothesis turns out to be a statement without a proof, this would prove that the Riemann hypothesis is true. If it were false, there would be a zero off the line, and it must be provably false. So, it must be true!