8 ms·

Poincaré, Heisenberg, Gödel and the limits of scientific knowledge

86 points by bmc7505 5y ago

deleted 5y ago
[deleted]
triska 5y ago
Quoting from the article: "The young Austrian mathematician Kurt Gödel tackled the problem and found that Hilbert’s expectations where [sic] fulfilled for first-order logic." This (i.e., "Hilbert's expectations were fulfilled for first-order logic") is a common misconception, but it is not the case. For instance, ZFC is an example of a first-order theory that does not satisfy Hilbert's expectations mentioned in the article (consistency, completeness and decidability). Notably, if ZFC is consistent, then it is incomplete. Another example of a first-order theory that is essentially incomplete and not decidable is Robinson arithmetic: https://en.wikipedia.org/wiki/Robinson_arithmetic https://en.wikipedia.org/wiki/Robinson_arithmetic The confusion likely stems from the fact that Gödel proved first-order logic to be semantically complete (Gödel's completeness theorem), i.e., all its valid formulae can be derived as theorems. This does not mean that all first-order theories are syntactically complete, i.e, for every statement S, either S or its negation ¬S is in the theory. This kind of incompleteness is what Gödel's incompleteness results are about, and this phenomenon already arises in first-order logic. The common independence results of ZFC are well-known examples of this kind of incompleteness: ZFC, if consistent, does not prove them, and also does not prove their negation. Gödel's first incompleteness theorem shows that every sufficiently powerful formal system exhibits this kind of incompleteness. Also first-order theories exhibit it if they are sufficiently powerful. With today's terminology and models of computation, it is easy to show this, because first-order logic is sufficient to express a Turing machine as a theory, and if we let S be the (first-order) statement "The machine reaches a halting state", then, if we had a mechanism that always terminates and always correctly decides whether S or its negation ¬S is in the theory, then we would have an algorithm that solves the halting problem, which, however, is easily shown to be only semi-decidable, not decidable. Hence, not all first-order theories are consistent, complete and decidable.
- bsaul 5y ago
  Not a logician, but it’s the first time i’ve heard Gödel incompleteness being about trying to say something about syntactically invalid formulas.. Do you have more pointers on that ? it makes me curious.
  - laszlokorte 5y ago
    „Valid“ does not mean syntactically valid but „true in any case“
  - triska 5y ago
    Every statement S has a negation ¬S, read as "not S". If S is well-formed, so is its negation. For example, if we take the continuum hypothesis, i.e.: "There is no set whose cardinality is strictly between that of the integers and the real numbers." and construct S to express this statement in the language of our theory (say ZFC), then the negated statement ¬S would correspond to: "There is a set whose cardinality is strictly between that of the integers and the real numbers." Famously, the continuum hypothesis is independent of ZFC. This means that (assuming consistency of ZFC), ZFC does not prove S, and also does not prove ¬S. From a consistent and syntactically complete theory, we expect that it contains exactly one of these statements. Is it the case or not? The fact that ZFC does not "tell" us which it is means that it is incomplete in this sense. Clearly, a question that is important to us is left unanswered by this theory, since neither the statement nor its negation is provable with the given axioms. A syntactically complete theory is also called deductively complete, or negation complete. An example of a first-order theory that is consistent, complete, and also decidable is Presburger arithmetic: https://en.wikipedia.org/wiki/Presburger_arithmetic https://en.wikipedia.org/wiki/Presburger_arithmetic Every question you have about its sentences will be answered by the theory one way or the other by either proving the statement or its negation.
    - ProfHewitt 5y ago
      The Continuum Hypothesis is still an open question in foundational mathematical theories that are more powerful than 1st-order ZFC such as the theory Ordinals. See the following: https://papers.ssrn.com/abstract=3457802 https://papers.ssrn.com/abstract=3457802 Someday, the Continuum Hypothesis might be proved or it might be disproved in foundational theories.
