4 ms·

Godel's First Incompleteness Theorem isn't particularly interesting, can be proved fairly easily (to an average high-schooler)[1], and, therefore, doesn't reall

by dvt 8y ago

Godel's First Incompleteness Theorem isn't particularly interesting, can be proved fairly easily (to an average high-schooler)[1], and, therefore, doesn't really have much "meat" on its bones. The Second Incompleteness Theorem, on the other hand, is another beast altogether[2]. It's much more interesting, much more beautiful, and much more difficult to grasp. At the end of the day, I agree with the essay (too many people misuse Godel -- starting with GEB, and onward), but I don't like the justification behind the post. After all, the First Theorem is used to drive towards the Second. It's intellectually lazy to just cover the first without touching the second: "Any consistent formal system S within which a “certain amount of elementary arithmetic” can be carried out cannot prove its own consistency." In other words, I think the essay falls prey to exactly what it's criticizing: a purposefully neutered explanation of Godel to arrive to some unrelated conclusion. [1] https://dvt.name/2018/03/12/godels-first-incompleteness-theorem-programmers/ https://dvt.name/2018/03/12/godels-first-incompleteness-theo... [2] https://dvt.name/2018/04/11/godels-second-incompleteness-theorem-programmers/ https://dvt.name/2018/04/11/godels-second-incompleteness-the...

joe_the_user 8y ago
"too many people misuse Godel -- starting with GEB, and onward." Assuming this is Hofstader's Godel Escher Bach, I'd like to see support for this claim. GEB is just a popular exposition of Godel and a paean to self-reference. It's not a rigorous work but I don't know of any terrible violations it involves.
- earthicus 8y ago
  GEB not just a popular exposition of mathematical logic, the book is quite explicitly about philosophy of mind. In particular, he develops the self-reference stuff so he can draw an analogy to brains and tell us his theory of consciousness. As for support for that claim, he clarified the point of the book in an elaborate preface to the 20th anniversary edition, and that still wasn't enough to get the point across, so he wrote an entire second book ('I am a Strange Loop') to explain his theory of mind again.
  - dvt 8y ago
    Exactly. Godel's Incompleteness Theorems have as much to do with philosophy of mind (consciousness/brains/AI) as the Pythagorean Theorem does.
  - bcherny 8y ago
    I found I Am a Strange Loop good, but a little sad.
  - Zanni 8y ago
    How is that a "misuse" of Godel's Theorem? He doesn't draw conclusions from it about consciousness. He only points to it as an example of a strange loop. Godel's Theorem is an analogy, not an explanation.
    - earthicus 8y ago
      That's not at all an accurate description of the book. Goedel is not just used as an example of a strange loop, he bases his entire model of mind on it. This is developed in chapter 20. Particularly noteworthy are the sections of that chapter titled "Undecidability is inseparable from a high-level viewpoint", immediately followed by "consciousness as an intrinsically high-level phenomenon". It's true that he uses it as an analogy, but not a loose or vague one. For example, "But it is important to realize that if we are being guided by Goedel's proof in making such bold hypotheses, we must carry the analogy through thoroughly [...] If our analogy is to hold, then, 'emergent' phenomena would become explicable in terms of a relationship between different levels in mental systems." p708 He's literally taking the logic of Goedel's proof, transferring it to brains step by step, to argue for a particular theory of consciousness.
- googlemike 8y ago
  +1 It is odd to think of someone "using" or "misusing" Godel - if the points are salient and clear, how is it misuse? (At least, in this case, where GEB is a philosophical text, not a scientific one.)
  - pulisse 8y ago
    The salience is exactly what's disputed.
thethirdone 8y ago
> Godel's First Incompleteness Theorem isn't particularly interesting, can be proved fairly easily (to an average high-schooler)[1] I don't agree. The more modern result of incomputability has certainly decreased the importance of the first incompleteness theorem, but the idea of unprovability is still important. And I don't think its a result that most high-schoolers can prove (with rigor). I would like to point out that your reference does not in fact even prove it (even informally). It only proves that there are incomputable functions. Such a function does allow you to make an unprovable statement, but that is an extra step at least as large as the given proof. There are a bunch of important details to the formal proof (as Godel wrote) that are not easy. The method to find a fixed point of the unprovable statement is definitely not something I could repeat from memory. Understanding why the "certain amount of elementary arithmetic" is one of the details I feel is important to understanding the theorem.
- dvt 8y ago
  > Such a function does allow you to make an unprovable statement, but that is an extra step at least as large as the given proof. Not at all. An unprovable statement is, in fact, exactly such a non-computable function. Supposing S is a non-computable function, all we need is a meta-logical jump from "computing S(x)" to "checking if the statement 'S(1) = 0' is correct" -- the latter of which is also trivially not possible (because S is not computable).
  - ginnungagap 8y ago
    I'm confused by your statement, there's plenty of not computable functions for which we know whether S(1)=0 is true or not
    - dvt 8y ago
      We might know it†, but we can't prove it† (because proving it implies computing it). † The knowing is external to the system at hand, and the proving is internal to the system at hand. I go into detail about this in my blog posts linked above.
