Lesson 9

Gödel's original proof is beautiful but tedious. However, there is an extremely short, elegant proof that uses the fact that the Halting problem is undecidable. Here's how it goes.

First, we choose a set of axioms that is strong enough to prove that the halting problem is undecidable. In particular, this set of axioms must be strong enough to reason about computer programs or algorithms. (In a more formal presentation, these notions would be much more clearly defined.)

Just so that you have a rough image in your mind, it might be helpful to think of the three axioms of equality plus some additional axioms that we won't worry about:

1. For any \(x\), \(x = x\).
2. For any \(x\) and \(y\), if \(x = y\) then \(y = x\).
3. For any \(x\), \(y\), and \(z\), if \(x = y\) and \(y = z\), then \(x = z\).
4. \(…\)

Suppose for the purposes of contradiction that every mathematical truth can be derived from these axioms in finitely many steps. (In a more formal presentation, this notion would be much more clearly defined.) Let's use this assumption to write a computer program, \(P\), that solves the halting problem, a contradiction:

Since we want \(P\) to solve the halting problem it will naturally take as input a description of another computer program, \(Q\). After taking its input, \(P\) will enumerate all of the theorems that follow logically from the axioms. So, using our example axioms, \(P\) might list theorems like this:

1. For any \(x\), \(x = x\). (Axiom)
2. For any \(x\) and \(y\), if \(x = y\) then \(y = x\). (Axiom)
3. For any \(x\), \(y\), and \(z\), if \(x = y\) and \(y = z\), then \(x = z\). (Axiom)
4. For any \(w\), \(x\), \(y\), and \(z\), if \(w = x\), \(x = y\), and \(y = z\), then \(w = z\). (Iterating theorem three twice)
5. For any \(x\), \(y\), and \(z\), if \(x = y\) and \(z = y\), then \(x = z\). (Combining theorems two and three)
6. \(…\)

If \(P\) happens to arrive at the theorem “\(Q\) eventually halts,” then \(P\) will output that fact. If \(P\) happens to arrive at the theorem “\(Q\) runs forever,” then \(P\) will output that fact. Obviously, \(Q\) must do one of these things, and since we assumed that our axioms can derive every mathematical truth in finitely many steps, it must be the case that \(P\) will eventually output the correct answer.

But, this means that \(P\) solves the halting problem. Since we've already proven that that's impossible, our assumption must have been wrong. In particular, there is no set of axioms from which all mathematical truths follow. Russell's attempts were guaranteed to fail from the beginning.