6 ms·
I never thought that Godel incompleteness of a logical system was particularly damaging; the ability to make self-referential statements is useful, the ability
by musicale 7y ago
I never thought that Godel incompleteness of a logical system was particularly damaging; the ability to make self-referential statements is useful, the ability to resolve self-referential paradoxes less so.
Same for the halting problem in CS, which is typically resolved by (sleep 9999; kill -9 $pid). QED. ;-)
- evanb 7y agoRussell's hope was to establish that one could find proof of all true mathematical statements, so that one needed a fixed-for-all-time set of axioms and nothing more. Incompleteness obviously destroys that hope.
- drchewbacca 7y agoThere is an interesting, if quite technical, answer here about Goodstein's Theorem which is a very reasonable number theory theorem which cannot be proven in first order logic. So questions around statements which are true but not provable in certain logical systems do have concrete examples and are interesting imo. https://math.stackexchange.com/questions/625223/do-we-know-if-there-exist-true-mathematical-statements-that-can-not-be-proven/625404 https://math.stackexchange.com/questions/625223/do-we-know-i...
- zajio1am 7y agoGoodstein's Theorem cannot be proved in Peano axiomatization of natural numbers in first order logic. You can have stronger axiomatization of natural numbers in first order logic that allows to prove Goodstein's Theorem - such axiomatization would contain subset of set theory and transfinite induction up to ordinal e_0. But it is still axiomatixation in first order logic.
- 6gvONxR4sf7o 7y agoAs mentioned in that answer, these "natural independence phenomena" do seem much more interesting than Gödel's incompleteness results.
- scotty79 7y agoMy thoughts exactly. Goedel is just basically "set of all sets that don't contain themselves ... does it contain itself or not?" applied to 'provability'. It gives you no more profound insight than "you can eff yourself with recursion if you aren't super careful" which is obvious for any beginner programmer who encounters recursion and tries to write whatever he likes in recursive function. I guess this might have been surprise for mathematicians who always thought they have all infinites at their disposal and thus are completely unrestricted and brushed self-referential paradoxes under the rug as curiosities until Godel showed they can be constructed about things mathematicians care about like provability. I believe you can make a consistent fully provable axiomatic system by excluding statements that are not provable from your system, as meaningless. You don't consider whether "number 5 contains itself" is true because it's nonsensical. "This statement is unprovable" can be considered similarily nonsensical not because it wrongly combines math concepts but because it's a self-referential paradox and we choose to not allow that.
- pdonis 7y ago> I believe you can make a consistent fully provable axiomatic system by excluding statements that are not provable from your system, as meaningless. The problem is not how to exclude the unprovable statements. The problem is that the unprovable statements will include statements that are true, but that the system can't prove. Some of those statements are probably not ones you care about, like "this statement is unprovable". But you have no way of knowing that all of the unprovable true statements are like that. Some of them might be ones you do care about. Thus, the real import of Goedel's theorem is not "you need to exclude unprovable statements"; it is "the intuitively attractive ideal of having a system in which every true statement you care about can be proved is not achievable".
- zajio1am 7y ago> The problem is that the unprovable statements will include statements that are true, but that the system can't prove. No, that is a misrepresentation of Goedel's results. A theorem that is undecidable (neither provable nor refutable) from a set of axioms cannot be 'true' in the logical sense (because there are models of that set of axioms in which the theorem is true, and other models in which the theorem is false) - see Goedel's completeness theorem, which says that every truth is provable (and vice versa). Goedel's incompleteness theorems can be understood on the semantic level as the mathematical structure of natural numbers cannot be characterized by a sane set of axioms, so any such attempt (e.g. peano axioms) that describes natural numbers also describes a different mathematical structure (a nonstandard model of arithmetic) and there exists a theorem that is true in one and false in the other model (so that theorem is undecidable).
- strbean 7y agoThe trope of self-referential paradoxes as the foundation for grander proofs has always bugged me. My gut always says "sure, but what if we just banned self-referential paradoxes?"
- deleted 7y ago[deleted]
- andrewflnr 7y agoI think those are called type theories. IIRC that was at least the idea behind the original type theories, before they got co-opted by the CS rabble. :)
- dllthomas 7y agoRight, IIUC type theory started as Bertrand Russell's attempt to do exactly that (and follow through the ramifications - you can't "just" anything in math). Then suddenly, Haskell. Or something.
- nl 7y agoThen suddenly, Haskell. Sequence of events: Russell publishes Principia Mathematica (1910-1913) David Hilbert studies Principia Mathematica, and keeps working on open questions from it (1913 onwards): He poses the proof of the consistency of arithmetic (and of set theory) again as the main open problems. In both these cases, there seems to be nothing more fundamental available to which the consistency could be reduced other than logic itself. And Hilbert then thought that the problem had essentially been solved by Russell’s work in Principia. Nevertheless, other fundamental problems of axiomatics remained unsolved, including the problem of the “decidability of every mathematical question,” which also traces back to Hilbert’s 1900 address. These unresolved problems of axiomatics led Hilbert to devote significant effort to work on logic in the following years. In 1917, Paul Bernays joined him as his assistant in Göttingen. In a series of courses from 1917–1921, Hilbert, with the assistance of Bernays and Behmann, made significant new contributions to formal logic.[1] In 1928 Haskell Curry moved to Germany to study under David Hilbert Curry's work developed into the Curry–Howard correspondence[2] which led to the language being named after him. [1] https://plato.stanford.edu/entries/hilbert-program/#1.2 https://plato.stanford.edu/entries/hilbert-program/#1.2 [2] https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence#Origin,_scope,_and_consequences https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...
- unhammer 7y agoBut imagine what we could do if we didn't have incompleteness or the halting problem
- jlokier 7y agoSomething like a Turing machine, with its finite states, deterministic transitions, and simple tape seems so mechanical, so physical. So predictable. Sure, there's the halting problem, but that relies on a paradox. Surely something as artifical as self-referential statements would seem a bit pointless. And yet, with the help of that principle, it turns out we can write simple, mechanical programs where if the input is < N we can calculate the answer, and if the input is > N we can't figure out what the program will do (using standard mathematical thinking). For some N we can get creative, but for a yet bigger N, we may well find ourselves unable to be creative enough to work out if we could ever work out the the answer. https://en.wikipedia.org/wiki/Busy_beaver#Non-computability https://en.wikipedia.org/wiki/Busy_beaver#Non-computability "In 2016, Adam Yedidia and Scott Aaronson obtained the first (explicit) upper bound on the minimum n for which Σ(n) is unprovable in ZFC. To do so they constructed a 7910-state[2] Turing machine whose behavior cannot be proven based on the usual axioms of set theory (Zermelo–Fraenkel set theory with the axiom of choice), under reasonable consistency hypotheses (stationary Ramsey property).[3][4] This was later reduced to 1919 states, with the dependency on the stationary Ramsey property eliminated.[5][6]"