The Black Hole in Mathematics

Abstract

Some theorems cannot be proven.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

The main activity of research mathematicians is to search for new and interesting theorems. Until 1930 mathematicians had always assumed that if a mathematical statement was true, there must be a proof for it. But in that year, the logician Kurt Gödel showed that there exist theorems that, while true, could never be proved. They exist in a kind of mathematical black hole from which nothing—no proof—can ever emerge.

Certain mathematical impossibilities are not of this type. For example, squaring the circle, finding a ruler-and-compass construction of a square that has the same area as a given circle, is now known to be impossible.

If a mathematician ever succeeded in squaring the circle, the following statement would soon appear in a leading journal:

Theorem: Pi is a constructable number.

The term constructable means that the number in question is the length of a line segment that can be constructed with ruler and compass. Unfortunately, no one has been able to square the circle. It was the German mathematician, Ferdinand Lindemann who, in 1882 proved a theorem that forever ruled out the possibility that pi is constructable:

Theorem: Pi is a transcendental number.

Another theorem tells us that no transcendental number is constructable. Transcendental numbers are not algebraic and therefore not constructable, either. Mathematicians tend to accept such limitations philosophically. After all, a theorem is a theorem, and once it has been proved, that’s it. But imagine a limitation on our ability to prove theorems. What if not all theorems are provable?

When mathematicians encounter a statement they think might be true, they call it a conjecture, then attempt to prove it. Or they may try to disprove it by finding a counterexample. If the conjecture says that every object with property A also has property B, they may hunt for an example of an object with property A that does not have property B.

Conjectures are both famous and infamous in mathematics. Our inability to prove them may seem insurmountable until some bright young wizard finds the proof that had eluded everyone else—or finds a counter-example. Conjectures inspire much research and so play a valuable role in the development of mathematics. But should one of the conjectures currently before mathematics happen to be true yet have no proof, then a truckload of young wizards would not suffice to prove it. Yet it would be true.

Perhaps an unprovable theorem would involve concepts far beyond our ability to understand. (Who knows?) Or perhaps an unprovable theorem would involve obscure, grotesque, or utterly unappealing content. (Who cares?) Or perhaps an unprovable theorem might be both easy to understand and involve an interesting proposition. Perhaps the conjecture made by the German mathematician Christian Goldbach in 1742 is both true and unprovable. That would be something!

Goldbach’s conjecture declares that every even number greater than 2 is the sum of two odd prime numbers. Going on 300 years, mathematicians have yet to prove the conjecture (which would automatically make it Goldbach’s theorem) or to find a counterexample. Yet the conjecture seems to be true. Give me an even number such as 142 and it will not take me long to find two primes that have 142 as their sum. Let’s see. How about 59 and 83?

What we used to call “Fermat’s Last Theorem” was, until recently, actually unproven. But in 1998, a young Cambridge mathematician named Andrew Wiles proved what we may now call a “theorem:” An equation of the form,

$$ {\text{x}}^{\text{n}} + {\text{y}}^{\text{n}} = {\text{z}}^{\text{n}} $$

has no solution for any value of n > 2.

Will Goldbach’s conjecture go the way of Fermat’s? Or does it lurk somewhere in a mathematical black hole? Do true but unprovable theorems exist? If such a thing could be proved, it would be a theorem, to be sure, and a metatheorem, at that. Such a theorem would have seemed incredible to the Greeks, as well as to the Indian and Arab mathematicians who followed them, no less to the Europeans up to the end of the nineteenth century. Yet this is exactly what the twentieth-century mathematician Kurt Gödel proved in 1930.

There is a back door to Gödel’s theorem: either there exist unprovable theorems or the standard arithmetic is inconsistent. Gödel’s theorem is about the “standard arithmetic,” a term I will explain later, but which is merely a formalized portion of the mathematics we all learned in elementary school. In short, either there are theorems that our mathematics is simply not capable of dealing with, or our mathematics is itself inconsistent.

From the Greeks to the Europeans, to all the world’s mathematicians in the year 1900, nothing would have been more disturbing than the idea of an unprovable theorem—unless it was an inconsistency within mathematics itself. The story of this amazing result begins in the year 1900. The setting is Paris, the Second International Congress of Mathematicians. It was an ideal time for one of the world’s leading researchers to set the agenda for a new century. The German mathematician David Hilbert challenged his worldwide audience with twenty-three problems. The first two of these would have a profound influence on Kurt Gödel, whose birth lay six years in the future.

