2
$\begingroup$

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
    You might want to consider accepting some answers to your questions, or point out what was insufficient in the given answers.2011-04-22
  • 0
    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!2011-04-22
  • 0
    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.2011-04-22
  • 2
    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.2011-04-22

2 Answers 2

5

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

3

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
    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)2011-04-22
  • 0
    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.2011-04-22
  • 0
    As a side question, would you perhaps know, what was meant by the construction by hull operators and the construction "from the top/bottom" ?2011-04-22
  • 0
    joriki: Out of sheer curiosity, what is your field of research?2011-04-22
  • 0
    @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? :-)2011-04-22
  • 0
    @joriki: You seem very well knowledgeable in many different areas of mathematics (at least in undergrad level or so), and I am a curious fella ;-)2011-04-22
  • 0
    @Asaf: Yes, the problem is that more often than not it ends at the undergrad level :-) I've solved a lot of different kinds of problems in different areas over the years, so I know quite a few techniques and tricks and connections, but I've never really delved very deeply into anything in math (as opposed to physics); that's why you don't see much of me on MO.2011-04-22
  • 0
    @joriki: I see. This is a good home as any. :-)2011-04-22