I have to show that the greatest integer function of a square root $F(x)=[\sqrt{x}]$ is primitive recursive.
I have so far this description: $pr(\mu y_{y\leq n+1}(y^{2}>n))$, where $pr$ is the predecessor function, $\mu$ is minimization.
I want to rewrite this using the alphabet of recursive language, for example $\mathbf{C}$ is composition, $\mathbf{I}_{n,i}$ takes the ith term from n variables, etc. Does anyone have an idea?
Primitive recursion allows us to define $F(x+1)$ in terms of both $x$ and $F(x)$ like this:
$$F(0)=0$$ $$F(S(x))=g(x,F(x))$$
Now, we need to figure out what $g(x, y)$ is, where $y=F(x)=\lfloor\sqrt{x}\rfloor$ and $g(x,y)=F(S(x))=\lfloor\sqrt{x+1}\rfloor$. In this case, it is pretty easy to show:
$$\lfloor\sqrt {x}\rfloor \leq \lfloor \sqrt {x+1} \rfloor \leq \lfloor \sqrt{x}\rfloor +1\rightarrow y \leq g(x,y)\leq y+1$$
Thus, once we know $y=F(x)$, we simply need to test if $\lfloor\sqrt{x+1}\rfloor$ is $y$ or $y+1$. One way to do this is by testing if $\lfloor \sqrt{x+1}\rfloor \geq y+1$, which combined with the above inequality, would confirm $\sqrt{x+1}=y+1$. Otherwise, if the inequality failed, the above inequality would confirm $\sqrt{x+1}=y$.
Now, $\lfloor \sqrt{x+1}\rfloor \geq y+1$ can not be tested since we don't know what $\lfloor \sqrt{x+1}\rfloor$ is. However, if we square both sides, we can instead test $x+1 \geq (y+1)^2$. In order to make this inequality more strict, since we are dealing with the integers, we can instead say $x+2 > (y+1)^2$. Thus, if $x+2 > (y+1)^2$, then $\lfloor \sqrt{x+1} \rfloor=g(x,y)=y+1$. Otherwise, $\lfloor \sqrt{x+1} \rfloor=g(x,y)=y$. Therefore, $g(x,y)$ is in the form of an if loop, like this:
$$g(x,y)=IF(h(x, y), S(I_{2,2}(x, y)), I_{2,2}(x,y))$$
The first argument, $h(x, y)$ tests if $(y+1)^2 < x+2$: Returns $0$ for false, and a positive number if true. The second argument is $y+1$ and the third argument is $y$. Thus, $IF$ is a primitive recursive which chooses the second argument if the first argument is positive and chooses the third argument if the first argument is zero. This is pretty easy to define as a primitive recursive function:
$$IF(0, b, c)=I_{2,2}(b, c)$$ $$IF(S(y), b, c)=I_{4,3}(y, IF(y, b, c), b, c)$$
Finally, we need to define $h$, a primitive recursive function that tests if $(y+1)^2 < x+2$. From Wikipedia, we have a primitive recursive function $SUB(a, b)$ which returns a positive number $b-a$ if $a < b$ and $0$ otherwise. Thus, $h(x,y)=SUB((y+1)^2,x+2)$:
$$h(x, y)=SUB(MULT(S(I_{2,2}(x,y)), S(I_{2,2}(x,y))), S(S(I_{2,1}(x,y))))$$
Here, I've used $MULT(x,y)$ which finds $x\cdot y$ in the integers, but it is well-known that multiplication is primitive recursive. Thus, we have finally defined $F(x)$ completely as a primitive recursive function.
I know this definition is pretty long and kind of confusing, but I think it goes to show that even simply functions like $\lfloor \sqrt x \rfloor$ can get pretty complicated when you break it down like this. Also, I never explicitly used the composition operator, but I did use the composition rule when I defined $g(x,y)$ and $h(x,y)$, so composition is definitely present in this definition. If you have any questions, feel free to comment below and ask. In any case, I hope this explanation helps you understand primitive recursion!