1 The Ghosts of Infinity

The first problem was to prove the continuum hypothesis, formulated some sixteen years earlier by another German mathematician, Georg Cantor. As a result of his groundbreaking conceptual invasion of infinity during the years 1871 to 1884, Cantor had formulated a new system of infinite numbers with a strange arithmetic all their own. The first of these was written $\aleph_{0}$ and called aleph nought. It was the cardinality (infinite, to be sure) of the natural numbers, or counting integers. If the members of any infinite set could be paired off with the numbers 1, 2, 3, … and so on forever, that set has $\aleph_{0}$ members. The second number, $\aleph_{1}$ (aleph one), stood for the cardinality of the set of real numbers. If the members of an infinite set could be paired off with the real numbers, that set would have $\aleph_{1}$ members.

The continuum hypothesis, as formulated by Cantor, stated that every subset of the real numbers either had cardinality $\aleph_{1}$ or had cardinality $\aleph_{0}$. There was nothing in between the two numbers. Every attempt to construct a set of real numbers that was not in one-to-one correspondence with either the integers or with the real numbers met with failure.

Thus was born the new field of transfinite arithmetic, with its first two numbers, $\aleph_{0}$ and $\aleph_{1}$. However, it was not until 1891 that Cantor was able to prove that the transfinite numbers $\aleph_{0}$ and $\aleph_{1}$ were different! To understand Cantor’s proof of this result we need one or two mental tools.

The power set of a set is simply the set of all subsets of the set. For example, the power set of the finite set A = {1, 2, 3} consists of eight sets, namely {1, 2, 3} itself, as well as {1, 2}, {1, 3}, {2, 3}, {1}, {2}, {3}, and the empty set. We can write the power set of A as 2^A.

The new system of transfinite arithmetic was justified, in part, by Cantor’s 1891 theorem, a humble but profound result: Specifically, he showed that no pairing or one-to-one correspondence could exist between the real numbers and the integers themselves. His method of proof involved a type of argument that was new to the mathematics of the day but that later would play a key role in Gödel’s theorem. His argument used diagonalization, a process that singled out the main diagonal of entries in an infinite table. His proof is simple enough to be presented here.

Suppose that a one-to-one correspondence could be found between Z and its power set, 2^Z. It could then be written as a function f that, for every integer k, would produce a set f(k) of integers. As the variable k ran through the integers 1, 2, 3, and so on, the function f would run through the subsets of Z, all of them, sooner or later. Cantor then examined a very special set that consisted of all the integers z that were not members of their corresponding set f(z).

This was a peculiar thing to do. If we made a vast table with the integers down one side and the subsets of Z across the top, every entry of the table would consist of a pairing between an integer and a subset of Z. It would be natural, in such a table, to place the pairs z, f(z) down the main diagonal. That, at least, accounts for the name “diagonal argument.”

Some of the integers z will appear inside their corresponding subsets f(z) and some won’t. If we take the set of all integers z that are not members of f(z) and place them in a special set W, we can ask a very serious question about W: To what integer does W correspond under this scheme? If we write that integer as w, we can ask if w belongs to W. If w belonged to W, then w would not be a member of f(w) by the definition of W. But wait! This is a contradiction, since W = f(w). On the other hand, if w were not a member of W, then w must lie in f(w) (i.e., W), another contradiction.

What has gone wrong? We got into this mess by assuming that there was a function f with the stated property. The assumption must therefore be wrong. There is no one-to-one association between integers and all subsets of the integers. Hence there is no one-to-one correspondence between the integers and the real numbers. It immediately follows that $\aleph_{0}$ and $\aleph_{1}$ cannot have the same cardinality and that the distinction between them is real. The question that would immediately suggest itself did so to Cantor. Was there yet another transfinite number between $\aleph_{0}$ and $\aleph_{1}$? The “continuum hypothesis remains unresolved to this day.

In his 1900 address to the world mathematical community, Hilbert proposed that resolving the continuum hypothesis was problem one. He also wished to resolve a another question that had been simmering on back burners (and a few front ones) for a decade or more: Could arithmetic be axiomatized in such a way as to guarantee the exclusion of any and all inconsistencies?

2 Consistency

