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

##### June 24, 2014 by Florian Aigner

"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: CMU professor honored for computational complexity breakthrough

## Related Stories

#### CMU professor honored for computational complexity breakthrough

May 21, 2007

Computer scientists at Carnegie Mellon University and the Russian Academy of Science will share the Association for Computing Machinery's 2007 Gödel Prize for their seminal work on what many consider the most important unresolved ...

#### Mathematician announces that he's proved the ABC conjecture

September 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 ...

#### Fermat's Last Theorem, more can be proved more simply: Professor steers field toward a numbers-only proof

March 4, 2013

Fermat's Last Theorem—the idea that a certain simple equation had no solutions— went unsolved for nearly 350 years until Oxford mathematician Andrew Wiles created a proof in 1995. Now, Case Western Reserve University's ...

#### Russia's Yakov Sinai wins Abel mathematics prize

March 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.

#### 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: the computer ...

#### Simulating time travel: Doctor Who meets Professor Heisenberg

June 20, 2014

(Phys.org)—University of Queensland researchers have simulated time travel using light particles. Lead author and PhD student Martin Ringbauer, from UQ's School of Mathematics and Physics, said the study used photons – ...

## Recommended for you

#### Antarctic fossils reveal creatures weren't safer in the south

May 26, 2016

A study of more than 6,000 marine fossils from the Antarctic shows that the mass extinction event that killed the dinosaurs was sudden and just as deadly to life in the polar regions.

#### Neanderthals were stocky from birth

May 26, 2016

If a Neandertal were to sit down next to us on the underground, we would probably first notice his receding forehead, prominent brow ridges and projecting, chinless face. Only on closer inspection would we notice his wider ...

#### Unusual tusks in a new species of dicynodont from the Permian of Brazil

May 26, 2016

May has been a spectacularly busy month. And a lot of awesome research was recently published on PLOS ONE and other open access journals (check out our Fossil Friday Roundup feature for lists of the latest publications and ...

#### High altitude archaeology: Prehistoric paintings revealed

May 26, 2016

Archaeologists at the University of York have undertaken pioneering scans of the highest prehistoric paintings of animals in Europe.

#### Tiny vampires

May 26, 2016

Vampires are real, and they've been around for millions of years. At least, the amoebae variety has. So suggests new research from UC Santa Barbara paleobiologist Susannah Porter.

#### Strange sea-dwelling reptile fossil hints at rapid evolution after mass extinction

May 23, 2016

Two hundred and fifty million years ago, life on earth was in a tail-spin—climate change, volcanic eruptions, and rising sea levels contributed to a mass extinction that makes the death of the dinosaurs look like child's ...

##### wizenberg
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.
##### wealthychef
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.
##### julianpenrod
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.
##### malapropism
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.
##### Job001
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.
##### alfie_null
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.
##### Doiea
Jun 25, 2014
This comment has been removed by a moderator.
##### Doiea
Jun 25, 2014
This comment has been removed by a moderator.
##### swordsman
not rated yet Jun 30, 2014
The universe is obviously incomplete.