4 ms·

This might be an ignorant question, but can one still force a decidable solution by assuming a stronger set of axioms? And if so, does this undecidability have

This might be an ignorant question, but can one still force a decidable solution by assuming a stronger set of axioms? And if so, does this undecidability have any physical significance?

jordigh 11y ago
Yes, you can add more axioms, but your new system with more axioms will have other undecidable statements. I don't know much physics, but my interpretation is this: we have a mathematical model of physics in which we have found a "naturally-ocurring" undecidable statement (scare quotes because most famous undecidable statements were specifically constructed to be undecidable). This does not really say anything about the natural world, merely that our mathematical modelling of it is incomplete, but it always must be incomplete.
- noobermin 11y ago
  Is it really impossible to have some system of axioms where most statements you care about (ie. can make a physical experiment out of) can be decided? If you can't measure something (ie., decide it someway from your theory or leave it as a free parameter), it's not science, string-theory nonwithstanding.
  - jordigh 11y ago
    > Is it really impossible to have some system of axioms where most statements you care about (ie. can make a physical experiment out of) can be decided? Of course it's possible. Most statements we care about are decidable. Otherwise, mathematics would be pretty hopeless. :-) It's just that any system has undecidable statements, as long as it's strong enough to do arithmetic. That's Gödel's theorem.
    - noobermin 11y ago
      I know due to Godel in principle that a logical system can't be complete, but science is a little more specified beyond just logical consistency, it has to be experimentally verifiable, which is a constraint that the mathematics used by science doesn't have. What I'm hinting at is there is a subset of logical statements that the mathematics of science contains defined by the set of experimentally testable statements, and this subset is decidable given independent axioms and free parameters. EDIT: to expand upon this further, things like the continuum hypothesis are interesting from a mathematical perspective, let's say I'm Godel and I assert that CH is false and there is some set A "in between" the reals and N in cardinality. However, if my friend Enrico Fermi wants to do experiments and he wants me to do a calculation, I won't use elements from A because it wouldn't be useful for his experiments in with particle physics. Worse, I can't even use all the real numbers, because he'll need numbers he can compare to his measurements, so I'm restricted to a countable subset of even the reals, and of course, I'm restricted to using statements from the decidable subset of mathematics. There's a big difference between what mathematics is capable of saying and what we observe in the real world. Even if the real world had a set of undecidable facts, the fact that the only way science can understand it is by experiments restricts falsifiable scientific statements to a subset of mathematical statements which is incomplete (because of the need of axioms and free parameters like the mass of particles or their charge, fundamental constants, etc), but decidable within it's axioms, because otherwise, it's not testable and it's not science.
      - jordigh 11y ago
        As Einstein said, "As far as the laws of mathematics refer to reality, they are not certain; and as far as they are certain, they do not refer to reality."[1] Forgive me for not addressing directly what you said, as you seem to be using "countable" to mean something other than "in bijection with the natural numbers". I don't really understand exactly what you mean. But it appears to me that you're trying to perfectly reconcile mathematics with experimental reality. This is impossible. Also, a lot of mathematical physics is very distant from experimental reality. -- [1] http://www-groups.dcs.st-and.ac.uk/history/Extras/Einstein_geometry.html http://www-groups.dcs.st-and.ac.uk/history/Extras/Einstein_g...
        noobermin 11y ago
        I might be confusing this thread with another. The posters there claimed that when considering the infinite number of possible systems that you end up with undecidable statements. Probably countability has nothing to do with this. Also, the popular article linked elsewhere seems to imply that this has very real implications on experiment, which is upsetting.
  - Natanael_L 11y ago
    Undecidability is a consequence of the vast range of askable questions. For practically any system you can come up with questions that have an answer that can't be computed in the generic case. It isn't even a case of number of possible solutions - it can be a case of how long it takes to parse the very question itself.
  - lmm 11y ago
    It probably is impossible because it's usually possible to encode mathematics into anything. Gödel's big result was essentially encoding proof theory into arithmetic, thus proving that any system powerful enough to contain arithmetic contained undecidable statements. Likewise this result - AIUI they've found a way to encode the same mathematics into the arrangement of atoms in a material.