By the turn of the nineteenth century, mathematicians had become aware that deep questions attended the simplest-seeming subject: arithmetic. In particular, the attempt to axiomatize arithmetic had led, in some cases, to the recognition of logical anomalies.

For example, in 1888 the Italian mathematician Giuseppe Peano had introduced a set of five axioms that characterized the natural numbers (positive integers). They were nothing if not simple.

• 1. 1 is a natural number.

• 2. If a is a natural number, so is a + 1.

• 3. If a and b are natural numbers and a = b, then a + 1 = b + 1.

• 4. If a is a natural number, then a + 1 ≠ 1.

These statements will trouble few readers. From these axioms, with the aid of a fifth axiom that Peano would employ for the deductive process itself, all the properties of the natural numbers could be derived.

For example, from these axioms it was possible to prove the associative law that for all natural numbers a, b, and c, a + (b + c) = (a + b) + c

This law justifies something that people do all the time: It makes no difference in what order numbers are added. The fifth axiom would prove troublesome. By allowing a set to be arbitrary, it implicitly included a very nasty set that consisted of all sets whatsoever.

• 5. If A is a set and 1 lies in A, and if for every natural number a in A, a + 1 also lies in A, then all natural numbers lie in A.

Known as the principle of induction, this axiom was meant simply as a formal statement of a major tool for working with natural numbers. As long as mathematicians using the axiom of induction do not invoke the monstrous set of all sets, they are safe. This bizarre object seemed to spew out anomalies and downright contradictions. The “set of all sets” sounds almost like a spiritual entity.

In 1893, the German logician Gottlieb Frege published the first volume of his Grundgesetze der Arithmetik, a rigorous formulation of arithmetic that appealed to the same concept, the set of all sets. The English logician Bertrand Russell was at first unaware of the anomaly and championed the work of Frege, whose unnecessarily difficult book had attracted few readers. But as Frege’s second volume was about to appear, Russell discovered to his horror that a severe logical flaw underlay the entire work.

The set of all sets contains some nasty items. My vain attempt to render the situation graphically appears here.

It is surely no more difficult to conceive of sets that are not members of themselves than it is to conceive of sets that are. I will use my favorite nonsense word for such sets: “gzernmplatz.” I will go farther and define G to be the set of all gzernmplatz sets. Now I come, as Russell did, to the key question: Is G gzernmplatz? Even an amateur logician could work a proof, perhaps something like this: suppose G is gzernmplatz. Then G must lie within the set of all gzernmplatz sets, namely G. Thus G is a member of itself. Whoops! I guess G can’t be gzernmplatz after all. It follows that G is not in the set G and, therefore, not a member of itself. So G must be gzernmplatz. Whoops again! Has mathematics suddenly become inconsistent under my feet? Does a black hole await me?

The impact on Frege’s second volume was devastating, and the Grundgesetze was nearly forgotten. There was a growing awareness of difficulties in axiom systems, in the tendency for paradoxes to leap out from the shadows of the subject. It also had been extremely difficult to prove even the simplest of fields, such as arithmetic, consistent. No one knew if serious contradictions might someday appear in our reasoning about numbers.

The dream of a purely logical formulation of mathematics itself, became the passion not only of Hilbert but also of Bertrand Russell and his English colleague Alfred North Whitehead. In 1910 Russell and Whitehead published the first volume of Principia Mathematica, a strict formulation of mathematics in terms of a purely logical system that involved both propositions and predicates.

In the Principia Russell and Whitehead clearly demonstrated that not only could mathematics—or significant portions of it—be reduced to logic, but also that all mathematical truths were ultimately logical truths. Here was the vehicle that mathematicians could ride in search of consistency. Simply demonstrate that the axioms of the Principia could never lead to an inconsistency or contradiction.

In 1923, Hilbert rode forth to the lists with a new program of action that he called Beweisstheorie, or the theory of proofs. He published the proposal in a paper and followed up at many talks and conferences to promote the idea. But the current climate of logical uncertainly had rattled him. Speaking at a conference in June of that year, he declared paradoxes as “intolerable.”

In a nutshell, Hilbert proposed the reduction of mathematics to a symbolic script—marks on paper, as it were. A proof would amount to a sequence of formulas, each derivable by purely logical (and symbolic) operations from one or more of its predecessors, each leading inexorably to the final formula, a statement of the theorem being proved. Following in the footsteps of Russell and Whitehead, he cast his ideas in predicate logic. Hilbert’s system began with so-called atomic formulas, the simplest combinations of variables and constants, then proceeded to statements or well-formed formulas that were themselves composed of atomic formulas, logical connectives, and quantifiers of the type discussed above.

