5
$\begingroup$

There is a recursive definition of the set of squares which uses only addition:

$CS(x,y) := IS(x) \wedge IS(y) \wedge x \lt y \wedge \forall z: (x \lt z) \wedge (z \lt y)⇒\neg IS(z)$

$IS(x)⇔ x=0 \vee x=1 \vee \exists y: \exists z: (CS(z,y) \wedge IS(y) \wedge (\forall z: (y < z \wedge z < x) ⇒ \neg IS(z)) \wedge x + z = y + y + 2)$

($IS$ stands for IsSquare, $CS$ stands for ConsecutiveSquares.)

Expanding $CS$ in terms of $IS$ gives an axiom in the language:

IS(x) ⇔x=0 \vee x=1 \vee

\exists y: \exists z: (IS(z) \wedge IS(y) \wedge z \lt y \wedge \forall w: (z \lt w) \wedge (w \lt y)⇒\neg IS(w)) \wedge IS(y) \wedge

(\forall z: (y < z \wedge z < x) ⇒ \neg IS(z)) \wedge

x + z = y + y + 2

This seems to generalize to a recursive definition, using only addition, of the set of values of any univariate polynomial. Formally I am considering Presburger arithmetic with a unary predicate and associated axioms, yielding an incomplete system in this case.

There are other unary predicates which result in a complete theory. But my question is:

Is there any recursive definition, using only addition, of the set of values of $x^2+y^2$? If so, does it yield an incomplete system? Otherwise, how to prove that such a definition does not exist?

I recently asked "Is there no univariate integer polynomial that takes on the same positive values as the multivariate polynomial $x^2+y^2$? and accepted an answer but I don't understand how to apply it to this situation.

  • 0
    @André, sorry, I meant to say that the auxiliary predicate $CS$ is defined only in terms of _addition_ and $IS$. The point is that $IS$ is defined in terms of itself, $CS$ is not.2012-02-22

1 Answers 1

1

The function $ f(z) = \begin{cases} 1 & (\exists x)(\exists y)[z = x^2 + y^2]\\ 0 & \text{otherwise} \end{cases} $ is primitive recursive. Therefore there is a recursive definition for this function which uses only the constant $0$ and the successor function $S(z) =z+1$ as starting points.