4 ms·
Waiting for Gödel (2016)
- dang 6y agoDiscussed at the time: https://news.ycombinator.com/item?id=12008020 https://news.ycombinator.com/item?id=12008020
- ur-whale 6y agohttps://archive.is/IAsgM https://archive.is/IAsgM
- KineticLensman 6y agoThis Gödel's killing me
- smitty1e 6y agoTitle alludes to Beckett => https://en.m.wikipedia.org/wiki/Waiting_for_Godot https://en.m.wikipedia.org/wiki/Waiting_for_Godot
- p0llard 6y ago> There are true statements that are unprovable within the system. I really don't like this, and it verges on being flat-out incorrect: the first incompleteness theorem does not say this at all. It says that there are sentences (and indeed it constructs one, the so-called Gödel Sentence) that cannot be proven or refuted within the system. For first-order theories it follows from the contraposition of Gödel's completeness theorem that there exist (classical) models of the theory where this sentence holds and models where it doesn't: the existence of models where the sentence does not hold means that this must be a very different meaning of "true" to the one used in common parlance. In higher-order logics, which do not have a completeness theorem, it makes sense to talk about true statements which are unprovable: there can exist tautologies, sentences which hold in all models of a theory, which cannot be proven from the axioms of a higher-order theory (and you don't need the incompleteness theorem for this); on the other hand, in a first-order theory all tautologies are provable. Sentences which cannot be proven or refuted within a theory are said to be logically independent of the theory. Famously, the Axiom of Choice is independent of the axioms of Zermelo–Fraenkel set theory: it's up to mathematicians to decide whether they accept the Axiom of Choice. If they do, they can work in ZF+C; if not, they can work in ZF. Neither system is "more true" from a purely logical perspective, so I really don't like describing logically independent sentences as "true but unprovable": it almost certainly doesn't mean what people think it means. The first incompleteness theorem could perhaps be stated better for a lay audience as: No recursive set of axioms can capture our notion of arithmetic it its entirety. This is a limitation on how we can use axiom systems to represent mathematical objects: even more informally, we might say: Truth is subjective in sufficiently complex systems.
- ProfHewitt 6y agoIncompleteness in the sense of inferential undecidability still must be proven for higher-order strongly-typed theories in computer science. For an example of such as proof see the following: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3459566 https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3459566
- deleted 6y ago[deleted]
- ProfHewitt 6y agoPerhaps a higher-order theory of the ordinals is better than ZFC for the mathematical foundations of computer science. For example, see the following: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3457802 https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3457802
- natcombs 6y ago> so I really don't like describing logically independent sentences as "true but unprovable": I don't see a particular problem with it. It can be "true but unprovable" within a given system. I feel like you may be arguing semantics, but the sentence is still clear and accurate to me, while your lay audience definition is less clear and steps further away from the theorems than necessary
- p0llard 6y ago> I feel like you may be arguing semantics Yeah, I am; it really depends on how you define "true". I prefer this to be interpreted as "true in all models" so sentences are "true" when they are tautological consequences of a theory. Using this definition, all "true" sentences are provable in first-order logic. The (usual) Gödel sentence is true in the intended model of arithmetic, but I don't really like this property being referred to as "truth" without qualification. > "true but unprovable" within a given system Not sure about this: I don't think you can really say something is "true in a system" if it isn't provable. You can only assert its truth by saying it's "true in the intended model" without qualification, or by doing some meta-reasoning in a more powerful system outside the original one.
- ProfHewitt 6y ago[Gödel 1931] is not applicable to the foundations of computer science for the reasons stated here: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3603021 https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3603021
- caleb-allen 6y agoThank you for this link. A few months ago I stumbled across your paper, Common sense for concurrency and strong paraconsistency using unstratified inference and reflection and found it entirely remarkable. I look forward to reading the new paper you linked.
- ProfHewitt 6y agoYou are very welcome! Comments and suggestions for the linked article are greatly appreciated!