Question Hello philosophers. I was just wondering about Gödel's Incompleteness Theorem. What exactly is it and does it limit what we are capable of knowing? I have no training in mathematics or formal logic so if you could reply in lay terms, I would appreciate that. Thanks, Tim.

Accepted:
February 14, 2006

Comments

Godel's Incompleteness Theorem is a theorem about formal axiomatic theories: theories in which there is a collection of axioms from which all of the theorems are deduced, and in which the theorems are deduced from these axioms by the application of rules of logic. It applies to a wide range of theories, but to start off it might be helpful to focus on one such theory, so let's consider Peano Arithmetic, often abbreviated PA. This is an axiomatic theory of the properties of addition and multiplication of the natural numbers 0, 1, 2, ... (Peano Arithmetic is named after Giuseppe Peano.)

Godel's Incompleteness Theorem says that if PA is consistent--that is, if the axioms don't contradict each other--then there are statements about the arithmetic of the natural numbers that are neither provable nor disprovable from the PA axioms. Thus, the axioms are not powerful enough to settle every question of number theory.

Now, you might think that all this shows is that Peano must have forgotten an axiom or two; maybe all we need to do is add a few axioms, and then we'll be able to get the answers to all the questions of number theory. But as I said earlier, the theorem applies to a wide range of axiomatic theories. In particular, it applies to any "reasonable" extension of PA. Without going into detail about what "reasonable" means, let me say that if you add any finite number of axioms to PA you get a reasonable extension. So adding a finite number of axioms is not going to solve the problem. If you add finitely many axioms, and the new axioms don't introduce any contradictions into the theory, then there will still be statements of number theory that are neither provable nor disprovable. You might say that the truths of number theory are too complicated to be captured by any "reasonable" axiomatic theory. (A closely related fact: It is impossible to program a computer so that if you type in a statement about the arithmetic of the natural numbers, it will tell you whether the statement is true or false.)

The Incompleteness Theorem also applies to Zermelo-Frankel set theory with the axiom of choice, often abbreviated ZFC. This is an interesting case, because many mathematicians regard ZFC as the foundation for all of mathematics; some people would claim that all correct mathematical reasoning can be justified using the ZFC axioms. The Incompleteness Theorem tells us that if ZFC is consistent, then there are statements of set theory that are neither provable nor disprovable in ZFC. If we accept the idea that all correct mathematical reasoning can be carried out in ZFC, then this means that there are statements of set theory that cannot be settled by any correct mathematical reasoning.

By the way, what I have been describing so far is sometimes called Godel's First Incompleteness Theorem. The Second Incompleteness Theorem says that if PA is consistent, then one of the statements that is neither provable nor disprovable from the axioms is the statement "PA is consistent". More generally, for a wide range of axiomatic theories T, if T is consistent then in T you can neither prove nor disprove the statement "T is consistent".

Regarding your second question, whether the incompleteness theorem limits what we are capable of knowing, people disagree about this question. But the short answer is: There is no decent, short argument from the incompleteness theorem to that conclusion. If it does limit what we are capable of knowing, then it will take a very sophisticated argument to show that it does.

One might think it followed from the theorem that we cannot prove that PA is consistent. But we can. I proved it yesterday, in fact, in my class on truth. The incompleteness theorem says only that we cannot prove that PA is consistent in PA, if PA is consistent. (If it's not, then we can prove in PA that PA is consistent! But that won't do us much good, since we can also prove in PA that PA is not consistent, and indeed prove absolutely everything else in PA, e.g., that 2+3 = 127.—This last remark assumes that we have classical logic at our disposal.)

So when I proved that PA was consistent, I didn't do so in PA. I had to use some assumptions that do not follow from the axioms of PA, but that's no big deal. It just means that not all acceptable mathematical reasoning can be carried out in PA. So call PA plus my extra assumptions PA+. Can the consistency of PA+ be proven? Not in PA+ (if PA+ is consistent). But its consistency can be proven, for example, in ZFC. What about the consistency of ZFC? That too can be proven, in ZFC plus the axiom "There exists a strongly inacessible cardinal number". (I won't try to say that that means.) And so on and so forth.

Dan mentioned that some people hold that "all correct mathematical reasoning can be carried out in ZFC". If so, then there is no "correct mathematical reasoning" that can be used to prove that ZFC is consistent. Such people would hold that the statement that there is a strongly inaccessible cardinal shouldn't be accepted as mathematically correct. At least not yet.

But it's here that some people, such as Roger Penrose, start to smell trouble. Suppose I claim to know all the axioms of ZFC. Not, that is, to know what they are, but to know the axioms themselves. For example, I claim to know that there is a set with no members, that every set has a union, and so on and so forth. Well, if I know the axioms, then they must be true, since you can't know that p if it isn't true that p. (You can think you know, but you can't actually know.) But if the axioms are all true, then surely they must be consistent. But if so, then it seems as if I can use precisely this reasoning to convince myself that ZFC is consistent: I know its axioms; hence they are true; hence ZFC is consistent. But our hypothesis was that there is no correct mathematical proof of that claim. And it's really irrelevant whether it's ZFC that correctly captures acceptable mathematical reasoning. The same puzzle could be formulated for whatever "reasonable" theory one might propose. What's gone wrong?

Well, there are lots of different views about that. Some people, such as Hilary Putnam, think there is a subtle (or maybe not so subtle) fallacy in the argument just given. Others, such as Penrose, think it shows that no "reasonable" theory can capture correct mathematical reasoning. I won't try to resolve the issue here. (I'm more with Putnam, but I tend to think that there is a puzzle here, nonetheless, that hasn't really been adequately addressed.) But perhaps it is at least clear now why it's not clear whether the incompleteness theorem limits what we can know.