Gödel’s Incompleteness Theorem

by Reetobrata Chatterjee

David Hilbert

In the early 20th century, one of the greatest mathematical minds of the time, David Hilbert, posed 23 problems to the mathematical world, which he hoped would be solved by the end of the century. These are similar to the Millennium Problems.

He would have disappointed.

That may be a slight. Of the original 23 problems, called Hilbert’s Problems, only four remain completely unresolved. Most are fully or partially resolved, which is always good. The 2nd Problem is the one this article is concerned with. It simply states:

“Prove that the axioms of arithmetic are consistent”

The axioms of any branch of mathematics are the concepts which are accepted to be true without any proof. Such fundamental “truths” are required in order to build onto more complex things, known to us as theorems. These axioms are only accepted because they are considered self-evident. This includes things like if a=b and b=c then a=c. The only difference between this and the actual axiom is a bunch of mathematical symbols.

Perhaps a more complex one is the axiom of induction. This enables mathematicians to use proof by induction, a very powerful technique. The outline, or lemma, goes as follows:

1. Prove the “base case” – i.e. prove that for most basic instance, such as when x = 1, the results of the theorem match the calculated result.
2. Assume that when x = k, the theorem holds true.
3. Prove that if when x=k, the theorem holds true, then when x = k + 1, the theorem holds true as well.
4. Induction Statement – If x = k => x = k + 1 and x = 1 is true, then x = 1 => x = 2 => x = 3 => … => for all x in the defined range.

Kurt Godel

Hilbert’s Challenge was met by Kurt Gödel in 1931, in the form of his incompleteness theorem, which is the actual topic of this essay. He actually had 2 theorems, but the first one is considered more important and to keep things (relatively) short, I’ll only discuss that.

The statement of the theorem is:

“For any given axioms of arithmetic, the resulting system can either consistent or complete, but not both.”

In simpler terms, this states that no matter which “truths” you choose to accept in order to create the system we know as arithmetic (currently Peano Arithmetic is used). 

There will always be things that cannot be proved, if the axioms don’t contradict each other. This was akin to saying that a statement which could seem obvious, like 2 + 2 = 4, could not be proved from first principles by using the axioms. The other possibility (corresponding to the “incomplete” in the statement), is that a statement like 2 + 2 = 5, could be proved correct.

Mathematicians, being advocates of consistency decided to take the first choice, have an incomplete system, as opposed to an inconsistent one, because although it must be annoying to know that a proof they were working on might not exist, it was better than one of their “correct” proofs being obviously false.

This was a huge blow to other mathematicians working at this time, because they were completely devoted to formalising the axioms of arithmetic, like Hilbert had intended, only to have their work thrown out of the window by a young American upstart who was only 25 at the time.

The proof is really complicated.

However, an analogy to the proof can be provided simply:

Imagine there is a printer, which will accepts and prints documents. The one catch is that it will only print the document if the statements it contains are true. If any statement is false, it won’t do anything.

So for example if you put a statement saying “It’s going to rain today” it would print it (since this is England).

However a statement like “Its 50C outside” would cause the printer to do nothing (again because this is England).

It all seems fine up till now. There seems to be no statements that will cause a paradox is there?

A clever guy named Gödel comes up with one.

Let this Gödel Sentence be: “I can never print this”

This leads to a conundrum because if the printer prints this, then the statement must be true. But then the printer couldn’t have printed it. If the printer doesn’t print this, then the statement must be false right? No.

If this was actually the case, the printer would probably just explode or malfunction since then it would be out of order so the truth of the statement would become undeterminable.

But mathematics cannot just explode or malfunction (probably). So this leads to a paradox, which cannot exist either. This is what Gödel proved in his work, that given a set of axioms of arithmetic, there is a counterpart of “I can never print this”, which the fabric of mathematics cannot take.

In conclusion, this theorem shook mathematics and I would consider it one of the most significant of all time, alongside the likes of calculus and Pythagoras’ Theorem, purely because it shows that even the most simple systems in what’s considered the purest science is to some extent flawed at its very core.