Kurt Godel studied statements which refer to themselves, and his results shook the foundations of mathematics

"All Cretans are liars", said Epimenides, a Cretan. But this means that his statement must be a lie too. But then it is false that Cretans are liars and the statement must be true. So what now?

Sentences which say something about themselves can lead to paradoxes. The mathematician and logician Kurt Gödel found ways to study such statements using the tools of modern logic, which made him one the founders of metamathematics – a branch of mathematics that does not try to come up with new proofs or calculations, but in a way investigates mathematics itself. It is mathematics trying to figure out what can be figured out with mathematics.

Complete and Self-Consistent Mathematics

Whoever tries to define new mathematical objects has to take great care not to get tangled up in contradictions. Gottlob Frege struggled with this problem, when he was trying to use set theory to create a new, solid foundation for mathematics. Just as he was finishing his magnum opus "Foundations of Arithmetic" in 1902, he received a letter from his young colleague Bertrand Russell, who drew his attention to a particularly tricky problem:

In set theory, a set may consist of any kind of objects, for instance the set of numbers between three and seven, or the set of isosceles triangles. A set can even contain itself – such as the set of all sets. But what about the set of all sets that do not contain themselves? It has to contain itself precisely if it does not contain itself – an unsolvable contradiction. Frege was heartstricken and finally gave up his work on set theory.

In the 1920s, the goal was set to get rid of such annoyances once and for all. David Hilbert, arguably the most prominent mathematician of his time, initiated "Hilbert's Program". His idea was that all of mathematics should be rigorously and unequivocally grounded on a small number of axioms – clear, evident truths, such as "every natural number has a successor". From these simple axioms all mathematical theorems should follow.

Additionally, a proof should be found that every true statement can be proved within the mathematical formalism, and that the truth of any given statement can unambiguously be checked with mathematical methods. Mathematics should be free of inner contradictions. It was an era of optimism and bold visions: "We must know – we will know" was Hilbert's slogan – in this spirit, he wanted to set mathematics on a firm, unshakable foundation.

Gödel and His Incompleteness Theorems

But this dream of a complete, consistent mathematical theory was shattered by Kurt Gödel. He managed to show that in any mathematical system which is at least powerful enough to provide a theory of natural numbers, one can formulate mathematical statements which are true, but cannot be derived from the axioms within the system. This put an end to Hilbert's program.

Kurt Gödel was born in 1906 in Brno. He studied in Vienna, where he got in touch with the Vienna Circle. He was probably not the easiest person to get along with: Gödel suffered from hypochondria and paranoia. But even if his behaviour in everyday life may have seemed irrational at times, in his work he proved to be a remarkably clear thinker.

Logic deals with statements about numbers – such as: "For any two natural numbers x and y, x+y is the same as y+x." This can be written down as a simple formula in the language of logic. Gödel's great idea was that such statements about numbers can themselves be coded as numbers. One just has to assign suitable number codes to the symbols which are used in logical formulas.

Back then, this idea may have appeared much more outrageous than it does now. Today, in the digital age, we are used to all kinds of information being represented as numbers: Is some sense, the holiday pictures on our hard drive are stored as a number, just like our favourite music on a CD. In a similar way, a number can be assigned to any mathematical statement – the so called "Gödel number". Gödel came up with this concept a decade before the first computers were built.

With a suitable coding system, some numbers can be interpreted as a mathematical statement or as a mathematical proof. But this way, sentences can be constructed which are not only statements about numbers, but statements about mathematical formulas – such as "n is not the Gödel number of a proof of the statement F" – and this statement itself can again be coded with a Gödel number.

That way, Gödel could construct a statement saying "there is no number which is the Gödel number of a proof of this statement" – or, in simpler terms, a statement saying "I am not provable".

If this statement is true, then there is a true statement which cannot be proved within the mathematical system. This means that the system is incomplete. If the statement is false, and the statement "I am not provable" can in fact be proved, then we have found an inner contradiction.

Therefore, Gödel's first incompleteness theorem says – in layman's terms: "Any logical system (which is at least powerful enough to include a theory of natural numbers) is either inconsistent or incomplete." From this, Gödel's even more general second incompleteness theorem follows: "Any sufficiently powerful consistent system cannot prove its own consistency."

A New Branch of Science is Born

Hilbert's dream of a closed, complete, consistent theory of mathematics was dead, but in a sense, this made logic even more interesting than it had ever been before. One of the main reasons for this was that a completely new branch of science emerged at around the same time – informatics was born. John von Neumann, who was one of the first scientists to fully grasp the significance of Gödel's incompleteness theorems, turned away from fundamental mathematics and became one of the founding fathers of modern computer science.

Alan Turing, who was also one of the most influential people in the history of informatics, applied ideas quite similar to Gödel's arguments to the question which kind of calculations can be done by computers. Turing's famous "halting problem" is closely related to Gödel's incompleteness theorems: There are computer programs that stop calculating at some point, others get stuck in infinite loops. Turing posed the question whether there are computer programs that check if a given program will ever terminate. Similar to Gödels statements which refer to themselves, Turing studied computer codes which analyse themselves. His result: Such a computer program is logically impossible.

From Vienna to Princeton

In 1940 Gödel left Vienna, together with his wife Adele. Via Russia he went to the USA, where he became a colleague and friend of Albert Einstein at Princeton University. Sometimes Gödel even worked on the Theory of Relativity – he was able to show that according to Einstein's equations a rotating universe is possible, in which a time traveller can travel into his own past.

Gödel's mental problems tormented him until his death: Obsessed with the fear of being poisoned, he only ate what his wife prepared for him. When she had to stay in a hospital for a while, Gödel refused to eat, eventually starving to death in 1978.

His ideas, however, are more alive than ever: Gödel is, without any doubt, one of the most influential scientists of the 20th century. Mathematics, Informatics and even Philosophy have been deeply influenced by his thoughts and ideas.