Can every mathematical truth be proven?

For centuries, mathematicians believed the answer to that question to be ‘yes’.

However, in the early 20th century, there were a number of mathematical paradoxes and problems that threatened the foundations of mathematics. 

For example, in 1901, Bertrand Russell identified Russell’s Paradox in set theory, which focused on “the set of all sets that do not contain themselves.” If this set contains itself, it cannot; but if it does not, it must. This is clearly a contradiction.

Hilbert’s Dream of Perfect Mathematics

In the 1920s, David Hilbert, one of the most famous mathematicians at the time, proposed what became known as ‘Hilbert’s Program’. He wanted to formalise all of mathematics under one system with no paradoxes or inconsistencies. He believed that mathematics was fundamentally complete, consistent and decidable. 

A system is complete if every true statement in it can be proven, consistent if it has no contradictions, and decidable if there is a method to determine whether any statement is true or false.

In other words, Hilbert believed that every true statement in mathematics can be proven, and every false statement disproven, and no statement can be simultaneously proven both true and false.

Hilbert was convinced that every problem in mathematics had a solution. In his 1930 address to the Society of German Scientists and Physicians in Königsberg, he proclaimed, in opposition to the statement ‘Ignoramus et ignorabimus’ (we do not know, we will not know), ‘Wir müssen wissen. Wir werden wissen’, meaning ‘We must know. We will know.’ In fact, he believed this so strongly that these words appear on his gravestone.

Gödel’s Challenge

Austrian mathematician Kurt Gödel was unconvinced.

In 1931, Gödel published his groundbreaking paper ‘On Formally Undecidable Propositions of Principia Mathematica and Related Systems I’. In this paper, he effectively shattered Hilbert’s dream of a perfect mathematics with his two incompleteness theorems.

Firstly, Gödel argued that no sufficiently powerful axiomatic system of mathematics could be both complete and consistent simultaneously.

He did this by constructing a mathematical statement similar to that of the liar paradox. The liar paradox states: “This sentence is false”. If the sentence is true, then the sentence is false, and if the sentence is false, then it must be true. So the statement cannot be either true or false.

How can a statement about language be translated into mathematics? How can we get mathematics to ‘talk’ about itself?

Arithmetization of Syntax

He did this by encoding statements into numbers. He assigned each symbol in the system, such as ‘=‘, ‘+’, and ‘-‘, a unique code, called its Gödel number. The number ‘0’ is given the Gödel number 1, and to encode other numbers, he used the function s(), meaning ‘increase by 1’, which has the Gödel number 3.

Then, he combined these Gödel numbers together to make formulas, like ‘1+1=2’. To encode n integers, he would raise the first n primes to the values of each integer. For example, to encode (4, 7) we might map this to 2⁴ × 4⁷. The result of this would be the Gödel number of the entire formula.

The Gödel number of each formula would be unique, as shown by the fundamental theorem of arithmetic, which says that every number has a unique prime factorization. Therefore, it is always possible to find the original formula or statement from its Gödel number.

Proofs, then, are made up of sequences of formulas, so he could repeat this method to assign Gödel numbers to proofs of statements about the natural numbers. Crucially, this allowed language to be represented using numbers.

Creating the Paradox

The next step then was to force the proof to talk about itself.

Assuming for contradiction that the system is complete, every statement must be able to be represented in it. So, Gödel constructed a particular statement: “The statement with Gödel number x is not provable.” Let’s say this statement has Gödel number G. Then you could substitute this Gödel number back into the statement, so that the statement with Gödel number G says: “The statement with Gödel number G is not provable.”

You’ll notice that this looks a lot like the liar paradox we mentioned earlier. If the system proves G, then G is false, so it proves a false statement, making it inconsistent. If the system doesn’t prove G, then G is true, but not provable.

This means that for every consistent system that can express sufficient arithmetic, there are statements that are true but unprovable. In other words, any sufficiently powerful reasoning system cannot completely understand itself. Not all mathematical truths can be proven. There are limits on how much we can know about the mathematical realm.

It should be noted that not all mathematical systems are incomplete. An example is Presburger arithmetic, which is both complete and decidable. However, it is a weak system with only addition and no multiplication, so it doesn’t fit the criteria of Gödel’s theorem.

Can Mathematics Prove Itself?

This idea was followed by Gödel’s second incompleteness theorem, which goes even further. It states that no sufficiently powerful mathematical system can prove its own consistency from within, meaning a system cannot fully justify itself using only its own rules. So we have no way of knowing if our logical and mathematical systems are even consistent within themselves, unless we eventually discover a contradiction in mathematics.

The Limits of Knowledge

At this point, you might ask: What is the point of all this? When would we ever have to prove a self-referential statement? But it was soon discovered that there are non-self-referential statements that are also undecidable, i.e. cannot be proven true or false. An example of this is the Continuum Hypothesis, which states that ‘there is no set whose cardinality is strictly between that of the integers and the real numbers’. Another interesting problem is John Conway’s ‘Game of Life’, whose long-term behaviour is fundamentally undecidable.

This idea has consequences for many related fields. For instance, the Halting Problem in computer science is largely based on Gödel’s Incompleteness Theorems and defines the absolute limits of computation. This has led to one of the biggest unsolved problems in maths and computer science, the ‘P vs NP Problem’, which is one of the Millennium Prize Problems.

Moreover, if mathematics is fundamentally incomplete, since physics is expressed in the language of mathematics, does this mean that physics itself is undecidable? Does this mean we will never find the ‘Theory of Everything’ that physicists have been seeking for so long? In his 2002 lecture ‘Gödel and the end of physics’, Stephen Hawking declared: ‘If there are mathematical results that cannot be proved, there are physical problems that cannot be predicted.’ However, this is a controversial claim, and not all physicists agree with it.

Also, Gödel’s Incompleteness Theorems have recently been used to argue against Mechanism, the philosophical view that life and the human mind can be explained solely by physical and chemical processes. For example, Roger Penrose recently claimed: ‘Gödel’s theorems imply that the human mind infinitely surpasses the power of any finite machine or formal system’. This is also a speculative and controversial claim.

In a way, Hilbert was right. We do know. We know that we will never know.

Further Reading

Gödel, Escher, Bach – Douglas Hofstadter

Incompleteness: The Proof and Paradox of Kurt Gödel – Rebecca Goldstein

Gödel, K. (1931), On Formally Undecidable Propositions…

Stanford Encyclopedia of Philosophy — Gödel’s Incompleteness Theorems: https://plato.stanford.edu/entries/goedel-incompleteness/