Is there a physical problem that is undecidable in Zermelo-Fraenkel-Choice set theory? Something related with free abelian groups and Whitehead problem perhaps?
Physics undecidable problem in ZFC.
-
7How could any physical problem possibly be formulated in set theory except in idealised form? One could argue that any undecidability would be a side-effect of idealisation rather than anything inherent to the problem itself. – 2012-01-15
-
4@ZhenLin: One could ask whether there is a physical _theory_ such that which experimental predictions the theory makes is independent of ZFC. However, that just moves the problem to what qualifies as "a physical theory". It is easy to postulate toy "theories" that _explicitly_ depend on, say, the Continuum Hypothesis. – 2012-01-15
-
3Does infinitely divisible objects does exist? This is a reasonable question for physicist, but a silly question for mathematician. – 2012-01-15
-
2It would be amazing if there were a physical theory that relied on extra-ZFC axioms. Then one could make a case for what new axioms should be included in ZFC based on the outcome of experiments. – 2012-01-16
-
1The concept of undecidability itself is an idealization. For example, you can define undecidability in terms of Turing machines, but a Turing machine has an infinite amount of memory, and there are only finitely many atoms in the observable universe. – 2012-01-17
-
0@Ben Crowell: No, it's not. It turns out the possibility to construct a real Turing machine remains an open problem in GR + QM. It's related to the problem of threading the wormhole to keep it open. – 2014-12-27
1 Answers
There are numerous questions about the nature of the solutions to specific differential equations that are computationally undecidable, and which therefore admit numerous specific instances whose solution has a nature independent of ZFC or of any other fixed consistent theory.
For example, in the paper Boundedness of the domain of definition is undecidable for polynomial ODEs, the authors Graca, Buescu and Campagnolo prove that the question of whether the differential equation $\frac{dx}{dt}=p(t,x)$ with initial conditiion $x(t_0)=x_0$, where $p$ is a vector of polynomials, has a solution with unbounded domain or not, is computationally undecidable.
My point is that whenever a problem like this is computationally undecidable, then it follows that infinitely many specific instances of it are also provably undecidable in any fixed consistent true theory, such as PA or ZFC (or ZFC + large cardinals). The reason is that if a consistent true theory were able to settle all but finitely many instances of the question, then the original problem would be decidable by the algorithm that simply searched for proofs. One can write down a very specific polynomial ODE, such that one cannot prove or refute in ZFC whether it has an unbounded solution or not.
I think there are many other similar examples. I recall hearing in my graduate student days about similar examples, such as the question of whether a given dynamical system is chaotic or not, is also undecidable in general. Therefore these other questions also admit numerous instances of ZFC independence.
-
1I don't think this works, for the reasons given by Zhen Lin. The problem discussed by Graca et al. includes lots of idealizations. For example, the abstract refers explicitly to the real number system. But the real number system is an idealization. Real-world physical measurements always have limited precision. We don't even know whether spacetime is infinitely divisible, as $\mathbb{R}^n$ is; it's likely that at the Planck scale, spacetime is granular. – 2012-01-17
-
4@Ben, in principle, you're right, but in practice, physicists are always writing down differential equations and saying, "this gives the motion of a simple harmonic oscillator" or whatever, and ignoring any possible granularity of spacetime. I think the problem wants to be interpreted as, in the models commonly used by physicists, are there any problems undecidable in ZFC? – 2012-01-17
-
1@Gerry Myerson: The abstract of the Graca paper specifically refers to $\mathbb{R}^n$. Suppose that there is undecidability when you construct a differential equation over the reals, but none when you construct the analogous difference equation over a discrete lattice? These two mathematical constructs are then physically indistinguishable when the lattice spacing is small enough, and the undecidability is clearly something to do with mathematical idealizations rather than physics. – 2012-01-18
-
1@Ben, I concede your point that the undecidability has to do with the mathematical idealization - but I believe there are situations in which every working physicist would use the same, "canonical" idealization. I don't think anyone working on the motions of the Earth-Moon-Sun system under gravity would consider writing difference equations over a discrete lattice. I think the question still makes sense if asked as whether there are problems where the canonical mathematical model leads to undecidability. – 2012-01-18
-
0@GerryMyerson: I agree that if you impute this interpretation to the question, then it has the answer you claim. But under this interpretation, I think it's a question about the sociology of science, not a question about the philosophical foundations of science. It seems to me that the OP intended to ask a question that he thought had implications for the philosophical foundations of science. – 2012-01-19