Show that if $b\in\mathbb{N}$, then the set $\{b\}$ is primitive recursive.

58 Views Asked by At

Question: Show that if $b\in\mathbb{N}$, then the set $\{b\}$ is primitive recursive. Hint: The functions "addition", "multiplication", "subtraction", and the relations = and < are primitive recursive.

Definition. The set of primitive recursive functions is the smallest set containing the basic functions and closed under both composition and primitive recursion.

I tried: The set $\{b\}$ is primitive recursive if it's characteristic function $$X_{\{b\}}(x) = \left\{ \begin{array}{rcl} {1} & \mbox{if} & x \in {\{b\} } \\ 0 & \mbox{otherwise} \\ \end{array}\right.$$ is primitive recursive.

$$X_{=}(x,y) = \left\{ \begin{array}{rcl} {1} & \mbox{if} & x = {y} \\ 0 & \mbox{otherwise} \\ \end{array}\right.$$ is primitive recursive.

$X_{\{b\}}(x)=X_{=}(x,y)$, so ${\{b\} }$ is primitive recursive.

Hints?