Let $PR$ be the set of of [primitive recursive functions][1]. Given $X\subset PR$, let $$ \hat X=\{ h(g_1(\vec x),\dots,g_k(\vec x)):k\in \mathbb{N}\wedge h,g_1,\dots,g_k\in X\}, $$ i.e. $\hat X$ is obtained from $X$ by taking compositions.
Fix $F\subset PR$ finite and let $I$ be the set of initial functions, i.e. $I$ consists of the unary successor function, the unary constantly $0$ function and all the projections. Define: $$A_0=F\cup I$$ $$A_{n+1}=\hat{A_n}$$ $$A=\bigcup_{n\in\mathbb{N}}A_n$$ I'd like to show that $A\neq PR$.
In other words, the set of primitive recursive functions cannot be obtained from finitely many functions (plus the initial functions) just by taking compositions, i.e. the recursion part of definition is really necessary to get all the primitive recursive functions.
This is clearly not true if $F$ is not finite and just countable, since then we can just take $F=PR$, so $F$ being finite should play an important role.
Any hints?
EDIT: I've changed the question since the previous one was not very well formulated.
First, note that we can just do this in terms of one variable encodings of all the $g$'s, since if we find a majorizing function, we can lift it back to one which majorizes all the usual $g_i$'s.
Next we can define a function $G(x)$ which majorizes all the $g_i$'s via the primitive recursive $$G(0) = \max_{i\leq k}(g_i(0)) + 1$$ and $$G(n) = \max_{i\leq k}(g_i(n), G(n-1)) + 1$$ This definition also ensures that $G$ is increasing, so we have $x<y\implies G(x) < G(y)$, which allows composing this function to act well, as then $$g_i(x) < G(x) \implies g_j(g_i(x)) < G(g_i(x)) < G(G(x))$$
and so on. Now we can define a primitive recursive function which majorizes all the elements in $\hat{X}$ via $F(1, x) = G(x)$ and $$F(n,x) = G(F(n-1, x)) $$ Now, note that $F(n, x)$ majorizes all functions obtained via composing $n$ functions together. Also, since we've defined $\hat{X}$ inductively via compositon, every function in $\hat{X}$ is obtained by composing functions together $n$ times. Diagonalizing, we then get that $M(x) = F(x,x)$ is eventually greater than all the functions in $\hat{X}$ and we've found our majorizing function!