Charlie Ahrendts

For most of human history, mathematicians believed that maths was in some way universal – that a set of axioms could be found such that every statement could either be proven to be true or false using these axioms. This changed radically with a mathematician named Kurt Gödel, when in 1931 he proved that there are fundamentally unprovable problems in every axiomatic system. This is of course quite a lot to get your head around so in this article we will try to get an understanding of his proof, and then look at an example of one of these ‘unprovable problems’.

Following the approach of Godel, we want to prove that there are true statements that cannot be proven to be true. A simplified version of the actual proof goes like this: 

Imagine an all-knowing printer that will only print out true statements. We know that each statement we can make has to be either true or false. We consider every statement that is printed as proven. No problem so far, until the printer prints: I will not print the following sentence twice. I will not print the following sentence twice. There are now two possibilities. Either the machine prints it, or it doesn’t. If it does, it contradicts itself since the latter part was printed twice. This would mean that our machine is broken, which is not a satisfactory answer.

The other possibility is that it never prints: I will not print the following sentence twice. I will not print the following sentence twice. In this case the original statement would be true, since it said it would never print it and it didn’t. But there would be no way of printing it out and thus no way of proving it.

Ultimately, this example corresponds to the statement: “This statement can not be proven to be true”. If we are able to prove it, then a contradiction arises since we proved a statement that cannot be proven. So, this means that the statement must be true, it can not be proven without contradiction, but it also means that we can not prove it to be true (as this is what it states and we have shown it to be true).

Gödel managed to translate the idea of a self-contradictory statement – like those we have seen above – into a formal mathematical proof. To be able to follow his argument there are a few things that we need to understand, which are essential to his proof. First, in mathematics, every statement is either true or false. There is no statement that is neither, nor one that is both. Second, we want mathematics to be consistent. This means that there cannot be any contradictions. Whenever one arises, the statement that produced it must be false. 

Our goal is to prove that there are true statements that cannot be proved to be true. 

The problem is that maths is all about numbers. A verbal paradox like ‘this statement can not be proved’ is too vague. We would need to define what ‘this statement’ means and through that we would create an infinite loop of definition that doesn’t lead us anywhere. So, we need a different approach, and that’s exactly what Gödel managed to do. He gave every possible mathematical statement a sort of code number, which could be translated back and forth. We can imagine it like a computer that takes a sentence and stores it in binary code, then once we want to read it just translates it back. The great thing about this is that we can now use the language of mathematics to talk about these statements.

We already know that every statement is either true or false. This also means that every one of the code numbers, we call them Gödel numbers, has some property that defines their truth value. This property could be very obvious, for example the code number of every true statement is even and that of every false statement is odd. In actuality the property is less straightforward, but the important thing is that it does exist. 

Within this system we can now introduce the statement ‘this statement is not provable to be true from the axioms’. In the original proof, this was changed to be a statement about the Gödel number of another statement, but the meaning is the same. To reiterate, we did all of this converting to numbers to be able to prove our statement about mathematics in its own language and using its own rules. This way we can be certain that it has to be either true or false, which is not the case for verbal paradoxes.

Now, suppose we put the statement in the ‘false’ category. This would mean that the statement could in fact be proven to be true from the axioms, but we assumed that it was false, so we end up with a contradiction. And remember that we cannot have contradictions, so therefore it can’t be false. This means it has to be true since this is the only other option. But if it is true, so is the fact that it is not provable to be true. Hence, we just managed to create a true statement that is not provable. 

This came as a huge shock to the mathematical world and has definitely changed the way we view mathematics today. Many still wanted to believe that the case of an unprovable statement would only come up in this kind of constructed verbal paradox, but that too was proven to be false. There are very relevant areas where this kind of situation can arise, with one famous example being Alan Turing’s halting problem. 

We imagine some sort of machine that runs a computer program. What happens inside it is not relevant, but we know that we can give it some input and it will produce an output that is either yes or no. We want to be able to give this machine any program as an input and have it determine whether or not it will halt. Consider the following program: 

print (hello world)

which will execute and then stop. On the other hand:

while (true): print (hello world) 

will not stop, since while (true) tells the computer to loop forever. 

Let us now suppose that our machine could perfectly determine whether any given program halts (like our first example). If it does, it would output yes and if it doesn’t, it would output no. In fact let us expand this machine. Every time it outputs yes, we tell it to go into an endless loop, and every time it outputs no, we tell it to halt. Now we feed that machine into itself. By doing so, we have created a contradiction. Since we told the program to halt if it loops forever, and loop if it halts, we will get a contradictory answer, no matter what we do. Turing proved that no possible algorithm could ever solve the halting problem and we therefore call it undecidable.

These kinds of paradoxes are very hard to get your head around and sometimes the longer you think about them, the more confusing they get. But, the important thing to take away is that no mathematical system we can construct will ever be complete. We can always find and add new things, we can keep learning and exploring, and personally I think that is definitely a good thing!