mjburgess 5y ago
Observations on the limits of knowledge, 1. Predicting long-run evolution of chaotic systems require more measurement precision in the initial conditions than quantum mechanics allows 2. With sufficient density, a discrete system cannot be simulated with less energy than the original system possess 3. With sufficient complexity, (as above) 4. The mass required for measurement, and energy required for computing, the structure of ordinary objects (eg., chairs) from their parts eclipses anything we could build 5. Randomness isnt computable 6. Real numbers aren computable 7... Any more?
- motohagiography 5y ago
  Is there a formal definition of randomness that is just an information gap (like Shannon), and the predictability and measurability of complex systems breaks down because the chaos is just a loss of information in each iteration of its function? If so, where does the information go?
  - mjburgess 5y ago
    It never existed in the first place: reality isnt fully determined.
JDEW 5y ago
> We have already noted that quantum physics offers a world view in which the future is not entirely determined. This indeterminacy is not practical but fundamental. It permits us to think that our experience of free will may be real instead of merely subjective. If the outcome of a quantum process is undetermined, there is no fundamental reason to deny that possibility in some neural events which may be a macroscopic amplification of microscopic processes where quantum indeterminacy plays an essential role. I don't see how free will follows from indeterminacy. Just because you can't predict future outcomes from initial values doesn't mean that there is "choice" involved in the evolution of a system.
- akimball 5y ago
  The quote and your observation are compatible. I would also observe that predictive determinacy does not preclude choice.
  - simonh 5y ago
    I am not convinced of their compatibility, as I explained in my sibling post to yours. I think free will of an agent means the choice is determined by the agent's state, because as a materialist I think your state and 'you' are the same thing. I am my state. Any choice that does not principally depend on my state is not my choice, because I am not the cause of it.
    - deleted 5y ago
      [deleted]
    - deleted 5y ago
      [deleted]
    - jes 5y ago
      How can one know when a choice does or does not principally depend on one’s state? If someone elects to have wheat toast rather than sourdough toast at breakfast, can they really know why they made that choice? It seems like an infinite regress to me.
mellosouls 5y ago
(2013)
8bitsrule 5y ago
I, for one, am unconcerned that we don't live in a clockwork universe. Or, at the least, one so complex that the initial conditions can never be known. Because that leaves open the possibility that all isn't determined, and that we can finally take responsibility for our own actions.
- TheOtherHobbes 5y ago
  Or we can assume that we have no responsibility because our internal experiences and our actions are not deterministic. Which means there is no consistent self which can determine them.
- naasking 5y ago
  > Because that leaves open the possibility that all isn't determined, and that we can finally take responsibility for our own actions. I'm not clear why your path in life being determined precludes you from taking responsibility for your actions. Presumably if the universe is deterministic, then the consequences of your actions literally follow from your choices. Therefore the proximal cause of those consequences can be attributed to you, ie. you are responsible for causing those outcomes. That you were determined to make those choices doesn't erase this basic fact. That you can learn from mistakes and make different choices in the future given similar circumstances is exactly why holding you responsible for your choices works as a form of moral feedback. If your choices were not deterministic, then this implies that they were partly random, in which case holding you responsible is no longer a valuable tool for moral feedback, because no amount of responsibility or feedback can influence a random variable. Therefore, the degree to which you should be held responsible is arguably proportional to the degree in which your choices are deterministic; we see this in every day life, where babies and the clinically insane who act for no apparent reason are not held responsible for the actions, while people who are mentally competent and can operate within systems of rules are held responsible.
  - mikevm 5y ago
    So if we really assume determinism, does that mean that we'll have to make some changes to the legal system? For example, getting rid of the insanity defense[0]? [0] https://en.wikipedia.org/wiki/Insanity_defense https://en.wikipedia.org/wiki/Insanity_defense
ProfHewitt 5y ago
In foundational theories of mathematics, the following kind of proposition is true but unprovable: Theorems are enumerable by an algorithm. See the following article and associated video: https://papers.ssrn.com/abstract=3603021 https://papers.ssrn.com/abstract=3603021 https://www.youtube.com/watch?v=AJP1VL7shiI https://www.youtube.com/watch?v=AJP1VL7shiI In foundational theories, the proposition I'mUnprovable (used in the proof in [Gödel 1931]) does not exist because of restrictions on orders of propositions that were introduced by Bertrand Russell to prevent logical contradictions in mathematics.

