Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
It should say "the smallest of all sets" in both definitions; the smallest subsets of all these sets would be the empty set. –  joriki Apr 22 '11 at 10:54
ah, of course. I corrected it. –  temo Apr 22 '11 at 15:16

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
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 Apr 22 '11 at 15:34
You're welcome. –  joriki Apr 22 '11 at 15:52

The standard example of a R-and-not-PR function is the 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.

share|improve this answer

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.

share|improve this answer
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. –  joriki Apr 22 '11 at 10:57
thanks, illustrating this constructive process was indeed helpful –  temo Apr 22 '11 at 15:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.