7 ms·

This theorem actually changed my life. Once it clicked for me it shifted my understanding of reality significantly.

by theWheez 7y ago

vga805 7y ago
Can you expand on this, I am quite curious.
- theWheez 7y ago
  This, alongside the second incompleteness theorem, showed me that any formal system cannot prove itself, and any system deemed "consistent" can only be considered as such from outside that system. A great way that I visualize it (thanks to Hofstadter) is like Escher's never ending staircase painting. If you look at each step, it looks just fine. In fact, you can say that each step on its own is "consistent". But it is only when you take a step back, outside the system of each isolated step, that you see the paradox. Similarly, the theorem applies this to mathematics, and by extent, any formal system. Just as we can see each "step" going from one to the next, in mathematics we must hold an axiom as truth without proof, so that subsequent theorems may use it as the next "step". It is, in a sense, a paradox which we agree to use. In practical terms, I may extrapolate that further and more philosophically than was intended (or that I have commonly seen), but the subsequent Halting Problem combined with the Curry-Howard isomorphism shows me that Godel's Theorem has major real world effects. The idea that there can be something that is true but not provable rings true to me in many regards. I, like many, spend nearly every moment of the day unconsciously putting faith into the "truth" that I am not alone in the universe, thereby fending off solipsism. I cannot prove "I" exist. But it is true. What are the other truths that cannot be proven? That question guides my thinking.
  - psychometry 7y ago
    The FIT is a statement about finitary number theory. Even Godel, who was an ardent platonist, wouldn't try to extrapolate it to philosophy.
    - theWheez 7y ago
      Yes, I understand that, and am well aware of Godel's position on its application. Hence my statement that I extrapolate it further than intended. My extrapolation is influenced by the Curry-Howard isomorphism, equating computer programs and mathematical proofs. Extrapolation to "reality" and philosophy, to me, comes from my belief of computing as universal and that consciousness is not so separate from computing.
      - psychometry 7y ago
        That's kind of ridiculous, though. You completely lose the sense of the theorem once you expand the axioms beyond those explicitly defined. It would be like saying we don't know whether a boulder will stop rolling down a hill or not...because of the Halting Problem. That's just not how mathematics works.
        theWheez 7y ago
        I'm not expanding the axioms, I'm comparing the paradoxical nature of mathematics to other systems. I'm not saying that reality is encompassed in the theorem because "mathematics", I'm positing that if mathematics, a man-made formal system, is self-consistent but requires a true, unprovable statement, then perhaps other man-made systems might reveal similar paradoxes, when put under scrutiny. Mathematics is unique in that it is systematic and, as Godel discovered, able to be self referential and explicitly outline this paradox. Yet one can recreate the sense of the theorem in English with the phrase "this sentence is false". This doesn't invalidate mathematics, nor English, nor any system. It simply demonstrates that what we may consider the "sound" logic of mathematics is paridoxical, and I believe that this paradox, this strange loop, is not unique to Godel's mathematical theory alone.
        psychometry 7y ago
        Considering the Godel sentence is a purely syntactical construction, I think even Godel himself would have a very difficult time even imagining what an analog would be in some higher system (much less actually constructing one). This is why he was so critical of attempts by others (e.g. Wittgenstein) to knock down the theorem by discussing its philosophical implications.
meowface 7y ago
I've tried to make this click for me for a long time, to no avail. Do you have any tips?
- solinent 7y ago
  Essentially, all logically valid formulae have proofs in first-order logics. Remember, logically valid formulae means that if you enumerate all possible interpretations (boolean values for the variables), the formulae remains true. So you could prove everything that ever exists by creating a set of all possible proofs using the given deduction rules.
  - xamuel 7y ago
    This is 1st-order logic so it's a bit more complicated, though you're on the right track (what you stated is the completeness theorem for propositional logic, not first-order logic). Rather than boolean values for the variables, you need to enumerate all possible... * Ambient universes where the language is interpreted * Values (taken from the ambient universe) for the constant symbols * Sets-of-tuples-of-values (from the ambient universe) for the predicate symbols * Functions-from-tuples-of-values-to-values (from the ambient universe) for the function symbols
    - solinent 7y ago
      Yup, my definition of interpretation was limited for pedagogical purposes, but I should have been clearer. The propositional logic version is much simpler to understand, but the implications of the theorem are much more interesting in first-order logic, so introducing all of this nomenclature may be too much for someone who isn't motivated yet.
- theWheez 7y ago
  I think going through The Little Schemer by Daniel Friedman and Matthias Felleisen helped me a lot. It builds up your knowledge in a conversational way to achieve understanding of quite complex ideas in simple terms. In that case, it builds up to an understanding of the halting problem, and then to the Y Combinator. The click felt to me similar to understanding recursion for the first time--it doesn't fit into your head naturally. Once it does "click", even then you have to re-remember it later, and trace your logic on how you "realized" recursion. Godel's Theorem brings that "feeling" of recursion and takes it to the extreme, in that its subject matter is "meta"-mathematical. So in the same way that recursion can't be grokked in terms of only loops, Godel's Theorem can't be grokked only in terms of equations. I don't know if that made sense, I've also seen some links in this thread which I think may help as well
disease 7y ago
I took an entire college course on it and it never really clicked for me. Still very interesting though.
pkulak 7y ago
I read most of Gödel, Escher, Bach years ago and I remember it clicking back then... but now I've lost it again. :(

