Let $\Sigma$ an alphabet. We define the primitive recursive set as follows:
$PR_{0}^{\Sigma}$ contains the succesor, predecessor, projection and constant functions. It also contains the $d_a$ function, defined if $a \in \Sigma$, s.t. $d_a(\alpha) = \alpha a$. Then, recursively,
\begin{align*} PR_{k}^{\Sigma} = PR_{k-1}^{\Sigma} \cup \left\{ f \circ [f_1\ldots f_m] : f, f_i \in PR_{k-1}^{\Sigma} \right\} \cup \left\{ R(f, g) : f, g \in PR_{k-1}^{\Sigma} \right\} \end{align*}
where $R(f, g)$ means $R$ is built via primitive recursion by the functions $f, g$. Finally, $PR^{\Sigma} = \bigcup_{k\geq0} PR_k^{\Sigma}$. We say a function is primitive recursive over $\Sigma$, or $\Sigma$-p.r., if it belongs to $PR^{\Sigma}$.
I was given the following problem:
Let $f, g : \omega \mapsto \omega$ s.t. $g \in PR^{\Sigma}$ and $f \in PR_3^{\Sigma} - PR_2^{\Sigma}$. Then, is it true that $f \circ g \subset PR_5^{\Sigma} -PR_3^{\Sigma}$?
I proceeded as follows, but have the strong feeling that a simple approach exists.
Recall that
\begin{align*} PR_{k}^{\Sigma} = PR_{k-1}^{\Sigma} \cup \left\{ f \circ [f_1\ldots f_m] : f, f_i \in PR_{k-1}^{\Sigma} \right\} \cup \left\{ R(f, g) : f, g \in PR_{k-1}^{\Sigma} \right\} \end{align*}
For brevity, we will call the second and third sets in the union $A_{k-1}, B_{k-1}$
From the definition of $PR_k^{\Sigma}$ follows that
\begin{align*} PR_3^{\Sigma} - PR_2^{\Sigma} &= PR_{2}^{\Sigma} \cup A_2 \cup B_2 - PR_2^{\Sigma}\\ &= A_2 \cup B_2 \end{align*}
and
\begin{align*} PR_5^{\Sigma} - PR_3^{\Sigma} &= PR_4 \cup A_4 \cup B_4 - PR_3^{\Sigma} \\ &= (PR_3^{\Sigma} \cup A_3 \cup B_3) \cup A_4 \cup B_4 - PR_3^{\Sigma} \\ &=A_3 \cup B_3 \cup A_4 \cup B_4 \end{align*}
From this follows that $g \in PR_3^{\Sigma}$, because $g \in A_2 \cup B_2$ is either a composition of functions from $PR_2^{\Sigma}$ or a function built via primitive recursion with functions of $PR_{2}^{\Sigma}$.
Assume $f \in PR_k^{\Sigma}$ with $k > 5$. Then $f \circ g \in PR_6^{\Sigma}$. Then $f$ is neither a composition of functions in $PR_3^{\Sigma} \cup PR_{4}^{\Sigma}$ nor built via primitive recursion by functions in $PR_3^{\Sigma} \cup PR_4^{\Sigma}$. In other words, $f \not\in PR_5^{\Sigma} - PR_3^{\Sigma}$. This counter-example suffices to show that the statement is false. $\blacksquare$
This proof by counter-example seems a bit too long and I believe more direct approaches must exist. Any idea on an alternative way to determine whether the statement is true or false? Thanks