Gödel’s Theorems
Kurt Gödel is most famous for his second incompleteness theorem, and many people are unaware that, important as it was and is within the field of mathematical logic and beyond, this result is only the middle movement, so to speak, of a metamathematical symphony of results stretching from 1929 through 1937. These results are: (1) the Completeness Theorem; (2) the First and Second Incompleteness Theorems; and (3) the consistency of the Generalized Continuum Hypothesis (GCH) and the Axiom of Choice (AC) with the other axioms of Zermelo-Fränkel Set Theory. These results are discussed in detail below.
The Completeness Theorem (1929)
In 1928, David Hilbert and Wilhelm Ackermann published Grundzüge der Theoretischen Logik, a slender but potent text on the foundations of logic. In this text they posed the question of whether a certain system of axioms for the first-order predicate calculus is complete, i.e., whether every logically valid sentence in first-order logic can be derived from the axioms and rules of inference of the system. Gödel’s Completeness Theorem, which he presented as his doctoral dissertation at the University of Vienna in 1929, showed that first-order logic is indeed complete in this sense. In other words, every valid sentence in first-order logic can be derived in first-order logic.
The Incompleteness Theorems (1933)
This question of completeness of theories was central to the larger metamathematical program, initiated by David Hilbert, of determining a complete axiom set for mathematics as a whole that would be:
- Finitely given,
- Consistent, and
- Complete.
By finitely given, we mean that the set of assumptions must be describable in a finite way. (Without this condition, one could take as one’s axioms the set of all true propositions of mathematics—a vacuous supposition!) By consistent, we mean that the axioms, together with the rules of inference, must not allow the deduction of a contradiction, such as \(1 = 2\). (Math is doomed if we can’t satisfy this condition.) The third condition, completeness, is the crux of the matter: We want, given any true mathematical statement, the assurance that our axioms and rules of inference are strong enough to give a proof of the statement. (We might not, for a given statement, actually know the proof, but we would like to be assured that, supposing the statement is really true, a proof exists.) This was the Holy Grail, and it was this that Gödel showed was unattainable.
Gödel’s first effort was in the realm of number theory, and specifically addressed whether the accepted axiomatization of arithmetic (the Peano axioms) are complete. Through an ingenious device known as Gödel numbering, Gödel found a way to assign a unique natural number to any statement of arithmetic, effectively turning statements about numbers into numbers—numbers moreover about which new statements could be made. He made numbers talk about themselves, in other words. This permitted him to construct a Gödel sentence, a logical sentence in the language of number theory which amounts to the statement, “this theorem is not provable in number theory.”
What does this achieve? If the Gödel sentence is false, then it is necessarily provable in arithmetic—a contradiction. If this contradiction stands then arithmetic is inconsistent. But there are very strong reasons for believing arithmetic is consistent, so we must suppose that the Gödel sentence is a true theorem of arithmetic, and therefore arithmetic itself can never prove it. (You see why this is called metamathematics!) So, arithmetic is necessarily incomplete.
This result stunned the mathematical world, but Gödel wasn’t finished yet. For he realized at once that the only requirement for this result was that the axiom system in question be strong enough to permit one to do arithmetic. Consequently, any mathematical theory (axiomatic system) which meets this criterion is likewise incomplete. Set theory, algebra, analysis—indeed the whole of mathematics is incomplete, assuming that the axioms are finitely given and consistent (which are conditions mathematics cannot forego), and robust enough to account for arithmetic. This means that there are true statements of mathematics (theorems) which we can never formally know to be true. We are barred from achieving complete knowledge of mathematical truth.
It is this second incompleteness result which is generally meant when people talk about “the Gödel Incompleteness Theorem.” It is widely believed to have important repercussions beyond mathematics, since it is really a statement about the limits of formal knowledge, that is, knowledge which depends upon the rigors of logic. However, one must be careful here to remember what the entire edifice rests upon: numbers. The incompleteness theorems should not be made to do service in areas outside of mathematics unless that crucial link to formal logic and robust axioms can be made. That Gödel should have found his result by discovering the potential for self-reference in arithmetic should not surprise us, in retrospect, because the importance of paradoxes that arise in this way have been know since ancient times. (Consider, for example, the so-called liar paradox.)
There are other results which Gödel’s incompleteness theorems made possible. These include the fact (which he formulated) that no theory can prove its own consistency. (Arithmetic, for example, can only be proved consistent within a larger theoretical framework such as Zermelo Fraenkel set theory—but then set theory can’t prove it’s own consistency.) Another closely related statement is Alfred Tarski’s result that “truth” in a formal system or model cannot be defined within that system or model.
The Consistency of GCH and AC (1937)
Important and compelling as the incompleteness results are, from a mathematical point of view they closed the book on the completeness question, and little more is to be said about them. Gödel’s next result, however, led to decades of important research in set theory, research that continues today. To understand the significance of his result, it will be necessary to set the historical stage for it, so to speak.
Georg Cantor proved in the late 19th century that any set, including in particular any infinite set, is, in a sense that is mathematically well-defined, smaller than the collection of all of its subsets (its power set). The question arose whether there could be any set whose “size” in this important sense—called cardinality—is intermediate between the cardinality of the original set and the cardinality of its powerset. For instance, the power set of the natural numbers has the cardinality of the continuum (the real numbers). Is there a set with an intermediate cardinality? Cantor thought there was not, and this statement became known has the continuum hypothesis. (The generalized continuum hypothesis, GCH, is the more general statement regarding any set and its powerset.) Neither Cantor nor anyone else was able to prove it, however. (For more on the nature of cardinality, infinite sets, and Cantor's Theorem, see the Infinity Mini-Text.)
Then Ernst Zermelo, in the period 1904-08, had formalized an assumption which it turned out mathematicians had been using all along without realizing it; the Axiom of Choice. This amounts to the following statement: Given any (infinite) collection of non-empty sets, we may construct a new set by choosing as its elements one element from each of the sets in our given collection. Seems plausible, but unless it can be proved from the other axioms of mathematics it must be formally recognized as an assumption, that is, it must be taken as an axiom itself. And, of course, no one was able to prove it.
Along comes Gödel. One of the most powerful techniques for determing the nature of the axioms of a theory is to construct a model of that theory, and then see what impact the model has on the axioms. In particular, if one can construct a model of a theory that also supports some extra axioms, then one has shown that the extra axioms are consistent with the theory. It was this that Gödel achieved. He found a way of describing a subcollection of the class of all sets (what in set theory is called the “set universe”), to identify what he called the constructible sets. This collection (the constructible set universe), is a model of set theory, that is, it supports all of the axioms of set theory (the axioms are “true” in it), and in addition it supports the GCH. This showed that one may safely assume the GCH without fear that by doing so one will make one’s theory inconsistent. If set theory is consistent, than set theory with GCH is consistent.
Moreover, Gödel showed that set theory together with GCH can prove AC, the Axiom of Choice, so we may be confident that it will never lead us to a contradiction either.
So, are GCH and AC true, then? That is not the question Gödel answered. He only showed that assuming them, together with the other ordinary axioms of mathematics, won’t lead to a contradiction. To make them “true” in some stronger sense, we would want to be able to show that not assuming them (that is, assuming their opposite) would lead to a contradiction. However, in 1963 the mathematician Paul Cohen did just the opposite of that. Like Gödel, he built a model of set theory, but unlike in the previous case, this model supported the negation of GCH and AC, while still supporting the other axioms of set theory. This showed that both statements are independent, that is, that neither they nor their negations can be established by the known axioms of mathematics. So far as current mathematics is concerned, you are free to choose.
So, are GCH and AC true, then, or what? That question cannot presently be answered. Some believe that there is no answer; that the question is essentially meaningless. They believe such a question is just like asking if Euclid’s parallels postulate is “true” or not—just choose as you like, and you’ll get a Euclidean or non-Euclidean geometry, accordingly. Others, however, can’t escape the feeling that, in some real sense, GCH and AC are either true or they are not true, and we just don’t know enough now to decide. And thus the work that Gödel began more than 80 years ago looks to keep mathematicians well occupied for many more years to come.
