Eighty Years of Incompleteness

godelThis 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.


7 Responses to “Eighty Years of Incompleteness”

  1. 1 1 S P Suresh

    Great series of posts! Just wanted to add that for people who want a little more detail, there is an excellent series of notes put up by Peter Smith at Cambridge University. The link is: http://www.logicmatters.net/igt/godel-without-tears/

  2. 2 2 Eric H

    I’m surprised you didn’t mention “Godel, Escher, Bach” (http://www.amazon.com/G%C3%B6del-Escher-Bach-Eternal-Golden/dp/0465026567/). I first learned about Godel from that book; I bet that’s true of a lot of people.

  3. 3 3 Steve Reilly

    Eric H, you might also enjoy Nagel and Newman’s book Goedel’s Proof. Hofstadter edited it and wrote an introduction.

    The Completeness Theorem has me confused. Here’s what I’m not understanding: We know that the Continuum Hypothesis is undecidable if we use the ordinary axioms of set theory (Zermelo-Frankel with the Axiom of Choice, or ZFC). We can make a consistent set of axioms by using ZFC and adding the “The Continuum Hypothesis is true” as another axiom. And we can make a consistent set of axioms by using ZFC and adding “The Continuum Hypothesis is false” as another axiom.

    Assuming I haven’t screwed anything up so far (a big assumption, granted) then the Completeness Theorem states that there’s one mathematical structure wherein the Continuum Hypothesis is true, and another where it’s false. But I’ve never heard anyone argue the Continuum Hypothesis is somehow both true and false, so surely the mathematicians patient enough to read this are cringing at some parts, at least, of my post. So what’s the cringe-inducing bit? What am I getting wrong?

  4. 4 4 Steve Landsburg

    Steve Reilly:

    There is indeed one mathematical structure in which the continuum hypothesis is true and another where it’s false. In fact, this is exactly how its undecidability is proven. Godel constructed a “universe of sets” satisfying all the axioms of set theory (i.e. the ZFC axioms) in which CH is true. Cohen constructed an alternative universe in which CH is false.

    Now one can still ask whether CH is true or false in the “real honest to God universe of sets” — the universe of sets we “have in mind” when we think of sets. It’s quite unclear whether this question is a) important, b) meaningless or c) other. In other words, it’s quite unclear whether our notion of “the universe of sets” is sufficiently clear that it specifies one unique structure.

    This situation is a bit different than the situation with the natural numbers and the Peano Axioms. With the natural numbers, it’s crystal clear to almost everyone that when we talk about THE natural numbers, we have one unique structure in mind, and that it’s meaningful to ask what’s true within that structure. With the universe of sets, some people think it’s equally crystal clear that we have one unique structure in mind, and others think it’s clear that we don’t.

    In any event, if we DO have one particular “standard universe” in mind, that universe is not uniquely specified by the ZFC axioms. There are multiple universes satisfying those axioms, and CH is true in some of them (e.g. Godel’s universe) and false in others (e.g. Cohen’s).

  5. 5 5 Steve Reilly

    Ah, thanks for that. Yeah, I guess my confusion was between “true mathematical structure” and “real honest to God universe of sets”.

  6. 6 6 Doc Merlin

    You can’t run the argument backwards and say “if the natural numbers exist then the axioms are true.” You /can/ form structures with inconsistent axioms.

  7. 7 7 dave

    zero is not a natural number. i think the whole thing flops when it comes to zero. why is zero included, anyway? because 1 + 0 = 1? or because 1 – 1 = 0? what about 1 / 0 ?

  1. 1 Clearing the Browser Tabs – Why Does Tuesday Never Get the Publicity of Monday?
  2. 2 Weekend Roundup at Steven Landsburg | The Big Questions: Tackling the Problems of Philosophy with Ideas from Mathematics, Economics, and Physics
Comments are currently closed.