Showing minimum between x and y is a primitive recursive function with initial functions

Question

for $f(x)=min(x,y)$ with this formula: \begin{equation} min(x,y) = \begin{cases} x & \text{ x<y} \\ y & \text{ y<x} \ \end{cases} \end{equation} how we can show it's primitive recursive with initial functions?

Answer 1

For showing $f(x)$ function is primitive recursive with any formula we must generate $f(x)$ function with initial functions or functions that can built with initial functions. in this problem, we can do it by the following steps.

• Extended subtraction is primitive recursive

  $ x ∸ y = \begin{cases} x-y & \text{ x ≥ y} \\ 0 & \text{ x < y} \ \end{cases} $

• Negation function is primitive recursive

  $ \alpha(x) = \begin{cases} 0 & \text{ x = y} \\ 1 & \text{ x ≠ y} \ \end{cases} $

• So by combining these two we can have

  $ \alpha(x ∸ y) = \begin{cases} 1 & \text{ x ≥ y} \\ 0 & \text{ x < y} \ \end{cases} $

• And multiplication is primitive recursive and we can generate this

  $y.\alpha(x ∸ y) = \begin{cases} y & \text{ x ≥ y} \\ 0 & \text{ x < y} \ \end{cases}$

• And the final step is this

  $min(x,y) = y.\alpha(x ∸ y) + x.\alpha(y ∸ x)$

So min(x,y) is premitive recursive.