Tuesday, May 27, 2008

Gödel's Incompleteness Theorem: The Most Important Mathematical Theorem in the Twentieth Century

Below is a photo the late mathematical genius Kurt Gödel (left) with Albert Einstein. Gödel's Incompleteness Theorem was the most important mathematical theorem in the twentieth century (its significance is explained in simple terms below). Among other things, Gödel's theorem proves no "Theory of Everything" in physics can ever achieve the status of certainty (this was only recently recognized by Stephen Hawking, as explained by Physicist and Philosopher of Science Stanley Jaki here.



The following material, which explains the mind-bending implications of this crucial theorem in simple terms, is reproduced from http://www.miskatonic.org/godel.html

From Jones and Wilson, An Incomplete Education:

"In 1931, the Czech-born mathematician Kurt Gödel demonstrated that within any given branch of mathematics, there would always be some propositions that couldn't be proven either true or false using the rules and axioms... of that mathematical branch itself. You might be able to prove every conceivable statement about numbers within a system by going outside the system in order to come up with new rules and axioms, but by doing so you'll only create a larger system with its own unprovable statements. The implication is that all logical system of any complexity are, by definition, incomplete; each of them contains, at any given time, more true statements than it can possibly prove according to its own defining set of rules.

"Gödel's Theorem has been used to argue that a computer can never be as smart as a human being because the extent of its knowledge is limited by a fixed set of axioms, whereas people can discover unexpected truths... It plays a part in modern linguistic theories, which emphasize the power of language to come up with new ways to express ideas. And it has been taken to imply that you'll never entirely understand yourself, since your mind, like any other closed system, can only be sure of what it knows about itself by relying on what it knows about itself."

From Boyer, History of Mathematics

"Gödel showed that within a rigidly logical system such as Russell and Whitehead had developed for arithmetic, propositions can be formulated that are undecidable or undemonstrable within the axioms of the system. That is, within the system, there exist certain clear-cut statements that can neither be proved or disproved. Hence one cannot, using the usual methods, be certain that the axioms of arithmetic will not lead to contradictions ... It appears to foredoom hope of mathematical certitude through use of the obvious methods. Perhaps doomed also, as a result, is the ideal of science - to devise a set of axioms from which all phenomena of the external world can be deduced."

From Nagel and Newman, Gödel's Proof

"He proved it impossible to establish the internal logical consistency of a very large class of deductive systems - elementary arithmetic, for example - unless one adopts principles of reasoning so complex that their internal consistency is as open to doubt as that of the systems themselves... Second main conclusion is... Gödel showed that Principia, or any other system within which arithmetic can be developed, is essentially incomplete. In other words, given any consistent set of arithmetical axioms, there are true mathematical statements that cannot be derived from the set... Even if the axioms of arithmetic are augmented by an indefinite number of other true ones, there will always be further mathematical truths that are not formally derivable from the augmented set."

From Rucker, Infinity and the Mind

"The proof of Gödel's Incompleteness Theorem is so simple, and so sneaky, that it is almost embarassing to relate. His basic procedure is as follows:
1. Someone introduces Gödel to a UTM, a machine that is supposed to be a Universal Truth Machine, capable of correctly answering any question at all.
2. Gödel asks for the program and the circuit design of the UTM. The program may be complicated, but it can only be finitely long. Call the program P(UTM) for Program of the Universal Truth Machine.
3. Smiling a little, Gödel writes out the following sentence: "The machine constructed on the basis of the program P(UTM) will never say that this sentence is true." Call this sentence G for Gödel. Note that G is equivalent to: "UTM will never say G is true."
4. Now Gödel laughs his high laugh and asks UTM whether G is true or not.
5. If UTM says G is true, then "UTM will never say G is true" is false. If "UTM will never say G is true" is false, then G is false (since G = "UTM will never say G is true"). So if UTM says G is true, then G is in fact false, and UTM has made a false statement. So UTM will never say that G is true, since UTM makes only true statements.
6. We have established that UTM will never say G is true. So "UTM will never say G is true" is in fact a true statement. So G is true (since G = "UTM will never say G is true").
7. "I know a truth that UTM can never utter," Gödel says. "I know that G is true. UTM is not truly universal."

Think about it - it grows on you... With his great mathematical and logical genius, Gödel was able to find a way (for any given P(UTM)) actually to write down a complicated polynomial equation that has a solution if and only if G is true. So G is not at all some vague or non-mathematical sentence. G is a specific mathematical problem that we know the answer to, even though UTM does not! So UTM does not, and cannot, embody a best and final theory of mathematics...

Although this theorem can be stated and proved in a rigorously mathematical way, what it seems to say is that rational thought can never penetrate to the final ultimate truth... But, paradoxically, to understand Gödel's proof is to find a sort of liberation. For many logic students, the final breakthrough to full understanding of the Incompleteness Theorem is practically a conversion experience. This is partly a by-product of the potent mystique Gödel's name carries. But, more profoundly, to understand the essentially labyrinthine nature of the castle is, somehow, to be free of it.

From Douglas Hofstadter, Gödel, Escher, and Bach

"All consistent axiomatic formulations of number theory include undecidable propositions... Gödel showed that provability is a weaker notion than truth, no matter what axiom system is involved... How can you figure out if you are sane? ...Once you begin to question your own sanity, you get trapped in an ever-tighter vortex of self-fulfilling prophecies, though the process is by no means inevitable. Everyone knows that the insane interpret the world via their own peculiarly consistent logic; how can you tell if your own logic is "peculiar' or not, given that you have only your own logic to judge itself? I don't see any answer. I am reminded of Gödel's second theorem, which implies that the only versions of formal number theory which assert their own consistency are inconsistent.

The other metaphorical analogue to Gödel's Theorem which I find provocative suggests that ultimately, we cannot understand our own mind/brains... Just as we cannot see our faces with our own eyes, is it not inconceivable to expect that we cannot mirror our complete mental structures in the symbols which carry them out? All the limitative theorems of mathematics and the theory of computation suggest that once the ability to represent your own structure has reached a certain critical point, that is the kiss of death: it guarantees that you can never represent yourself totally."

43 comments:

Quintessential said...

Very profound. Makes me think of The Limitations of Scientific Tuth by Nigel Brush.

catherinaogren said...

歲月的流失..................................................

世界 said...

路過~很有趣吶...........................................

紅包 said...

人應該做自己認為對的事,而不是一味跟著群眾的建議走。 ..................................................

九份 said...

good~ keep sharing with us, please....I will waiting your up date everyday!! Have a nice day........................................

lesson said...

far from eye, far from heart...................................................

與發 said...

若對自己誠實,日積月累,就無法對別人不忠了。........................................

陳石薇 said...

how do u do?xvideo打飛機專用網洪爺免費洪爺色情片洪爺貼圖區洪爺成人線上洪爺影城洪爺色論壇洪爺貼圖洪爺成年人網洪爺免費色情洪爺色情貼援交妹辣妹野球拳情色文學情趣聊天室性感辣妹裸體遊戲做愛偷拍一夜情視訊洪爺色情貼洪爺免費色情洪爺成年人網洪爺貼圖洪爺色論壇洪爺影城洪爺成人線上洪爺貼圖區洪爺色情片洪爺免費洪爺色情貼洪爺免費色情洪爺成年人網洪爺貼圖洪爺色論壇洪爺影城洪爺成人線上洪爺貼圖區洪爺色情片洪爺免費洪爺免費洪爺色情片洪爺貼圖區洪爺影城洪爺色論壇洪爺貼圖洪爺成年人網洪爺免費色情洪爺色情貼洪爺成人線上

瑜吟 said...

A片-殺很大 成人a影片論壇 kk777視訊俱樂部 avdvd情色影片 嘟嘟無碼a片情色 視訊聊天 視訊交友聊天室 avdvd無碼情色電影 卡通美女a片免費試看 小魔女免費影片3d 美女視訊免費看 哈拉網路成人區 jp成人jp58 avooo影音 a片天堂 ut影音視訊聊天室13077 aa免費影片 s383情色大網咖免費a片 網愛聊天室 hilive-免費影片 甜心寶貝貼影片 免費成人片觀賞 xvediox免費影片 sod特輯 sex520免費影片yawu uthome視訊聊天室 av女優王國 情色a片flashxyz utobe影片分享 小弟貼影片 bt成人 免費視訊美眉 A片-sex520 免費a片 獸皇影片分享區 小澤圓線上免費影片 女生自衛影片 日本a電影 okav成人影院 免費avdvd影片 免費線上影片 情色a片 免費無碼a片 小魔女影片交流 嘟嘟情人色網影片 華人色片 ol線上免費影片 葉子媚影片分享 色瞇瞇影片網 熟女人影片 金瓶影片交流區-無碼a片 免費影片-無碼a片 免費影片欣賞 aaaaa7777788 卡提諾成人 . . . .

嘉偉 said...

^^ 謝謝你的分享,祝你生活永遠多彩多姿!........................................

誠侑 said...

Better say nothing than nothing to the purpose. ........................................

香廷 said...

Say not all that you know, believe not all that you hear.......................................................

韋于倫成 said...

朝著既定的目標走,就不會迷失。..................................................

NealVa憲妤 said...

黑色豪門企業綜合娛樂論壇 ez洪爺的家 嘟嘟情人色網dvd hot辣妺視訊網 限制性漫畫 一夜情人視訊 av1688大天使娛樂網 bt成人網 go2av成人聊天室 免費a長片線上看,女優影片 無碼 av影片 美眉 美女 聊天室 遊戲區 18成人http 17hi tw 情色聊天 百分百貼圖區亞洲avdvd 免費視訊聊天mm17i 情色a片 88天下淫書,少年阿賓系列小說,中文情色文學小說 0401線上影城 視訊做愛 杜蕾斯成人 亞洲辣妹妹影音視訊聊天室 美女聊天室 麗的情色小遊戲 韓劇人妻的秘密85cc影城 playboy國際中文網 免費影音視訊hibb 6k情人網暗戀視訊 免費視訊4h 無碼av女優微風成人區 甜心寶貝直播貼片aio交友愛情館 xvediox免費影片 視訊交友520show net 視訊美女聊天 kk 台灣kiss911h影片線上a片 aaaa 片俱樂部 2girl女子拉拉學園 av168成人網 辣妹影片直播台南援交友留言 omyga美色女影城 go2av免費影片情色 網站 ut聊天室kww 情人視訊高雄網 性行為補給站 後宮視訊聊天網 網愛mmshow 主播情人視訊情色交友 104愛戀速配網 視訊美女聊天室 免費色咪咪影片網 兼職援交 影音視訊聊天室dudu sex

ShilaL_Kappler said...

若無一番寒徹骨,焉得梅花撲鼻香。 ............................................................

ShilaL_Kappler said...

原來這世上能跟你共同領略一個笑話的人竟如此難得 ............................................................

07_TeddyF_Silvey0 said...

當一個人內心能容納兩樣相互衝突的東西,這個人便開始變得有價值了。...........................................................................

張孟勳 said...

不要把生命看得太嚴肅,反正我們不會活著離開。............................................................

SadeRa盈君iford0412 said...

生活盡可低,志氣當高潔..............................

佳梅 said...

you did a good job..................................................

怡迪怡迪 said...

pleasure to find such a good artical! please keep update!!.................................................................

韋以韋以 said...

pleasure to find such a good artical! please keep update!!.................................................................

青卉青卉 said...

成熟,就是有能力適應生活中的模糊。.................................................................

吳婷婷 said...

當一個人內心能容納兩樣相互衝突的東西,這個人便開始變得有價值了。............................................................

姿柯瑩柯dgdd憶曾g智曾 said...

Failure is the mother of success...................................................

舜佳 said...

第一次來這裡 愛上你的部落格 感謝你的分享............................................................

李冠文 said...

單純喜歡你的部落格 留個言跟您問聲好~~............................................................

陳倩江陳倩江 said...

下次再來希望可以看到新的作品喔。............................................................

芸茂芸茂 said...

從來愛都不知它的深度,非得等到別離的時候.................................................................

宜欣宜欣 said...

美麗的事物是永恆的快樂,它的可愛日有增加,不會消逝而去................................................

蔡靜芳蔡靜芳 said...

開懷幸福的生活,是每個人的夢想~~希望大家都能夠實現!..................................................................

童祖如童祖如 said...

知識可以傳授,智慧卻不行。每個人必須成為他自己。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

家唐銘 said...

幸福不是一切,人還有責任。............................................................

家唐銘 said...

每日都有新日光,每日都有新希望。.................................................

秀李李迪秀李李迪 said...

閱讀您的BLOG文章,真是件快樂的事!!.................................................................

建邱勳 said...

好的開始並不代表會成功,壞的開始並不代表是失敗............................................................

老陆 said...

Drive carefully. It is not only cars that can be recalled by their Maker...................................................................

承王蓁 said...

Never put off till tomorrow what may be done today..................................................................

建枫 said...

等很久了 謝謝你的用心............................................................

木詹詹詹詹詹行詹詹 said...

善言能贏得聽眾,善聽才能贏得朋友。......................................................................

孫邦柔 said...

很耐斯的部落格,留言支持你繼續加油............................................................

黃英吳思潔吳思潔邦 said...

快樂,是享受工作過程的結果......................................................................

惠邱邱邱邱雯 said...

出遊不拘名勝,有景就是好的..................................................