# How does primitive recursion handle mutual recursion?

My intuition is that you can't call a function that has not yet been defined, although I have yet to find a source confirming this.

Is this true?

Thanks, friends :)

## 1 Answer

Suppose you have two mutually recursive maps $$f, g : \mathbb{N} \to \mathbb{N}$$ defined by \begin{align*} f(n) &= \Phi(f, g, n), \\ g(n) &= \Psi(f, g, n) \end{align*} We may replace this with a single recursive map $$h : \mathbb{N} \to \mathbb{N} \times \mathbb{N}$$, where $$h(n) = (f(n), g(n))$$, so that $$f(n) = \pi_1(h(n))$$, $$g(n) = \pi_2(h(n))$$. Then the above recursive definition may be rewriten as $$h(n) = (\Phi(\pi_1 \circ h, \pi_2 \circ h, n), \Psi(\pi_1 \circ h, \pi_2 \circ h, n))$$ The above trick is very general and works in many situations. Regarding primitive recursion, we just have to verify that the passage between $$f, g$$ and $$h$$ preserves the primitive recursive nature of functions, which it does because pairing, projections and compositions are primitive recursive.