Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there a physical problem that is undecidable in Zermelo-Fraenkel-Choice set theory? Something related with free abelian groups and Whitehead problem perhaps?

share|cite|improve this question
How 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. – Zhen Lin Jan 15 '12 at 17:10
@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. – Henning Makholm Jan 15 '12 at 17:51
Does infinitely divisible objects does exist? This is a reasonable question for physicist, but a silly question for mathematician. – Norbert Jan 15 '12 at 18:05
It 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. – Grumpy Parsnip Jan 16 '12 at 21:36
The 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. – Ben Crowell Jan 17 '12 at 3:02
up vote 9 down vote accepted

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.

share|cite|improve this answer
I 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. – Ben Crowell Jan 17 '12 at 2:47
@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? – Gerry Myerson Jan 17 '12 at 3:51
@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. – Ben Crowell Jan 18 '12 at 5:27
@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. – Gerry Myerson Jan 18 '12 at 5:43
@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. – Ben Crowell Jan 19 '12 at 15:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.