5
$\begingroup$

Apologies in advance for asking the following "philosophical" question, which falls dramatically short of any reasonable standards of mathematical rigour:

Is it possible that there should exist a single polynomial $P \in \mathbb{Z}[X_1,\ldots,X_n]$, for some $n \in \mathbb{Z}_{\geq 1}$, such that the question whether $$ P(X_1,\ldots,X_n)=0 $$ has a solution in integers is "absolutely undecidable", that is, can never be settled by any mathematical argument whatsoever?

My thinking about this is very rudimentary, but goes as follows: if the answer would be a mathematically provable "yes", then the proof would have to be (extremely) non-constructive, because if we would ever "know" that the equation $P=0$ is undecidable, we know that it can't have any solutions, but then the equation is decidable: contradiction. However, I would also accept a "yes" answer on philosophical grounds.

On the contrary, if the answer to the question is "no", then I fail to see how this could be proved except on philosophical grounds, since it is hard to imagine a mathematical proof of a "no" answer except by actually constructing a decision procedure for Diophantine equations over $\mathbb{Z}$ (which we know doesn't exist).

Finally, I could envision a philosophical proof of a "no", which would run (very roughly) as follows: it seems very strange to think that there could be a specific equation $P=0$ that has no solutions, but we would have absolutely no way of ever proving it. (It would mean there exists a single Turing machine $T$ that does not halt, but we wouldn't be able to prove it.) This would somehow mean that elementary number theory is absolutely incomplete, in a sense stronger than that alluded to in Gödel's theorems. Unfortunately, I lack the background in logic to judge, whether this "argument" could be formulated in a clearer way, or whether my thinking here is just fundamentally confused.

$\endgroup$
6
  • 1
    $\begingroup$ math.stackexchange.com/questions/434/… $\endgroup$
    – Asaf Karagila
    Commented Jul 2, 2015 at 18:39
  • 1
    $\begingroup$ And also mathoverflow.net/questions/32892/… $\endgroup$
    – Asaf Karagila
    Commented Jul 2, 2015 at 18:40
  • $\begingroup$ Right, but there everything is "relative to ZFC". I could imagine something being true along the lines of "ZFC does not capture all properties of the natural numbers/integers"... $\endgroup$
    – Milton
    Commented Jul 2, 2015 at 18:45
  • 1
    $\begingroup$ Sure, but my point is, the set of axioms of ZFC seems a pretty arbitrary point to stop if one is just interested in properties of natural numbers (or integers). Couldn't one just keep adding axioms that are consistent with the nature of Z? (And if not, I would at least like to know why this doesn't make sense.) $\endgroup$
    – Milton
    Commented Jul 2, 2015 at 18:47
  • 1
    $\begingroup$ Sure, but I'm pretty sure that this method can be extrapolated to any recursively axiomatizable theory. $\endgroup$
    – Asaf Karagila
    Commented Jul 2, 2015 at 18:50

1 Answer 1

4
$\begingroup$

One can (as the OP suggests in a Comment on the Question) "just keep adding axioms that are consistent" to any first-order theory, and thus in the limit obtain a complete (therefore decidable, modulo an "oracle" for the extended axioms) first-order theory.

The "rub" as Asaf suggests is that this recipe for a complete theory does not necessarily produce a recursive set of axioms, i.e. the theory is not a formal first-order theory because the membership of the axioms may not be decidable. One would then have difficulty checking the validity of proofs because it would not be possible to check if a given step was an axiom of the completed theory.

This is the case with (say) Peano arithmetic by virtue of Gödel's incompleteness theorems. Peano arithmetic does not have a consistent and complete recursively defined extension. Therefore ZFC does not have a consistent and complete recursively defined extension.

Note that the existence of an integer solution to an explicit multivariate polynomial $P(x_1,\ldots,x_n)$ with integer coefficients can be stated as a sentence in Peano arithmetic.

Hilbert's tenth problem (1900) asks about a strengthening of Gödel's incompleteness results to produce undecidable sentences of the special form you ask about, also known as Diophantine problems. Yuri Matiyasevich contributed the last piece of the solution in 1970, showing in combination with earlier results by Martin Davis, Hilary Putnam and Julia Robinson, that such undecidable Diophantine sentences exist, relative to any consistent formal extension of Peano arithmetic.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .