Suppose that $Rxy$ is a (primitive) recursive relation. Let the function $ \phi $ be defined as follows:
$\phi(x)$ = the number of $y < x$ such that $Rxy$.
Show that $ \phi $ is (primitive) recursive.
I'm not sure how I would begin to approach a construction for a recursive definition of this function. Would anyone have some ideas to point me in the right direction?
Since $Rxy$ is primitive recursive, there is a primitive recursive function $f \colon \mathbb N \times \mathbb N \to \mathbb N$ such that
$$ f(x,y) = \begin{cases} 1 & \text{, if } Rxy \\ 0 & \text{, otherwise} \end{cases} $$
Let $g \colon \mathbb N \to \mathbb N$ be the primitive recursive function with constant value $0$. Also recall that $+ \colon \mathbb N \to \mathbb N, (x,y) \mapsto x+y$ is primitive recursive. [Please feel free to ask for further assistance, if you have trouble proving this fact.]
We now define a primitively recursive function $\phi \colon \mathbb N \to \mathbb N$ by letting $\phi(0) = g(0) = 0$ and $\phi(n+1) = +(\phi(n),f(n+1,n))$.
It's easy to verify (by induction on $x$) that $\phi(x) = \operatorname{card} (\{ y \mid y < x \wedge Rxy \})$.