10 Mar 2019
The short story
Any sufficiently expressive2 math system is either incomplete or inconsistent and any consistent math system cannot prove its consistency. In other words, the theorem says that not all true statements in mathematics have proof.
The long story
Background
Let’s start by looking at what verbal paradoxes are. These are statements that create a paradox. Suppose you have ONLY two statements – A and B. A says “The other statement is true”, B says “The other statement is false”. Let’s suppose statement A is true. Given that statement A says that the other statement is true, this means that statement B is true. Now, given that statement B says that the other statement is false, this means that statement A must be false. But we started by supposing that statement A is true, hence we have a contradiction. These verbal paradoxes are fine because we don’t expect every statement to have a truth value. But when it comes to maths, you can’t have a contradiction. Maths is supposed to be consistent.
What is also important is to consider how maths currently works. In mathematics, there are a bunch of axioms, unprovable, intuitive, blindingly obvious statements from which deductions can be made. The good thing about axioms is that you can add more axioms if you haven’t captured the whole of mathematics. The GOAL of a mathematical system is to prove ALL true statements using its axioms. If a true statement cannot be proven from the axioms, then we can add the statement as an axiom and we can expand the mathematical system. Importantly, all true statements are provable from the axioms, or are axioms themselves.
The build-up to the problem
An interim step to the Incompleteness Theorem itself is that Godel produced what has been called Godel’s encoding. Simply put, that means that every statement about mathematics has a unique Godel number, or in other words, some sort of code number. The numbers are very long, but simply put in Godel’s code, to express 0 = 0, that would correspond to the number 17, because 0 is encoded as 6 and “=” is encoded as 5, ergo 6+6+5 = 173. Hence, now we have a number for all true/false mathematical statements as well as the axioms and we can use that to prove statements.
What Godel showed is that for a statement to be provable from the axioms of the mathematical system, the code of the statement must have a specific relationship to the axioms. For example, the code of the statement must be divisible by the code of the statements.
Godel’s challenge
Godel gave the following sentence: “This statement cannot be proved from the axioms”.
As with all statements, this statement has a code number as well. Because it is a statement in mathematics it can only be true or false. It is also NOT a verbal paradox because verbal paradoxes do not necessarily have a truth value.
Now, let’s suppose the statement is false. Given the content of the statement, this means that it can be proved from the axioms. However, mathematics supposes that every provable statement must be true. But we supposed that it is false, hence we have a contradiction. Mathematics also supposes that there can be no contradiction, therefore the statement must be true.
Now that we’ve deduced that the statement must be true, let’s look at its content again. The statement itself asserts that it cannot be proved from the axioms. Therefore, we’ve reached a point where we have a true statement, which cannot be proved from the axioms.
The Big Picture
What we now have is a statement – “This statement cannot be proved from the axioms” that is true, but cannot be proved from the axioms of the mathematical system.
Above we’ve seen that an assumption of mathematics is that we can either have a true statement that is provable or the true statement can become an axiom. Hence, we are only left with 1 move – the statement becomes an axiom and we have a new system with that statement as an axiom. However, this does not save the mathematical system, because we can use the same sentence in the new system ad infinitum and arrive at an infinite regression.
An obvious question is whether this applies only to this one, single sentence that Godel conjured up. Apparently no. Mathematicians have shown that you can still derive a true statement that is not provable from the axioms in a standard mathematical system (Paris-Harrington theorem).
Why does this matter?
I find this Theorem quite compelling as I am highly interested in whether it has any metaphysical and ontological implications. Is it the case that we can never have a logical, consistent, complete system (mathematical or otherwise) that cannot prove statements that are otherwise true? And does our understanding of this Theorem prove that we are not like computers? In other words, the Theorem requires us to go outside of the mathematical system to evaluate the meaning of a specific sentence (Godel’s statement) and then go back into the system and evaluate its truthfulness based on the system’s axioms; but computers cannot go outside of the system within which they are designed.
Notes
1 There are actually two theorems but I will treat them as one for simplicity sake. Also, the review is mostly based on this youtube explanation.
2 What is meant by ‘sufficiently expressive’ is that some basic arithmetic can be done.
3 This is not perfectly accurate but I use it just as an example to get a taste of it. The encoding is much more complex but it’s not an important point here.
