7 ms·

Kurt Gödel and the romance of logic

126 points by daddy_drank 8y ago

craigr1972 8y ago
" He announced that he had studied the US constitution in detail, and—no doubt, forensically examining its propositions one at a time and perhaps testing it against thought experiments against wild possible futures in which the president was allowed to get out of control—he had discovered how the US could legally be turned into a dictatorship."
- oska 8y ago
  Suggestions as to what this found flaw might have been has been discussed on Quora a couple of times [1][2] [1] https://www.quora.com/How-did-G%C3%B6del-believe-the-US-could-become-a-dictatorship-without-the-constitution-being-violated https://www.quora.com/How-did-G%C3%B6del-believe-the-US-coul... [2] https://www.quora.com/What-was-the-flaw-Kurt-G%C3%B6del-discovered-in-the-US-constitution-that-would-allow-conversion-to-a-dictatorship https://www.quora.com/What-was-the-flaw-Kurt-G%C3%B6del-disc...
  - JoeSmithson 8y ago
    The first answer is from someone claiming a BS from the University of Autodidacts, who finishes with an unexplained dig at the Democratic Party.
- DyslexicAtheist 8y ago
  sadly this article skips a lot of detail on what happened during and before the hearing and how Einstein tried to coach him. The New Yorker had a much better summary on this. Here in all its hilarity: ---- from https://www.newyorker.com/magazine/2005/02/28/time-bandits-2 https://www.newyorker.com/magazine/2005/02/28/time-bandits-2 So naïve and otherworldly was the great logician that Einstein felt obliged to help look after the practical aspects of his life. One much retailed story concerns Gödel’s decision after the war to become an American citizen. The character witnesses at his hearing were to be Einstein and Oskar Morgenstern, one of the founders of game theory. Gödel took the matter of citizenship with great solemnity, preparing for the exam by making a close study of the United States Constitution. On the eve of the hearing, he called Morgenstern in an agitated state, saying he had found an “inconsistency” in the Constitution, one that could allow a dictatorship to arise. Morgenstern was amused, but he realized that Gödel was serious and urged him not to mention it to the judge, fearing that it would jeopardize Gödel’s citizenship bid. On the short drive to Trenton the next day, with Morgenstern serving as chauffeur, Einstein tried to distract Gödel with jokes. When they arrived at the courthouse, the judge was impressed by Gödel’s eminent witnesses, and he invited the trio into his chambers. After some small talk, he said to Gödel, “Up to now you have held German citizenship.” No, Gödel corrected, Austrian. “In any case, it was under an evil dictatorship,” the judge continued. “Fortunately that’s not possible in America.” “On the contrary, I can prove it is possible!” Gödel exclaimed, and he began describing the constitutional loophole he had descried. But the judge told the examinee that “he needn’t go into that,” and Einstein and Morgenstern succeeded in quieting him down. A few months later, Gödel took his oath of citizenship. ---- Another one: https://www.quickanddirtytips.com/education/science/when-g-del-almost-took-on-the-us-constitution https://www.quickanddirtytips.com/education/science/when-g-d... --- EDIT: something I also missed in this piece was that Gödel developed rheumatic fevers as a child and started reading medical books with the age of 8 to learn more about the condition. He concluded that he had a weak heart :D Gödel is really worth studying closer and this article just leaves out a lot.
  - edmundsauto 8y ago
    Coincidentally, I'm reading When Einstein Walked with Godel, and this anecdote is in there. Such an interesting man -- he's up there with Von Neumann for historical figures I'd like to learn more about, as the work they develop is a form of first principles that a lot of modern thought is derived from. Any reccs on books to read, more focused on their theories than their lives?
deleted 8y ago
[deleted]
joe_the_user 8y ago
Actually, Gödel's theory is fairly accessible compared to, say, the General Theory of Relativity. All you have to know that the process of proving a statement is a fairly mechanical, step-by-step process. At that point, "statements that can be proven true" and "statements that be proven false" are two fairly defined sets. At that point, "there are some true statements that cannot be proven true" is moderately clear. Then you introduce the idea of a model and make the concept fully exact. The thing to remember is Gödel himself never really liked this simple view and wanted truth to be more transcendent. He shared with Einstein the quality of not liking the results of his discoveries, perhaps a source of their friendship.
- skh 8y ago
  The quality of being “true” is dependent on the model one is using. One can not talk about “truth” without being in a model. (Assuming we are talking about standard mathematical logic.). A statement in a first order system is provable if and only if it is true in all models for that system.
  - joe_the_user 8y ago
    That's it, plus a model is an assignment of a truth value to every well-formed statement of logic language.
  - eximius 8y ago
    You either don't understand the point of the theorems or are being contrarian. In the context for the Incompleteness theorems, there are two 'kinds' of truths: a more informal kind used by all of us everyday and the mathematical kind as in, proven true under a given system. The entire purpose of the theorems is to establish that there exists theorems in the first set that are not in the second set, while being expressable in the system. To deny the existence of the first kind of true statements ignores the entire purpose of it all.
    - skh 8y ago
      I used the term ‘truth’ as used in mathematical logic. In a given model a statement can be true or false. Under a given axiomatic system a statement is either provable or not. We don’t use the word “true” when dealing with statement under an axiomatic system. We do use the word when dealing with a statement in a given model. Your third paragraph doens’t make sense. In first order logic a theorem is a statement that is true in all models and is one that is provable. This is a result of the Completeness Theorem.
