# If $g ∘ f$ is primitive recursive, are $f$ and $g$, too?

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?

• What have you tried and where did you get stuck? Hint: you don't know anything. Find examples. – Raphael Jan 28 '15 at 11:50
• Hint: $g(x) = 1$ – Pseudonym Jan 28 '15 at 13:21

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.