International Journal of Computers, Communications & Control Vol. I (2006), No. 1, pp. 69-71 “Logic will never be the same again” - Kurt Gödel Centenary Gabriel Ciobanu Kurt Gödel (1906 - 1978) Kurt Gödel was born on 28th of April 1906 in Brno, which was at that time a city of the Austrian-Hungarian Monarchy. This year we celebrate the 100th birthday of Kurt Gödel, perhaps the greatest logician of the twentieth century. We mark this event by a short article on his life and scientific results. Kurt Gödel enrolled at the University of Vienna in 1923, and his scientific evolution is strongly related to the cultural environment of Vienna. As a student, Gödel became interested in mathematical logic, the field to which he made his major contributions. During that period, under the strong influence of David Hilbert, the mathematicians were concerned about the consistency and completeness of the formal systems used in mathematics. Hilbert has noticed the strong relationship between logic and mathematics; he argued in favor of an axiomatic approach, believing that all of mathematics can be formulated based on a logical foundation, and each result in mathematics follows from a system of axioms. Moreover, such an axiom system can be proved to be consistent. A formal system S is consistent whenever no contradiction is provable from S, and it is complete whenever every sentence A is decided by S in the sense that either S proves A, or S proves A. If neither A nor A is provable in S, then A is undecidable by S, and S is said to be incomplete. In his doctoral dissertation, Gödel proved the completeness of first-order predicate logic, that states that any logically valid formula is provable, i.e., any sentence that holds in every model of the first-order predicate logic is derivable in the logic. The completeness theorem is an important property of first-order predicate logic. It does not hold for all logics; for instance, second-order predicate logic does not have a completeness theorem. This result was published in 1930, in “Die Vollstandigkeit der Axiome des logischen Funktionenkalkuls”, Monatshefte f.Math. 37, p.349-360. In 1930 Gödel became a member of the University of Vienna (where he remains until 1938, the year when Austria became part of nazi Germany). In 1931, at only 25 years old, Gödel proved his most famous results, the incompleteness theorems. The first incompleteness theorem is perhaps the most surprising result in mathematical logic. It states that for any consistent formal theory that proves basic arithmetical truths, it is possible to construct an arithmetical statement Copyright c© 2006 by CCC Publications 70 Gabriel Ciobanu that is true, but not provable in the theory. That is, any consistent theory of a certain expressive strength cannot prove everything which is true, i.e. such theories are necessarily incomplete. The second incompleteness theorem states that for any formal theory S including basic arithmetical truths and certain truths about formal provability, S includes a statement of its own consistency if and only if S is inconsistent. These results showed that Hilbert’s program is impossible. They were first announced by Gödel at a meeting in 1930 at Koenigsberg, where also Hilbert and von Neumann were present, and it was published in 1931 as “Uber formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme”, in I.Monatsh.Math.Phys. 38, p.173-198. This paper is elegantly organized and clearly presented, progressing efficiently with no wasted energy devoted to collateral aspects. Godel’s incompleteness results were simply unexpected, and their proofs, though involving new techniques, are not very difficult. Their relevance to mathematical logic and in the theory of computation is preeminent and dominant. Their relevance to philosophy is important, even though it is not clear yet in what way and how the things will evolve. In the philosophy of mind, Lucas-Penrose arguments that the human mind does not work on mechanical principles in mathematics use the incompleteness theorem. The second incompleteness theorem has prompted theologians and postmodernists to reflect why mathematics cannot prove its own consistency. Gödel’s results has also interesting interpretations in the language of computer science. On the other hand, the impact of Gödel’s incompleteness results among working mathematicians is not impressive. The mathematicians, although generally aware of the theoretical possibility that a problem they are working on may be unsolvable in the current axiomatic framework of mathematics, do not have difficulties in using their field results in order to find a solution. In mathematics, Gödel’s incompleteness results show that in many cases, such as in number theory or real analysis, it is not possible to create a complete and consistent finite list of axioms, or even an infinite list that can be produced by a computer program. Each time you add a statement as an axiom, there are other true statements which still cannot be proved as true, even with the new axiom. Furthermore if the system can prove that it is consistent, then it is inconsistent. In his book “From Here to Infinity”, Ian Stewart expresses this by saying that “Gödel showed that if anyone finds a proof that arithmetic is consistent, then it isn’t!”. In 1935 Gödel established the relative consistency of the axiom of choice, and in 1938 that of the generalized continuum hypothesis; these results are published in “The consistency of the axiom of choice and of the general- ized continuum-hypothesis”, Proc.Nat.Acad.Sci.USA 24, p.556-557, 1938. In 1940 Gödel took a position at the Institute for Advanced Study in Princeton. At Princeton University Press he published “Consistency of the axiom of choice and of the generalized continuum-hypothesis with the axioms of set theory” where he introduced the constructible universe, a model of the set theory in which the only sets which exist are those which can be constructed from simpler sets. In such a constructible universe both the axiom of choice and the generalized continuum hypothesis are true, and therefore the model should be consistent. During his many years at Princeton, Gödel’s interests turned to philosophy and physics. At Princeton Godel had a legendary friendship with Einstein. Regarding their walks to and from the Institute for Advanced Studies, “Logic will never be the same again” - Kurt Gödel Centenary 71 Einstein said that “his own work no longer meant much; he came to the Institute merely to have the privilege of walking home with Gödel”. Gödel demonstrated the existence of some paradoxical solutions to Einstein’s field equations in general relativity. Gödel’s “rotating universes” allow time travel, and caused Einstein to have doubts about his own theory. In the early 1970s Gödel wrote an ontological proof of God’s existence. Due to his psychological disorder, in late 1977 Gödel refused to eat, and thus he died of starvation in January 1978. An extensive biography of Gödel can be found at the MacTutor History of Mathematics archive at http://www- gap.dcs.st-and.ac.uk/ history/Mathematicians/ Gödel.html, which also provides a list of papers. “Kurt Gödel Col- lected Works” were published in five volumes at Oxford University Press (S. Feferman et al., editors). An international symposium celebrating the 100th birthday of Kurt Godel was organized between 27 and 29 April 2006 by the Kurt Gödel Society and University of Vienna. This symposium commemorated the life, work, and foundational views of Kurt Gödel, exploring also the current research and ideas in the fields of the logic, math- ematics, and computer science. The symposium has attracted important scientific personalities: P.Cohen (Fields Medal), S.Feferman (main editor of “Collected Works”), H.Putnam (Harvard), H.Woodin (Berkeley), G.Kreisel (FRS), D.Scott (Turing Award), A.Wigderson (Nevanlinna Prize), C.Papadimitriou (Knuth Prize), J.D.Barrow (Kelvin Medal), R.Penrose (Wolf Prize). The talks presented various aspects related to logic, mathematics, com- puter science, artificial intelligence, cosmology, philosophy, and theology. There were a lot of discussions, includ- ing difficult questions, debatable answers, and polemics. According to a selection process, two submissions of Romanian authors were accepted to be presented at this symposium: G.Ciobanu (Iasi) with a paper regarding a new characterization of computable real numbers, and L.Leustean (Darmstadt) with a paper on “proof mining”, a technique of getting new knowledge from proofs in mathematics. The volumes devoted to this symposium will be published in the series Collegium Logicum of the Kurt Gödel Society, and by Cambridge University Press. Gabriel Ciobanu http://thor.info.uaic.ro/ gabriel E-mail: gabriel@iit.tuiasi.ro Editor’s note about the author: Gabriel Ciobanu Institute of Computer Science Romanian Academy, Iaşi Born: 5 July 1957, Piatra Neamţ. Dr. Gabriel Ciobanu has wide ranging interests in computing including Distributed Systems, Theory of Pro- gramming and Computational Aspects in Biology (molecular interac- tion, membrane computing). He has edited/authored 6 books and over 100 papers on these topics. He enjoy developing new ideas, both the practical ones and the more abstract ones, drawing on both his com- puter science and mathematical background. Over the years he has re- ceived public recognition for his research, including the 2004 “Octav Mayer” Award, and the 2000 “Grigore Moisil” Award of the Romanian Academy of Sciences. He was a visiting academic to Edinburgh Uni- versity, Paris XI, Tohoku University, and National University of Singa- pore, among others. He is a member of some professional associations and societies (EATCS, EAPLS, AMS, ISCB), and he have been in the program committees for many international conferences.