Why are the primitive recursive functions a subset of the recursive ones?

Question

I am trying to show, that the set $PR$ of primitive recursive functions is a subset of $R$, the recursive functions. Could someone help me, complete the proof of that assertion ?

My idea: Since $PR$ is defined as the smallest set of all sets $PR'\subseteq \cup _{k\in \mathbb{N}} \{f:\mathbb{N}^k \rightarrow \mathbb{N}\}$, satisfying the properties

1) $PR'$ contains the constant zero function, the successor function and the projection functions

2) $PR'$ is closed under composition by functions

3) $PR'$ is closed under primitive recursion

and $R$ is the smallest set of all sets $R'\subseteq \cup _{k\in \mathbb{N}} \{f:\mathbb{N}^k \rightarrow \mathbb{N}\}$, satisfying the properties 1)-3) and additionaly the property

4) $R'$ is closed under $\mu$-recursion

we obviously have $R' \subseteq PR'$, since there are more constraints on the functions in $R'$ than in $PR'$. But why does the "$\subseteq$" sign gets reversed, if we take the minimum ob both sets, meaning $\min R'=R\supseteq PR=\min PR'$ ?

(m idea was nonsense)

Answer 1

Your assertion $R'\subseteq PR'$ is a) unclear, since $R'$ and $PR'$ weren't introduced as specific sets; b) if clarified to mean "for all $R'$ and all $PR'$", it is incorrect. The constraints are on the sets, not on the functions; to be closed under a certain operation is a constraint that tends to make a set larger, not smaller, if anything. But the (universally quantified version of the) opposite inclusion would also not be correct, since $\cup _{k\in \mathbb{N}} \{f:\mathbb{N}^k \rightarrow \mathbb{N}\}$ satisfies properties 1) to 3), whereas R satisfies 1) to 4) and is a strict subset of $\cup _{k\in \mathbb{N}} \{f:\mathbb{N}^k \rightarrow \mathbb{N}\}$. Thus, you can't make any general statements about inclusion between such sets $R'$ and $PR'$ in general. Rather, you need to use the minimal property of $PR$: Since $PR$ is the smallest set satisfying 1) to 3) and $R$ also satisfies 1) to 3), then $PR$ must be contained in $R$.

Answer 2

we obviously have $R′ \subseteq PR′$, since there are more constraints on the functions in $R′$ than in $PR′$.

You're doing it wrong: closing a set under whatever increases its size. One way to understand this is to see the closing process as an iterative process. Let's build the set U that contains base functions and is closed under $G$ (a unary function):

$U_0 = \lbrace \text{ base functions } \rbrace$

$U_{n+1} = \lbrace f | f \in U_n \vee f = G (h) \text{ where } h \in U_n\rbrace$

Then $U = \bigcup_{k=0}^{+\infty} U_k$ is closed under G.

It is straightforward to extend this definition to n-ary functions and closure under k functions.

Answer 3

The standard example of a R-and-not-PR function is the Ackermann function:

http://en.wikipedia.org/wiki/Ackermann_function

The proof that its not PR is based on the fact that one can bound the growth rate of PR functions, and the Ackermann function grows much too fast.