This is really excellent. Amazing how much clearer the author’s Lisp code makes things (even to a non mathematician and non lisper). It’s rare to find explanations of difficult topics that are this well communicated, but I hope it becomes a trend.
What Gödel Discovered
31–40 of 271 posts
Re: What Gödel Discovered
#32Something I've always been curious about: does Gödel's theorem imply an infinity of inconsistent statements, or is the "this statement cannot be proven..." statement the only one? If it's the latter, then of what practical significance is the singularity? If a system is incomplete only in that regard, couldn't one redefine incompleteness to exclude it, and render the system complete for all practical purposes?
It implies an infinity of inconsistent statements. I'm not a mathematician, but the way I understand it is to do an analogy with the halting problem: for any programming language that is powerful enough you can build a program where you don't know if it's going to halt or not. About avoiding singularities, the GEB book (Godel,Escher,Bach) mentions at the beginning: mathematicians like Russel tried to avoid paradoxes…
I think the question is a bit more specific in the context of the halting problem
We know by contradiction that we cannot write a program that determines if any program halts, if the program being checked also contains the program that determines if itself halts.
Is this the only class of program that cannot be determined to halt?
Re: What Gödel Discovered
#33I read stuff like this on HN and feel like I'm an child watching dad work on a car. Except papa Godel was younger than me when he wrote his paper.
Re: What Gödel Discovered
#34Just to be clear. This implies that it's possible to write some specific statement (using PM axioms) that contradicts itself? Is there a readable example of this statement without using Gödel numbers but instead just with the axiom statements?
Re: What Gödel Discovered
#35I read stuff like this on HN and feel like I'm an child watching dad work on a car. Except papa Godel was younger than me when he wrote his paper.
Who cares how old he was? Life is not a competition about age ;)
Re: What Gödel Discovered
#36> This proof showed that “1 + 1”, does indeed equal “2”. It took 2 volumes to get here. I know this seems logical to mathematicians, but it feels to me like having to take 2 volumes to prove something than any child knows intuitively is... I don't know what word I am looking for... obsessive?
They're describing a new "programming" language, and demonstrating their "hello world".
Re: What Gödel Discovered
#37I've been trying to understand it for so long and finally it's clear
Re: What Gödel Discovered
#38Something I've always been curious about: does Gödel's theorem imply an infinity of inconsistent statements, or is the "this statement cannot be proven..." statement the only one? If it's the latter, then of what practical significance is the singularity? If a system is incomplete only in that regard, couldn't one redefine incompleteness to exclude it, and render the system complete for all practical purposes?
From Wikipedia [0]: > The proof constructs a particular Gödel sentence for the system F, but there are infinitely many statements in the language of the system that share the same properties, such as the conjunction of the Gödel sentence and any logically valid sentence. [0] https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...
Yes, but the "such as..." example incorporates the original "this statement is not provable" statement, so it seems a bit of a cheat. If you could exclude that statement, it would also by definition exclude any compound versions of it. It seems to me that the issue boils down to, can "this statement is not provable" be leveraged to get to something like 1 + 1 = 3?
Re: What Gödel Discovered
#39Something I've always been curious about: does Gödel's theorem imply an infinity of inconsistent statements, or is the "this statement cannot be proven..." statement the only one? If it's the latter, then of what practical significance is the singularity? If a system is incomplete only in that regard, couldn't one redefine incompleteness to exclude it, and render the system complete for all practical purposes?
Others have explained why you can't wave away inconsistency (principle of explosion) nor incompleteness (adding new axioms just creates a new axiomatic system with its own Godel sentences). However you might also find it interesting what incompletenesses exist in our own mathematical system (ZFC) -- the most well-known example is the Continuum Hypothesis[1]: > There is no set whose cardinality is strictly between tha…
I thought that independent (undecidable) statements are totally different than the Gödel sentences which demonstrate incompleteness. The latter is a statement which is true in the axiomatic system but which cannot be proven using the axiomatic system. The former is just a statement that essentially has no truth value in the axiomatic system.
Re: What Gödel Discovered
#40Earlier quoted context omitted.
It implies an infinity of inconsistent statements. I'm not a mathematician, but the way I understand it is to do an analogy with the halting problem: for any programming language that is powerful enough you can build a program where you don't know if it's going to halt or not. About avoiding singularities, the GEB book (Godel,Escher,Bach) mentions at the beginning: mathematicians like Russel tried to avoid paradoxes…
I think the question is a bit more specific in the context of the halting problem We know by contradiction that we cannot write a program that determines if any program halts, if the program being checked also contains the program that determines if itself halts. Is this the only class of program that cannot be determined to halt?
It's a tough question to answer because it highly depends on interpretation, after all what does it mean for a program to check whether it itself halts, what does it mean for a program to be self referential? There are many sneaky and indirect ways to make a program self referential.
All undecidable languages that are recognizable in some sense contain a self referential program sneaking within it. This is because the halting problem is complete for its complexity class and hence any undecidable but recognizable language is Turing reducible to the halting problem.
However for undecidable and unrecognizable languages, there are proofs of undecidability that are independent of diagonalization and instead use other proof techniques that in a very strong sense are entirely independent of self-reference. Of course this isn't a formal answer mostly because the idea of a self referential program is not a formal concept but there are techniques such as reverse mathematics [1] that can be used to determine a minimal set of axioms needed to prove a theorem along with proof techniques that depend on the Low basis theorem [2] that are able to prove that some languages are undecidable and unrecognizable that do not in any way depend on diagonalization, which is the proof technique that is associated with self referential programs.