I'm completely stuck at exercise 5.8.5 of Mathematical Logic, Chiswell & Hodges:

enter image description here

Here are the mentioned definition and theorem:

enter image description here

enter image description here

enter image description here

I'm stuck because I failed to use the hint given in the exercise. I can't figure out how to use such a property of functions on a relation (a function is a relation but the opposite isn't true). Also, I couldn't even figure out how this can be true for the following diophantine relation: "$x_1+x_2$ is a power of $5$". The equation $\phi(x_1,x_2,y)$ for such a relation is $x_1+x_2=y^5$.

Could you please help me?


You probably mean "$x_1+x_2$ is a fifth power", that is, $\exists y(x_1+x_2=y^5)$.

We want to say this: There exist $y, s, t, u, v$ such that $s=y^2$ and $t=sy$ and $u=ty$ and $v=uy$ such that $x_1+x_2=v$. This is equivalent to $$\exists y\exists s\exists t\exists u\exists v((s-y^2)^2+(t-sy)^2+(u-ty)^2+(v-uy)^2+(x_1+x_2-v)^2=0).\tag{1}$$ Note that the polynomial in (1) has degree $4$. Call it $P$. We are not quite finished, since $P$ contains minus signs. But we can rewrite $P=0$ as $Q=R$, where $Q$ and $R$ have positive coefficients (just bring the minus stuff in $P$ to the right-hand side).

The idea will work in general. We replace $z=y^{n+1}$, where $n$ is a fixed positive integer, by $$\exists t_1\cdots\exists t_{n}((t_1=y^2)\land (t_2=yt_1)\land \cdots \land (t_{n}=yt_{n-1})\land (z=t_n)).$$ Then (over the naturals, or the integers, or $\dots$) we use the sum of squares trick, $(a=b)\land (c=d)$ if and only if $(a-b)^2+(c-d)^2=0$.

Remark: This trick for avoiding high degree polynomials, but at the cost of introducing additional variables, occurs first, I believe, in the work of Skolem.

  • $\begingroup$ Thank you very much for your answer! I understand the trick thanks to you. I'm going to try using it and induction to solve the exercise. Your Remark is what you taught me through the exercise: introducing additional variables. $\endgroup$ – Scientifica Jun 19 '16 at 22:57
  • 2
    $\begingroup$ @Scientifica: You are welcome. Once upon a long time ago, I thought I had invented the trick. $\endgroup$ – André Nicolas Jun 19 '16 at 23:06
  • $\begingroup$ :o that's impressive! $\endgroup$ – Scientifica Jun 20 '16 at 23:39
  • $\begingroup$ Using the result you are proving, one can show that there is no algorithm for determining whether $F(x_1,\cdots,x_n)$ has a solution in integers, where $F$ is a quartic. By pushing a little more, one can show that there is no algorithm for determining whether $Q(x_1,\cdots,x_n)=1$ has a solution in integers, where $Q$ is a homogeneous quartic. $\endgroup$ – André Nicolas Jun 20 '16 at 23:51
  • $\begingroup$ :o thank you for this comment. You gave an example of the importance of this result and that's nice. If I understand correctly, by showing that this result holds for quartics and using the exercise, we can conclude that there's no algorithm where $F$ is any polynomial (seems related to Hilbert's 10th problem), and I guess working on a particular case (quartic function) can make the proof easier. Since the problem reduces to quartics, I was quite tempted to think about it hhh. $\endgroup$ – Scientifica Jun 24 '16 at 1:20

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.