Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Do you mean $\{z\mid\exists x\exists y:x\cdot x+y\cdot y=z\}$, but first you want to define multiplication recursively? – Asaf Karagila Feb 22 '12 at 8:35
@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)). – Dan Brumleve Feb 22 '12 at 8:40
@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$? – André Nicolas Feb 22 '12 at 8:47
@Dan Brumleve: The predicate $P$ can be defined recursively in terms of addition, in the usual way. – André Nicolas Feb 22 '12 at 8:52
@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. – 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.