An example of a well-formed formula in mathematics would be

$$ \forall {\text{x}}\,\exists {\text{y}}\,{\text{s}}.\,{\text{t}}.\,({\text{x}}\, < \,{\text{y}})\,\& \,({\text{x}} + 1\, > \,{\text{y}}). $$

This rather compact notation may be interpreted as follows:

“For all x there exists a y such that x is less than y and x + 1 is greater than y.” The symbols ∀ and ∃ are the same quantifiers we discussed earlier. Their role is to specify for each variable under their jurisdiction, whether the formula is to be true for all values or at least one of them, respectively. The & symbol is an example of a logical connective, and the expressions “x < y” and “x + 1 > y” are examples of atomic formulas. The whole point of predicate logic was that it amounted to a language in which axiom systems and theorems for various areas of mathematics could be expressed. This language became the focus of interest in the newly emerging field that Hilbert called “metamathematics.” It would interest young Gödel profoundly.

3 The Troublemaker

Kurt Gödel was born in 1906, the second son of Rudolph and Marianne Gödel in Brno, a city in the Moravian part of Czechoslovakia. Although living in Czechoslovakia, the Gödels always considered themselves German. Rudolph Gödel was a successful businessman in the textile industry. In a privileged but highly structured household, young Kurt flourished academically. He graduated from High School in 1924 and was sent to study at the University of Vienna.

Gödel began in physics but found himself increasingly attracted to mathematics. While taking courses in physics, he would read the classic works of Euclid, Euler, and others. Gödel examined mathematics from a philosophical point of view, reading Kant and Russell as well. Indeed, his interest in mathematics was sparked even more strongly by attending a weekly seminar conducted by the philosopher Moritz Schlick. Sometime that year, Gödel met Hans Hahn, a prominent Viennese mathematician. Hahn had recently turned his attention to the foundations of mathematics. It may have been Hahn who suggested that Gödel attend another special weekly seminar, later to be called Der Wiener Kreis (the Vienna Circle). It was there that Gödel heard the crucial logical issues of the day discussed.

By 1927, Gödel was hopelessly involved in mathematical issues and questions. The Vienna Circle had brought him to the heart of difficult and important mathematical questions. He read and attended lectures. He walked the streets of Vienna alone or with colleagues. He sat for hours in various coffeehouses discussing mathematics. In 1928 Gödel had finished his undergraduate work and by 1929 was already hard at work on his Ph.D. thesis, an attempt to show that predicate logic was complete. In 1929 Hilbert and his colleague Willheim Ackermann had published their Grundzuge der Theoretischen Logik. In his thesis, Gödel succeeded in proving that the logical system suggested by Hilbert and Ackermann was complete. Gödel showed that every valid formula (true expression) was derivable within the system. He began by reducing the problem of proving completeness to showing that each formula within Hilbert’s system was either satisfiable or refutable. He established the latter result, in turn, by using induction.

It was an impressive performance from someone so young. But the result surprised no one. Everyone expected Hilbert’s system to be complete.

4 The Trouble

The “habilitation” denotes a second hurdle that had to be leaped by all aspiring academics in Continental universities. It was not enough to write and defend a thesis. If one expected employment at an institution of higher learning, one had to publish something of note after the thesis. For his habilitation paper Gödel chose to work on Hilbert’s second problem, that of showing the consistency of arithmetic. It would undoubtedly be more difficult than the proof that predicate logic was consistent and infinitely more difficult than the proof that propositional logic was consistent. That result had been achieved by Emil Post, a mathematician at New York’s City College in 1921. The propositional calculus is the simplest form of logic, essentially a subject first codified by Aristotle in the fourth century B.C. The “propositions” are merely symbols such as a, b, and c, which stand for fixed statements that contain no variables. Two propositions could be conjoined logically by either the “and” operator or the “or” operator.

In their classic Principia Mathematica, Russell and Whitehead gave axioms for the propositional calculus. Instead of the “and” connective, however, they used implication, symbolized by the double arrow, ⇒. The expression a ⇒ b, or “a implies b,” is understood at the outset to be logically equivalent to ~a v b.

