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.

  • $\begingroup$ Do you mean $\{z\mid\exists x\exists y:x\cdot x+y\cdot y=z\}$, but first you want to define multiplication recursively? $\endgroup$ – Asaf Karagila Feb 22 '12 at 8:35
  • $\begingroup$ @Asaf, no, I want some definition of IsSumOfTwoSquares in terms of itself (and addition), and if that is somehow possible I would like to know whether it can define multiplication (which implies the system is incomplete (or else inconsistent of course)). $\endgroup$ – Dan Brumleve Feb 22 '12 at 8:40
  • $\begingroup$ @Dan Brumleve: Your recursive definition of $IS$ uses an auxiliary predicate, so presumably that is allowed. However, how does one rule out the auxiliary predicate $P(x,y,z)$ that says that $z=xy$? $\endgroup$ – André Nicolas Feb 22 '12 at 8:47
  • $\begingroup$ @Dan Brumleve: The predicate $P$ can be defined recursively in terms of addition, in the usual way. $\endgroup$ – André Nicolas Feb 22 '12 at 8:52
  • $\begingroup$ @André, in the case of the set of squares, we can define multiplication, in accordance with your answer to my old question that I linked to. The case I am wondering about here is the set of sums of two squares. $\endgroup$ – Dan Brumleve Feb 22 '12 at 8:56

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.


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.