Modern Logic: From Frege to Gödel: Gödel

views updated

MODERN LOGIC: FROM FREGE TO GÖDEL: GöDEL

Kurt Gödel (1906–1978), a major figure in the history of logic, is best known for his celebrated incompleteness theorem presented in "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" (Monatshefte für Mathematik und Physik 38 [1931]: 173–198) and his associated proof of the impossibility of establishing the consistency of customary formulations of arithmetic by methods formalizable within the systems themselves. In addition to these results (discussed in the entry Gödel's Theorem), Gödel made important contributions to several other branches of logic, and prior to his 1931 paper he had already presented the first completeness proof for the first-order functional calculus (in "Die Völlstandigkeit der Axiome des logischen Funktionkalküls," Monatshefte für Mathematik und Physik 37[1930]: 349–360). Making use of a normal form devised by Thoralf Skolem, Gödel elaborated a proof along lines that were followed by Jacques Herbrand to a similar end in a publication of the same year (Recherches sur la théorie de la démonstration, in Travaux de la Société des Sciences et des Lettres de Varsovie, Classe III [33] [1930]: 33–160), but he went further than Herbrand in his method for showing how any unprovable formula may be falsified.

Intuitionistic as well as classical logic has been one of Gödel's major concerns, and his results in this field are of importance to an understanding of the formalizations of this logic initiated by Arend Heyting in 1930. The intuitionist propositional calculus is naturally thought of as a subsystem of classical logic, obtained by omitting from the latter those theses that are intuitionistically unacceptable. Gödel indicated that this picture could in a sense be reversed, since it is possible to define all two-valued truth-functions by means of the connectives for negation and conjunction, and he was able to show that any formula involving only these connectives is provable within intuitionistic logic if it is provable classically. Gödel showed, further, that even classical number theory, if suitably interpreted, can be thought of as included within intuitionistic number theory. He also proved that the intuitionist propositional calculus has no finite characteristic matrix. That is, although the two-valued truth tables for classical logic serve to verify all and only those theses provable in this logic, it is impossible, according to Gödel's result, to devise truth tables having any finite number of values that will perform the same service for the intuitionist system.

Two propositions that have been at the center of much investigation and controversy are the axiom of choice and Cantor's generalized continuum hypothesis. It was Gödel who proved that both are consistent with the axioms of set theory provided only that these axioms are themselves consistent. The axiom of choice is a highly nonconstructive axiom licensing the selection of an unspecified element from each of a (possibly infinite) family of sets and the formation of a set comprising just the elements so selected. The generalized continuum hypothesis, which in fact implies the axiom of choice, states that 2^ℵ_α = ℵ_{α + 1}; that is, starting with ℵ₀, which is the number of the natural numbers, the series of increasingly higher cardinals is successively generated by raising 2 to the power of the preceding aleph. The system Σ of set theory that Gödel used derives from John von Neumann and Paul Bernays. Gödel showed that if it were possible to derive a contradiction from the axiom of choice and the continuum hypothesis in Σ, then the axioms of Σ alone would suffice for the derivation of a contradiction. This result is obtained by constructing a model Δ within Σ itself, where Δ is such that the propositions asserting that the axioms of Σ hold for Δ are demonstrable in Σ and the similar relativizations to Δ of the axiom of choice and the generalized continuum hypothesis are likewise demonstrable in Σ. Paul J. Cohen showed, in 1963, that the negations of these propositions are also consistent with the axioms of set theory. In other words, the axiom of choice and the generalized continuum hypothesis are now known to be independent of the other axioms of set theory.