In my book, Gödel’s incompleteness theorem is one of the greatest achievements of human thinking. It crashed into mathematics like a hammer when it was published. It destroyed the firm ideas of Hilbert that we will be able to base mathematics on a small set of axioms and get firm knowledge of everything. Yet, it is now widely ignored. Most students of mathematics will never hear about it. I think I never wrote about this marvel. It is time to do so.
This is a difficult topic. The text below omits most of the details. Yet, it may be digestible by mathematically trained only.
Mathematics is based on axioms, usually expressed in the language of set theory. Set theory itself has been axiomatized, but we can restrict ourselves to the much simpler axioms of arithmetic. In fact, all it takes to understand the incompleteness theorem are the natural numbers and inductive reasoning.
The basic ingredient is the set of natural numbers N, the special number 1, and the successor mapping, which maps n to n+1 with two additional properties that we omit here. The principle of induction says that any subset of N which contains 1 and with any n also n+1, is equal to N. Thus, we can prove theorems for all numbers n by showing that they are true for n=1, and if they are true for n, they will always be true for n+1. Additionally, we need to define some simple axioms for addition and multiplication, and maybe also for exponents. The details do not matter here. Now, we already have the axioms of arithmetic.
Mathematical reasoning uses only these axioms and logic to prove theorems. The proofs can be quite tricky. But we can prove all the familiar facts based on these axioms, such as the commutative or distributive laws.
We can also define primes and prove that there are infinitely many primes, or that each number is uniquely a product of primes. Using set theory, we could also go from the natural numbers to the rational numbers and then to the real numbers. But for our purpose, we don’t have to. Those theories simply extend and contain the natural numbers, and incompleteness already happens there.
What does the incompleteness theorem of Gödel tell us?
Gödel’s theorem says that there will always be theorems which we can formulate in the language of arithmetic, but we cannot prove them or disprove them.
I.e., logic reasoning will not yield the theorem or its contrary.
Let me give two examples.
- If we state a theorem that all numbers have a specific property, then we could check each number for this property. Obviously, if the theorem is true, this process will never end because there are infinitely many numbers. So, this is no route we can take. The incompleteness theorem says that for some theorems there is no direct prove from the axioms that the check will indeed work for all numbers.
- Let us say, we state that there are infinitely many numbers with a given property. Again, we could try to check that by finding more and of these numbers. If the theorem is true, we will never fail. But this takes infinitely many steps. The incompleteness theorem tells us that for some theorems we cannot prove that the collecting will work.
This astonished most mathematicians, because we can prove in set theory that there is essentially only one version of the natural numbers. Two versions will have the same properties. So, each theorem must either true or false.
But that is a misunderstanding. Incompleteness just means that we cannot setup a finite set of axioms which will yield all theorems or their contrary with logic reasoning.
You can indeed add each unprovable theorem or its contrary to your set of axioms to your liking. The point of the incompleteness theorem is that you will not be able to derive a contradiction with your set of axioms. I think this means, that we cannot fully understand N, even though we think we can.
It is worse. Gödel also told us that it is impossible to prove that the axioms of arithmetic don’t contain a contradiction, even without adding anything. Note, that we might find such a contradiction if it exists. But if it doesn’t, we cannot prove that it doesn’t.
The idea is that logical reasoning is based on rules that we apply to our axioms to get new theorems. We can go on and on and get all provable theorems in an infinite process. The provable theorems are enumerable, i.e., they can be created by a constructive process. The problem is that we might not get some theorems in the process, nor their contrary.
The process of enumerating the provable theorems inspired von Neumann to get hold of the incompleteness by considering the halting problem. Today, most of us will have an understanding of a computer program or an algorithm and what it can do. The only extension to our everyday computers is that we assume that we have as much memory as we want. We also know that some programs get into an eternal loop.
The halting problem is the problem to determine by inspection of the code that the program will stop when given a specific number as an input.
It turns out that there is no way of doing this in a rigorous way.
The argument is based on a diagonal construction like in Cantor’s prove that the reals are uncountable. Since the set of all possible programs is enumerable, i.e. we can write down all of them in a proper manner, we can assign a number to each program.
We claim that it is impossible to write a program which stops with the input n, if and only if the program n does not stop when it is given its own number.
This is easy to understand. If there were such a program, it can neither stop nor not stop when given its own number.
Consequently, we cannot design a machine that solves the holding problem. The main argument is now that logical reasoning can be done by machines since it is only applying rules. Thus, if logical reasoning could solve the halting problem for each given program, we could also design a program that does. But we cannot do that.
In the last step, we have to show what this has to do with Gödel’s incompleteness theorem. For this, we remark that the halting problem can be formulated as a theorem in arithmetic. The details of this formulation are involved. But it should be no surprise to us. After all, we can teach computers to reason logically, and computers are just handling numbers by rules which are arithmetically based.
This is all beautiful mathematical philosophy. Why is it not taught in universities? Maybe, because we don’t need it for our mathematical research. All we do is constructive mathematics, going one step after each other and deriving new results from our given axioms. Sometimes, we may wonder if any of the yet unproven theorems in number theory can be proved at all. But most likely, they can. We actually may never be able to prove that they can’t.