I'm completely stuck at exercise 5.8.5 of Mathematical Logic, Chiswell & Hodges:
Here are the mentioned definition and theorem:
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.