3 ms·

Godel's theorem is actually not that complex. Sure, you may think of "Godel, Escher, Bach", but that book is stuffed with sooo much material that is only tangen

Godel's theorem is actually not that complex. Sure, you may think of "Godel, Escher, Bach", but that book is stuffed with sooo much material that is only tangentially related to the theorem. Of course the consequences of that theorem are legion, and they do warrant many books worth of discussion. But the proof itself can fit in a long-ish blog post, I think. Fermat's last theorem, on the other hand...

pdpi 5y ago
GEB is a book about intelligence/consciousness. The incompleteness theorem is incidental — it’s only there to illustrate the notion of self-referentiality, and I’m not sure it does a particularly good job at it.
qweqwweqwe-90i 5y ago
If you could prove the ABC conjecture then Fermat's last theorem becomes much less than a page of proof :)
- lou1306 5y ago
  Speaking of ABC, some years ago HN was all abuzz with inter-universal Teichmuller theory, did that fizzle out or what?
  - qweqwweqwe-90i 5y ago
    https://www.math.columbia.edu/~woit/wordpress/?p=12220 https://www.math.columbia.edu/~woit/wordpress/?p=12220
moomin 5y ago
For those interested: Assume a formal language that can model the natural numbers. Consider the set of all provable statements. This is countable because it’s a subset of the list of strings of a finite number of characters, which is countable. Consider the statement “Statement N is false”. This is both a valid statement and cannot appear in the list. Godel proved significantly more than that, but that’s the basic result. It’s basically the same as the diagonal argument of real numbers being uncountable and it’s also basically the halting problem.
- harmoat 5y ago
  Since these 3 results are so similar are they a subset of a more general concept?
  - deleted 5y ago
    [deleted]
  - moomin 5y ago
    Arguably the halting problem is just a subset of Godel where every theorem is "This does or does not halt". Someone's written a paper going the other way: https://www.andrew.cmu.edu/user/avigad/Teaching/halting.pdf https://www.andrew.cmu.edu/user/avigad/Teaching/halting.pdf The crucial trick is that you can plug in an entry as data to another "program/theorem". This is extremely interesting, because there are limited logics and limited computation models where Godel and the Halting Problem do not apply. Not so sure about the diagonal argument.
- alisonkisk 5y ago
  It's "This cannot be proved.", where "this" is defined via the mathematical coding system he created. The intuitive idea is very simple, but Godel's achievement in this theorem was in finding a way to rigorously define the word "this".
- deleted 5y ago
  [deleted]

pdpi 5y ago

GEB is a book about intelligence/consciousness. The incompleteness theorem is incidental — it’s only there to illustrate the notion of self-referentiality, and I’m not sure it does a particularly good job at it.

qweqwweqwe-90i 5y ago

If you could prove the ABC conjecture then Fermat's last theorem becomes much less than a page of proof :)

lou1306 5y ago
Speaking of ABC, some years ago HN was all abuzz with inter-universal Teichmuller theory, did that fizzle out or what?
- qweqwweqwe-90i 5y ago
  https://www.math.columbia.edu/~woit/wordpress/?p=12220 https://www.math.columbia.edu/~woit/wordpress/?p=12220

moomin 5y ago

For those interested: Assume a formal language that can model the natural numbers. Consider the set of all provable statements. This is countable because it’s a subset of the list of strings of a finite number of characters, which is countable. Consider the statement “Statement N is false”. This is both a valid statement and cannot appear in the list. Godel proved significantly more than that, but that’s the basic result. It’s basically the same as the diagonal argument of real numbers being uncountable and it’s also basically the halting problem.

harmoat 5y ago
Since these 3 results are so similar are they a subset of a more general concept?
- deleted 5y ago
  [deleted]
- moomin 5y ago
  Arguably the halting problem is just a subset of Godel where every theorem is "This does or does not halt". Someone's written a paper going the other way: https://www.andrew.cmu.edu/user/avigad/Teaching/halting.pdf https://www.andrew.cmu.edu/user/avigad/Teaching/halting.pdf The crucial trick is that you can plug in an entry as data to another "program/theorem". This is extremely interesting, because there are limited logics and limited computation models where Godel and the Halting Problem do not apply. Not so sure about the diagonal argument.
alisonkisk 5y ago
It's "This cannot be proved.", where "this" is defined via the mathematical coding system he created. The intuitive idea is very simple, but Godel's achievement in this theorem was in finding a way to rigorously define the word "this".
deleted 5y ago
[deleted]