¿Existe alguna definición recursiva, usando sólo la adición, del conjunto de valores de$x^2+y^2$?

Question

No hay una definición recursiva de la serie de los cuadrados de los cuales sólo utiliza además:

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

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

($IS$ representa IsSquare, $CS$ representa ConsecutiveSquares.)

La expansión de $CS$ en términos de $IS$ da un axioma en el idioma:

$ES(x) ⇔x=0 \vee x=1 \vee \existe y: \existe z: (ES(z) \wedge ES(y) \wedge z \lt y \wedge \forall w: (z \lt w) \cuña (w \lt y)⇒\neg ES(w)) \wedge ES(y) \wedge (\forall z: (y < z \wedge z < x) ⇒ \neg ES(z)) \wedge x + z = y + y + 2 $

Esto parece generalizar a una definición recursiva, sólo el uso de la suma, el conjunto de valores de cualquier polinomio univariado. Oficialmente estoy considerando la aritmética de Presburger con un predicado unario y asociados axiomas, produciendo una incompleta del sistema en este caso.

Hay otros predicados unarios que se traducen en una teoría completa. Pero mi pregunta es:

¿Hay alguna definición recursiva, sólo el uso de la suma, de que el conjunto de valores de $x^2+y^2$? Si es así, ¿el rendimiento de una incompleta del sistema? De lo contrario, ¿cómo probar que tal definición no existe?

Recientemente me preguntó "no hay univariante polinomio entero que toma los mismos valores positivos como el multivariante polinomio $x^2+y^2$? y aceptó una respuesta, pero no entiendo cómo se aplica a esta situación.

Answer 1

La función $$ f (z) = \begin{cases} 1 & (\exists x)(\exists y)[z = x^2 + y^2]\\ 0 & \text{otherwise} \end {cases} $$ es recursiva primitiva. Por lo tanto, existe una definición recursiva para esta función que utiliza sólo la constante$0$ y la función sucesora$S(z) =z+1$ como puntos de partida.