0
$\begingroup$

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)

  • 0
    ah, of course. I corrected it.2011-04-22

3 Answers 3

4

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

  • 0
    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.2011-04-22
2

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.

1

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.

  • 0
    thanks, illustrating this constructive process was indeed helpful2011-04-22