9

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?

Marty
  • 13,104
  • 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? – Steven Landsburg May 16 '13 at 00:45
  • 3
    @Steven Landsburg: For each fixed $n$ it is, but you can't quantify over $n$ in the first-order language of fields. – Henry Cohn May 16 '13 at 00:57
  • 3
    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. – Felipe Voloch May 16 '13 at 01:08
  • Henry Cohn: Ah. Right. I forgot that the first order theory of fields can't talk about natural numbers. I knew I was missing something! – Steven Landsburg May 16 '13 at 01:15
  • 2
    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. – Steven Landsburg May 16 '13 at 01:30
  • @Steven: My logic is rusty but I don't think the Godel sentence is automatically true. But I may be wrong. Of course "undecidable" is within a set of axioms and something undecidable in PA may be provable in ZFC. Hopefully, one of the many experts will chime in. – Felipe Voloch May 16 '13 at 03:07
  • Felipe: If PA is consistent, then the Godel sentence is automatically true for trivial reasons, though it can't be proved in PA. – Steven Landsburg May 16 '13 at 03:56
  • 2
    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. – Emil Jeřábek May 17 '13 at 14:25

1 Answers1

5

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.

Community
  • 1
Timothy Chow
  • 78,129
  • 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 http://mathoverflow.net/questions/105478/finite-dimensional-real-division-algebras is an example? – Adam Epstein Dec 31 '14 at 23:54
  • @AdamEpstein : What do you mean by "this phenomenon"? What phenomenon? – Timothy Chow Jan 02 '15 at 15:44
  • 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). – Adam Epstein Jan 03 '15 at 01:24
  • @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. – Timothy Chow Jan 04 '15 at 20:24
  • @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. – Timothy Chow Jan 04 '15 at 20:29
  • Yes, I'm aware of Goodstein's Theorem. What I am after is something that could be construed as more "natural" in some mathematical sense. While "naturality" itself is clearly subjective, I do think that it should be possible to attach meaning in certain contexts. For example, various theorems in commutative algebra, algebraic geometry, etc. that trade a finiteness hypothesis for a finiteness conclusion. If sufficiently effective bounds are known, such a proof might be unwound into an arithmetic statement. As you also mention, there is the possibility of coding into PA. – Adam Epstein Jan 05 '15 at 09:28
  • @AdamEpstein: Examples of natural statements that are unprovable in PA are notoriously rare. I'd also like to reiterate that although it's very tempting to mentally equate "provable in PA" with "has an elementary proof", this is probably not a useful way of thinking. Proofs in PA can use advanced machinery from all areas of mathematics, and can be long, complicated, and difficult to find. Conversely, there are statements not provable in PA whose proofs (formalizable in some other system) would be regarded by most people as "elementary" or even trivial. – Timothy Chow Jan 06 '15 at 22:12
  • Reposting a link mentioned in a previous comment so that it appears in the "Linked" questions list: Finite dimensional real division algebras – The Amplitwist Apr 07 '23 at 21:10