标 题: Re: 对Godel教授的纪念

发信站: 南京大学小百合站 (Mon May 1 11:42:56 2006)

If the Peano's arithmetic is consistent, then the consistency of the Peano's a

rithmetic cannot be proved, but the disproveness is provable.

宋公的话

发信人: Doubling (且听风吟), 信区: D_Computer 标 题: 对Godel教授的纪念 发信站: 南京大学小百合站 (Mon May 1 01:06:31 2006) 4月28日 对于我们 其实是个大日子 相当于3月14日之于学物理的 是一个“让人感到无助的”人的诞辰100周年 Kurt Godel 冯.诺依曼对普林斯顿抱怨： “如果他都不能当教授，我们这些人怎么可以当教授” 爱因斯坦曾经对朋友们表示： 我自己的研究已经不重要，我呆在普林斯顿是为了享受陪伴Godel教授步行回家 Kurt Godel 哥德爾 来源（http://episte.math.ntu.edu.tw/people/p_godel/） Godel（1906～1978）生於現捷克之 Brno，卒於普林斯頓。Godel 是廿世紀最偉大之數理 邏輯學家，其不完備定理是廿世紀最具啟發性的思想發現之一。 Godel 自小便很好奇，青少年時即對數學、哲學、語言與歷史產生極大的研究熱誠。他在 維也納大學原主修理論物理，後轉回數學，並參與 Schlick（石里克）領導的「維也納學 圈」，對數學與科學作本質的哲學探索，1928年因聽了 Brouwer 的演講，乃致力於數理邏 輯的研究。 自19世紀中，由於非歐幾何的確立、分析嚴格化的要求與羅素悖論的出現，數學基礎的問 題吸引許多一流數學家的眼光，當時數學∕哲學家熱切地想將數學確定性的大廈奠基於某 種不可懷疑的基礎上，雖然多數人都很樂觀，但是從 Hilbert 與 Ackermann 在1928年提 出下列的未解問題：「一階邏輯是否完備(complete)或可決定(decidable)？」，顯示整個 基礎化計畫的進度十分緩慢。 1929/30年 Godel 初試啼聲，漂亮地在他的博士論文中證明一階邏輯的完備性，給 Hilbe rt 的計畫打下一劑強心針，但是不久後(1931)，Godel 卻證明了他最知名的「不完備定理 」： 設S為一包含算術系統的公理系統，若 S 相容（consistent，即不自我矛盾），則 S 不完 備（即在 S 中有些敘述為真，卻無法由 S 的公理推導出來）。 徹底崩毀了基礎化計畫。這一前一後兩個關於完備性的定理，使數學界（尤其是 Hilbert 學派）戲劇性地經歷烈火寒冰般的巨變。Godel 也因此聲名如日中天。1933年他應邀訪美 講學演說，此行他結識日後的摯友愛因斯坦。 30年代的歐洲瀰漫著法西斯的氣氛，Godel 亦師亦友的 Schlick 也因此被刺殺，這個噩耗 使他陷入精神沮喪，終其一生困擾著他的研究生活。大戰前夕，他完成另一個重要的工作 ─證明選擇公理與連續統假設皆與ZF集合論相容。1940年他經由俄羅斯、日本到達美國， 從此定居於普林斯頓。 Godel 在美國的研究重心，逐漸轉移到其他方面。由於與愛因斯坦時相往來，40年代末， Godel 致力於探討廣義相對論與時間的意義，證明循環時間與愛因斯坦方程並無矛盾（他 還因此在1950年的國際數學家會議提出報告）。另外，Godel 一直從事於哲學的深度思考 ，專心研讀 Leibniz、康德、Husserl（胡賽爾）等的著作，留下的哲學思考筆記無數，還 沒有充分地編註印行。Godel 晚年（1971年起）時常與華裔邏輯∕哲學家王浩討論，並因 而促成王浩撰寫《Reflection on Kurt Godel》的佳話。 Godel 個人包辦了數理邏輯幾個經典定理，並為整個領域帶來革命性的風貌，堪稱是廿世 紀最偉大的數理邏輯學家。尤其是他的「不完備定理」，由於暗示了一個理性系統不可能 是全知的想法，經常被引申（或過度引申）到其他領域。例如：自然是無法被人類瞭解； 語言是沒有界限的；心靈無法認識自己等。非科學家最常引用的數學定理，竟然如此晦澀 ，也該算是廿世紀的數學奇談了。 本文參考資料：（1）王浩，《Reflection on Kurt Godel》（2）大英百科全書 。（3） MacTutor 數學史檔案網站：Godel。 发信人: iamanisland (cure), 信区: D_Computer 标 题: Re: 对Godel教授的纪念 发信站: 南京大学小百合站 (Mon May 1 02:18:31 2006) Kurt Gödel 引自 The Time 100, Monday, March 29, 1999 Kurt Gödel was born in 1906 in Brunn, then part of the Austro-Hungarian E mpire and now part of the Czech Republic, to a father who owned a textile fact ory and had a fondness for logic and reason and a mother who believed in start ing her son's education early. By age 10, Gödel was studying math, religi on and several languages. By 25 he had produced what many consider the most im portant result of 20th century mathematics: his famous "incompleteness theorem ." Gödel's astonishing and disorienting discovery, published in 1931, pro ved that nearly a century of effort by the world's greatest mathematicians was doomed to failure. To appreciate Gödel's theorem, it is crucial to understand how mathematic s was perceived at the time. After many centuries of being a typically sloppy human mishmash in which vague intuitions and precise logic coexisted on equal terms, mathematics at the end of the 19th century was finally being shaped up. So-called formal systems were devised (the prime example being Russell and Wh itehead's Principia Mathematica) in which theorems, following strict rules of inference, sprout from axioms like limbs from a tree. This process of theorem sprouting had to start somewhere, and that is where the axioms came in: they w ere the primordial seeds, the Ur-theorems from which all others sprang. The beauty of this mechanistic vision of mathematics was that it eliminated al l need for thought or judgment. As long as the axioms were true statements and as long as the rules of inference were truth preserving, mathematics could no t be derailed; falsehoods simply could never creep in. Truth was an automatic hereditary property of theoremhood. The set of symbols in which statements in formal systems were written generall y included, for the sake of clarity, standard numerals, plus signs, parenthese s and so forth, but they were not a necessary feature; statements could equall y well be built out of icons representing plums, bananas, apples and oranges, or any utterly arbitrary set of chicken scratches, as long as a given chicken scratch always turned up in the proper places and only in such proper places. Mathematical statements in such systems were, it then became apparent, merely precisely structured patterns made up of arbitrary symbols. Soon it dawned on a few insightful souls, Gödel foremost among them, that this way of looking at things opened up a brand-new branch of mathematics — namely, metamathematics. The familiar methods of mathematical analysis could b e brought to bear on the very pattern-sprouting processes that formed the esse nce of formal systems — of which mathematics itself was supposed to be the pr imary example. Thus mathematics twists back on itself, like a self-eating snak e. Bizarre consequences, Gödel showed, come from focusing the lens of mathem atics on mathematics itself. One way to make this concrete is to imagine that on some far planet (Mars, let's say) all the symbols used to write math books happen — by some amazing coincidence — to look like our numerals 0 through 9 . Thus when Martians discuss in their textbooks a certain famous discovery tha t we on Earth attribute to Euclid and that we would express as follows: "There are infinitely many prime numbers," what they write down turns out to look li ke this: "84453298445087 87863070005766619463864545067111." To us it looks lik e one big 46-digit number. To Martians, however, it is not a number at all but a statement; indeed, to them it declares the infinitude of primes as transpar ently as that set of 34 letters constituting six words a few lines back does t o you and me. Now imagine that we wanted to talk about the general nature of all theorems of mathematics. If we look in the Martians' textbooks, all such theorems will lo ok to our eyes like mere numbers. And so we might develop an elaborate theory about which numbers could turn up in Martian textbooks and which numbers would never turn up there. Of course we would not really be talking about numbers, but rather about strings of symbols that to us look like numbers. And yet, mig ht it not be easier for us to forget about what these strings of symbols mean to the Martians and just to look at them as plain old numerals? By such a simple shift of perspective, Gödel wrought deep magic. The G&ou ml;delian trick is to imagine studying what might be called "Martian-producibl e numbers" (those numbers that are in fact theorems in the Martian textbooks), and to ask questions such as, "Is or is not the number 8030974 Martian-produc ible (M.P., for short)?" This question means, Will the statement '8030974' eve r turn up in a Martian textbook? Gödel, in thinking very carefully about this rather surreal scenario, soo n realized that the property of being M.P. was not all that different from suc h familiar notions as "prime number," "odd number" and so forth. Thus earthbou nd number theorists could, with their standard tools, tackle such questions as , "Which numbers are M.P. numbers, and which are not?" for example, or "Are th ere infinitely many non-M.P. numbers?" Advanced math textbooks — on Earth, an d in principle on Mars as well — might have whole chapters about M.P. numbers . And thus, in one of the keenest insights in the history of mathematics, Gö ;del devised a remarkable statement that said simply, "X is not an M.P. number " where X is the exact number we read when the statement "X is not an M.P. num ber" is translated into Martian math notation. Think about this for a little w hile until you get it. Translated into Martian notation, the statement "X is n ot an M.P. number" will look to us like just some huge string of digits — a v ery big numeral. But that string of Martian writing is our numeral for the num ber X (about which the statement itself talks). Talk about twisty; this is rea lly twisty! But twists were Gödel's specialty — twists in the fabric of space-time, twists in reasoning, twists of all sorts. By thinking of theorems as patterns of symbols, Gödel discovered that it is possible for a statement in a formal system not only to talk about itself, but also to deny its own theoremhood. The consequences of this unexpected tang le lurking inside mathematics were rich, mind-boggling and — rather oddly — very sad for the Martians. Why sad? Because the Martians--like Russell and Whi tehead — had hoped with all their hearts that their formal system would captu re all true statements of mathematics. If Gödel's statement is true, it i s not a theorem in their textbooks and will never, ever show up — because it says it won't! If it did show up in their textbooks, then what it says about i tself would be wrong, and who — even on Mars — wants math textbooks that pre ach falsehoods as if they were true? The upshot of all this is that the cherished goal of formalization is revealed as chimerical. All formal systems — at least ones that are powerful enough t o be of interest — turn out to be incomplete because they are able to express statements that say of themselves that they are unprovable. And that, in a nu tshell, is what is meant when it is said that Gödel in 1931 demonstrated the "incompleteness of mathematics." It's not really math itself that is incom plete, but any formal system that attempts to capture all the truths of mathem atics in its finite set of axioms and rules. To you that may not come as a sho ck, but to mathematicians in the 1930s, it upended their entire world view, an d math has never been the same since. Gödel's 1931 article did something else: it invented the theory of recurs ive functions, which today is the basis of a powerful theory of computing. Ind eed, at the heart of Gödel's article lies what can be seen as an elaborat e computer program for producing M.P. numbers, and this "program" is written i n a formalism that strongly resembles the programming language Lisp, which was n't invented until nearly 30 years later. Gödel the man was every bit as eccentric as his theories. He and his wife Adele, a dancer, fled the Nazis in 1939 and settled at the Institute for Adva nced Study in Princeton, where he worked with Einstein. In his later years G&o uml;del grew paranoid about the spread of germs, and he became notorious for c ompulsively cleaning his eating utensils and wearing ski masks with eye holes wherever he went. He died at age 72 in a Princeton hospital, essentially becau se he refused to eat. Much as formal systems, thanks to their very power, are doomed to incompleteness, so living beings, thanks to their complexity, are do omed to perish, each in its own unique manner. Douglas Hofstadter is the Pulitzer-prizewinning author ofGödel, Escher, Bach