This theorem actually changed my life. Once it clicked for me it shifted my understanding of reality significantly.

vga805 7y ago

Can you expand on this, I am quite curious.

theWheez 7y ago
This, alongside the second incompleteness theorem, showed me that any formal system cannot prove itself, and any system deemed "consistent" can only be considered as such from outside that system. A great way that I visualize it (thanks to Hofstadter) is like Escher's never ending staircase painting. If you look at each step, it looks just fine. In fact, you can say that each step on its own is "consistent". But it is only when you take a step back, outside the system of each isolated step, that you see the paradox. Similarly, the theorem applies this to mathematics, and by extent, any formal system. Just as we can see each "step" going from one to the next, in mathematics we must hold an axiom as truth without proof, so that subsequent theorems may use it as the next "step". It is, in a sense, a paradox which we agree to use. In practical terms, I may extrapolate that further and more philosophically than was intended (or that I have commonly seen), but the subsequent Halting Problem combined with the Curry-Howard isomorphism shows me that Godel's Theorem has major real world effects. The idea that there can be something that is true but not provable rings true to me in many regards. I, like many, spend nearly every moment of the day unconsciously putting faith into the "truth" that I am not alone in the universe, thereby fending off solipsism. I cannot prove "I" exist. But it is true. What are the other truths that cannot be proven? That question guides my thinking.
- psychometry 7y ago
  The FIT is a statement about finitary number theory. Even Godel, who was an ardent platonist, wouldn't try to extrapolate it to philosophy.
  - theWheez 7y ago
    Yes, I understand that, and am well aware of Godel's position on its application. Hence my statement that I extrapolate it further than intended. My extrapolation is influenced by the Curry-Howard isomorphism, equating computer programs and mathematical proofs. Extrapolation to "reality" and philosophy, to me, comes from my belief of computing as universal and that consciousness is not so separate from computing.
    - psychometry 7y ago
      That's kind of ridiculous, though. You completely lose the sense of the theorem once you expand the axioms beyond those explicitly defined. It would be like saying we don't know whether a boulder will stop rolling down a hill or not...because of the Halting Problem. That's just not how mathematics works.
      - theWheez 7y ago
        I'm not expanding the axioms, I'm comparing the paradoxical nature of mathematics to other systems. I'm not saying that reality is encompassed in the theorem because "mathematics", I'm positing that if mathematics, a man-made formal system, is self-consistent but requires a true, unprovable statement, then perhaps other man-made systems might reveal similar paradoxes, when put under scrutiny. Mathematics is unique in that it is systematic and, as Godel discovered, able to be self referential and explicitly outline this paradox. Yet one can recreate the sense of the theorem in English with the phrase "this sentence is false". This doesn't invalidate mathematics, nor English, nor any system. It simply demonstrates that what we may consider the "sound" logic of mathematics is paridoxical, and I believe that this paradox, this strange loop, is not unique to Godel's mathematical theory alone.
        psychometry 7y ago
        Considering the Godel sentence is a purely syntactical construction, I think even Godel himself would have a very difficult time even imagining what an analog would be in some higher system (much less actually constructing one). This is why he was so critical of attempts by others (e.g. Wittgenstein) to knock down the theorem by discussing its philosophical implications.

meowface 7y ago

I've tried to make this click for me for a long time, to no avail. Do you have any tips?

solinent 7y ago
Essentially, all logically valid formulae have proofs in first-order logics. Remember, logically valid formulae means that if you enumerate all possible interpretations (boolean values for the variables), the formulae remains true. So you could prove everything that ever exists by creating a set of all possible proofs using the given deduction rules.
- xamuel 7y ago
  This is 1st-order logic so it's a bit more complicated, though you're on the right track (what you stated is the completeness theorem for propositional logic, not first-order logic). Rather than boolean values for the variables, you need to enumerate all possible... * Ambient universes where the language is interpreted * Values (taken from the ambient universe) for the constant symbols * Sets-of-tuples-of-values (from the ambient universe) for the predicate symbols * Functions-from-tuples-of-values-to-values (from the ambient universe) for the function symbols
  - solinent 7y ago
    Yup, my definition of interpretation was limited for pedagogical purposes, but I should have been clearer. The propositional logic version is much simpler to understand, but the implications of the theorem are much more interesting in first-order logic, so introducing all of this nomenclature may be too much for someone who isn't motivated yet.
theWheez 7y ago
I think going through The Little Schemer by Daniel Friedman and Matthias Felleisen helped me a lot. It builds up your knowledge in a conversational way to achieve understanding of quite complex ideas in simple terms. In that case, it builds up to an understanding of the halting problem, and then to the Y Combinator. The click felt to me similar to understanding recursion for the first time--it doesn't fit into your head naturally. Once it does "click", even then you have to re-remember it later, and trace your logic on how you "realized" recursion. Godel's Theorem brings that "feeling" of recursion and takes it to the extreme, in that its subject matter is "meta"-mathematical. So in the same way that recursion can't be grokked in terms of only loops, Godel's Theorem can't be grokked only in terms of equations. I don't know if that made sense, I've also seen some links in this thread which I think may help as well

disease 7y ago

I took an entire college course on it and it never really clicked for me. Still very interesting though.

pkulak 7y ago

I read most of Gödel, Escher, Bach years ago and I remember it clicking back then... but now I've lost it again. :(