Most of us know the Jacobian conjecture. Here's a version below for fixed positive integers $d$ and $n$:

$J(d,n)$: If $f: C^n \rightarrow C^n$ is a polynomial map of degree $d$, and if the Jacobian determinant $\vert Jf \vert$ is nowhere vanishing (hence constant), then $f$ is injective (hence bijective).

We know that the sentence "For all $n$, $J(3,n)$" implies the sentence "For all $d,n$, $J(d,n)$." In other words, the Jacobian conjecture has been reduced to degree $3$.

We also know that, for any fixed $n$, $J(3,n)$ is provably true or provably false. This boils down to the completeness of the theory of algebraically closed fields of characteristic zero.

But, do we know whether the sentence "For all $n$, $J(3,n)$" is provably true or false? In other words, might the Jacobian conjecture be... (oh no).. undecidable?!

In other words, I could theoretically program my computer to set out to prove the Jacobian conjecture $J(3,1)$ (easy) and $J(3,2)$ then $J(3,3)$, etc.., and my theoretical computer would keep on going for epochs and epochs. But would it ever halt? Might this be undecidable?

  • $\begingroup$ I'm probably missing something fundamental here, but....isn't "For all $n$, $J(3,n)$" a sentence in the theory of algebraically closed fields of characteristic zero? So doesn't completeness still apply? $\endgroup$ – Steven Landsburg May 16 '13 at 0:45
  • 3
    $\begingroup$ @Steven Landsburg: For each fixed $n$ it is, but you can't quantify over $n$ in the first-order language of fields. $\endgroup$ – Henry Cohn May 16 '13 at 0:57
  • 2
    $\begingroup$ If it is undecidable, then it is true, since if it were false, your program would halt for some n with a proof that it is false. So you can't prove that it is undecidable. $\endgroup$ – Felipe Voloch May 16 '13 at 1:08
  • 2
    $\begingroup$ Felipe Voloch: It's clear from my earlier comment that I'm not at my best tonight, so maybe I'm missing something fundamental again, but: The Godel sentence for Peano Arithmetic is undecidable and therefore true, but it doesn't follow that I can't prove it's undecideable. $\endgroup$ – Steven Landsburg May 16 '13 at 1:30
  • 1
    $\begingroup$ Yes, if it is undecidable in a half-decent theory, then it is true. Yes, you cannot prove in, say, ZFC that it is undecidable in ZFC, but then again, you cannot prove in ZFC that anything is undecidable in ZFC. However, it is conceivable that the undecidability of the conjecture in ZFC is provable by assuming some stronger hypothesis, such as the consistency of ZFC. $\endgroup$ – Emil Jeřábek May 17 '13 at 14:25

There's no way to rule out a priori that the Jacobian conjecture is undecidable (in your favorite axiomatic system).

As I pointed out in my answer to another MO question, a proof that some statement is decidable would automatically mean that its status would be resolved up to a finite computation. You can be sure that if a conjecture as important as the Jacobian conjecture were reduced to a finite computation, then we would hear about it. This observation yields an informal "proof" that (almost) all the major open problems you care to name are not known to be decidable.

See also this related MO question.

| cite | improve this answer | |
  • $\begingroup$ Are there any known examples of results from algebra that actually exhibit this phenomenon? For example, is it conceivable that the 1,2,4,8 theorem mathoverflow.net/questions/105478/… is an example? $\endgroup$ – Adam Epstein Dec 31 '14 at 23:54
  • $\begingroup$ @AdamEpstein : What do you mean by "this phenomenon"? What phenomenon? $\endgroup$ – Timothy Chow Jan 2 '15 at 15:44
  • $\begingroup$ A problem of "natural origin" which may be viewed as a parametric family of positively resolvable problems in some decidable theory, but whose universal quantification is not known to be provable. Suitable algebra problems with a natural number "complexity parameter" (degree, dimension, etc.) are equivalent to true $\Pi_1$ statements in the language of arithmetic. Are these provable in first-order arithmetic? Are there documented examples which are not? For example, see the above query of Steven Landsburg regarding J(3,n). $\endgroup$ – Adam Epstein Jan 3 '15 at 1:24
  • $\begingroup$ @AdamEpstein : I don't know of examples that I think you would regard as interesting. Any $\Pi_1$ conjecture $\forall n: P(n)$ is an example of sorts, because for any fixed $n$, $P(n)$ is trivially decidable, but it sounds like you're asking for more than that. I would add that being provable in PA does not line up very well with what most people intuitively think of as an "elementary" or "algebraic" proof. It is possible to formalize a sizable amount of real and complex analysis in PA. $\endgroup$ – Timothy Chow Jan 4 '15 at 20:24
  • $\begingroup$ @AdamEpstein : You may already know this, but Goodstein's theorem is not provable in PA, yet it is a universal quantification over statements that are trivially decidable. $\endgroup$ – Timothy Chow Jan 4 '15 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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