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.

  • 2
    ah, I $s$ee 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.

  • 0
    @joriki: I see. This is a good home as any. :-)2011-04-22