by Simon Singh
On 8 August 1900 Hilbert gave a historic talk at the International Congress of Mathematicians in Paris. Hilbert posed twenty-three unsolved problems in mathematics which he believed were of the most immediate importance. Some of the problems related to more general areas of mathematics, but most of them concentrated on the logical foundations of the subject. These problems were intended to focus the attention of the mathematical world and provide a programme of research. Hilbert wanted to galvanise the community into helping him realise his vision of a mathematical system free of doubt and inconsistency – an ambition he had inscribed on his tombstone:
Wir müssen wissen,
Wir werden wissen.
We must know,
We will know.
Although sometimes a bitter rival of Hilbert, Gottlob Frege was one of the leading lights in the so-called Hilbert programme. For over a decade Frege devoted himself to deriving hundreds of complicated theorems from the simple axioms, and his successes led him to believe that he was well on the way to completing a significant chunk of Hilbert’s dream. One of Frege’s key breakthroughs was to create the very definition of a number. For example, what do we actually mean by the number 3? It turns out that to define 3, Frege first had to define ‘threeness’.
‘Threeness’ is the abstract quality which belongs to collections or sets of objects containing three objects. For instance ‘threeness’ could be used to describe the collection of blind mice in the popular nursery rhyme, or ‘threeness’ is equally appropriate for describing the set of sides of a triangle. Frege noticed that there were numerous sets which exhibited ‘threeness’ and used the idea of sets to define ‘3’ itself. He created a new set and placed inside it all the sets exhibiting ‘threeness’ and called this new set of sets ‘3’. Therefore, a set has three members if and only if it is inside the set ‘3’.
This might appear to be an over-complex definition for a concept we use every day, but Frege’s description of ‘3’ is rigorous and indisputable and wholly necessary for Hilbert’s uncompromising programme.
In 1902 Frege’s ordeal seemed to be coming to an end as he prepared to publish Grundgesetze der Arithmetik (Fundamental Laws of Arithmetic) – a gigantic and authoritative two-volume work intended to establish a new standard of certainty within mathematics. At the same time the English logician Bertrand Russell, who was also contributing to Hilbert’s great project, was making a devastating discovery. Despite following the rigorous protocol of Hilbert, he had come up against an inconsistency. Russell recalled his own reaction to the dreaded realisation that mathematics might be inherently contradictory:
At first I supposed that I should be able to overcome the contradiction quite easily, and that probably there was some trivial error in the reasoning. Gradually, however, it became clear that this was not the case … Throughout the latter half of 1901 I supposed the solution would be easy, but by the end of that time I had concluded that it was a big job … I made a practice of wandering about the common every night from eleven until one, by which time I came to know the three different noises made by nightjars. (Most people only know one.) I was trying hard to solve the contradiction. Every morning I would sit down before a blank sheet of paper. Throughout the day, with a brief interval for lunch, I would stare at the blank sheet. Often when evening came it was still empty.
There was no escaping from the contradiction. Russell’s work would cause immense damage to the dream of a mathematical system free of doubt, inconsistency and paradox. He wrote to Frege, whose manuscript was already at the printers. The letter made Frege’s life’s work effectively worthless, but despite the mortal blow he published his magnum opus regardless and merely added a postscript to the second volume: ‘A scientist can hardly meet with anything more undesirable than to have the foundation give way just as the work is finished. In this position I was put by a letter from Mr Bertrand Russell as the work was nearly through the press.’
Ironically Russell’s contradiction grew out of Frege’s much loved sets, or collections. Many years later, in his book My Philosophical Development, he recalled the thoughts that sparked his questioning of Frege’s work: ‘It seemed to me that a class sometimes is, and sometimes is not, a member of itself. The class of teaspoons, for example, is not another teaspoon, but the class of things that are not teaspoons is one of the things that are not teaspoons.’ It was this curious and apparently innocuous observation that led to the catastrophic paradox.
Russell’s paradox is often explained using the tale of the meticulous librarian. One day, while wandering between the shelves, the librarian discovers a collection of catalogues. There are separate catalogues for novels, reference, poetry, and so on. The librarian notices that some of the catalogues list themselves, while others do not.
In order to simplify the system the librarian makes two more catalogues, one of which lists all the catalogues which do list themselves and, more interestingly, one which lists all the catalogues which do not list themselves. Upon completing the task the librarian has a problem: should the catalogue which lists all the catalogues which do not list themselves, be listed in itself? If it is listed, then by definition it should not be listed. However, if it is not listed, then by definition it should be listed. The librarian is in a no-win situation.
The catalogues are very similar to the sets or classes which Frege used as the fundamental definition of numbers. Therefore the inconsistency which plagues the librarian will also cause problems in the supposedly logical structure of mathematics. Mathematics cannot tolerate inconsistencies, paradoxes or contradictions. For example, the powerful tool of proof by contradiction relies on a mathematics free of paradox. Proof by contradiction states that if an assumption leads to absurdity then the assumption must be false, but according to Russell even the axioms can lead to absurdity. Therefore proof by contradiction could show an axiom to be false, and yet axioms are the foundations of mathematics and acknowledged to be true.
Many intellectuals questioned Russell’s work, claiming that mathematics was an obviously successful and unflawed pursuit. He responded by explaining the significance of his work in the following way:
‘But,’ you might say, ‘none of this shakes my belief that 2 and 2 are 4.’ You are quite right, except in marginal cases – and it is only in marginal cases that you are doubtful whether a certain animal is a dog or a certain length is less than a metre. Two must be two of something, and the proposition ‘2 and 2 are 4’ is useless unless it can be applied. Two dogs and two dogs are certainly four dogs, but cases arise in which you are doubtful whether two of them are dogs. ‘Well, at any rate there are four animals,’ you might say. But there are microorganisms concerning which it is doubtful whether they are animals or plants. ‘Well, then living organisms,’ you say. But there are things of which it is doubtful whether they are living or not. You will be driven into say: ‘Two entities and two entities are four entities.’ When you have told me what you mean by ‘entity’, we will resume the argument.
Russell’s work shook the fundations of mathematics and threw the study of mathematical logic into a state of chaos. The logicians were aware that a paradox lurking in the foundations of mathematics could sooner or later rear its illogical head and cause profound problems. Along with Hilbert and the other logicians, Russell set about trying to remedy the situation and restore sanity to mathematics.
This inconsistency was a direct consequence of working with the axioms of mathematics, which until this point had been assumed to be self-evident and sufficient to define the rest of mathematics. One approach was to create an additional axiom which forbade any class from being a member of itself. This would prevent Russell’s paradox by making redundant the question of whether or not to enter the catalogue of catalogues which do not list themselves in itself.
Russell spent the next decade considering the axioms of mathematics, the very essence of the subject. Then in 1910, in partnership with Alfred North Whitehead, he published the first of three volumes of P
rincipia Mathematica — an apparently successful attempt to partly address the problem created by his own paradox. For the next two decades others used Principia Mathematica as a guide for establishing a flawless mathematical edifice, and by the time Hilbert retired in 1930 he felt confident that mathematics was well on the road to recovery. His dream of a consistent logic, powerful enough to answer every question, was apparently on its way to becoming a reality.
Then in 1931 an unknown twenty-five-year-old mathematician published a paper which would forever destroy Hilbert’s hopes. Kurt Gödel would force mathematicians to accept that mathematics could never be logically perfect, and implicit in his works was the idea that problems like Fermat’s Last Theorem might even be impossible to solve.
Kurt Gödel was born on 28 April 1906 in Moravia, then part of the Austro-Hungarian Empire, now part of the Czech Republic. From an early age he suffered from severe illness, the most serious being a bout of rheumatic fever at the age of six. This early brush with death caused Gödel to develop an obsessive hypochondria which stayed with him throughout his life. At the age of eight, having read a medical textbook, he became convinced that he had a weak heart, even though his doctors could find no evidence of the condition. Later, towards the end of his life, he mistakenly believed that he was being poisoned and refused to eat, almost starving himself to death.
As a child Gödel displayed a talent for science and mathematics, and his inquisitive nature led his family to nickname him der Herr Warum (Mr Why). He went to the University of Vienna unsure of whether to specialise in mathematics or physics, but an inspiring and passionate lecture course on number theory by Professor P. Furtwängler persuaded Gödel to devote his life to numbers. The lectures were all the more extraordinary because Furtwängler was paralysed from the neck down and had to lecture from his wheelchair without notes while his assistant wrote on the blackboard.
By his early twenties Gödel had established himself in the mathematics department, but along with his colleagues he would occasionally wander down the corridor to attend meetings of the Wiener Kreis (Viennese Circle), a group of philosophers who would gather to discuss the day’s great questions of logic. It was during this period that Gödel developed the ideas that would devastate the foundations of mathematics.
In 1931 Gödel published his book Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (On Formally Undecidable Propositions in Principia Mathematica and Related Systems), which contained his so-called theorems of undecidability. When news of the theorems reached America the great mathematician John von Neumann immediately cancelled a lecture series he was giving on Hilbert’s programme and replaced the remainder of the course with a discussion of Gödel’s revolutionary work.
Gödel had proved that trying to create a complete and consistent mathematical system was an impossible task. His ideas could be encapsulated in two statements.
First theorem of undecidability
If axiomatic set theory is consistent, there exist theorems which can neither be proved or disproved.
Second theorem of undecidability
There is no constructive procedure which will prove axiomatic theory to be consistent.
Essentially Gödel’s first statement said that no matter what set of axioms were being used there would be questions which mathematics could not answer – completeness could never be achieved. Worse still, the second statement said that mathematicians could never even be sure that their choice of axioms would not lead to a contradiction – consistency could never be proved. Gödel had shown that the Hilbert programme was an impossible exercise.
Decades later, in Portraits from Memory, Bertrand Russell reflected on his reaction to Gödel’s discovery:
I wanted certainty in the kind of way in which people want religious faith. I thought that certainty is more likely to be found in mathematics than elsewhere. But I discovered that many mathematical demonstrations, which my teachers expected me to accept, were full of fallacies, and that, if certainty were indeed discoverable in mathematics, it would be in a new field of mathematics, with more solid foundations than those that had hitherto been thought secure. But as the work proceeded, I was continually reminded of the fable about the elephant and the tortoise. Having constructed an elephant upon which the mathematical world could rest, I found the elephant tottering, and proceeded to construct a tortoise to keep the elephant from falling. But the tortoise was no more secure than the elephant, and after some twenty years of arduous toil, I came to the conclusion that there was nothing more that I could do in the way of making mathematical knowledge indubitable.
Although Gödel’s second statement said that it was impossible to prove that the axioms were consistent, this did not necessarily mean that they were inconsistent. In their hearts many mathematicians still believed that their mathematics would remain consistent, but in their minds they could not prove it. Many years later the great number theorist Andre Weil would say: ‘God exists since mathematics is consistent, and the Devil exists since we cannot prove it.’
The proof of Gödel’s theorems of undecidability is immensely complicated, and in fact a more rigorous statement of the First Theorem should be:
To every ω-consistent recursive class k of formulae there correspond recursive class-signs r, such that neither ν Gen r nor Neg(ν Gen r) belongs to Flg(k) (where ν is the free variable of r).
Fortunately, as with Russell’s paradox and the tale of the librarian, Gödel’s first theorem can be illustrated with another logical analogy due to Epimenides and known as the Cretan paradox, or liar’s paradox. Epimenides was a Cretan who exclaimed:
‘I am a liar!’
The paradox arises when we try and determine whether this statement is true or false. First let us see what happens if we assume that the statement is true. A true statement implies that Epimenides is a liar, but we initially assumed that he made a true statement and therefore Epimenides is not a liar – we have an inconsistency. On the other hand let us see what happens if we assume that the statement is false. A false statement implies that Epimenides is not a liar, but we initially assumed that he made a false statement and therefore Epimenides is a liar – we have another inconsistency. Whether we assume that the statement is true or false we end up with an inconsistency, and therefore the statement is neither true nor false.
Gödel reinterpreted the liar’s paradox and introduced the concept of proof. The result was a statement along the following lines:
This statement does not have any proof.
If the statement were false then the statement would be provable, but this would contradict the statement. Therefore the statement must be true in order to avoid the contradiction. However, although the statement is true it cannot be proven, because this statement (which we now know to be true) says so.
Because Gödel could translate the above statement into mathematical notation, he was able to demonstrate that there existed statements in mathematics which are true but which could never be proven to be true, so-called undecidable statements. This was the death-blow for the Hilbert programme.
In many ways Gödel’s work paralleled similar discoveries being made in quantum physics. Just four years before Gödel published his work on undecidability, the German physicist Werner Heisenberg uncovered the uncertainty principle. Just as there was a fundamental limit to what theorems mathematicians could prove, Heisenberg showed that there was a fundamental limit to what properties physicists could measure. For example, if they wanted to measure the exact position of an object, then they could measure the object’s velocity with only relatively poor accuracy. This is because in order to measure the position of the object it would be necessary to illuminate it with photons of light, but to pinpoint its exact locality the photons of light would have to have enormous energy. However, if the object is being bombarded by high-energy photons its own velocity will be affected and becomes inherently uncertain. Hence, by demanding knowledge of an object’s position, physicists
would have to give up some knowledge of its velocity.
Heisenberg’s uncertainty principle only reveals itself at atomic scales, when high-precision measurements become critical. Therefore much of physics could carry on regardless while quantum physicists concerned themselves with profound questions about the limits of knowledge. The same was happening in the world of mathematics. While the logicians concerned themselves with a highly esoteric debate about undecidability, the rest of the mathematical community carried on regardless. Although Gödel had proved that there were some statements which could not be proven, there were plenty of statements which could be proven and his discovery did not invalidate anything proven in the past. Furthermore, many mathematicians believed that Gödel’s undecidable statements would only be found in the most obscure and extreme regions of mathematics and might therefore never be encountered. After all Gödel had only said that these statements existed; he could not actually point to one. Then in 1963 Gödel’s theoretical nightmare became a full-blooded reality.
Paul Cohen, a twenty-nine-year-old mathematician at Stanford University, developed a technique for testing whether or not a particular question is undecidable. The technique only works in a few very special cases, but he was nevertheless the first person to discover specific questions which were indeed undecidable. Having made his discovery Cohen immediately flew to Princeton, proof in hand, to have it verified by Gödel himself. Gödel, who by now was entering a paranoid phase of his life, opened the door slightly, snatched the papers and slammed the door shut. Two days later Cohen received an invitation to tea at Gödel’s house, a sign that the master had given the proof his stamp of authority. What was particularly dramatic was that some of these undecidable questions were central to mathematics. Ironically Cohen proved that one of the questions which David Hilbert declared to be among the twenty-three most important problems in mathematics, the continuum hypothesis, was undecidable.
