# Prove $\varphi(x)$ to be primitive recursive

Let $\varphi(x)=2x$ if $x$ is a perfect square, $\varphi(x) = 2x+1$ otherwise. Show $\varphi$ is primitive recursive.

In proving $\varphi$ to be a p.r. function I think it could come in handy the following theorem:

Let $\mathcal C$ be a PRC class. Let the functions $g$, $h$ and the predicate $P$ belong to $\mathcal C$, let

\begin{equation} f(x_1,\ldots, x_n) = \begin{cases} g(x_1, \ldots, x_n) \;\;\;\;\;\text{ if } P(x_1, \ldots, x_n)\\ h(x_1,\ldots,x_n) \;\;\;\;\;\text{ otherwise} \end{cases} \end{equation} Then $f$ belongs to $\mathcal C$ because $$f(x_1, \ldots, x_n) = g(x_1, \ldots, x_n) \cdot P(x_1, \ldots, x_n) + g(x_1, \ldots, x_n) \cdot \alpha(P(x_1, \ldots, x_n))$$ where

\begin{equation} \alpha(x) = \begin{cases} 1 \;\;\;\;\;\text{ if } x = 0\\ 0 \;\;\;\;\;\text{ if } x \neq 0 \end{cases} \end{equation}

and $\alpha(x)$ is p.r.

So similarly I would say that $\varphi(x)$ is p.r. as

\begin{equation} \varphi(x) = \begin{cases} 2x \;\;\;\;\;\;\;\;\;\;\;\text{ if } x = t \cdot t \\ 2x+1 \;\;\;\;\;\text{ otherwise} \end{cases} \end{equation} hence $$\varphi(x) = 2x \cdot P(x_1, \ldots, x_n) + (2x+1) \cdot \alpha(P(x_1, \ldots, x_n))$$ and $P$ is a primitive recursive predicate as $x \cdot y$ is p.r. and also $x = y$.

Does everything hold? Is there anything wrong? If so, since I am tackling this kind of exercise for the fist time, will you please tell me what's the proper way to solve this?

• You need to show that you can write an "if,then,else"-function, i.e. $f(x,y,z) = y$ if $x$ is true and $z$ otherwise. Then you need to show that you can test whether or not $x$ is a perfect square. This you can do by iterating $i$ from 1 to $x$ testing if $i^2 = x$. – Pål GD Jan 17 '13 at 18:54

To see if $x$ is a perfect square is easy (for example, by adding 1 + 3 + 5 ... you get the succesive squares); once that is settled your problem is solved. Think of such problems primarily as programming asignments (in a rather cruel programming language).
• Not so cruel, once you developed the right tools. All you need here is bounded existential quantification: is_square(x) = $\exists n \le x, n^2 =x$. – Andrea Asperti Feb 23 '17 at 12:57