# Undecidability and algorithmic verification

The following question has been asked few hours ago : How can any statements be proven undecidable? I'd like to ask a similar but more precise question.

Could we imagine that the Syracuse conjecture is undecidable w.r.t. ZF ?

Could we imagine that Riemann conjecture is undecidable ?

Or even simpler, let say we are in 1990, could we imagine that Fermat conjecture is undecidable ?

For all these questions, I would say no. For the latter, here is a (buggy ?) sketch of proof. Take x, y, z, n, positive integers, $n>2$. You can compute easily $x^n+y^n-z^n$. If you get zero, then you get a proof that Fermat's conjecture is false. So if the Fermat's conjecture were undecidable, then I could not get such a proof, so there would not exists a counter-example, so the Fermat's conjecture would be true, and not undecidable.

Is this reasoning flawed ?

This argument would apply to any statement which can by written in the following form : $$\forall n_i\in \mathbb N, \dotsc, \forall n_k\in \mathbb N, F(x_1,\dotsc,x_k) ,$$ where $F$ is an assertion we can check algorithmically.

I think the Riemann conjecture fits this form. But the Syracuse conjecture, does not (a priori) : you can check that a sequence reach 1, but not that this sequence does not reach 1.

-

It was perfectly possible to imagine in $1990$ that the Fermat Last Theorem was neither provable nor refutable in ZF. That could only happen, as you point out, only if FLT is actually true in the natural numbers. But truth in the natural numbers and provability in a specific formal theory are not the same thing.

As a consequence of Matiyasevich's solution of Hilbert's Tenth Problem, one can in fact construct an explicit polynomial $P(x_1,x_2,\dots, x_n)$ such that the equation $P(x_1,x_2,\dots, x_n)=0$ has no solution in the integers, but such that this fact is not provable in ZF (if ZF is consistent). Actually, for exponential Diophantine equations (so we allow variable exponents, as in the Fermat equation), the result was known well before Matiyasevich's Theorem, as a consequence of work of Julia Robinson, Martin Davis, and Hilary Putnam.

As for the Syracuse problem (Collatz Conjecture), Conway showed that there are relatively simple generalizations of the Collatz Conjecture that are (algorithmically) undecidable. As a consequence of the result, there are Collatz-like sentences that are neither provable nor refutable in ZF.

-
Very naively, I would say that the algorithmic of integers does not depend on the model of ZF in which you are. So is Fermat's conjecture is true in the natural numbers (I mean true for all the natural numbers of a Turing machine, do you mean the same ?), then it is true for all the natural numbers of all models of ZF, and hence provable. I guess I'm wrong when I assume that an integer of a model of ZF can be converted into a natural number of my universe. Am I ? – Lierre Apr 16 '12 at 15:47
@Lierre: ZF, if it is consistent, has many models. One can prove the categoricity of the natural numbers in ZF. This means that a model of ZF will only have one set of natural numbers. However, this set need not be isomorphic to the "real" set of natural numbers. – André Nicolas Apr 16 '12 at 15:54
J'achète ! Merci pour ces précisions. – Lierre Apr 16 '12 at 15:56