infinity0 8y ago
> rescued the idea that there are truths that humans can never prove This is a gross misinterpretation of Gödel's actual theorem that helps perpetuate irrational superstitious attitudes against science, mathematics, and logic. What Gödel showed was that proofs are relative to some underlying axiomatic model and that for any particular axiomatic model there are always truths unprovable by it. That doesn't mean "there are truths that humans can never prove", all it means is that we have to extend our axiomatic systems in order to prove some truths. (And whether they are true or false "in reality" is another question, to be determined empirically.) A more accurate (and just-as-click-baity) way of interpreting Gödel's theorem is that "mathematicians and logicians will always have a job".
- lukaa 8y ago
  "And whether they are true or false "in reality" is another question, to be determined empirically." Mathematical and logic truths have highest apstraction level.By definition they can 't be proved or disapproved in reality they exist only in apstraction.
- joe_the_user 8y ago
  This is a gross misinterpretation of Gödel's actual theorem that helps perpetuate irrational superstitious attitudes against science, mathematics, and logic. It is, it really is. Yet is also an interpretation that Gödel himself would indulge in. Consider his most famous quote: "Either mathematics is too big for the human mind, or the human mind is more than a machine." (I remember reading this statement in the Time-Life book on mathematics when I was a kid).
  - madmax96 8y ago
    What’s the problem with the disjunction?
    - joe_the_user 8y ago
      Well, the only thing that Godel showed was that if you have consistent assignment of a truth value to every well-formed statement in a given logic language (at least as complex the Peano postulates), you will get some statements which are assigned "true" or "false" but whose truth cannot be deduced in a given axiom system for the language. However, the above statement very much involves a statement about "truth" in much transcendent sense - see the discussion of Godel's Platonism and religious beliefs in the article.
kkylin 8y ago
Anyone interested in this article may also be interested in this discussion from a while back: https://news.ycombinator.com/item?id=18115696 https://news.ycombinator.com/item?id=18115696 Also of interest is Godel's AMS Gibbs Lecture, which unfortunately I have not been able to locate on-line. It can be found in Volume 3 of Godel's Collected Works, alongside his paper / lecture notes on closed time loops in general relativity.
neokantian 8y ago
The biggest qualm that I have with the example for the incompleteness theorem, is the use of two-valued, Boolean/Aristotelian logic, in which "not true" automatically becomes "false". If you allow the use of a three-valued logic, for example, with (true, undetermined, false), the Gödel statement, “I am not provable" amounts to saying "My provability is false or undetermined". The same problem occurs in Russell's paradox, "Does the set of all sets that do NOT contain themselves, contain itself?" The use of the NOT-operator is degenerated in a cyclic group Z2. It is the only situation in which the NOT-operator is not set-valued. In my opinion, if the "isProvable()" predicate allowed for multi-valued logic, Gödel's incompleteness theorem would look much less paradoxical. In other words, the paradoxical outcome could simply be the result of Boolean shoehorning.
- deleted 8y ago
  [deleted]
- theaeolist 8y ago
  The incompleteness result does not even mention "true" and "false". It says that "there are statements of the language of F which can neither be proved nor disproved in F." Whether those statements are true/false is left unsaid.
- chewz 8y ago
  You don't grasp. Gödel's incompleteness theorems is not dependent on chosen logic or any set of axioms. It stands in 3-, 4- and N-value logic as well.
