Gödel’s incompleteness theorem: the man who ruined mathematics

Kurt Gödel, the man who ruined mathematics, was one of the most important thinkers of the 20th century. He was born in 1906 in the midst of the biggest crisis mathematics has ever faced. Just a few decades later, he would help resolve this dilemma, but in doing so would force mathematicians into an even smaller world than 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 we have to a cognitive perpetual-motion machine – there’s always a new mathematical idea lurking on the horizon, and we just need to take the steps to get there. Or it may seem so. But in reality, there is a dark fundamental truth at the core of mathematics that places limits on our intellectual exploration. This is called Godel’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 3000 years had been built on quicksand. Unexplained contradictions began to emerge and mathematicians panicked.

As the century turned, one man decided to fight the anarchy. Mathematician David Hilbert taking the stage at the Paris Conference in 1900 Presented a list of 23 unsolved problems of mathematicsLaying the foundation for a research program that would be useful to most mathematicians of the 20th century. “As long as a branch of science presents a lot of problems, it is still alive,” he told the gathered crowd.

Hilbert’s second problem was the task of capturing Gödel later. It deals with the principles of a given mathematical field, essentially notions that serve as the rules of the game and allow you to make logical derivations from them. Hilbert’s challenge to his fellow mathematicians was to prove that the principles of arithmetic, in particular, “are not contradictory, that is, that a finite number of logical steps based on them can never give contradictory results.”

This is a very desirable thing to prove. Imagine playing a board game where one interpretation of the rules wins you points, while another, equally valid, interpretation of the same rules can cause you to lose points. Such a game, well, would be meaningless.

Over the next few decades, Hilbert and close collaborators attempted to solve his second problem, known as proof theoryor “proof theory”, a way of converting proofs into mathematical objects. Whereas a proof is typically a collection of natural language words and mathematical symbols, this turn to more abstract mathematical concepts allowed Hilbert and his colleagues to study the proofs themselves with the tools of mathematics – like a recipe book that contains recipes. In In 1928 he gave a lecture titled Die Grundlagen der Mathematik (“Foundations of Mathematics”), explaining that this new method would allow him to “definitely solve fundamental questions in mathematics by converting every mathematical statement into a concretely demonstrable and rigorously derived formula”, although he acknowledged that “much work would still be necessary”.

By this time, Gödel was a 22-year-old PhD student at the University of Vienna, Austria. He was working under the supervision of mathematicians following Hilbert’s program, although we have no historical evidence showing that the two men ever met or corresponded directly. A year later, as part of his PhD thesis, Gödel published his completeness theorem – a good step towards Hilbert’s goals.

Completeness theorems relate to models of sets of axioms, these models contain mathematical understanding that connects collections of symbols such as “2”, “+” or “=” to the actual mathematical objects they describe. This is quite abstract, so it’s worth considering a small example. Imagine that our principles are “two things are” and “things are different”. These aren’t very powerful theories – you can’t prove much with just these two – but they are perfectly valid. We can apply many different models to these principles, such as the sides of the coin (heads or tails), your hand (left or right) or even just numbers (0 and 1). Although these models appear different, they describe the same mathematical object – a collection of two different things.

The important thing is that you can apply many different models to the same set of axioms, and what Gödel proved is that any statement that is true in all possible models of a set of axioms must therefore be provable by those axioms. This may seem a bit circular, as it often happens when we delve into the depths of mathematical definitions, but it was promising for Hilbert’s attempt to strengthen the foundations of mathematics.

Not that Hilbert noticed, mind you. Gödel presented his completeness theorem at the conference in Königsberg on 6 September 1930 (today known as Kaliningrad in Russia). Hilbert was at a different conference in Königsberg Gave a grand speech on 8th SeptemberIn which he famously rejected the idea that there are limits to human knowledge. “We must know. We will know,” he said – words that were eventually engraved on his tombstone.

Mathematicians have only one problem with Hilbert’s rally – Gödel had destroyed all hope for it the day before. Not on September 6, when he presented his completeness theorem, but on September 7. During a discussion with fellow logicians that day, Gödel let it be known that he had identified the possibility of “undecidable” statements – those that cannot be proven true with a fixed set of axioms, but also cannot be proven false significantly. This was the genesis of an idea that forever limited the horizons of mathematics.

It is fascinating to see Gödel laughing quietly to himself in the audience during Hilbert’s talk, although we have no evidence that this ever happened – both conferences were in different parts of the city. What we do know is that Gödel published his incompleteness theorem – a dark mirror of his PhD thesis – a few months later in January 1931.

This theorem makes two important claims, which should be examined separately. The first is exactly what Gödel brought up in the September 7 discussion – that whatever your theories, there will always be problems within those theories that are undecidable. These are somewhat like the mathematical version of the paradoxical phrase “this sentence is false”, a statement that itself is neither true nor false. Mathematicians now call this discovery about undecidable problems Godel’s First Incompleteness Theorem, and it’s still relevant almost a century later – here’s a fun story I wrote about a computer program with the theoretical ability to break mathematics, all because of undecidable problems.

The First Incompleteness Theorem is a major rewriting of our understanding of what mathematics can do, but it was what we now call Gödel’s Second Incompleteness Theorem that really got Hilbert into trouble. This is because Gödel showed that any sufficiently powerful axiom set (essentially, the ones that mathematicians care about) can never be used to prove that the same axioms will not yield incompatibilities.

To go back to the board game analogy, you can read the rules all you want, but you can never be assured that they won’t lead to contradictory results. Assurances against contradiction are exactly what Hilbert was looking for in the principles of arithmetic – and Gödel showed that in fact this problem is undecidable. There is a get-out clause: if you move to another set of axioms, you can potentially prove the consistency of your previous axioms. But this doesn’t solve the problem, because your new theory will now have other inconsistencies. Instead of pursuing infinite mathematical horizons, mathematicians should be content with the unknown.

So how did Hilbert react to this shocking news? Incredibly, he didn’t do so, at least not publicly. according to Godel’s biographersJohn 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 “infuriated Hilbert”, but the only time Hilbert put pen to paper in response to Gödel did not come until 1934. “This view, which arose temporarily and which said that some recent results of Gödel showed that my proof theory could not be applied, has been proven wrong,” Hilbert wrote in a book co-authored with Bernays.

In other words, poor Gödel never got a proper response from Hilbert after essentially destroying Hilbert’s view of mathematics as an infinite engine of knowledge. Perhaps Hilbert could not bring himself to accept this. In the end Gödel wins – incompleteness is accepted as part of mathematical theory, with the result that the limits of mathematics make us both richer and poorer for it. Still, I can’t help but wonder whether Gödel felt unfulfilled by being rejected by Hilbert.