This weekend marked the 80th anniversary of the most significant event in the history of logic since the days of Aristotle. On October 23, 1930, the 24-year-old Kurt Godel presented his incompleteness theorems to the Vienna Academy of Sciences.

The first incompleteness theorem says this: No matter what axioms you start with, there will always be statements in arithmetic that you can neither prove nor disprove. (I am glossing over some technicalities here, but in this context they are not important.) Some of those statements take the form “Such-and-such an equation has (or does not have) any solutions”. You tell me your axioms, and I’ll produce an equation that you can neither prove solvable nor prove insolvable.

When we’re doing arithmetic, we often start with the Peano Axioms, which codify the basic facts about addition and multiplication and the ordering of the natural numbers. (When I say “the ordering of the natural numbers”, I mean things like “every number has a successor”, “no two numbers have the same successor” and “starting from zero, if you keep taking successors, you’ll eventually get to any number you want”.) Sometimes, if we want a more powerful system, we begin with the Zermelo-Frankel Axioms, which allow us to talk not just about numbers, but about sets of numbers. Among mathematicians, these axiom systems are the industry standards.

Now Godel’s first incompleteness theorem tells us that there is an equation whose solvability/insolvability cannot be determined from the standard axioms. This means that if you like, you can simply assume this equation to be either solvable or unsolvable, and you will never risk contradicting yourself.

Nevertheless, mathematicians usually want to do more than just avoid contradicting themselves. They want to restrict themselves to proving things that are true. One interpretation of Godel’s theorem is that, regardless of your axiom system, there are true statements in arithmetic that you won’t be able to deduce from your axioms. That’s unsettling.

Godel’s second incompleteness theorem says that not only are there true statements in arithmetic you can’t derive from your axioms; there are also true statements about the axioms themselves that you can’t derive from the axioms — and one of those statements is that your axioms are consistent. More precisely: A consistent set of axioms cannot prove its own consistency. (An inconsistent set of axioms can prove its own consistency, but of course it will be lying to you.)

(Once again I’m glossing over technicalities that would be important in other contexts but are not important here.)

The second incompleteness theorem is sometimes misstated in something like the following form: “It is impossible to know that the axioms we use for arithmetic are consistent” or even “It is impossible to know that the things we prove about arithmetic are true”. That’s not what the theorem says at all. Godel’s theorem rules out the possiblity of deducing the consistency of the axioms from the axioms themselves. This is in fact earth-shattering (or was in the context of what other people were trying to accomplish in 1930), but it still doesn’t rule out the possibility that we can know the consistency of the axioms in some other way.

Indeed, most mathematicians are perfectly comfortable with the following argument: The Peano axioms must be consistent because the Peano axioms are true — and a set of true statements cannot be inconsistent. An extreme skeptic might reject this argument on the grounds that we can’t know the Peano axioms to be true — just as an extreme skeptic might insist we can’t know that anyone other than ourselves experiences consciousness, or that we weren’t all created five minutes ago with a lifetime’s worth of false memories built in. But as the late lamented logician Torkel Franzen never tired of pointing out — if that’s your position, then you must be skeptical not just of the consistency of the Peano axioms, but of pretty much everything else the rest of us think we know about arithmetic. This just doesn’t seem like a very productive way to go.

Godel is famous not just for his incompleteness theorems, but for his completeness theorem, which says that if a set of axioms is consistent, then there must be some mathematical structure it describes. So we can run this argument in both directions: If the natural numbers exist, then the Peano axioms are true statements about them, and therefore the Peano axioms are consistent. In the other direction, if the Peano axioms are consistent, then the completeness theorem says that the structure they describe — that is, the natural numbers — must exist.

Of course I’ve blogged about much of this before, but the anniversary seemed like a good occasion to reiterate it. Here are few relevant past posts:

Godel in a Nutshell gives the essence of Godel’s argument.

Basic Arithmetic, Part I, Part II, Part III and Part IV, on the relationship among truth, provability, consistency and existence.

First Things and Second Things and Godel, Fermat, Hercules, answering a readers’ questions about the applicability of Godel’s theorem and what it means for working mathematicians.

Just the Facts — more on the distinction between truth and provability.