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

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)

• It should say "the smallest of all sets" in both definitions; the smallest subsets of all these sets would be the empty set. Commented Apr 22, 2011 at 10:54
• ah, of course. I corrected it.
– temo
Commented Apr 22, 2011 at 15:16

## 3 Answers

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$.

• Thank you very much for your enlightening answer. Elaborating on my error, that I can't compare $R'$ and $PR'$, really cleared things up for me.
– temo
Commented Apr 22, 2011 at 15:34

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.

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.

• Note that "closing a set increases its size" doesn't imply that the inclusion is merely the wrong way around; as I explain in my answer, there is no such general inclusion either way; the only inclusion is between a set and its closure. Commented Apr 22, 2011 at 10:57
• thanks, illustrating this constructive process was indeed helpful
– temo
Commented Apr 22, 2011 at 15:37