Gödel’s Incompleteness Theorem: The Man Who Ruined Mathematics

Kurt Gödel, the man who destroyed mathematics, was one of the most important thinkers of the 20th century. He was born in 1906, at the time of the greatest crisis that mathematics has ever known. Only a few decades later he would help to resolve this confusion, but in doing so he condemned mathematicians to a smaller world than the one before.

Mathematics as an intellectual framework is incredibly powerful. The whole point is to take one set of logical ideas and use them to build another, making mathematics the closest thing we have to a cognitive perpetual-motion machine—there’s always a new mathematical idea lurking over the horizon, and we just need to assemble the steps to get there. Now I know it can seem like it. But in fact there is a dark underlying truth at the heart of mathematics that limits our intellectual inquiry. This is called Gödel’s Incompleteness Theorem.

The story of this theorem begins in the late 19th century, when mathematicians began to unravel the foundations of their subject and quickly discovered that the intellectual edifice of the past 3,000 years or so had been built on shifting sands. Unruly paradoxes began to emerge and mathematicians panicked.

As the century turned, one man decided to fight the chaos. Mathematician David Hilbert spoke at the Paris Conference in 1900 presented a list of 23 unsolved problems in mathematicswhich laid the foundations for a research program that would occupy mathematicians for much of the 20th century. “As long as a field of science offers a multitude of problems, so long is it alive,” he told the assembled crowd.

The task later to occupy Gödel was Hilbert’s second problem. It refers to the axioms of a given mathematical arena, basically the assumptions that serve as the rules of the game and allow logical deductions from them. Hilbert’s challenge to his fellow mathematicians was to prove that specifically the axioms of arithmetic “are not contradictory, that is, a finite number of logical steps based on them can never lead to contradictory results”.

This is very desirable to try. Imagine playing a board game where one interpretation of the rules wins you points while another equally valid interpretation of the same rules can lose points. Such a game would be pointless.

Over the next several decades, Hilbert and close colleagues attempted to eliminate his second problem and developed what was known as Beweisteorieor “proof theory”, a way of turning proofs into mathematical objects. While a proof is usually a collection of words and mathematical symbols in natural language, this transformation into more abstract mathematical concepts allowed Hilbert and his collaborators to study the proofs themselves using mathematical tools—a bit like a recipe book that contains a recipe for making recipes. IN In 1928 he gave a lecture entitled Die Grundlagen Der Mathematik (“Fundamentals of Mathematics”), explaining that this new method would allow him to “definitely solve fundamental questions in mathematics by converting every mathematical proposition into a concretely provable and precisely deducible formula”, although he admitted that “much work will still be required”.

At this point, Gödel was a 22-year-old doctoral student at the University of Vienna in Austria. He worked under the supervision of mathematicians who followed Hilbert’s program, although we have no historical evidence that the two men ever met or corresponded directly. A year later, as part of his doctoral thesis, Gödel published his completeness theorem—a good step toward Hilbert’s goals.

The completeness theorem refers to models of axiom sets, these models being mathematical understandings that relate a collection of symbols like “2”, “+” or “=” to the actual mathematical objects they describe. This is pretty abstract, so it’s worth going through a little example. Imagine that our axioms are “there are two things” and “things are different”. They’re not very strong axioms—you can’t do much with just those two—but they’re perfectly valid. We can use many different models for these axioms, such as the sides of a coin (heads or tails), your hands (left or right), or even just numbers (0 and 1). Although these models appear to be different, they describe the same mathematical object – a set of two distinct things.

Importantly, you can apply many different models to the same set of axioms, and Gödel proved that any proposition that is true in all possible models of the set of axioms must therefore be provable from those axioms. This may sound slightly circular, as it often does when we delve into the guts of mathematical definitions, but it was promising for Hilbert’s efforts to solidify the foundations of mathematics.

Not that Hilbert noticed. Gödel presented his completeness theorem on September 6, 1930 at a conference in Königsberg (today known as Kaliningrad in Russia). Hilbert was at another conference in Königsberg and delivered a magnificent speech on September 8in which he famously rejected the idea that human knowledge has its limits. “We have to know. We will know,” he said — words that were eventually engraved on his tombstone.

There is only one problem with Hilbert’s shout at a gathering of mathematicians – Gödel had already destroyed all hope for him the day before. Not on September 6th, when he gave his completeness theorem, but on September 7th. During a discussion with fellow logicians that day, Gödel let it slip that he had identified the possibility of “undecidable” propositions—propositions that cannot be proven true with respect to a certain set of axioms, but in principle cannot be proven false either. This was the genesis of an idea that would forever limit the horizons of mathematics.

It’s tempting to imagine Gödel in the audience of Hilbert’s talk chuckling quietly to himself, although we have no evidence that this ever happened—the two conferences were held in different parts of the city. What we do know is that Gödel published his incompleteness theorem a few months later in January 1931 – a dark mirror of his dissertation.

This sentence makes two important claims that are worth examining separately. The first is exactly what Gödel came up with in the September 7th discussion—that whatever your axioms are, there will always be problems that are undecidable within those axioms. They are a bit like the mathematical version of the paradoxical phrase “this sentence is false”, a statement that is made neither true nor false. Mathematicians now call this finding about undecidable problems Gödel’s first incompleteness theorem, and it’s still relevant nearly a century later—here’s a fun story I wrote about computer programs with the theoretical potential to break math, all because of undecidable problems.

The first incompleteness theorem is a fundamental rewrite of our understanding of what mathematics can do, but it was what we now call Gödel’s second incompleteness theorem that really threw Hilbert on the ropes. This is because Gödel showed that any sufficiently effective set of axioms (basically the ones mathematicians are interested in) can never be used to prove that the same axioms do not introduce inconsistencies.

To return to the board game analogy, you can read the rules however you want, but you can never be sure they won’t produce conflicting results. Assurance against contradiction is exactly what Hilbert sought for the axioms of arithmetic—and Gödel showed that precisely this problem is undecidable. There is an exit clause: if you switch to a different set of axioms, you can potentially prove the consistency of your previous axioms. But that doesn’t solve the problem because there will now be more inconsistencies in your new axioms. Instead of chasing endless mathematical horizons, mathematicians must settle for the unknowable.

So how did Hilbert react to this stunning news? Incredibly not, at least not publicly. According to Gödel’s biographerJohn Dawson, we know that Gödel sent a draft of his paper to Hilbert’s assistant and close collaborator Paul Bernays, who acknowledged receipt, and later sent copies of the final published paper.

Dawson says that Gödel’s results “provoked Hilbert’s wrath”, but the only time Hilbert put pen to paper in response to Gödel came in 1934. “The view that had temporarily arisen, which claimed that some of Gödel’s recent results showed that my theory of evidence could not be carried out, proved to be wrong,” Hilbert wrote in a book he co-wrote with Bernays.

In other words, poor Gödel never got a proper answer from Hilbert after he essentially destroyed his vision of mathematics as an infinite engine of knowledge. Perhaps Hilbert just couldn’t bring himself to accept it. Gödel won in the end – incompleteness is accepted as part of the mathematical canon, the resulting limits of mathematics make us both richer and poorer for it. Still, I can’t help but wonder if Hilbert’s rejection made Gödel himself feel incomplete.

topics: