4 ms·

Gödel and the limits of logic (2006)

148 points by Pishky 10y ago

kruhft 10y ago
I highly recommend getting Godel's proof[1] and reading it. It's an amazing journey and quite understandable from the start (the first half of the book is introduction), and I've never been able to read proofs very well. It takes concentration, but once you get it (at '17 GenR') it's almost like a symphony going off. The crystalline brilliance of the "System P" decomposition is worth it just to see how math as a process could be reduced to a such simple, clear and concise set of symbol manipulations...and then the rest shows how that could be used topple itself. Incredibly philosophically insightful. [1] https://www.amazon.ca/Undecidable-Propositions-Principia-Mathematica-Mathematics-ebook/dp/B00A44R3E8/ref=sr_1_1?ie=UTF8&qid=1489447527&sr=8-1&keywords=on+formally+undecidable+systems+godel https://www.amazon.ca/Undecidable-Propositions-Principia-Mat...
- ucarion 10y ago
  I can't speak for Godel's original proof since I haven't seen it before, but I certainly found Computability and Logic [1] to be pretty approachable. It's the textbook used for UC Berkeley's "Intermediate Logic" philosophy course (in other words, it's so easy even philosophy majors can understand it! :P). From my understanding, C&L diverges from Godel's original proof technique in order to make it easier to follow, but it's much more rigorous and explicit than what you'd find in Godel, Escher, Bach or something. It's still a textbook. [1]: https://www.amazon.com/Computability-Logic-George-S-Boolos/dp/0521701465 https://www.amazon.com/Computability-Logic-George-S-Boolos/d...
- cgh 10y ago
  I try to read Godel's Proof once a year or so. You might also be interested in Gregory Chaitin's Meta Math! The Quest For Omega, which relates the halting problem (among other things) to Godel. A word of warning though, the book is rather idiosyncratic, as you might have seen from the title.
  - kruhft 10y ago
    Got it years ago and loved it. Have to give it another read some day.
bitL 10y ago
Isn't Gödel's incompleteness a consequence of overly ambitious material implication properties? When you look at the truth table: A | B | A -> B 0 | 0 | 1 0 | 1 | 1 1 | 0 | 0 1 | 1 | 1 I fail to see why all except for 1 -> 0 = 0 aren't undefined. I understand reasoning behind why this was done, but mixing unrelated predicates seems like a generally bad idea, even if it allows mechanical proofs. Aren't there already "complete" systems like relevance logic? Now with computers we can perhaps make proofs we need "relevant" instead of being based on fundamentally incomplete though "simpler" logic?
- acchow 10y ago
  1 -> 0 = 0 What does this mean? Is the 0 after the equals the antecedent? Consequent?
  - pmcjones 10y ago
    (1 -> 0) = 0. In other words, (true implies false) is false.
    - acchow 10y ago
      "is false" doesn't mean anything in Godel's system. That's too high level and imprecise. We're dealing with only symbol manipulation here. We only have provability (which really is "there exists a derivation for") - we don't have "truth".
- contravariant 10y ago
  Logic already has separate symbols for 'A implies B' and 'A proves B', where the first can be considered equivalent to '(not A) or B' for all intents and purposes. Since 'A proves B' seems like the very definition of relevance, the only part you could possibly object to is that 'A proves B' implies 'A implies B', but that's given since the alternative would lead to a contradiction where A proves B, but B is false while A is not. Also, if I understand you correctly you're trying to 'fix' incompleteness by making A -> B undecidable, which seems like it would achieve the opposite.
- 10y ago
tmsldd 10y ago
I like very much the program x virus example/citation.. but I would put it in the other way around: "A program can find all virus, unless the operating system is a virus itself."
noobee 10y ago
A light take on the subject can be found in Logicomix: https://en.wikipedia.org/wiki/Logicomix https://en.wikipedia.org/wiki/Logicomix - a cool blend between the dry topic and comics.
- AndrewKemendo 10y ago
  Thanks for the recommendation. I found it on scribd if anyone is interested: https://www.scribd.com/document/98921232/Bertrand-Russell-Logicomix https://www.scribd.com/document/98921232/Bertrand-Russell-Lo...
