> For the complete documentation index, see [llms.txt](https://mandober.gitbook.io/math-debrief/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mandober.gitbook.io/math-debrief/600-toc/634-primitive-recursive-functions/primitive-composition.md).

# Primitive composition

Given a k-ary primitive recursive function f, and k many m-ary primitive recursive functions g₁,...,gₖ, the composition of f with g₁,...,gₖ, i.e. the m-ary function ℎ(x₁,...,xₖ) = f ( g₁(x₁,...,xₖ),..., gₖ(x₁,...,xₖ) ) is primitive recursive.

Summary, we have:

* k-ary primitive recursive function fᵏ
* k many m-ary primitive recursive functions gᵐ₁,...,gᵐₖ
* m-tuple denoted by Xᵐ := (x₁,...,xₘ) where Xᵐ is just a shorthand

So each m-ary gᵐ function takes the m-tuple producing a list of k results as a k-tuple. Then this k-tuple of results is fed to fᵏ:

```
    fᵏ ( gᵐ₁(x₁,...,xₘ) , ... , gᵐₖ(x₁,...,xₘ) )
```

* In a point free form (without mentioning the X tuple as an arg to g's), the composition is denoted by:

  ```
    fᵏ ∘ [g₁,...,gₖ]
  ```
* In point-full form with the X tuple mentioned, it may be denoted as:

  ```
    (fᵏ ∘ [g₁,...,gₖ]) Xᵏ
  ```
* As an illustration

g₁(x₁...xₘ)\
g₂(x₁...xₘ) \ f ⁝ / gₖ(x₁...xₘ) /

* For example, if the tuple is unary, containing just `x`, and there is only one `g` function, then the composition looks like the classical composition:

`f ∘ g` that is `(f ∘ g) x`

* For example

We take f(x) as the Succ(x) defined above. This f is a 1-ary primitive recursive function. And so is g(x) = Succ(x). So h(x) defined as f(g(x)) = Succ(Succ(x)) is a primitive recursive 1-ary function too. Informally speaking, h(x) is the function that turns x into x+2.