{"id":13,"date":"2008-11-25T16:20:57","date_gmt":"2008-11-25T20:20:57","guid":{"rendered":"http:\/\/blogs.williams.edu\/Morgan\/?p=13"},"modified":"2011-06-15T10:13:49","modified_gmt":"2011-06-15T15:13:49","slug":"godels-incompleteness-theorem","status":"publish","type":"post","link":"https:\/\/sites.williams.edu\/Morgan\/2008\/11\/25\/godels-incompleteness-theorem\/","title":{"rendered":"G\u00f6del’s Incompleteness Theorem"},"content":{"rendered":"

My senior seminar on “The Big Questions” asked me for a succinct explanation of G\u00f6del’s Incompleteness Theorem, a radical result which I’m beginning to think is a simple one.G\u00f6del’s Incompleteness Theorem says roughly that in any consistent model including arithmetic, there are true statements which cannot be proved. The idea of the proof is to consider the statement:<\/p>\n

“This statement cannot be proved.”<\/p>\n

If it could be proved, what it says would be true, and it says it cannot be proved. Hence it is unprovable and therefore what it says is true.<\/p>\n

The trouble with this proof is that the statement is self-referential. Mathematicians and logicians long ago discovered that unregulated self-reference leads to contradictions and outlawed it.<\/p>\n

G\u00f6del’s proof begins by encoding every statement by a natural number, called the G\u00f6del number of the statement. For example, the statement “n is even” might be encoded by some huge G\u00f6del number g:<\/p>\n

S_g(n) = “n is even.”<\/p>\n

Now consider the weird statement “S_n(n) is not provable.” It is encoded by some G\u00f6del number N:<\/p>\n

S_N(n) = “S_n(n) is not provable.”<\/p>\n

Now look what follows by taking n = N:<\/p>\n

S_N(N) = “S_N(N) is not provable.”<\/p>\n

Without violating the axioms, G\u00f6del has presented a statement which accidentally refers to itself. As before, it is unprovable and hence true.<\/p>\n","protected":false},"excerpt":{"rendered":"

My senior seminar on “The Big Questions” asked me for a succinct explanation of G\u00f6del’s Incompleteness Theorem, a radical result which I’m beginning to think is a simple one.<\/p>\n","protected":false},"author":269,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[14043],"tags":[],"class_list":["post-13","post","type-post","status-publish","format-standard","hentry","category-math"],"acf":[],"_links":{"self":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/posts\/13","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/users\/269"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/comments?post=13"}],"version-history":[{"count":1,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/posts\/13\/revisions"}],"predecessor-version":[{"id":654,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/posts\/13\/revisions\/654"}],"wp:attachment":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/media?parent=13"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/categories?post=13"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/tags?post=13"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}