Assuming I have functions $f, g : \mathbb{N} \to \mathbb{N}$ and I know that $g \circ f$ is a primitive recursive function. What can I tell about $f$ and $g$? Are they primitive recursive as well? Or at least one of them?
$\begingroup$
$\endgroup$
-
$\begingroup$ What have you tried and where did you get stuck? Hint: you don't know anything. Find examples. $\endgroup$ – Raphael♦ Jan 28 '15 at 11:50
-
2$\begingroup$ Hint: $g(x) = 1$ $\endgroup$ – Pseudonym Jan 28 '15 at 13:21
$\begingroup$
$\endgroup$
Let $f$ be a bijective function, which is not primitive recursive. We know, that such a function exists. Let further be $g=f^{-1}$ the inverse function of $f$. Therefore $f\circ g$ is the identity function, which is clearly primitive recursive.
-
3$\begingroup$ Another fun example is if one function is constant, the other can be arbitrary (i.e. non-primitive recursive, or even noncomputable) $\endgroup$ – Mike B. Jan 28 '15 at 15:17