86 points by bmc7505 5y ago

deleted 5y ago

[deleted]

Quoting from the article: "The young Austrian mathematician Kurt Gödel tackled the problem and found that Hilbert’s expectations where [sic] fulfilled for first-order logic." This (i.e., "Hilbert's expectations were fulfilled for first-order logic") is a common misconception, but it is not the case. For instance, ZFC is an example of a first-order theory that does not satisfy Hilbert's expectations mentioned in the article (consistency, completeness and decidability). Notably, if ZFC is consistent, then it is incomplete. Another example of a first-order theory that is essentially incomplete and not decidable is Robinson arithmetic: https://en.wikipedia.org/wiki/Robinson_arithmetic https://en.wikipedia.org/wiki/Robinson_arithmetic The confusion likely stems from the fact that Gödel proved first-order logic to be semantically complete (Gödel's completeness theorem), i.e., all its valid formulae can be derived as theorems. This does not mean that all first-order theories are syntactically complete, i.e, for every statement S, either S or its negation ¬S is in the theory. This kind of incompleteness is what Gödel's incompleteness results are about, and this phenomenon already arises in first-order logic. The common independence results of ZFC are well-known examples of this kind of incompleteness: ZFC, if consistent, does not prove them, and also does not prove their negation. Gödel's first incompleteness theorem shows that every sufficiently powerful formal system exhibits this kind of incompleteness. Also first-order theories exhibit it if they are sufficiently powerful. With today's terminology and models of computation, it is easy to show this, because first-order logic is sufficient to express a Turing machine as a theory, and if we let S be the (first-order) statement "The machine reaches a halting state", then, if we had a mechanism that always terminates and always correctly decides whether S or its negation ¬S is in the theory, then we would have an algorithm that solves the halting problem, which, however, is easily shown to be only semi-decidable, not decidable. Hence, not all first-order theories are consistent, complete and decidable.

bsaul 5y ago
Not a logician, but it’s the first time i’ve heard Gödel incompleteness being about trying to say something about syntactically invalid formulas.. Do you have more pointers on that ? it makes me curious.
- laszlokorte 5y ago
  „Valid“ does not mean syntactically valid but „true in any case“
- triska 5y ago
  Every statement S has a negation ¬S, read as "not S". If S is well-formed, so is its negation. For example, if we take the continuum hypothesis, i.e.: "There is no set whose cardinality is strictly between that of the integers and the real numbers." and construct S to express this statement in the language of our theory (say ZFC), then the negated statement ¬S would correspond to: "There is a set whose cardinality is strictly between that of the integers and the real numbers." Famously, the continuum hypothesis is independent of ZFC. This means that (assuming consistency of ZFC), ZFC does not prove S, and also does not prove ¬S. From a consistent and syntactically complete theory, we expect that it contains exactly one of these statements. Is it the case or not? The fact that ZFC does not "tell" us which it is means that it is incomplete in this sense. Clearly, a question that is important to us is left unanswered by this theory, since neither the statement nor its negation is provable with the given axioms. A syntactically complete theory is also called deductively complete, or negation complete. An example of a first-order theory that is consistent, complete, and also decidable is Presburger arithmetic: https://en.wikipedia.org/wiki/Presburger_arithmetic https://en.wikipedia.org/wiki/Presburger_arithmetic Every question you have about its sentences will be answered by the theory one way or the other by either proving the statement or its negation.
  - ProfHewitt 5y ago
    The Continuum Hypothesis is still an open question in foundational mathematical theories that are more powerful than 1st-order ZFC such as the theory Ordinals. See the following: https://papers.ssrn.com/abstract=3457802 https://papers.ssrn.com/abstract=3457802 Someday, the Continuum Hypothesis might be proved or it might be disproved in foundational theories.

mjburgess 5y ago

Observations on the limits of knowledge, 1. Predicting long-run evolution of chaotic systems require more measurement precision in the initial conditions than quantum mechanics allows 2. With sufficient density, a discrete system cannot be simulated with less energy than the original system possess 3. With sufficient complexity, (as above) 4. The mass required for measurement, and energy required for computing, the structure of ordinary objects (eg., chairs) from their parts eclipses anything we could build 5. Randomness isnt computable 6. Real numbers aren computable 7... Any more?

