The set of primitive recursive functions is defined as the smallest subset $F\subseteq \cup _{k\in \mathbb{N}} \{f:\mathbb{N}^k \rightarrow \mathbb{N}\}$, satisfying the properties

1) $F$ contains the constant zero function: $0:\mathbb{N}^0 \rightarrow \mathbb{N}$, the successor function and the projection functions

2) $F$ is closed under composition by functions

3) $F$ is closed under primitive recursion

My question is: Why can one even assume, that a set with properties 1)-3) exists, so that one can take the smallest such set ? As well, I was told, that one can construct $F$ by using hull operators, "from the bottom" and "from the top", but I'm not quite sure, about the meaning of that.

  • 1
    $\begingroup$ You might want to consider accepting some answers to your questions, or point out what was insufficient in the given answers. $\endgroup$ – Asaf Karagila Apr 22 '11 at 9:49
  • $\begingroup$ I'm not quite sure what you mean. Did you mean to specify exactly what I was told about hull operators and how to ? Pretty much just that what I wrote here, so I can't add anything to that. Or did you mean to point out, what was insufficient in the answers given here, at, math.SE ? I posted the question barely half an hour ago! $\endgroup$ – temo Apr 22 '11 at 10:13
  • $\begingroup$ You've asked numerous questions on the website, some have gotten several answers. By the answers there is a transparent V sign, which can be used to say "This answer an answer which gives me the information I was looking for, and it does so the best from the offered answers.", you should choose such to at least some of your questions. It is also customary to upvote answers that were given to your questions. $\endgroup$ – Asaf Karagila Apr 22 '11 at 10:19
  • 2
    $\begingroup$ ah, I see what you mean. sorry, I didn't get round to log in to math.SE for some time. I fixed it now. $\endgroup$ – temo Apr 22 '11 at 10:21

The set $\cup _{k\in \mathbb{N}} \{f:\mathbb{N}^k \rightarrow \mathbb{N}\}$ satisfies these properties.


This smallest subset is given by the intersection of all sets with these properties.

[Edit in response to the comment:]

"Hull operator" in this context is another term for "closure operator". For instance, the hull (or closure) operator for composition of functions applied to any set of functions yields the set of all (finite) compositions of these functions (including the functions themselves). This set is evidently closed under composition. This definition describes the hull operator "from the bottom": starting with the given set of functions, and constructing more and more functions by composition to build up a set closed under composition. But the same operator can equivalently be defined to yield the smallest set of functions containing the given set of functions and closed under composition. This definition describes the operator "from the top": You take an enormous overkill of sets (including the entire set of all functions) and intersect all of them to whittle them down to just the ones you need for the closure. Hope that makes it clearer.

  • 1
    $\begingroup$ yes, but it could be, that there are no sets, that satisfy 1)-3), so I would be intersecting over the empty set, and in that case $F$ wouldn't be well defined, I think. How do I show that there exists at least one non-empty set, that satisfies 1)-3) $\endgroup$ – temo Apr 22 '11 at 10:11
  • $\begingroup$ Sorry, I see now that I'd misread the question -- I thought you were asking how we know there's a smallest such set, but I see now you were in fact asking how we know there is such a set. That's answered by @aaa's answer. $\endgroup$ – joriki Apr 22 '11 at 10:32
  • $\begingroup$ As a side question, would you perhaps know, what was meant by the construction by hull operators and the construction "from the top/bottom" ? $\endgroup$ – temo Apr 22 '11 at 10:47
  • $\begingroup$ joriki: Out of sheer curiosity, what is your field of research? $\endgroup$ – Asaf Karagila Apr 22 '11 at 11:00
  • $\begingroup$ @Asaf: None specifically, currently -- I studied theoretical physics, did some lattice gauge theory and quantum chemistry, and then concentrated on politics for the last $5$ or so years and am now going back to math and physics. Out of sheer curiosity, what made you wonder? :-) $\endgroup$ – joriki Apr 22 '11 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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