5 ms·
World's shortest explanation of Gödel's theorem
- statictype 17y agoWhile we're on the topic, something that always puzzled me: doesn't Gödel's theorem apply only to 'non-trivial' axiomatic systems? Meaning you could come up with a trivial system to which it doesn't apply. Which begs the question: How do you define triviality here?
- idlewords 17y agoTrivial in this context means a system that's not powerful enough to express basic arithmetic. This includes some surprisingly complicated systems, like real (as opposed to integer) arithmetic. Bonus pedantipoint: it's not begging the question - that actually means 'to assume X in your proof of X'. It's just raising the question.
- ivey 17y agoFollowing the derail a little further...while you got my vote for the pedantipoint, the misuse of "beg the question" is so pervasive that I've given up. It means what people use it to mean, now. We probably need a new name for the logical fallacy, unless lumping it into circular reasoning is sufficient.
- vidarh 17y agoEnglish is my second language, and until a few years ago I wasn't even aware of the original usage, while I'd seen the "misuse" on a regular basis. I don't think I've actually ever seen it used in the original usage "in the wild", as opposed to in the posts of pedants complaining about people using it wrongly.
- ars 17y agoI once told people the correct definition of "begs", and they refused to believe me, and thought I was wrong. To them begs means: raises a very obvious question. So it's over, "begs" has a new meaning, and complaining about it is pointless.
- philwelch 17y agoIt's because the original usage is rather technical--I've only seen philosophers use it, and only then as the adjective "question-begging".
- DoctorToWhom 17y agoThis includes some surprisingly complicated systems, like real (as opposed to integer) arithmetic. Real arithmetic is not enough to express integer arithmetic? I suppose it all boils down to how you define "arithmetic", but what is it that the integers have that the reals lack under the relevant definition? I would think that real arithmetic by any reasonable definition would give you enough tools to check whether a number was an integer, and in that case, doesn't it necessarily contain integer arithmetic as a subset?
- idlewords 17y agoCribbing from this book: http://books.google.com/books?id=71pK8Zz9Dd8C&printsec=frontcover&dq=godels+theorem&ei=nhglS777Non4zAS3n62uCw&client=safari&cd=2#v=onepage&q=godels%20theorem&f=false http://books.google.com/books?id=71pK8Zz9Dd8C&printsec=f... "Since the natural numbers form a subset of the real numbers, it may seem odd that the theory of real numbers can be complete when the theory of the natural numbers is incomplete. The incompleteness of the theory of the natural numbers does not carry over to the theory of the real numbers because even though every natural number is also a real number, we cannot define the natural numbers as a subset of the real numbers [...] How would we ordinarily define the natural numbers as a subset of the real numbers? The real numbers 0 and 1 can be identified with the corresponding natural numbers, and using addition of real numbers we get the natural numbers as the subset of the real numbers containing 0, 1, 1+1, 1+1+1, and so on. However, this "and so on" cannot be expressed in the language of the theory of real numbers [because it requires the notion of sets, a second-order concept outside of the theory]."
- 30ss 17y agoYour reasoning is correct, so it means that integers are not definable inside "real arithmetic". http://en.wikipedia.org/wiki/Real-closed_field http://en.wikipedia.org/wiki/Real-closed_field If you don't believe this, try writing down a formula in the language of this theory that says "x is an integer". Ultimately, the issue is that the first-order theory of real closed fields contains no axiom approaching the induction scheme of PA in power.
- jimfl 17y agoThe system need be no more complex than first-order Peano arithmetic, which is the Peano axioms (reflexivity, transitivity, succession, etc.) combined with the concept of induction.
- idlewords 17y agoWell, leave out succession and you get the reals, which are still complex enough (no pun intended) to offer hours of fun.
- gahahaha 17y agoTo construct the Gödel number (a part of the proof) requires use of an arithmetic that can express addition and multiplication. If any one of them is missing, the system can be shown to be complete.
- Lozzer 17y agoBeen a while since I studied it, but I thought induction was the key ingredient.
- rjprins 17y agoGödel's theorem: If you print only true statements, you can not print all true statements. Proof: "I do not print this statement"
- maurycy 17y agoNot quite; this is a liar's paradox. the Gödel's sentence deals with "provability", not "truth". (see Tarski's undefinability theorem if you wonder why it matters)
- anatoly 17y agoThis is a version of the Liar paradox, not Goedel's theorem.
- dejb 17y agoThey are pretty close to a 1:1 mapping http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Relation_to_the_liar_paradox http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_t... 'The analysis of the truth and provability of G is a formalized version of the analysis of the truth of the liar sentence.'
- anatoly 17y agoThis is only approximately true. What really is a straightforward formalized version of the liar paradox is Tarski's undefinability theorem, which is what's demonstrated in the blogpost. Goedel's incompleteness sentence is more like inspired by the liar sentence rather than being its formalization; and the proof of Goedel's incompleteness is much more challenging than the simple true->false->true bounce of the liar paradox.
- joe_the_user 17y agoDude, there's no formal version "the liar's paradox". Back to base camp...
- idlewords 17y agoHere's my attempt: Gödel figured out how to encode the statement "you can't prove me" as an arithmetical expression. Minds blew.
- DougBTX 17y agoCan you point me to an explanation of the arithmetical expression itself?
- idlewords 17y agohttp://books.google.com/books?id=FtclgZ1yYDEC&printsec=frontcover&dq=godels+theorem&ei=bwglS8GONoqGzAS07NCZCw&cd=1#v=onepage&q=godels%20theorem&f=false http://books.google.com/books?id=FtclgZ1yYDEC&printsec=f...
- mdemare 17y agoWow, that was a disappointment. I've always thought of Gödel's incompleteness theorem as something so arcane that I'd never understood it. Now it turns out to be both trivial and really similar to the Halting problem. Good explanation though.
- Confusion 17y agoThe explanation on the Wikipedia page (when taken together with the explanation of a Gödel_number[1]) is actually not that hard to follow. [1]http://en.wikipedia.org/wiki/Gödel_number http://en.wikipedia.org/wiki/Gödel_number
- anatoly 17y agoThis isn't a proof of Goedel's incompleteness theorem. It's a demonstration of Tarski's undefinability theorem. Goedel's theorem is far stronger and more difficult to prove. The confusion between the two is widespread. Goedel's first incompleteness theorem doesn't talk about "true" or "false" statements at all. Technically speaking, it is entirely syntactic, not semantic. It says that in any sufficiently complex axiom system there will be statements that it can neither prove nor refute, "undecidable" statements. The notions of "prove", "refute", "axiom", "undecidable" do not require any definition of "true" or "false".
- jimfl 17y agoMy guess is that Raymond Smullyan is not confused about this. The explanation isn't presented as proof, it's an explanation of the theorem and its consequences.
- anatoly 17y agoI'm sure that Smullyan's not confused. In fact, his _Goedel's Incompleteness Theorems_ is the most lucid and brillian exposition (a mathematical and rigorous one) of the theorems I've ever seen. I absolutely adore that book. However, I also doubt that Smullyan presented the NPR* story as a proof of Goedel's theorem. He probably said something to the effect of it being a good demonstration of the relevant issues. And that's probably right.
- swixmix 17y agoFrom the article, "Either the machine prints NPR@NPR@, or it never prints NPR@NPR@." This makes sense in that the machine has told itself never to print NPR@NPR@ in the future. It would be like trying to verify someone doesn't know a secret by asking them about the secret they shouldn't know. Zero knowledge proofs come to mind. And that's probably a good description of my knowledge on this subject. edit: changed asterisks to @ because HN doesn't display asterisks.
- RiderOfGiraffes 17y agoThe article in Wikipedia is pretty good, although stops short of the full details. In particular it addresses this question of the Liar's Paradox versus Gödel's theorem "proper". http://en.wikipedia.org/wiki/Goedel%27s_incompleteness_theorems#Relation_to_the_liar_paradox http://en.wikipedia.org/wiki/Goedel%27s_incompleteness_theor...
- deleted 17y ago[deleted]
- deleted 17y ago[deleted]
- dbz 17y agoOkay. I have a problem maybe someone can help me with. The article says: "If the machine prints NPRNPR, it has printed a false statement. But if the machine never prints NPRNPR, then NPRNPR is a true statement that the machine never prints." This part seems logically true: "If the machine prints NPRNPR, it has printed a false statement." It seems logically true, and I wont say why because I view it as obvious =/ This part seems logically false: "if the machine never prints NPRNPR, then NPRNPR is a true statement" I don't understand the logic of "If it is not printed, it is true." I was under the impression that the only true statement was "If it prints, then it is true", and of course the contrapositive: "If it is not true, it doesn't print". The statement taken from the article is NOT the contrapositive. It is the inverse, and because the converse of a statement is not always true, the inverse is not always true because the inverse is always equal to the converse. "if the machine never prints NPRNPR, then NPRNPR is a true statement" That statement is the inverse of the original if-then statement, and the inverse/converse is FALSE because it allows opportunities which violate the original if-then statement. I logically concluded that the statement in the proof: "if the machine never prints NPRNPR, then NPRNPR is a true statement" is a false statement. And therefore the proof is incorrect. Okay. If I am wrong, can someone please tell me where?
- evo 17y agoThe truth of the statement does not derive from being an inverse, converse, or contrapositive of the statement before it. Rather, it is inferred from what we defined "NPR" to mean. Since "NPR" is defined as true if what follows it is never printed twice in succession, and "NPRNPR" is never printed as a given, then "NPRNPR" as a statement is true.
- dbz 17y agoAh. Wonderful. I see now. Thanks a lot =]