motohagiography 5y ago
Is there a formal definition of randomness that is just an information gap (like Shannon), and the predictability and measurability of complex systems breaks down because the chaos is just a loss of information in each iteration of its function? If so, where does the information go?
- mjburgess 5y ago
  It never existed in the first place: reality isnt fully determined.

JDEW 5y ago

> We have already noted that quantum physics offers a world view in which the future is not entirely determined. This indeterminacy is not practical but fundamental. It permits us to think that our experience of free will may be real instead of merely subjective. If the outcome of a quantum process is undetermined, there is no fundamental reason to deny that possibility in some neural events which may be a macroscopic amplification of microscopic processes where quantum indeterminacy plays an essential role. I don't see how free will follows from indeterminacy. Just because you can't predict future outcomes from initial values doesn't mean that there is "choice" involved in the evolution of a system.

akimball 5y ago
The quote and your observation are compatible. I would also observe that predictive determinacy does not preclude choice.
- simonh 5y ago
  I am not convinced of their compatibility, as I explained in my sibling post to yours. I think free will of an agent means the choice is determined by the agent's state, because as a materialist I think your state and 'you' are the same thing. I am my state. Any choice that does not principally depend on my state is not my choice, because I am not the cause of it.
  - deleted 5y ago
    [deleted]
  - deleted 5y ago
    [deleted]
  - jes 5y ago
    How can one know when a choice does or does not principally depend on one’s state? If someone elects to have wheat toast rather than sourdough toast at breakfast, can they really know why they made that choice? It seems like an infinite regress to me.

mellosouls 5y ago

(2013)

8bitsrule 5y ago

I, for one, am unconcerned that we don't live in a clockwork universe. Or, at the least, one so complex that the initial conditions can never be known. Because that leaves open the possibility that all isn't determined, and that we can finally take responsibility for our own actions.

TheOtherHobbes 5y ago
Or we can assume that we have no responsibility because our internal experiences and our actions are not deterministic. Which means there is no consistent self which can determine them.
naasking 5y ago
> Because that leaves open the possibility that all isn't determined, and that we can finally take responsibility for our own actions. I'm not clear why your path in life being determined precludes you from taking responsibility for your actions. Presumably if the universe is deterministic, then the consequences of your actions literally follow from your choices. Therefore the proximal cause of those consequences can be attributed to you, ie. you are responsible for causing those outcomes. That you were determined to make those choices doesn't erase this basic fact. That you can learn from mistakes and make different choices in the future given similar circumstances is exactly why holding you responsible for your choices works as a form of moral feedback. If your choices were not deterministic, then this implies that they were partly random, in which case holding you responsible is no longer a valuable tool for moral feedback, because no amount of responsibility or feedback can influence a random variable. Therefore, the degree to which you should be held responsible is arguably proportional to the degree in which your choices are deterministic; we see this in every day life, where babies and the clinically insane who act for no apparent reason are not held responsible for the actions, while people who are mentally competent and can operate within systems of rules are held responsible.
- mikevm 5y ago
  So if we really assume determinism, does that mean that we'll have to make some changes to the legal system? For example, getting rid of the insanity defense[0]? [0] https://en.wikipedia.org/wiki/Insanity_defense https://en.wikipedia.org/wiki/Insanity_defense

ProfHewitt 5y ago

In foundational theories of mathematics, the following kind of proposition is true but unprovable: Theorems are enumerable by an algorithm. See the following article and associated video: https://papers.ssrn.com/abstract=3603021 https://papers.ssrn.com/abstract=3603021 https://www.youtube.com/watch?v=AJP1VL7shiI https://www.youtube.com/watch?v=AJP1VL7shiI In foundational theories, the proposition I'mUnprovable (used in the proof in [Gödel 1931]) does not exist because of restrictions on orders of propositions that were introduced by Bertrand Russell to prevent logical contradictions in mathematics.