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

Jun 24, 2014 by Florian Aigner
Kurt Gödel, 1925

"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 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 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 , 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 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.

Explore further: Logic in computer science

add to favorites email to friend print save as pdf

Related Stories

Logic in computer science

May 27, 2014

All men are mortal. Socrates is a man. Therefore, Socrates is mortal. Logical arguments like this one have been studied since antiquity. In the last few decades, however, logic research has changed considerably: ...

Russia's Yakov Sinai wins Abel mathematics prize

Mar 26, 2014

Russian mathematician Yakov Sinai won the prestigious Abel mathematics prize for his work in dynamical systems and mathematical physics, the Norwegian Academy of Science and Letters said Wednesday.

Mathematician announces that he's proved the ABC conjecture

Sep 12, 2012

(Phys.org)—In all of history there are very few names that stand out in the field of mathematics, at least among those not in the field: Euclid, Newton, Pythagoras, etc. This is likely due to several reasons, chief among ...

Recommended for you

Computer games give a boost to English

6 hours ago

If you want to make a mark in the world of computer games you had better have a good English vocabulary. It has now also been scientifically proven that someone who is good at computer games has a larger ...

Saddam Hussein—a sincere dictator?

10 hours ago

Are political speeches manipulative and strategic? They could be – when politicians say one thing in public, and privately believe something else, political scientists say. Saddam Hussein's legacy of recording private discussions ...

Oldest representative of a weird arthropod group

10 hours ago

Biologists at Ludwig-Maximilians-Universitaet (LMU) in Munich have assigned a number of 435-million-year-old fossils to a new genus of predatory arthropods. These animals lived in shallow marine habitats ...

User comments : 7

Adjust slider to filter visible comments by rank

Display comments: newest first

not rated yet Jun 24, 2014
I believe that Godel became a colleague and friend of Einstein's not at Princeton University, but at the Institute for Advanced Study which is located in Princeton, New Jersey.
1 / 5 (1) Jun 24, 2014
Not a good example. If "all Cretans are liars" is false, that does not mean that everything every Cretan says is true.
1 / 5 (2) Jun 24, 2014
No one has ever seen the set of all sets that do not contain themselves. And, by its logivcal nature, it cannot exist, because it is self contradictory. They could have simply said it is not a vlid construct and eliminated all such from mathematics. But they wanted mathematics to include everything, and they may have been afraid of not counting an illegitimate object among those outlawed. So they accepted it and are credited with expanding understanding of the world. There are those who say God cannot exist because He can't make a stone so big He can't life it and that is self contradicting. But there is more evidence, even if only apocryphal, of being experiencing God's presence than there is of anyone coming face to face with the huge set. And yet those who praise such as Godel insist on stating, without proof, God is not present.
5 / 5 (2) Jun 24, 2014
There are those who say God cannot exist because He can't make a stone so big He can't life it and that is self contradicting.

My understanding of this is that it is merely an example of the logical inconsistency of the concept of a god who is omnipotent, omniscient and omnipresent. That is, it is a demonstration of the foolishness of religious theory, notably that of the Abrahamic religions.

But there is more evidence, even if only apocryphal, of being experiencing God's presence than there is of anyone coming face to face with the huge set.

However, apocryphal evidence, by its nature and definition, is not evidence at all.
not rated yet Jun 25, 2014
The logic and philosophical implications of Godel's incompleteness are far more significant than typically assumed;
Assumptions and iterative assumptions inevitably fail or paradox occurs.
Simple models must be replaced by more complex.
New knowledge systems are inevitably required.
Probabilistic data cannot provide absolute truth or logic.
5 / 5 (2) Jun 25, 2014
And yet those who praise such as Godel insist on stating, without proof, God is not present.

Wrong. Rather, you who claim God exists, cannot prove it. Don't be disingenuous.
Jun 25, 2014
This comment has been removed by a moderator.
Jun 25, 2014
This comment has been removed by a moderator.
not rated yet Jun 30, 2014
The universe is obviously incomplete.