• 1. (p v p) ⇒ p

• 2. p ⇒ (p v p)

• 3. (p v q) ⇒ (q v p)

• 4. (p ⇒ q) ⇒ [(p v r) ⇒ (q v r)]

Each axiom in this system seems either harebrained or mildly insane. Axiom 2, for example, says that if a proposition p is true, then either p is true or p is true. There is, in any event, very little to argue with in the axioms.

The consistency of propositional logic may be proved by supposing that it is possible to derive two contradictory statements, T and ~T, from the axioms. Suppose then that we have discovered a disastrous proposition T such that T and ~T are both true. We may use an additional tool of propositional logic, the principle of substitution, replacing a proposition symbol with T.

$$ {\text{T}}\, \Rightarrow \,( \sim {\text{T}}\, \Rightarrow \,{\text{q}}). $$

Since T is true, we may use the rule of detachment to establish that ~T ⇒ q is also true. But ~T is also true, and we may use the rule of detachment to show that q is also true. But q can be any proposition whatever. The assumption of a contradictory pair of propositions had therefore led to the conclusion that all propositions are true, including the negations of the axioms themselves. It follows from this contradiction that no such pair of contradictory statements or propositions can be derived within propositional logic, and the foundations are secured. It is consistent.

This example also serves to illustrate an important distinction between two kinds of reasoning. You will notice that our treatment of propositional logic involved proofs inside the system and proofs outside the system. The derivation of the theorem p ⇒ (~p v q), like all theorems of propositional calculus, was proved within the system by applying the rules of substitution and detachment, but the proof of consistency was proved outside the system. Our reasoning was no less formal, but there was no way to express it as a sequence of propositions, each derived logically from previous propositions in the sequence. In short, there was no way to express the assumption about T. The distinction is fundamental to metamathematics. We will see it made again when we consider Gödel’s amazing theorem.

It is still a long way from showing the consistency of propositional logic to that of predicate logic when applied to arithmetic. For one thing, propositional logic is silent on the subject of arithmetic. Numbers cannot be expressed within it. Gödel began by trying to prove that arithmetic, as expressed in the logical framework of the Principia, was consistent. In seeking to express the consistency of arithmetic, however, he discovered that he could express this consistency within arithmetic itself. Not only that, but this very expression led directly to a theorem that could not be derived within the logical system of Russell and Whitehead. After setting up the axioms of a predicate logic that embodied what is called the standard arithmetic, Gödel drew up a list of all the symbols used and assigned a special code number to each symbol, as shown in the following table:

Symbol	Code number	Symbol	Code number
0	1	x	9
s	2	l	10
+	3	⌉	11
X	4	&	12
=	5	∃	13
(	6	∀	14
)	7	→	15
.	8

The symbol that resembles the letter L rotated on its head stands for implication in the predicate calculus. Thus A ˥ B means simply that A implies B or that B can be deduced from A. The symbol s is the successor function. When applied to a natural number, it yields the next number in sequence. Because each formula would have to be expressed by a single, unique number, Gödel would need a way of boiling all the numbers that represented a given formula down into one number that would encode not only all the number symbols of the formula simultaneously, but also their order.

Gödel achieved this trick by using consecutive prime numbers such as

$$ 2,\, 3,\, 5,\, 7,\, 1 1,\, 1 3,\, 1 7,\, 1 9,\, 2 3,\, 2 9,\, 3 1,\,.\,.\,.\, $$

each raised to a certain power. The power used would depend on the position of the symbol in the formula. If a symbol x appeared as the seventh symbol in a formula, for example, it would be represented by a 9 (the symbol for x) raised to the 17th power (the 7th prime in the sequence).

Thus if Gödel wanted to translate the formula (axiom) into a single number, he would first replace every symbol by its numerical code:

$$ 9,\, 10,\, 3,\, 2,\, 9,\, 10,\, 10,\, 5,\, 2,\, 6,\, 9,\, 10,\, 3,\, 9,\, 10,\, 10,\, 7. $$

In this case he would obtain the seventeen integers listed above. Next he would raise the first seventeen prime numbers to these powers and multiply them all together, the raised decimal points representing ordinary multiplication.

$$ 2^{9} .3^{10} .5^{3} .7^{2} .11^{9} .13^{10} .17^{10} .19^{5} .23^{2} .29^{6} .31^{9} .37^{10} .41^{3} .43^{9} .47^{10} .53^{10} .59^{7} $$