Yajirobe 8y ago
A question about the article. Surely, for any function fn(x) we can just add gn(x) = 1-fn(x) to the table. And so then the argument that there are missing functions does not hold. Why is this reasoning wrong?
- kccqzy 8y ago
  I think you forgot to notice the diagonalization in the article. That is, the newly defined function precisely disagrees with the i-th function when input is i. A similar diagonalization process is used by Cantor to prove the reals are not countable.

by dvt 8y ago

joe_the_user 8y ago

"too many people misuse Godel -- starting with GEB, and onward." Assuming this is Hofstader's Godel Escher Bach, I'd like to see support for this claim. GEB is just a popular exposition of Godel and a paean to self-reference. It's not a rigorous work but I don't know of any terrible violations it involves.

earthicus 8y ago
GEB not just a popular exposition of mathematical logic, the book is quite explicitly about philosophy of mind. In particular, he develops the self-reference stuff so he can draw an analogy to brains and tell us his theory of consciousness. As for support for that claim, he clarified the point of the book in an elaborate preface to the 20th anniversary edition, and that still wasn't enough to get the point across, so he wrote an entire second book ('I am a Strange Loop') to explain his theory of mind again.
- dvt 8y ago
  Exactly. Godel's Incompleteness Theorems have as much to do with philosophy of mind (consciousness/brains/AI) as the Pythagorean Theorem does.
- bcherny 8y ago
  I found I Am a Strange Loop good, but a little sad.
- Zanni 8y ago
  How is that a "misuse" of Godel's Theorem? He doesn't draw conclusions from it about consciousness. He only points to it as an example of a strange loop. Godel's Theorem is an analogy, not an explanation.
  - earthicus 8y ago
    That's not at all an accurate description of the book. Goedel is not just used as an example of a strange loop, he bases his entire model of mind on it. This is developed in chapter 20. Particularly noteworthy are the sections of that chapter titled "Undecidability is inseparable from a high-level viewpoint", immediately followed by "consciousness as an intrinsically high-level phenomenon". It's true that he uses it as an analogy, but not a loose or vague one. For example, "But it is important to realize that if we are being guided by Goedel's proof in making such bold hypotheses, we must carry the analogy through thoroughly [...] If our analogy is to hold, then, 'emergent' phenomena would become explicable in terms of a relationship between different levels in mental systems." p708 He's literally taking the logic of Goedel's proof, transferring it to brains step by step, to argue for a particular theory of consciousness.
googlemike 8y ago
+1 It is odd to think of someone "using" or "misusing" Godel - if the points are salient and clear, how is it misuse? (At least, in this case, where GEB is a philosophical text, not a scientific one.)
- pulisse 8y ago
  The salience is exactly what's disputed.

thethirdone 8y ago

> Godel's First Incompleteness Theorem isn't particularly interesting, can be proved fairly easily (to an average high-schooler)[1] I don't agree. The more modern result of incomputability has certainly decreased the importance of the first incompleteness theorem, but the idea of unprovability is still important. And I don't think its a result that most high-schoolers can prove (with rigor). I would like to point out that your reference does not in fact even prove it (even informally). It only proves that there are incomputable functions. Such a function does allow you to make an unprovable statement, but that is an extra step at least as large as the given proof. There are a bunch of important details to the formal proof (as Godel wrote) that are not easy. The method to find a fixed point of the unprovable statement is definitely not something I could repeat from memory. Understanding why the "certain amount of elementary arithmetic" is one of the details I feel is important to understanding the theorem.

dvt 8y ago
> Such a function does allow you to make an unprovable statement, but that is an extra step at least as large as the given proof. Not at all. An unprovable statement is, in fact, exactly such a non-computable function. Supposing S is a non-computable function, all we need is a meta-logical jump from "computing S(x)" to "checking if the statement 'S(1) = 0' is correct" -- the latter of which is also trivially not possible (because S is not computable).
- ginnungagap 8y ago
  I'm confused by your statement, there's plenty of not computable functions for which we know whether S(1)=0 is true or not
  - dvt 8y ago
    We might know it†, but we can't prove it† (because proving it implies computing it). † The knowing is external to the system at hand, and the proving is internal to the system at hand. I go into detail about this in my blog posts linked above.

Yajirobe 8y ago

A question about the article. Surely, for any function fn(x) we can just add gn(x) = 1-fn(x) to the table. And so then the argument that there are missing functions does not hold. Why is this reasoning wrong?

kccqzy 8y ago
I think you forgot to notice the diagonalization in the article. That is, the newly defined function precisely disagrees with the i-th function when input is i. A similar diagonalization process is used by Cantor to prove the reals are not countable.