The Fall of the Hilbert Program

Hello all! Sorry it’s been a while since my last post. As some of you know, this past week was a little rough for me. Last weekend I spent Saturday at Setsucon, an anime convention in Centre County, PA, with the Penn State Taiko Club. (Check us out here!) Then on Sunday, my family’s dog passed away, so it was a sad start to the week and I was behind on work already, so that’s my excuse for no blog post last week. But now I’m mostly caught up with my life, so here goes the next installment of Numbers and Angels! In my last post, I introduced the question, “What is mathematics?” I talked a little about the difference between Platonism and Formalism. If you haven’t read that post, “An Innocent and Impossible Question,” go and read that first.

Now let’s see, where did we leave off? Ah, yes. The fall of the Hilbert Program. First, a story. On my first weekend at Penn State, seeing as it was a beautiful weekend and I didn’t have any significant work yet, I decided to be a good Catholic and find a local parish. So I attended the noon mass at Our Lady of Victory. After the service I introduced myself to a couple of the other parishioners, and one of them made a peculiar remark when I told him that I’m a mathematics grad student: “Oh, you’re a mathematician! So, do you know Kurt Gödel?”

If you don’t know who Gödel is, he's the guy on the left. Suffice it to say that asking a mathematician if they know about Kurt Gödel is like asking a physicist if they know about Stephen Hawking. Gödel is kind of a big deal. But it was this fellow’s next remark that really surprised me:

“Gödel mathematically proved that God exists, right?”

Now, that’s like asking a physicist if Hawking proved that God created the universe because of Hawking’s Big Bang Theory.

I shrugged and replied, “Well, I guess some people have that interpretation, yes. But it’s a little more subtle and complicated than that.”

I’m not sure if Gödel intended to prove God’s existence. What Gödel proved was that Hilbert’s initiative to axiomatize all of mathematics was something of a lost cause. To recap, Hilbert was trying to reduce mathematics to a finite set of axioms from which all of mathematics could be proven. Imagine that: all of mathematics, generated from a finite list of axioms. That’s a pretty incredible goal. Now in order for this formalization to be significant to Hilbert, it had to be consistent, it had to be complete, and it had to be decidable. Consistency means that the system of logic never contradicts itself; you can’t use the axioms of the system to arrive at a contradictory statement. (For an example of a “contradictory statement,” check out this “proof” that 1 = 2, where the authors decided to include an axiom allowing division by 0.)

