141–150 of 271 posts
Thanks for great write-up, fun to read! I only notices one tiny typo: "when apples are a fruit, then bananas or applies implies bananas or fruits" - "applies" should be "apples" I guess.
Two more typos: > These symbols map closely to the logical statements we are used too in programming. too => to > Hofstadter’s “I’m a Stange Loop” Stange => Strange
I thought I replied to this post, but I guess not and my reply ended up being a top-level reply, which is just as well. I will just mention my main two quibbles to this otherwise excellent post and others like it so that other people who embark on introductory posts to Godel's results don't fall into the same trap. 1. Please don't bring the notion of truth into an introductory explanation (such as in the section "Pow…
To offer possibly a comment to yours about the notion of "truth", in the article posted, when I read "true" (e.g. in the 1st paragraph of chapter Hilbert's Program) and next to it "false", I immediately made reference in my mind to the true/false duality of programmers. I think that helped in understanding the article, but coupled with a footnote with your details would certainly help the reader think further on the topic.
cheers :-)
Earlier quoted context omitted.
> all mathematics greater than or equal to number theory is uncomputable That's not what Godel's Incompleteness Theorem says though. Nor would I agree that "mathematicians compute /all sorts/ of uncomputable systems, with no apparent restriction." It is hard to describe the behavior of real-world mathematicians since that is the realm of psychology rather than logic or mathematics, but if we stick to the realm of ide…
> Alternatively do you believe that the real numbers are an artificial mathematical construction which can have different properties depending on which axioms you are willing to admit? Then there will be properties of the real numbers which are independent of ZFC as a result of Godel's incompleteness theorems. This is actually not correct. The propositions that are undecidable are NOT AT ALL connected to the proposit…
I'm not quite sure what you mean by undecidable propositions, but I assume it to mean something like the following?
Propositions which must be true or must be false (i.e. are satisfied/not satisfied respectively by all models which satisfy the overall theory), but for which there is no finite proof that they hold.
In contexts where Godel's Completeness theorem (not incompleteness theorem) holds undecidable propositions are exactly independent propositions. The two are one and the same. This is in fact an equivalent restatement of the Completeness theorem (which holds for contexts involving most common mathematical theories such as ZFC and Peano Arithmetic). In fact in such contexts, statements such as Con(PA) which is informally "the axioms of Peano Arithmetic are consistent" are in fact independent propositions and there are models of Peano Arithmetic that satisfy both Con(PA) and Not(Con(PA)).
What about contexts where the Completeness theorem fails (e.g. the second-order equivalents of those theories)? For example, what about CH in second-order ZFC (which is categorical under full semantics, i.e. has no independent statements and only undecidable ones?). In those contexts independence gets weird, especially in the way I think you're using it here. Usually we say that if a sentence s is independent of theory T then both s and Not(s) are consistent with T. However, consistency is phrased in terms of proofs. That is s is consistent with T if there is no finite proof in T of Not(s).
So if there are statements that are undecidable, but not independent (on the other hand all independent statements must be undecidable, although their independence may itself be decidable), we are effectively saying there exist consistent theories which have no mathematical model that satisfies them.
But this is a very weird way of doing mathematics (which is why most logicians are wary of using systems where the Completeness theorem fails to hold as foundations for mathematics). In particular it means that simply showing that a list of axioms is consistent is insufficient to allow its use. You must appeal to some other force to show that your mathematical theory is "valid" and allowed to be used.
But that's not a bar that modern mathematics tries to clear. Modern mathematicians do not try to justify the "validity" of mathematical theories beyond showing (or assuming) consistency.
For example, mathematicians generally don't hem and haw over whether the complex numbers "exist" in some real sense. They just show that they are a consistent extension of the real numbers and move on and use them.
To take a step back, the assertion that there are fundamentally undecidable mathematical propositions in the real sense you're laying out (as opposed to more formal treatments of truth in model theory) is a statement of the Platonist school of mathematical philosophy. Which is totally fine, but it is a statement of philosophy at the end of the day, rather than one of logic.
Earlier quoted context omitted.
The way I see it is that both theorems are statements about the relationship between a theory and models of that theory. Goedel's completeness theorem tells you that for a theory in first-order logic, there's a model that corresponds exactly to that theory: anything that's true in that model can be proven in the theory, and vice versa. Godel's incompleteness theorem tells you that there's no such model for any system…
> there's a model that corresponds exactly to that theory: anything that's true in that model can be proven in the theory, and vice versa. Unfortunately it doesn't work if you swap our "for all models" with "there exists a model." Take the theory of the natural numbers with the new symbol "Special" and the axiom "there exists a number n such that Special(n) holds." In every model of that theory there will be a concre…
Hmm. So which n is special in the model that you get from the model existence theorem? Doesn't it all get somehow equivalence-classed away?
> No in conjunction with Godel's completeness theorem, the incompleteness theorem would say rather that there is no theory that is strictly only the "full" version of arithmetic. Any theory will always be too broad and have too many models that satisfy it, only one of which is the "usual" model of arithmetic.
Sure. The point is that there's always a gap between the theory and the model, an "implementation-defined" part of the model.
I thought I replied to this post, but I guess not and my reply ended up being a top-level reply, which is just as well. I will just mention my main two quibbles to this otherwise excellent post and others like it so that other people who embark on introductory posts to Godel's results don't fall into the same trap. 1. Please don't bring the notion of truth into an introductory explanation (such as in the section "Pow…
> I thought I replied to this post, but I guess not and my reply ended up being a top-level reply, which is just as well. Sorry for the confusion. We detach comments that are replies to the top comment but don't respond to anything specific that that comment said. This is standard moderation. Sometimes we post that we did this ( https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que... ), but not always. We do…
Earlier quoted context omitted.
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?
No, is not the only class of program. An easy example is to take any of the unsolved math problems (like the Goldbach conjeture) and write a program for it, if the program halts it proves the conjeture. Can you tell if the program halts? You can’t without proving the conjeture.
Also, a lot of problems are proven unsolvable because solving them would imply solving the halting problem, but hey.
I thought I replied to this post, but I guess not and my reply ended up being a top-level reply, which is just as well. I will just mention my main two quibbles to this otherwise excellent post and others like it so that other people who embark on introductory posts to Godel's results don't fall into the same trap. 1. Please don't bring the notion of truth into an introductory explanation (such as in the section "Pow…
Thank you, reading this comment and some of yours further down, thinking about the topics you set out, was very interesting. To offer possibly a comment to yours about the notion of "truth", in the article posted, when I read "true" (e.g. in the 1st paragraph of chapter Hilbert's Program) and next to it "false", I immediately made reference in my mind to the true/false duality of programmers. I think that helped in u…
Earlier quoted context omitted.
The way I see it is that both theorems are statements about the relationship between a theory and models of that theory. Goedel's completeness theorem tells you that for a theory in first-order logic, there's a model that corresponds exactly to that theory: anything that's true in that model can be proven in the theory, and vice versa. Godel's incompleteness theorem tells you that there's no such model for any system…
Just want to point out that your answer is essentially incorrect. Godel's completeness theorem has nothing to do with the existence of models. It is about the provability of sentences that are true within all models. Also, the incompleteness theorem doesn't say anything about the nonexistence of a model. It gives the existence of at least one sentence X (for sufficiently nice theories that include enough arithmetic)…
I wouldn't say that it has "nothing to do" with existence of models. It wasn't the original Goedel's formulation of the theorem, but these days, one of the most, if not the most popular statement of it is to say that "if theory T is consistent, there exists a model of it".
Very off-topic, but long ago when Albert Einstein went for a car ride with Mr. Gödel to become U.S. citizens, Einstein was trying very hard to think of ways to shut him up about a Constitution loophole he discovered. Things didn't go exactly as planned, and in front of the naturalization examiner, Mr. Gödel started blabbing about how he had found a way the U.S could be transformed into a fascist regime... Sources: ht…
The constitution is BS anyway. For example, Article I, section 10 says "No state shall...coin money, emit bills of credit, make any thing but gold and silver a tender in payment of debts..." And look what the US has today; fiat money. No only is it not gold or silver, but it's not event backed by it. Based on this definition, nobody in the US earns any money so nobody should have to pay any income tax since basically…
- literally anyone can make it
- it is unsanitary and can spread disease
- it is difficult to measure
On the plus side:
- it does represent (some amount of) labor
Earlier quoted context omitted.
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.
But as others have said, both statements are equally unprovable in ZFC. The Godel sentences demonstrating incompleteness are constructed in such a way that you could argue (outside of the axiomatic system) they are provably true or false, while CH is a case where reasonable mathematicians may disagree on whether it is true or false. But ultimately there is no proof in ZFC for either, so they are both examples of incompleteness in ZFC.
And note that the Godel sentence demonstrating incompleteness doesn't need to be true -- the inverse of the Godel sentence demonstrating incompleteness is also unprovable.