The resulting number is huge but finite. The encoding procedure could be specified as a finite process that would, given enough time, serve to express any formula whatever by an integer, no matter how large. It was recognized by the early metamathematicians that in explorations of the infinite, the best way to stay out of trouble was to use only finite tools. A proof in Gödel’s system could, be encoded by a single integer (called its Gödel number). Conversely, given any positive integer whatever, there was a finite procedure for producing either a corresponding formula or sequence of formulas, complete nonsense, or nothing at all, depending on what symbols were encoded (or not) and in what order. Thanks to an important theorem within arithmetic itself, any positive integer can be written as the unique product of primes, which would represent the given number uniquely. The powers of the primes could then be translated directly into the corresponding symbols—unless they happened to be larger than 15. The fact that an arbitrary integer might not represent a formula was not a problem. But when it did, Gödel knew that no other integer could represent that formula. Gödel had developed a language that linked two seemingly different universes, the universe of formulas and the universe of Gödel numbers, a system of huge integers that each represented one of these expressions. The very process of thought, as embodied in the formulas, had been reduced to a cloud of numbers.

Among the formulas that Gödel showed how to construct were ones that would be typical of theorems and proofs. He had shown how formulas could express the process of checking that a proof really was a proof.

The Gödel numbers were all, of course, natural numbers, and as such formed part of the standard arithmetic. This meant that he could construct statements about the Gödel numbers, just as he could for ordinary integers. Within the standard arithmetic he could frame predicates that took the Gödel numbers as their subject matter. Of special interest is a rather complex predicate that I will write in a simple symbolic form:

Proof (x, y, z)

I have used the traditional variable names instead of x₁, x₁₁, and x₁₁₁ to make the path into Gödel’s mind a little easier to follow. The interpretation of the predicate called “proof” depends on knowing that X is a sequence of formulas that allegedly prove something, while x is the Gödel number of the proof X. Another formula, Y, has only one variable, and y is its Gödel number. With these elements in mind, the predicate can be described as saying, x is the Gödel number for the proof X of a one-variable formula Y with Gödel number y and with the integer z substituted into it.

In other words, Gödel number aside, X is a proof of Y, with z substituted into it. If the formula Y is true for this value of z, and if the system is complete in that every theorem can be proved in it, the proof X will exist, x being its Gödel number. In this case, of course, the formula Y will be the last formula in the string represented by X. Under these conditions the predicate called “Proof” will be true.

The expression “Proof(x, y, z)” does not belong to the system under study, but to the metalanguage in which truths about the system are expressed. Yet this shorthand, “Proof(x, y, z),” refers to a series of formulas that express what it means for X to be a proof of Y with z substituted into it, an encoding, if you like, of the mental machinery required to check such a proof. For example, the actual expression would have predicates that checked that each formula in the proof sequence was derivable from ones earlier in the same sequence. To spell out the proof-checking procedure, as long as it amounted to a finite process, was tantamount to an actual check. All that machinery within the logical system, along with the proof X of the formula Y, amounted to an extremely long, but finite, string of formulas. Consequently that string would itself be a formula and would have its own Gödel number.

The next and most important step that Gödel took was to realize that the formula Y referred to in the predicate Proof (x, y, z) could have its own Gödel number, y, substituted into it, instead of the more general variable Z- In other words, Gödel’s attention now focused on the predicate

Proof(x, y, y)

In this form the predicate is true if x is the Gödel number of a proof that the formula Y is true when its own Gödel number y is substituted into it. In other words, the predicate automatically symbolizes all formulas Y within the system that happen to have a proof X when y (the Gödel number of Y) is substituted into Y. This seems an odd thing to consider.

At this juncture, Gödel’s breath may have caught as he sensed himself on a collision course with common sense—or about to enter a black hole. What he did next was to form a new predicate that denied the existence of such a proof:

~∃x Proof(x, y, y)

This expression formed an element of the metalanguage that Gödel used to reason about the logical system under examination, the one that contained the standard arithmetic of integers. Yet by merely appending the same logical symbols to the extremely lengthy expression inside the logical system, the one represented by “Proof(x, y, y)” he now had a first-class anomaly on his hands.

