Consider the set $R_0=\{+,\cdot,I_<\}$, where $I_<$ is the characteristic function of the 2-ary relation $<$, and for every n let $R_{n+1}=\{p^n_1,...,p^n_n\}\cup R_n\cup C_n$, where $p^n_k:\mathbb{N}^n\rightarrow\mathbb{N}$ is the projection to the k-th component and $C_n$ is the set of all functions which can be made in a single step from functions of $R_n$ by either composition or applying the $\mu$-operator.
I want to show that the function $f:\mathbb{N}^2 \rightarrow\mathbb{N},(n,k)\mapsto\max\{g(k)\lvert g:\mathbb{N}\rightarrow\mathbb{N},g\in R_n\}$ is not recursive. How do I do this?
Obviously the union of all $R_n$ is the set of all recursive functions. So I have to prove the claim by deriving a contradiction from the assumption that f is recursive, because if it were, then it would be contained in an $R_n$ for an $n\in\mathbb{N}$. But what is the contradiction, and how do I get there?
Suppose $f\in R_{n_0}$. Then $g_0\colon n\mapsto f(n,n)+1$ is also recursive, so $g_0\in R_{m_0}$ for some $m_0$, where $m_0 = n_0+k$ for some $k$ ($k = 3$ should suffice). So we have $$\begin{align} g_0(m_0) &= 1 + \max\{g(m_0)\mid g\colon \Bbb N\to \Bbb N, g\in R_{m_0}\} \\ &> g_0(m_0). \end{align}$$