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
    Do you mean $\{z\mid\exists x\exists y:x\cdot x+y\cdot y=z\}$, but first you want to define multiplication recursively?2012-02-22
  • 0
    @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)).2012-02-22
  • 0
    @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$?2012-02-22
  • 0
    @Dan Brumleve: The predicate $P$ can be defined recursively in terms of addition, in the usual way.2012-02-22
  • 0
    @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.2012-02-22
  • 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