Completeness means that if a statement is true, there should be a way of proving it within that system. Decidability means that if you have a logical statement within that system, you should be able to prove whether or not it’s true using the axioms of this system. (Unfortunately I couldn't find a good web article describing decidability, so there's no hyperlink for that one in the previous paragraph. Sorry.) But there were two big problems, revealed by Gödel’s two Incompleteness Theorems. The first problem was this: Given any axiomatic system of logic capable of proving certain fundamental, elementary results of arithmetic number theory, there exist true statements within this system of logic that cannot be proven using the axioms of this system. In simplified language, this is Gödel’s first Incompleteness Theorem. Gödel referred to number theory in this theorem, but he extended it to ANY system of logic—in particular, those under investigation by Hilbert. The main idea is this: if you have a formal system of logic, one of two things will happen: either you will stumble across a true statement that cannot be proven, or you will prove a statement that contradicts something you’d previously proven. (Why this is true is a little difficult to describe, and requires a fair bit of mental contortion, but I'm hoping to devote a future blog post to explaining the general idea.) Obviously this caused a problem for Hilbert. No system of logic could prove everything in mathematics; there will always be questions we don’t have the answer to, and will in fact never be able to answer. Here’s an example of a seemingly obviously true statement that can’t be logically proven: suppose I have a collection of sets. Think of a set as a box of stuff. I might even have infinitely many sets, and each set might have infinitely many items inside of it. Now, is the following statement true or false? I can create a new set containing one element of each of the original sets. To put it another way, given any (possibly infinite) collection of nonempty boxes, I can take a new empty box, choose one item from each of my original boxes, and put it in the empty box. Intuitively, this is clearly true, right? Well that statement is known as the Axiom of Choice. It’s an obviously true statement. And it can’t be logically proven. More specifically, it can’t be proven using the standard canonical axioms of set theory, known as the Zermelo-Fraenkel axioms. There are other logical systems, and some can arguably "prove" the Axiom of Choice, but mathematicians generally don’t use these other systems for various technical reasons. Oh and also, the Axiom of Choice leads to some very strange results. (Click that link. I dare you.) Now, maybe Hilbert’s program could be salvaged, right? Even though there will always be questions we won’t be able to answer, and there will always be true statements we can’t prove, maybe we can prove the consistency of these axioms, right? At least we can use these systems of logic to verify that they never contradict themselves, right? Right? Wrong. This was the second problem with Hilbert’s Program, and the second of Gödel’s Incompleteness Theorems: If a sufficiently descriptive formal system of logic has a statement that proves its own consistency, then this system of logic is inconsistent. In other words, no system of logic can, on its own, prove that it’s consistent. To be sure, we can prove that systems of logic are consistent, but only by invoking rules from a different, more powerful system. For example, the axioms of Peano arithmetic are consistent; they never contradict each other. But we can only prove this using logical results from Zermelo-Fraenkel set theory, which is a more powerful system of logic than Peano arithmetic.

It's somewhat hard to explain how this works mathematically, but it's similar to the following problem. There is a school of philosophy known as New Atheism, which, among other things, insists that the only beliefs one can reasonably hold are ones that can objectively be proven. In other words, you can't reasonably justify a belief if you can't prove it scientifically. Except that very statement is not a scientific argument, but a philosophical stance. Not only that, but it doesn't seem to me that you can prove that stance using objective arguments without in some way invoking the very same stance you're trying to prove. So New Atheism holds that objective reasoning must be the basis of all belief, but requires non-objective arguments to validate its consistency. (I can go on and on about this, and I will at some other point, but that's for another day.)

This, I think, is what proved the futility of the Hilbert program. It’s also probably what that parishioner at Our Lady of Victory meant when he suggested that Gödel mathematically proved the existence of God. Mathematics only works because it is governed by logic, but mathematics is an infinite universe in and of itself, and it cannot prove its own consistency. Here was the basic problem with Hilbert’s vision. You can create a logical system of finitely many axioms. The precise axioms you choose are totally up to you. But once you settle on those axioms, the Universe takes over. You have to live with the consequences of your decisions, and one of the following two consequences is inevitable: either you will arrive at a question that cannot be answered, or you will prove a statement that is clearly false. Of course you’d rather have the first of those two problems, but to prove that your system is consistent, you have to invoke rules from a different, more powerful system of logic. So every axiomatic system of logic that we can put to paper can only be validated by a more powerful system. In turn, that more powerful system can only be validated by an even more powerful system! And so on, and so on, ad infinitum. So, what is mathematics? I’ll tell you what it’s not. Mathematics is not purely a product of human conception. Any human effort to ground all of mathematics will be influenced by some other outside factors, beyond human control. What are those factors? Is it the Universe? Nature? God? I honestly don’t know. I think that almost every theorem that we’ve proven in the course of human history comes from somewhere, some corner of the mathematical universe. That universe is the ultimate final frontier. In my vision, the mathematical universe is perfectly self-contained, and indeed proves its own consistency, but in a “turtles all the way down” kind of way. But it’s all there, waiting to be discovered. Proving mathematical results becomes a mission to explore and to chart a new region of the mathematical universe, a universe that exists independently of our physical one, and yet permeates every fabric of our physical reality. To me, few experiences can be so spiritually fulfilling. Yes, I find solving math problems spiritually fulfilling. I have reached a whole new level of dork. Do I care? No. And unlike G. H. Hardy, I make no apologies.