laxd 10y ago
Are there any Gödel-like problems that does not involve self references?
- jpt4 10y ago
  Yablo's Paradox [0], possibly [1]. Regarding [1], "circularity" in an uncountably infinite context seems different than "self-referential", though the latter is usually geometrically analogized as the former. I tentatively consider Yablo's Paradox to demonstrate that an ineradicable cycle of alternating truth-assignments is equivalent to an infinite (>= aleph-one) regression of alternating truth-assignments, and thus that circularity does not map coherently to self-reference in all logic systems. [0] http://www.mit.edu/~yablo/pwsr.pdf http://www.mit.edu/~yablo/pwsr.pdf [1] http://ferenc.andrasek.hu/papersybprx/jcbeal_is_yablo_non_circular.pdf http://ferenc.andrasek.hu/papersybprx/jcbeal_is_yablo_non_ci...
  - pacala 10y ago
    Yablo paradox is so cool. Imagine an infinite sequence of sentences S1, S2, S3, ..., (S1) for all k >1, Sk is untrue (S2) for all k >2, Sk is untrue (S3) for all k >3, Sk is untrue ... Perhaps another argument in favor of regarding infinites as a logical fallacy. Assuming our universe is finite, all objects in the universe are finite, including sets. Yablo's set chain ends at some N, possibly very very very large. Sentence N is true [there are no further sequences], all other sentences are untrue, as there exists a true sentence with k > i: the Nth sentence.
    - lmm 10y ago
      Infinities can be handled safely in logic. You just have to be careful about them. There may not be physically real infinities. But there are no physically real perfect squares either (assuming an analogue universe). It's a simplified model.
      - raattgift 10y ago
        > But there are no physically real perfect squares either (assuming an analogue universe). How does analogue vs digital (assuming you mean that analogue) matter here? You'd also want to specify which "digital physics" you want to rely on. We don't need to think along those lines to consider a physically real idealized geometrical object. Here I'll recast your square as a planar slice through a real object in our (3d+1d) universe. With reasonable assumptions about the local behaviour of spacetime, you can't construct a physically perfect square because of the small-length-scale behaviour of matter rather than that or the presence of infinities of infinitesimals. The assumption here is that locally around the square the spacetime is Minkowskian, which for a small and light square is practically guaranteed everywhere outside the event horizons of black holes and far from the hot dense phase of the universe. "Practically guaranteed" here means that in spite of plausible theoretical objections to the perfectness, there exists no mechanism to show that the object is not a perfect square (i.e., such objections are conjectural physics leaning hard on a purely mathematical argument). "Digitalization" and discretization arguments run into observational problems right away. The wavelength of light is not quantized, for example, and is not clearly bounded in the infrared. (In the ultraviolet you get pair production and gravitational collapse, however.) While one could make an argument that at the emission event of every photon there is not an infinity of available photon wavelengths, you would have to forbid infinitesimal spacetime intervals to avoid emitted photons stretching into arbitrary wavelengths under the metric expansion of the universe, and the only practical way of doing that is through discretization (with or without emergence). There is a substantial weight of evidence that suggests that if spacetime (or whatever it emerges from) is discretized, the discretization length is not significantly above the Planck length; notably gamma rays, x-rays, light and radio from violent astrophysical events do not appear to win races against each other in an ordered fashion. So there may be infinitesimal spacetime intervals, and so any quantity that depends on spacetime intervals has an infinite set of values to choose from. Absent a description of gravity-matter interaction when matter's small-scale behaviours are relevant, we cannot really preclude the possibility of building a perfect square in an unreasonable (but nevertheless physical) local patch of dynamical spacetime, such that the microscopic behaviour of the latter offsets the odd quantum mechanical contributions to the square. At best we can try to place limits on how long such a system could survive (it could last a very long time in the cold sparse phase of the universe).
personjerry 10y ago
This reminds me of the Berry Paradox: https://en.wikipedia.org/wiki/Berry_paradox https://en.wikipedia.org/wiki/Berry_paradox
470b23bb7c9c44b 10y ago
Why have I never had to debug a Gödel paradox in my day-to-day programming? Is it because of types? Finite memory? Can someone enlighten me? Thanks
- neel_k 10y ago
  You almost certainly have had to debug a Gödelian paradox in your day-to-day programming. It's just that programmers call it "nontermination" or "infinite loops". In 1952 the logician Martin Löb invented something called "provability logic" as a way to formulate Gödel's theorem more abstractly, so that we could see how the proof worked without having to work with explicit numerical encodings of formulas. (Think of this as the difference between working with strings versus abstract syntax trees.) His version of the proof is now called Löb's theorem, and its structure is almost identical to what logicians call Curry's paradox, and which (via the Curry-Howard correspondence) programmers know as the Y combinator. The Y combinator is used to implement recursion in the lambda calculus, specifically including the ability to go into infinite loops. I blogged about this last year: http://semantic-domain.blogspot.co.uk/2016/05/lobs-theorem-is-almost-y-combinator.html http://semantic-domain.blogspot.co.uk/2016/05/lobs-theorem-i...
DigitalPhysics 10y ago
"Digital Physics" (the movie) is now free on Amazon Prime. It is also available for rent/purchase on iTunes and Vimeo, in case you are kind enough to support an independent filmmaker:) Come explore the world of self-reference, infinity, complexity, Gödel & Turing, and psychedelics with Khatchig!!