jessriedel 11y ago
To expand on what jordigh said: all these sorts of undecidability problems depend on a formal infinity. One of the infinities in this model (not sure if it's the crucial one) is that the Hamiltonian system is infinitely large in space. Finite systems, like the ones in the real world, don't have this problem. These kind of results can sometimes be clarifying to help theorists who are deep in these abstractions from going down rabbit holes (e.g., by trying to construct an algorithm that always determines whether a system is gapped), but physical implications of this result are slight at best. Toby Cubitt is a really smart guy and I congratulate him on the Nature paper. However, the attention this gets from the public is mostly because the paper manages to call on a bunch of sexy ideas in one place without (I think) actually adding anything profound. It's possible I'm missing something.
- jessriedel 11y ago
  Scott Aaronson clarifies my first paragraph: http://www.scottaaronson.com/blog/?p=2586 http://www.scottaaronson.com/blog/?p=2586
Florin_Andrei 11y ago
If you keep adding axioms, the system at some point flips from having undecidable statements to having demonstrably true statements that are mutually contradictory. So you have a "choice" there.

This might be an ignorant question, but can one still force a decidable solution by assuming a stronger set of axioms? And if so, does this undecidability have any physical significance?

jordigh 11y ago

Yes, you can add more axioms, but your new system with more axioms will have other undecidable statements. I don't know much physics, but my interpretation is this: we have a mathematical model of physics in which we have found a "naturally-ocurring" undecidable statement (scare quotes because most famous undecidable statements were specifically constructed to be undecidable). This does not really say anything about the natural world, merely that our mathematical modelling of it is incomplete, but it always must be incomplete.

noobermin 11y ago
Is it really impossible to have some system of axioms where most statements you care about (ie. can make a physical experiment out of) can be decided? If you can't measure something (ie., decide it someway from your theory or leave it as a free parameter), it's not science, string-theory nonwithstanding.
- jordigh 11y ago
  > Is it really impossible to have some system of axioms where most statements you care about (ie. can make a physical experiment out of) can be decided? Of course it's possible. Most statements we care about are decidable. Otherwise, mathematics would be pretty hopeless. :-) It's just that any system has undecidable statements, as long as it's strong enough to do arithmetic. That's Gödel's theorem.
  - noobermin 11y ago
    I know due to Godel in principle that a logical system can't be complete, but science is a little more specified beyond just logical consistency, it has to be experimentally verifiable, which is a constraint that the mathematics used by science doesn't have. What I'm hinting at is there is a subset of logical statements that the mathematics of science contains defined by the set of experimentally testable statements, and this subset is decidable given independent axioms and free parameters. EDIT: to expand upon this further, things like the continuum hypothesis are interesting from a mathematical perspective, let's say I'm Godel and I assert that CH is false and there is some set A "in between" the reals and N in cardinality. However, if my friend Enrico Fermi wants to do experiments and he wants me to do a calculation, I won't use elements from A because it wouldn't be useful for his experiments in with particle physics. Worse, I can't even use all the real numbers, because he'll need numbers he can compare to his measurements, so I'm restricted to a countable subset of even the reals, and of course, I'm restricted to using statements from the decidable subset of mathematics. There's a big difference between what mathematics is capable of saying and what we observe in the real world. Even if the real world had a set of undecidable facts, the fact that the only way science can understand it is by experiments restricts falsifiable scientific statements to a subset of mathematical statements which is incomplete (because of the need of axioms and free parameters like the mass of particles or their charge, fundamental constants, etc), but decidable within it's axioms, because otherwise, it's not testable and it's not science.
    - jordigh 11y ago
      As Einstein said, "As far as the laws of mathematics refer to reality, they are not certain; and as far as they are certain, they do not refer to reality."[1] Forgive me for not addressing directly what you said, as you seem to be using "countable" to mean something other than "in bijection with the natural numbers". I don't really understand exactly what you mean. But it appears to me that you're trying to perfectly reconcile mathematics with experimental reality. This is impossible. Also, a lot of mathematical physics is very distant from experimental reality. -- [1] http://www-groups.dcs.st-and.ac.uk/history/Extras/Einstein_geometry.html http://www-groups.dcs.st-and.ac.uk/history/Extras/Einstein_g...
      - noobermin 11y ago
        I might be confusing this thread with another. The posters there claimed that when considering the infinite number of possible systems that you end up with undecidable statements. Probably countability has nothing to do with this. Also, the popular article linked elsewhere seems to imply that this has very real implications on experiment, which is upsetting.
- Natanael_L 11y ago
  Undecidability is a consequence of the vast range of askable questions. For practically any system you can come up with questions that have an answer that can't be computed in the generic case. It isn't even a case of number of possible solutions - it can be a case of how long it takes to parse the very question itself.
- lmm 11y ago
  It probably is impossible because it's usually possible to encode mathematics into anything. Gödel's big result was essentially encoding proof theory into arithmetic, thus proving that any system powerful enough to contain arithmetic contained undecidable statements. Likewise this result - AIUI they've found a way to encode the same mathematics into the arrangement of atoms in a material.

jessriedel 11y ago

To expand on what jordigh said: all these sorts of undecidability problems depend on a formal infinity. One of the infinities in this model (not sure if it's the crucial one) is that the Hamiltonian system is infinitely large in space. Finite systems, like the ones in the real world, don't have this problem. These kind of results can sometimes be clarifying to help theorists who are deep in these abstractions from going down rabbit holes (e.g., by trying to construct an algorithm that always determines whether a system is gapped), but physical implications of this result are slight at best. Toby Cubitt is a really smart guy and I congratulate him on the Nature paper. However, the attention this gets from the public is mostly because the paper manages to call on a bunch of sexy ideas in one place without (I think) actually adding anything profound. It's possible I'm missing something.

jessriedel 11y ago
Scott Aaronson clarifies my first paragraph: http://www.scottaaronson.com/blog/?p=2586 http://www.scottaaronson.com/blog/?p=2586

Florin_Andrei 11y ago

If you keep adding axioms, the system at some point flips from having undecidable statements to having demonstrably true statements that are mutually contradictory. So you have a "choice" there.