- myWindoonn 8y ago
  Gödel's result, being constructive, is buildable without the Law of Excluded Middle, and it should be buildable in any topos that has Boolean logic and LEM. (And probably some other features, like infinities.) Recall that provability from a set of axioms is a path or a chaining-together of many small deductions, each one machine-checkable, and thus we can construct a proof mechanically. Therefore we are in the realm of the Booleans since that is the realm in which the proof checker is operating. Crucially, for a given set of axioms and a given arbitrary statement, either the proof does exist, in which case we may machine-check it and use the proof statement as a witness to the proof's existence, or it does not exist, and it is equivalent to the Halting Problem to show so. To be pithy, if we choose a (true, undetermined, false) compatible with topos logic, we should be able to encode Gödel's work using only the "true" and "false" values. You have hit upon something important, though. Recall that, in constructive logic, (WFF) statements are either true, false, or not false, where "not false" is not an actual intermediate truth value, merely a potential truth value. If we take as an axiom that statements that are not false are true (double-negation elimination) then we can derive LEM. Nonetheless, "not false" is a wonderful truth value to assign to the classic paradoxes. To continue to be pithy, and to paraphrase a category theorist, "not false" is something that we see from the outside, but it isn't visible from the inside, and Gödel's theorems are all about encoding things into the inside. Suppose, indeed, that we write out the Gödel statement G in some formalized English, as "This statement is true and unprovable within Formal English." Can G be true? Yeah, sure, it's true in the integers, but not in a way that Formal English can show. (That's the incompleteness!) Can G be false? Meh, yes, but it gets nasty, because G is true in the integers, so ~G leads to a non-standard model. Could G be not false? Surprisingly, yes! I wonder whether this is the line of thought that led Bishop to his terminology.
DyslexicAtheist 8y ago
> The theoretical physicist and mathematician Roger Penrose, for example, has argued that Gödel’s theorem shows that “Strong AI” is false: our minds cannot be computers, and that by extension the intelligence of computers will never fully replicate them. Note that there are camps that have been disputing this (e.g. McCullough’s Objection): http://www.deepideas.net/godels-incompleteness-theorem-and-its-implications-for-artificial-intelligence/ http://www.deepideas.net/godels-incompleteness-theorem-and-i... and https://www.iep.utm.edu/lp-argue/#H3 https://www.iep.utm.edu/lp-argue/#H3 sadly, I'm not even close to figuring out if the Roger-Penrose argument is valid. Nada, not even a gut-feeling!
sorokod 8y ago
BBC podcast on the subject, interesting for historical background. https://www.bbc.co.uk/programmes/b00dshx3 https://www.bbc.co.uk/programmes/b00dshx3

126 points by daddy_drank 8y ago

craigr1972 8y ago

" He announced that he had studied the US constitution in detail, and—no doubt, forensically examining its propositions one at a time and perhaps testing it against thought experiments against wild possible futures in which the president was allowed to get out of control—he had discovered how the US could legally be turned into a dictatorship."

oska 8y ago
Suggestions as to what this found flaw might have been has been discussed on Quora a couple of times [1][2] [1] https://www.quora.com/How-did-G%C3%B6del-believe-the-US-could-become-a-dictatorship-without-the-constitution-being-violated https://www.quora.com/How-did-G%C3%B6del-believe-the-US-coul... [2] https://www.quora.com/What-was-the-flaw-Kurt-G%C3%B6del-discovered-in-the-US-constitution-that-would-allow-conversion-to-a-dictatorship https://www.quora.com/What-was-the-flaw-Kurt-G%C3%B6del-disc...
- JoeSmithson 8y ago
  The first answer is from someone claiming a BS from the University of Autodidacts, who finishes with an unexplained dig at the Democratic Party.
DyslexicAtheist 8y ago
sadly this article skips a lot of detail on what happened during and before the hearing and how Einstein tried to coach him. The New Yorker had a much better summary on this. Here in all its hilarity: ---- from https://www.newyorker.com/magazine/2005/02/28/time-bandits-2 https://www.newyorker.com/magazine/2005/02/28/time-bandits-2 So naïve and otherworldly was the great logician that Einstein felt obliged to help look after the practical aspects of his life. One much retailed story concerns Gödel’s decision after the war to become an American citizen. The character witnesses at his hearing were to be Einstein and Oskar Morgenstern, one of the founders of game theory. Gödel took the matter of citizenship with great solemnity, preparing for the exam by making a close study of the United States Constitution. On the eve of the hearing, he called Morgenstern in an agitated state, saying he had found an “inconsistency” in the Constitution, one that could allow a dictatorship to arise. Morgenstern was amused, but he realized that Gödel was serious and urged him not to mention it to the judge, fearing that it would jeopardize Gödel’s citizenship bid. On the short drive to Trenton the next day, with Morgenstern serving as chauffeur, Einstein tried to distract Gödel with jokes. When they arrived at the courthouse, the judge was impressed by Gödel’s eminent witnesses, and he invited the trio into his chambers. After some small talk, he said to Gödel, “Up to now you have held German citizenship.” No, Gödel corrected, Austrian. “In any case, it was under an evil dictatorship,” the judge continued. “Fortunately that’s not possible in America.” “On the contrary, I can prove it is possible!” Gödel exclaimed, and he began describing the constitutional loophole he had descried. But the judge told the examinee that “he needn’t go into that,” and Einstein and Morgenstern succeeded in quieting him down. A few months later, Gödel took his oath of citizenship. ---- Another one: https://www.quickanddirtytips.com/education/science/when-g-del-almost-took-on-the-us-constitution https://www.quickanddirtytips.com/education/science/when-g-d... --- EDIT: something I also missed in this piece was that Gödel developed rheumatic fevers as a child and started reading medical books with the age of 8 to learn more about the condition. He concluded that he had a weak heart :D Gödel is really worth studying closer and this article just leaves out a lot.
- edmundsauto 8y ago
  Coincidentally, I'm reading When Einstein Walked with Godel, and this anecdote is in there. Such an interesting man -- he's up there with Von Neumann for historical figures I'd like to learn more about, as the work they develop is a form of first principles that a lot of modern thought is derived from. Any reccs on books to read, more focused on their theories than their lives?

deleted 8y ago

[deleted]

joe_the_user 8y ago

Actually, Gödel's theory is fairly accessible compared to, say, the General Theory of Relativity. All you have to know that the process of proving a statement is a fairly mechanical, step-by-step process. At that point, "statements that can be proven true" and "statements that be proven false" are two fairly defined sets. At that point, "there are some true statements that cannot be proven true" is moderately clear. Then you introduce the idea of a model and make the concept fully exact. The thing to remember is Gödel himself never really liked this simple view and wanted truth to be more transcendent. He shared with Einstein the quality of not liking the results of his discoveries, perhaps a source of their friendship.

skh 8y ago
The quality of being “true” is dependent on the model one is using. One can not talk about “truth” without being in a model. (Assuming we are talking about standard mathematical logic.). A statement in a first order system is provable if and only if it is true in all models for that system.
- joe_the_user 8y ago
  That's it, plus a model is an assignment of a truth value to every well-formed statement of logic language.
- eximius 8y ago
  You either don't understand the point of the theorems or are being contrarian. In the context for the Incompleteness theorems, there are two 'kinds' of truths: a more informal kind used by all of us everyday and the mathematical kind as in, proven true under a given system. The entire purpose of the theorems is to establish that there exists theorems in the first set that are not in the second set, while being expressable in the system. To deny the existence of the first kind of true statements ignores the entire purpose of it all.
  - skh 8y ago
    I used the term ‘truth’ as used in mathematical logic. In a given model a statement can be true or false. Under a given axiomatic system a statement is either provable or not. We don’t use the word “true” when dealing with statement under an axiomatic system. We do use the word when dealing with a statement in a given model. Your third paragraph doens’t make sense. In first order logic a theorem is a statement that is true in all models and is one that is provable. This is a result of the Completeness Theorem.

infinity0 8y ago

> rescued the idea that there are truths that humans can never prove This is a gross misinterpretation of Gödel's actual theorem that helps perpetuate irrational superstitious attitudes against science, mathematics, and logic. What Gödel showed was that proofs are relative to some underlying axiomatic model and that for any particular axiomatic model there are always truths unprovable by it. That doesn't mean "there are truths that humans can never prove", all it means is that we have to extend our axiomatic systems in order to prove some truths. (And whether they are true or false "in reality" is another question, to be determined empirically.) A more accurate (and just-as-click-baity) way of interpreting Gödel's theorem is that "mathematicians and logicians will always have a job".

lukaa 8y ago
"And whether they are true or false "in reality" is another question, to be determined empirically." Mathematical and logic truths have highest apstraction level.By definition they can 't be proved or disapproved in reality they exist only in apstraction.
joe_the_user 8y ago
This is a gross misinterpretation of Gödel's actual theorem that helps perpetuate irrational superstitious attitudes against science, mathematics, and logic. It is, it really is. Yet is also an interpretation that Gödel himself would indulge in. Consider his most famous quote: "Either mathematics is too big for the human mind, or the human mind is more than a machine." (I remember reading this statement in the Time-Life book on mathematics when I was a kid).
- madmax96 8y ago
  What’s the problem with the disjunction?
  - joe_the_user 8y ago
    Well, the only thing that Godel showed was that if you have consistent assignment of a truth value to every well-formed statement in a given logic language (at least as complex the Peano postulates), you will get some statements which are assigned "true" or "false" but whose truth cannot be deduced in a given axiom system for the language. However, the above statement very much involves a statement about "truth" in much transcendent sense - see the discussion of Godel's Platonism and religious beliefs in the article.

kkylin 8y ago

Anyone interested in this article may also be interested in this discussion from a while back: https://news.ycombinator.com/item?id=18115696 https://news.ycombinator.com/item?id=18115696 Also of interest is Godel's AMS Gibbs Lecture, which unfortunately I have not been able to locate on-line. It can be found in Volume 3 of Godel's Collected Works, alongside his paper / lecture notes on closed time loops in general relativity.

neokantian 8y ago

The biggest qualm that I have with the example for the incompleteness theorem, is the use of two-valued, Boolean/Aristotelian logic, in which "not true" automatically becomes "false". If you allow the use of a three-valued logic, for example, with (true, undetermined, false), the Gödel statement, “I am not provable" amounts to saying "My provability is false or undetermined". The same problem occurs in Russell's paradox, "Does the set of all sets that do NOT contain themselves, contain itself?" The use of the NOT-operator is degenerated in a cyclic group Z2. It is the only situation in which the NOT-operator is not set-valued. In my opinion, if the "isProvable()" predicate allowed for multi-valued logic, Gödel's incompleteness theorem would look much less paradoxical. In other words, the paradoxical outcome could simply be the result of Boolean shoehorning.

deleted 8y ago
[deleted]
theaeolist 8y ago
The incompleteness result does not even mention "true" and "false". It says that "there are statements of the language of F which can neither be proved nor disproved in F." Whether those statements are true/false is left unsaid.
chewz 8y ago
You don't grasp. Gödel's incompleteness theorems is not dependent on chosen logic or any set of axioms. It stands in 3-, 4- and N-value logic as well.
myWindoonn 8y ago
Gödel's result, being constructive, is buildable without the Law of Excluded Middle, and it should be buildable in any topos that has Boolean logic and LEM. (And probably some other features, like infinities.) Recall that provability from a set of axioms is a path or a chaining-together of many small deductions, each one machine-checkable, and thus we can construct a proof mechanically. Therefore we are in the realm of the Booleans since that is the realm in which the proof checker is operating. Crucially, for a given set of axioms and a given arbitrary statement, either the proof does exist, in which case we may machine-check it and use the proof statement as a witness to the proof's existence, or it does not exist, and it is equivalent to the Halting Problem to show so. To be pithy, if we choose a (true, undetermined, false) compatible with topos logic, we should be able to encode Gödel's work using only the "true" and "false" values. You have hit upon something important, though. Recall that, in constructive logic, (WFF) statements are either true, false, or not false, where "not false" is not an actual intermediate truth value, merely a potential truth value. If we take as an axiom that statements that are not false are true (double-negation elimination) then we can derive LEM. Nonetheless, "not false" is a wonderful truth value to assign to the classic paradoxes. To continue to be pithy, and to paraphrase a category theorist, "not false" is something that we see from the outside, but it isn't visible from the inside, and Gödel's theorems are all about encoding things into the inside. Suppose, indeed, that we write out the Gödel statement G in some formalized English, as "This statement is true and unprovable within Formal English." Can G be true? Yeah, sure, it's true in the integers, but not in a way that Formal English can show. (That's the incompleteness!) Can G be false? Meh, yes, but it gets nasty, because G is true in the integers, so ~G leads to a non-standard model. Could G be not false? Surprisingly, yes! I wonder whether this is the line of thought that led Bishop to his terminology.

DyslexicAtheist 8y ago

> The theoretical physicist and mathematician Roger Penrose, for example, has argued that Gödel’s theorem shows that “Strong AI” is false: our minds cannot be computers, and that by extension the intelligence of computers will never fully replicate them. Note that there are camps that have been disputing this (e.g. McCullough’s Objection): http://www.deepideas.net/godels-incompleteness-theorem-and-its-implications-for-artificial-intelligence/ http://www.deepideas.net/godels-incompleteness-theorem-and-i... and https://www.iep.utm.edu/lp-argue/#H3 https://www.iep.utm.edu/lp-argue/#H3 sadly, I'm not even close to figuring out if the Roger-Penrose argument is valid. Nada, not even a gut-feeling!

sorokod 8y ago

BBC podcast on the subject, interesting for historical background. https://www.bbc.co.uk/programmes/b00dshx3 https://www.bbc.co.uk/programmes/b00dshx3