148 points by Pishky 10y ago

I highly recommend getting Godel's proof[1] and reading it. It's an amazing journey and quite understandable from the start (the first half of the book is introduction), and I've never been able to read proofs very well. It takes concentration, but once you get it (at '17 GenR') it's almost like a symphony going off. The crystalline brilliance of the "System P" decomposition is worth it just to see how math as a process could be reduced to a such simple, clear and concise set of symbol manipulations...and then the rest shows how that could be used topple itself. Incredibly philosophically insightful. [1] https://www.amazon.ca/Undecidable-Propositions-Principia-Mathematica-Mathematics-ebook/dp/B00A44R3E8/ref=sr_1_1?ie=UTF8&qid=1489447527&sr=8-1&keywords=on+formally+undecidable+systems+godel https://www.amazon.ca/Undecidable-Propositions-Principia-Mat...

ucarion 10y ago
I can't speak for Godel's original proof since I haven't seen it before, but I certainly found Computability and Logic [1] to be pretty approachable. It's the textbook used for UC Berkeley's "Intermediate Logic" philosophy course (in other words, it's so easy even philosophy majors can understand it! :P). From my understanding, C&L diverges from Godel's original proof technique in order to make it easier to follow, but it's much more rigorous and explicit than what you'd find in Godel, Escher, Bach or something. It's still a textbook. [1]: https://www.amazon.com/Computability-Logic-George-S-Boolos/dp/0521701465 https://www.amazon.com/Computability-Logic-George-S-Boolos/d...
cgh 10y ago
I try to read Godel's Proof once a year or so. You might also be interested in Gregory Chaitin's Meta Math! The Quest For Omega, which relates the halting problem (among other things) to Godel. A word of warning though, the book is rather idiosyncratic, as you might have seen from the title.
- kruhft 10y ago
  Got it years ago and loved it. Have to give it another read some day.

bitL 10y ago

Isn't Gödel's incompleteness a consequence of overly ambitious material implication properties? When you look at the truth table: A | B | A -> B 0 | 0 | 1 0 | 1 | 1 1 | 0 | 0 1 | 1 | 1 I fail to see why all except for 1 -> 0 = 0 aren't undefined. I understand reasoning behind why this was done, but mixing unrelated predicates seems like a generally bad idea, even if it allows mechanical proofs. Aren't there already "complete" systems like relevance logic? Now with computers we can perhaps make proofs we need "relevant" instead of being based on fundamentally incomplete though "simpler" logic?

acchow 10y ago
1 -> 0 = 0 What does this mean? Is the 0 after the equals the antecedent? Consequent?
- pmcjones 10y ago
  (1 -> 0) = 0. In other words, (true implies false) is false.
  - acchow 10y ago
    "is false" doesn't mean anything in Godel's system. That's too high level and imprecise. We're dealing with only symbol manipulation here. We only have provability (which really is "there exists a derivation for") - we don't have "truth".
contravariant 10y ago
Logic already has separate symbols for 'A implies B' and 'A proves B', where the first can be considered equivalent to '(not A) or B' for all intents and purposes. Since 'A proves B' seems like the very definition of relevance, the only part you could possibly object to is that 'A proves B' implies 'A implies B', but that's given since the alternative would lead to a contradiction where A proves B, but B is false while A is not. Also, if I understand you correctly you're trying to 'fix' incompleteness by making A -> B undecidable, which seems like it would achieve the opposite.
10y ago

tmsldd 10y ago

I like very much the program x virus example/citation.. but I would put it in the other way around: "A program can find all virus, unless the operating system is a virus itself."

noobee 10y ago

A light take on the subject can be found in Logicomix: https://en.wikipedia.org/wiki/Logicomix https://en.wikipedia.org/wiki/Logicomix - a cool blend between the dry topic and comics.

AndrewKemendo 10y ago
Thanks for the recommendation. I found it on scribd if anyone is interested: https://www.scribd.com/document/98921232/Bertrand-Russell-Logicomix https://www.scribd.com/document/98921232/Bertrand-Russell-Lo...

laxd 10y ago

Are there any Gödel-like problems that does not involve self references?

