Gödel’s Incompleteness Theorem

May 9, 2023

Share this article:

In mathematics, we like proofs. For thousands of years, mathematicians believed that we would always be able to say that a statement is true or false, and we do this by proving it. No one ever questioned whether this was always possible until 1931, when Austrian mathematician Kurt Gödel started to investigate, leading him to create what is now known as Gödel’s Incompleteness Theorem. The essence of this theorem is quite simple, stemming from a non-mathematical scenario. Ask yourself if the following statement is provable or unprovable: “This statement is unprovable.” At first, it seems obvious, of course it is provable, but if it was provable, then surely the statement would be incorrect? And vice versa, if the statement is unprovable, wouldn’t the opposite be true, that the sentence would become “This statement is provable”, which leads again to a contradiction. One can go round and round in circles, until we eventually realise, we are in a paradox. Gödel took it upon himself to sort this out, leading to the axiomatic system we live in for mathematics. An axiomatic system relies upon certain assumptions for proofs to hold. For example, the first Euclidian axiom states that things that are equal to the same thing are equal to each other. Gödel’s incompleteness theorem proves that we will always need these axioms and we will never be able to live in a mathematical world where everything can be proven.

The way Gödel’s theorem works is by first assigning a “Gödel number” to a symbol, so that we can construct any statement as a series of numbers. The following symbols are constructed below (note that these symbols come from logic, not from mathematics):

The same “mapping” is applied to all variables, such as x, y or z, which are labelled with prime numbers starting from 12. Then, any combination of these symbols or variables, or any formula or statement, can be expressed as a single Gödel number. Let us consider an example: 0 = 0. This would follow the Gödel numbers: 6,5,6. Gödel then changes this sequence of number into a unique number that will never be able to represent another sequence of numbers. To do this, we take the first three prime numbers in our sequence, raise each of these to the power according to our sequence, and multiply them together. Thus, 0 = 0 becomes 2^6 x 3^5 x 5^6 = 234,000,000. Since all Gödel numbers are integers and factors of primes, there is always only one single way in which we can decode a sequence.

Next, Gödel gave every sequence of formulas a Gödel number too, as most mathematical proofs are formed by a number of formulas. From this, Gödel’s theorem starts to become clear. We have now created a system of mapping that allows us to construct any formula or any statement as a single Gödel number. Most importantly, it allows us to “arithmetise” statements such as “The formula with Gödel number m can be proved”, setting the scene for the proof of our theorem.

Before we get to the crux of the proof, we need to understand one more concept: substitution. Let us take the formula:

meaning “there exists an x such thatis the successor of y”. This formula has, just like all formulas, its own unique Gödel number, let us call it k, for simplicity. Now we can insert this number into our original formula:

Which means k has a successor. What is this formula’s Gödel number? Well, there are 3 sections to this formula: we started with our original formula that has Gödel number k, then we substituted k in the place of y back into our formula, and we know from our mapping system that y has Gödel number equal to 17. So, let us label our Gödel number for this new formula:

We have finally set the stage for the heart of our proof. Consider the statement “The formula with Gödel number sub(y ,y, 17) cannot be proven.” Note that the formula with sub(y ,y, 17) as its Gödel number is the formula we obtain by taking the formula with Gödel number y and substituting it with the variable y wherever we have a symbol with Gödel number 17, or simply put, substituting a y everywhere we have a y. This is already starting to seem confusing, but we can continue and label this statement with its own Gödel number, say n.

Now, let us carry out some more substitution. We create a formula that substitutes our n anywhere we previously had a y. We shall call this formula G, which has Gödel number sub(n, n, 17), as this by definition, is the formula that takes the formula with Gödel number n substitutes an n wherever we have a symbol with Gödel number 17, which is exactly what we are doing! Now we see that the formula G is simply talking about itself – thus the statement or formula is true. Thus, we come to a contradiction: G has proven itself to be true.

We can try to prove that G can be proved, but that would mean we have some sequence of formulas that proves that the formula with Gödel number sub(n, n, 17) can be proved, but then that would prove G to be false! Both cannot be true in an axiomatic system, so we conclude that we do not know whether G is provable or unprovable.

This completes our proof. We have come to the conclusion that we cannot prove all statements in mathematics, leading to the importance of axioms. Axioms are a necessity in mathematics – without them, every proof falls apart. They form the building blocks of mathematics, and there will never be a proof for them. Gödel pointed out, to the disappointment of many, that even mathematics has its limitations: mathematics is in and of itself incomplete, hence the name “Incompleteness Theorem”. Whilst this may infuriate those who adore the concreteness of mathematics, this theorem is undeniable, and is actually right at the centre of all maths.  

Read more

The 100 Prisoner Problem

The 100 Prisoner Problem

Imagine if tomorrow you were abducted, and before you knew it, you were trapped in a room with 99 other people who seemed to know nothing more about what was happening than you. You notice that everyone is wearing an orange jumpsuit, which is uniquely numbered. You...

L’Hôpital’s Rule

L’Hôpital’s Rule

Some of you may have heard of the name L’Hôpital whilst you were at school, but why was it so important? L’Hôpital’s rule, more pedantically known as “la régle de L’Hôpital”, is a highly useful technique for finding the limit of complicated expressions. To refresh...