Kurt Gödel was an Austrian-American logician and mathematician who was born in 1906 in the city of Brünn, in Austria-Hungary (now the city of Brno, in the Czech Republic). He studied and taught mathematics at the University of Vienna, where he participated in meetings of the Vienna Circle, the famous group of philosophers that included Moritz Schlick (1882-1936) and Rudolf Carnap (1891-1970). In 1931, at the age of 25, he published a proof that is now known as Gödel's Incompleteness Theorem and that demonstrated the existence of formally undecidable propositions in any formal system of arithmetic (such as that described by Alfred North Whitehead and Bertrand Russell in the Principia Mathematica).1 This theorem is one of the most famous theorems in modern mathematics.2 In 1939, Gödel and his wife Adele emigrated to the United States, where he became a member of the faculty of the Institute for Advanced Study in Princeton, N.J., and where he developed a close friendship with Albert Einstein. Gödel and his wife became U.S. citizens in 1948. He died in Princeton, N.J. in 1978.
One way of roughly summarizing Gödel's (First) Incompleteness Theorem, as described by the cognitive scientist Douglas Hofstadter (1999), is to say that it shows that any consistent axiomatic formulation of number theory includes undecidable propositions (propositions that can neither be proven nor be disproven within that axiomatic formulation).3
Another way of roughly summarizing Gödel's (First) Incompleteness Theorem, as described by the logician and mathematician Jean van Heijenoort (1967), is to say that it shows that in any formal system adequate for number theory, there are formulas that are neither provable nor disprovable. A corollary to this theorem is that the consistency of any formal system adequate for number theory cannot be proven within that system.4 No consistent formal system that is adequate for number theory can prove its own consistency. This is known as Gödel's Second Incompleteness Theorem.
Another way of roughly summarizing Gödel's (First) Incompleteness Theorem, as described by the logician and philosopher Geoffrey Hunter (1971), is to say that it shows that for any consistent system S of formal arithmetic, if S has decidable sets of formulas and proofs and contains representations of every decidable set of natural numbers, then S is incomplete.5 Thus, for any consistent system of formal arithmetic in which (1) the set of axioms and the rules of inference are recursively definable, and (2) every recursive relation is definable, there are undecidable arithmetical propositions of the form (x)Fx, where F is a recursively defined property of natural numbers.6
Another way of roughly summarizing Gödel's (First) Incompleteness Theorem, as described by the logician and philosopher Peter Suber (2002), is to say that it shows that any consistent formal system of arithmetic that is of sufficient strength (to have decidable sets of formulas and proofs and to represent every decidable set of natural numbers) is deductively incomplete.7 In other words, any consistent formal system of arithmetic that is of sufficient strength contains arithmetical propositions that are undecidable (that are neither provable nor disprovable within that system).
This means that within any consistent nontrivial formal system of arithmetic, there are arithmetical propositions that are true or false but that cannot be proven to be true or false within that system. The axioms and inference rules of any consistent nontrivial formal system of arithmetic are insufficient to decide the truth or falsehood of every arithmetical proposition expressible within that system. It is impossible to devise a consistent nontrivial system of formal arithmetic whose axioms and inference rules are complete enough to prove or disprove all the arithmetical propositions expressible within that system. No formal system of arithmetic that is of sufficient strength to have decidable sets of formulas and proofs and to represent every decidable set of natural numbers can be both consistent and deductively complete.8
Moreover, a consistent formal system adequate for number theory cannot prove its own consistency. It cannot guarantee that it will not contain some inconsistency.
This means that in order for every possible proposition expressible within a nontrivial formal system of arithmetic to be provable or disprovable, the system has to be in some way inconsistent. Deductive completeness within such a system must therefore come at the price of inconsistency. All consistent nontrivial formal systems of arithmetic are deductively incomplete.
The logician and philosopher Jaako Hintikka (1996) explains that it is important not to confuse the incompleteness of a nonlogical (mathematical) theory with the nonaxiomatizability of a logical theory.9 He also explains that it is important not to confuse deductive incompleteness (the inability of an axiomatic system to prove or disprove all propositions expressible within that system) with semantic incompleteness (the inability of an axiomatic system to express as theorems all logically valid sentences of the underlying language), or with descriptive incompleteness (the inability of a formal system to provide models of all the objects or sets of objects that it is asked to describe), or with Hilbertian incompleteness (the inability of an axiomatic system to provide a set of axiomatic models to which none can be added without violating the axioms of that system).
1Larousse Biographical Dictionary, ed. by Magnus Magnusson and Rosemary Goring (New York: Larousse, 1990), p. 598.
2Ibid., p. 598.
3Douglas R. Hofstadter, Gödel, Escher, Bach: An Eternal Goldren Braid (New York: Basic Books, 1999), p. 17.
4Jean van Heijenoort, "Gödel's Theorem," in The Encyclopedia of Philosophy, ed. by Paul Edwards, Vol. 3 (New York: MacMillan, 1967), p. 348.
5Geoffrey Hunter, Metalogic: An Introduction to the Metatheory of Standard First Order Logic (Berkeley: University of California Press, 1971), p. 228.
6Kurt Gödel, "On formally undecidable propositions of Principia Mathematica and related systems" [Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme," 1931] in Kurt Gödel Collected Works, Volume I, edited by Solomon Feferman, et al. (Oxford: Oxford University Press, 2004) p. 181.
7Peter Suber, "Glossary of First-Order Logic," (1999-2002), online at http://www.earlham.edu/~peters/courses/logsys/glossary.htm.
8Ibid.
9Jaako Hintikka, The Principles of Mathematics Revisited (Cambridge: Cambridge University Press, 1996), p. 91.
No comments:
Post a Comment