jpt4 10y ago
Yablo's Paradox [0], possibly [1]. Regarding [1], "circularity" in an uncountably infinite context seems different than "self-referential", though the latter is usually geometrically analogized as the former. I tentatively consider Yablo's Paradox to demonstrate that an ineradicable cycle of alternating truth-assignments is equivalent to an infinite (>= aleph-one) regression of alternating truth-assignments, and thus that circularity does not map coherently to self-reference in all logic systems. [0] http://www.mit.edu/~yablo/pwsr.pdf http://www.mit.edu/~yablo/pwsr.pdf [1] http://ferenc.andrasek.hu/papersybprx/jcbeal_is_yablo_non_circular.pdf http://ferenc.andrasek.hu/papersybprx/jcbeal_is_yablo_non_ci...
- pacala 10y ago
  Yablo paradox is so cool. Imagine an infinite sequence of sentences S1, S2, S3, ..., (S1) for all k >1, Sk is untrue (S2) for all k >2, Sk is untrue (S3) for all k >3, Sk is untrue ... Perhaps another argument in favor of regarding infinites as a logical fallacy. Assuming our universe is finite, all objects in the universe are finite, including sets. Yablo's set chain ends at some N, possibly very very very large. Sentence N is true [there are no further sequences], all other sentences are untrue, as there exists a true sentence with k > i: the Nth sentence.
  - lmm 10y ago
    Infinities can be handled safely in logic. You just have to be careful about them. There may not be physically real infinities. But there are no physically real perfect squares either (assuming an analogue universe). It's a simplified model.
    - raattgift 10y ago
      > But there are no physically real perfect squares either (assuming an analogue universe). How does analogue vs digital (assuming you mean that analogue) matter here? You'd also want to specify which "digital physics" you want to rely on. We don't need to think along those lines to consider a physically real idealized geometrical object. Here I'll recast your square as a planar slice through a real object in our (3d+1d) universe. With reasonable assumptions about the local behaviour of spacetime, you can't construct a physically perfect square because of the small-length-scale behaviour of matter rather than that or the presence of infinities of infinitesimals. The assumption here is that locally around the square the spacetime is Minkowskian, which for a small and light square is practically guaranteed everywhere outside the event horizons of black holes and far from the hot dense phase of the universe. "Practically guaranteed" here means that in spite of plausible theoretical objections to the perfectness, there exists no mechanism to show that the object is not a perfect square (i.e., such objections are conjectural physics leaning hard on a purely mathematical argument). "Digitalization" and discretization arguments run into observational problems right away. The wavelength of light is not quantized, for example, and is not clearly bounded in the infrared. (In the ultraviolet you get pair production and gravitational collapse, however.) While one could make an argument that at the emission event of every photon there is not an infinity of available photon wavelengths, you would have to forbid infinitesimal spacetime intervals to avoid emitted photons stretching into arbitrary wavelengths under the metric expansion of the universe, and the only practical way of doing that is through discretization (with or without emergence). There is a substantial weight of evidence that suggests that if spacetime (or whatever it emerges from) is discretized, the discretization length is not significantly above the Planck length; notably gamma rays, x-rays, light and radio from violent astrophysical events do not appear to win races against each other in an ordered fashion. So there may be infinitesimal spacetime intervals, and so any quantity that depends on spacetime intervals has an infinite set of values to choose from. Absent a description of gravity-matter interaction when matter's small-scale behaviours are relevant, we cannot really preclude the possibility of building a perfect square in an unreasonable (but nevertheless physical) local patch of dynamical spacetime, such that the microscopic behaviour of the latter offsets the odd quantum mechanical contributions to the square. At best we can try to place limits on how long such a system could survive (it could last a very long time in the cold sparse phase of the universe).

personjerry 10y ago

This reminds me of the Berry Paradox: https://en.wikipedia.org/wiki/Berry_paradox https://en.wikipedia.org/wiki/Berry_paradox

470b23bb7c9c44b 10y ago

Why have I never had to debug a Gödel paradox in my day-to-day programming? Is it because of types? Finite memory? Can someone enlighten me? Thanks

neel_k 10y ago
You almost certainly have had to debug a Gödelian paradox in your day-to-day programming. It's just that programmers call it "nontermination" or "infinite loops". In 1952 the logician Martin Löb invented something called "provability logic" as a way to formulate Gödel's theorem more abstractly, so that we could see how the proof worked without having to work with explicit numerical encodings of formulas. (Think of this as the difference between working with strings versus abstract syntax trees.) His version of the proof is now called Löb's theorem, and its structure is almost identical to what logicians call Curry's paradox, and which (via the Curry-Howard correspondence) programmers know as the Y combinator. The Y combinator is used to implement recursion in the lambda calculus, specifically including the ability to go into infinite loops. I blogged about this last year: http://semantic-domain.blogspot.co.uk/2016/05/lobs-theorem-is-almost-y-combinator.html http://semantic-domain.blogspot.co.uk/2016/05/lobs-theorem-i...

DigitalPhysics 10y ago

"Digital Physics" (the movie) is now free on Amazon Prime. It is also available for rent/purchase on iTunes and Vimeo, in case you are kind enough to support an independent filmmaker:) Come explore the world of self-reference, infinity, complexity, Gödel & Turing, and psychedelics with Khatchig!!