<story><title>Gödel, Escher, Bach: an in-depth explainer</title><url>https://www.alignmentforum.org/posts/wwNnzaPnB5a48K86N/book-review-goedel-escher-bach-an-in-depth-explainer</url></story><parent_chain><item><author>adastra22</author><text>I’ve only ever seen examples like the one you give here, which seem like trite, trivial, and uninteresting middle-school level logical gotchas. Are there actually interesting properties which are true but can’t be proven? Or is it just a statement about self-referential recursive logic being unprovable?</text></item><item><author>mreid</author><text>It might be easiest to give a sense of what &amp;quot;unprovable but true&amp;quot; means by way of an imagined example.&lt;p&gt;Goldbach&amp;#x27;s conjecture is that &amp;quot;every even number bigger than 2 is the sum of exactly two prime numbers&amp;quot;, so 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, etc.&lt;p&gt;For this statement to be *true* it just means that every even number there must exist two primes that add to that number. This is a statement about infinitely many integers.&lt;p&gt;A *proof* of Goldbach&amp;#x27;s conjecture consists of a finite number of formal reasoning steps that start with some axioms and end up at the statement of the result.&lt;p&gt;To this day, it seems as though Goldbach&amp;#x27;s conjecture is true. It holds for every number we&amp;#x27;ve been able to test. However, no one has proved it is true or false yet (or proved that it is unprovable).&lt;p&gt;The proof of Gödel&amp;#x27;s result&amp;#x27;s involves very carefully formalizing what statements and proofs mean so that they can be encoded as statements about arithmetic. He then shows there is a statement with encoding G that says &amp;quot;The statement with encoding G cannot be proved&amp;quot; – if it is true, then it cannot be proved.&lt;p&gt;It&amp;#x27;s kind of confusing at first, but there is an easier way to get an intuition why there might be true statements that cannot be proved. Think of each statement about the natural numbers as a subset where each number in the subset makes the statement true. There are uncountably many subsets of the natural numbers (by Cantor&amp;#x27;s diagonalization argument). Proofs are finite chains of finite statements so there are only countably infinitely many of these. Therefore there must be subsets&amp;#x2F;statements that are true that do not have a matching proof.&lt;p&gt;The approach that Gödel&amp;#x27;s proof takes is not too different to the above argument – it is essentially a diagonalization argument – the complexity is in making the encoding of statements are numbers very precise.</text></item><item><author>red_trumpet</author><text>How can a statement that is unprovable be true?&lt;p&gt;I always had the impression that unprovable means you could add either the statement or its negation as an axiom, and both resulting systems are as consistent as the system you started with</text></item><item><author>jstanley</author><text>&amp;gt; Gödel&amp;#x27;s Incompleteness Theorem: any sufficiently rich formal system, together with an interpretation, has strings which are true but unprovable.&lt;p&gt;This is only half of it!&lt;p&gt;Gödel&amp;#x27;s Incompleteness Theorem states that any sufficiently rich formal system, together with an interpretation, &lt;i&gt;either&lt;/i&gt; has strings which are true but unprovable &lt;i&gt;or&lt;/i&gt; has strings which are provable but untrue. Either is possible! In practice people prefer to have true things that can&amp;#x27;t be proven rather than provable things that are untrue. But either is possible.</text></item></parent_chain><comment><author>memetomancer</author><text>Interesting take. You have casually dismissed the Goldbach Conjecture (perhaps the deepest centuries old problem in number theory) as &amp;#x27;trite, trivial and uninteresting&amp;#x27;... Suggesting that you are only minimally familiar with the issue... then toss about an inapplicable phrase &amp;#x27;self-referential recursive logic&amp;#x27; as if you are deeply immersed in such matters, perhaps even _much_ smarter than the thousands of mathematicians (including the likes of Euler) that have applied themselves to this problem. An odd contradiction!&lt;p&gt;I do believe this opinion places you very high on the &amp;#x27;confidence&amp;#x27; axis, but not especially far along the &amp;#x27;competence&amp;#x27; axis.</text></comment>
<story><title>Gödel, Escher, Bach: an in-depth explainer</title><url>https://www.alignmentforum.org/posts/wwNnzaPnB5a48K86N/book-review-goedel-escher-bach-an-in-depth-explainer</url></story><parent_chain><item><author>adastra22</author><text>I’ve only ever seen examples like the one you give here, which seem like trite, trivial, and uninteresting middle-school level logical gotchas. Are there actually interesting properties which are true but can’t be proven? Or is it just a statement about self-referential recursive logic being unprovable?</text></item><item><author>mreid</author><text>It might be easiest to give a sense of what &amp;quot;unprovable but true&amp;quot; means by way of an imagined example.&lt;p&gt;Goldbach&amp;#x27;s conjecture is that &amp;quot;every even number bigger than 2 is the sum of exactly two prime numbers&amp;quot;, so 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, etc.&lt;p&gt;For this statement to be *true* it just means that every even number there must exist two primes that add to that number. This is a statement about infinitely many integers.&lt;p&gt;A *proof* of Goldbach&amp;#x27;s conjecture consists of a finite number of formal reasoning steps that start with some axioms and end up at the statement of the result.&lt;p&gt;To this day, it seems as though Goldbach&amp;#x27;s conjecture is true. It holds for every number we&amp;#x27;ve been able to test. However, no one has proved it is true or false yet (or proved that it is unprovable).&lt;p&gt;The proof of Gödel&amp;#x27;s result&amp;#x27;s involves very carefully formalizing what statements and proofs mean so that they can be encoded as statements about arithmetic. He then shows there is a statement with encoding G that says &amp;quot;The statement with encoding G cannot be proved&amp;quot; – if it is true, then it cannot be proved.&lt;p&gt;It&amp;#x27;s kind of confusing at first, but there is an easier way to get an intuition why there might be true statements that cannot be proved. Think of each statement about the natural numbers as a subset where each number in the subset makes the statement true. There are uncountably many subsets of the natural numbers (by Cantor&amp;#x27;s diagonalization argument). Proofs are finite chains of finite statements so there are only countably infinitely many of these. Therefore there must be subsets&amp;#x2F;statements that are true that do not have a matching proof.&lt;p&gt;The approach that Gödel&amp;#x27;s proof takes is not too different to the above argument – it is essentially a diagonalization argument – the complexity is in making the encoding of statements are numbers very precise.</text></item><item><author>red_trumpet</author><text>How can a statement that is unprovable be true?&lt;p&gt;I always had the impression that unprovable means you could add either the statement or its negation as an axiom, and both resulting systems are as consistent as the system you started with</text></item><item><author>jstanley</author><text>&amp;gt; Gödel&amp;#x27;s Incompleteness Theorem: any sufficiently rich formal system, together with an interpretation, has strings which are true but unprovable.&lt;p&gt;This is only half of it!&lt;p&gt;Gödel&amp;#x27;s Incompleteness Theorem states that any sufficiently rich formal system, together with an interpretation, &lt;i&gt;either&lt;/i&gt; has strings which are true but unprovable &lt;i&gt;or&lt;/i&gt; has strings which are provable but untrue. Either is possible! In practice people prefer to have true things that can&amp;#x27;t be proven rather than provable things that are untrue. But either is possible.</text></item></parent_chain><comment><author>flebron</author><text>Well, most interesting properties about computer programs are, in general for all programs, undecidable (&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Rice%27s_theorem&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Rice%27s_theorem&lt;/a&gt;). Undecidability is a closely related notion to unprovability (&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Undecidable_problem#Relationship_with_G%C3%B6del&amp;#x27;s_incompleteness_theorem)&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Undecidable_problem#Relationsh...&lt;/a&gt;.</text></comment>