The new expression denied the existence of a proof X that the formula Y would be true with its own Gödel number substituted into it. Yet this new predicate, considered as a lengthy expression within the system, would have yet another Gödel number all its own—say, g.

What, asked Gödel, is the status of the predicate ~∃x Proof(x, g, g)? This expression asserts that there exists no proof of the predicate symbolized by g, namely the predicate ~∃x Proof(x, y, y). If ~∃x Proof(x, g, g) were true, then no proof could exist. If ~∃x Proof(x, g, g) were false then the expression

∃x Proof(x, g, g)

would be true and a proof would exist. But a proof of what? It would be a proof of ~∃x Proof(x, y, y), because that’s what g stood for. But a proof of this predicate would hold for all possible values of y including g, leading Gödel to the inevitable conclusion that ~∃x Proof(x, g, g) was indeed true.

Here was the crunch. If the predicate ∃x Proof(x, g, g) were both true and false, then his logical system—and therefore the standard arithmetic—was inconsistent. The only way out was to assume that the statement symbolized by g was true. And that statement had no proof. At the time of his discovery of the famous incompleteness theorem, Gödel was twenty-six. Perhaps because he was not then an established mathematician, news of the result did not exactly spread like wildfire. At the same time, the colleagues and contacts to whom Gödel communicated his result most frequently expressed confusion rather than admiration. And yes, resistance grew—to a point.

5 The Aftermath

In August 1930, Gödel met his colleague Rudolph Carnap to plan a trip to a conference in Konigsberg (today Kaliningrad) in one month’s time. Quietly announcing his result, Gödel was surprised to discover that Carnap did not quite follow the argument. But he was confident that the mathematical world would soon catch up with him. The conference in Konigsberg was attended by no less than John von Neumann, a world-renowned mathematician who had published in a great variety of areas and who took a particular interest in the new metamathematics, having wrestled with the consistency problem himself. After the talk, von Neumann congratulated Gödel and inquired further into the stunning new result. Once he fully understood it, von Neumann suffered a slight fit of pique. Yet his admiration was genuine, and the desire to promote Gödel’s new result was sincere.

Hilbert, who also attended the conference, apparently had no idea of what was going on. “For the mathematician there is no ignoramibus, and, in my opinion, not at all for natural science, either - - - The true reason why [no one] has succeeded in finding an unsolvable problem is, in my opinion, that there is no unsolvable problem. In contrast to the foolish ignoramibus, our credo avers: We must know. We shall know.”

Hilbert apparently was quite upset about the new theorem and probably somewhat depressed as well. After all, his credo that “we must know” had just been shattered by the knowledge that unless mathematics was inconsistent, there would be some things that we would never know, namely, which conjectures might turn out to be unprovable.

In March of 1931 a formal paper by Gödel appeared in the Monatshejte fur Mathematik und Physik titled “Uber Formal Unentscheldbare Satze Principia Mathematica und Verwandter System I” (On Certain Difficulties of Proof in the Principia Mathematica and Related Systems). The new paper slowly made its way into the collective consciousness of the mathematical world. The following September Gödel attended a meeting of the German Mathematical Union in Bad Elster. By now news of the result had made the rounds, and Gödel met his first real opposition in the person of Ernst Zarmelo, the mathematician who had first axiomatized set theory, a subject intimately related to logic. When colleagues proposed getting Zarmelo to lunch with Gödel, Zarmelo at first refused on a suspiciously wide variety of grounds: he didn’t like Gödel’s looks; he couldn’t walk that far; if he attended the lunch, there wouldn’t be enough food to go around. His subsequent hour with Gödel seemed outwardly pleasant, but Zarmelo held such different views of logic that he did not fully grasp the import of the iincompleteness theorem.

Other notables also found the result difficult to understand, including the mathematical philosopher Ludwig Wittgenstein and even Bertrand Russell, who expressed gratitude that he no longer worked in mathematical logic. By the mid-1930s there was barely a mathematician alive who did not know of Gödel’s theorem and its philosophical implications for mathematics. Most preferred to ignore the other horn of the dilemma in Gödel’s theorem, that mathematics was privately plagued by monsters of inconsistency.

Even assuming that mathematics was consistent, it would never be quite the same. The mere possibility of unprovable theorems has added a third potential outcome (or non-outcome) in the pursuit of conjectures. Someone will find a proof, someone will find a counterexample, or no one will find anything, thanks to the black hole.