{"id":6754,"date":"2022-10-12T16:52:31","date_gmt":"2022-10-12T21:52:31","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=6754"},"modified":"2022-10-14T16:36:13","modified_gmt":"2022-10-14T21:36:13","slug":"explanation-godel-and-plausibility-godel","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=6754","title":{"rendered":"Explanation-G\u00f6del and Plausibility-G\u00f6del"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Here&#8217;s an observation that&#8217;s mathematically trivial but might not be widely appreciated.  In kindergarten, we all learned G\u00f6del&#8217;s First <a href=\"https:\/\/en.wikipedia.org\/wiki\/G%C3%B6del%27s_incompleteness_theorems\">Incompleteness Theorem<\/a>, which given a formal system F, constructs an arithmetical encoding of<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">G(F) = &#8220;This sentence is not provable in F.&#8221;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">If G(F) is true, then it&#8217;s an example of a true arithmetical sentence that&#8217;s unprovable in F.  If, on the other hand, G(F) is false, then it&#8217;s provable, which means that F isn&#8217;t arithmetically sound.  Therefore F is either incomplete or unsound.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Many have objected: &#8220;but despite G\u00f6del&#8217;s Theorem, it&#8217;s still easy to <em>explain <\/em>why G(F) is true.  In fact, the argument above basically already did it!\u201d<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">[Note: Please stop leaving comments explaining to me that G(F) follows from F\u2019s consistency.  I understand that: the \u201cheuristic\u201d part of the argument <em>is<\/em> F\u2019s consistency!  I made a pedagogical choice to elide that, which nerd-sniping has now rendered untenable.]<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">You might make a more general point: there are many, many mathematical statements for which we currently lack a proof, but we do seem to have a fully convincing heuristic explanation: one that &#8220;proves the statement to physics standards of rigor.&#8221;  For example:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The <a href=\"https:\/\/en.wikipedia.org\/wiki\/Twin_prime\">Twin Primes Conjecture<\/a> (there are infinitely many primes p for which p+2 is also prime).  <\/li><li>The <a href=\"https:\/\/en.wikipedia.org\/wiki\/Collatz_conjecture\">Collatz Conjecture<\/a> (the iterative process that maps each positive integer n to n\/2 if n is even, or to 3n+1 if n is odd, eventually reaches 1 regardless of which n you start at).  <\/li><li>\u03c0 is a <a href=\"https:\/\/en.wikipedia.org\/wiki\/Normal_number\">normal number<\/a> (or even just: the digits 0-9 all occur with equal limiting frequencies in the decimal expansion of \u03c0).<\/li><li><a href=\"https:\/\/math.stackexchange.com\/questions\/159350\/why-is-it-hard-to-prove-whether-pie-is-an-irrational-number\">\u03c0+e<\/a> is irrational.<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">And so on.  No one has any idea how to prove any of the above statements&#8212;and yet, just on statistical grounds, it seems clear that it would require a ludicrous conspiracy to make any of them false.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Conversely, one could argue that there are statements for which we <em>do<\/em> have a proof, even though we lack a &#8220;convincing explanation&#8221; for the statements&#8217; truth.  Maybe the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Four_color_theorem\">Four-Color Theorem<\/a> or <a href=\"https:\/\/en.wikipedia.org\/wiki\/Kepler_conjecture\">Hales&#8217;s Theorem<\/a>, for which every known proof requires a massive computer enumeration of cases, belong to this class.  Other people might argue that, given a proof, an explanation could always be extracted with enough time and effort, though resolving this dispute won&#8217;t matter for what follows.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">You might hope that, even if some true mathematical statements can&#8217;t be <em>proved<\/em>, every true statement might nevertheless have a <em>convincing heuristic explanation<\/em>.  Alas, a trivial adaptation of G\u00f6del&#8217;s Theorem shows that, if (1) heuristic explanations are to be checkable by computer, and (2) only true statements are to have convincing heuristic explanations, then this isn&#8217;t possible either.  I mean, let E be a program that accepts or rejects proposed heuristic explanations, for statements like the Twin Prime Conjecture or the Collatz Conjecture.  Then construct the sentence<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">S(E) = &#8220;This sentence has no convincing heuristic explanation accepted by E.&#8221;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">If S(E) is true, then it&#8217;s an example of a true arithmetical statement without <em>even<\/em> a convincing heuristic explanation for its truth (!).  If, on the other hand, S(E) is false, then there&#8217;s a convincing heuristic explanation of its truth, which means that something has gone wrong.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">What&#8217;s happening, of course, is that given the two conditions we imposed, our &#8220;heuristic explanation system&#8221; <em>was<\/em> a proof system, even though we didn&#8217;t call it one.  This is my point, though: when we use the word &#8220;proof,&#8221; it normally invokes a specific image, of a sequence of statements that marches from axioms to a theorem, with each statement following from the preceding ones by rigid inference rules like those of first-order logic.  None of that, however, plays any direct role in the proof of the Incompleteness Theorem, which cares only about soundness (inability to prove falsehoods) and checkability by a computer (what, with hindsight, G\u00f6del&#8217;s &#8220;arithmetization of syntax&#8221; was all about).  The logic works for &#8220;heuristic explanations&#8221; too.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Now we come to something that I picked up from my former student (and now AI alignment leader) <a href=\"https:\/\/paulfchristiano.com\/\">Paul Christiano<\/a>, on a recent trip to the Bay Area, and which I share with Paul&#8217;s kind permission.  Having learned that there&#8217;s no way to mechanize even heuristic explanations for all the true statements of arithmetic, we could set our sights lower still, and ask about mere <em>plausibility arguments<\/em>&#8212;arguments that might be overturned on further reflection.  Is there some sense in which every true mathematical statement at least has a good plausibility argument?<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Maybe you see where this is going.  Letting P be a program that accepts or rejects proposed plausibility arguments, we can construct<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">S(P) = &#8220;This sentence has no argument for its plausibility accepted by P.&#8221;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">If S(P) is true, then it&#8217;s an example of a true arithmetical statement without even a plausibility argument for its truth (!).  If, on the other hand, S(P) is false, then there <em>is<\/em> a plausibility argument for it.  By itself, this is <em>not at all<\/em> a fatal problem: all sorts of false statements (IP\u2260PSPACE, switching doors doesn&#8217;t matter in <a href=\"https:\/\/en.wikipedia.org\/wiki\/Monty_Hall_problem\">Monty Hall<\/a>, Trump couldn&#8217;t possibly become president&#8230;) have had decent plausibility arguments.  Having said that, it&#8217;s pretty strange that you can have a plausibility argument that&#8217;s immediately contradicted by its own existence!  This rules out some properties that you might want your &#8220;plausibility system&#8221; to have, although maybe a plausibility system exists that&#8217;s still nontrivial and that has weaker properties.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Anyway, I don&#8217;t know where I&#8217;m going with this, or even why I posted it, but I hope you enjoyed it!  And maybe there&#8217;s something to be discovered in this direction.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Here&#8217;s an observation that&#8217;s mathematically trivial but might not be widely appreciated. In kindergarten, we all learned G\u00f6del&#8217;s First Incompleteness Theorem, which given a formal system F, constructs an arithmetical encoding of G(F) = &#8220;This sentence is not provable in F.&#8221; If G(F) is true, then it&#8217;s an example of a true arithmetical sentence that&#8217;s [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[12],"tags":[],"class_list":["post-6754","post","type-post","status-publish","format-standard","hentry","category-metaphysical-spouting"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/6754","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=6754"}],"version-history":[{"count":3,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/6754\/revisions"}],"predecessor-version":[{"id":6761,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/6754\/revisions\/6761"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=6754"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=6754"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=6754"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}