Minimization operator $\mu$, primitive recursive functions

159 Views Asked by At

What is the function obtained by applying the minimization operator $\mu y$ to

$$f(x,y,z)=1-Xr$$

where $$r=\{(x,y,z) \; | \; z=yx\}$$ and $Xr$ is the characteristic function or $r$

1

There are 1 best solutions below

4
On

There may be minor differences in the definition according to the book you are reading, but $(\mu y)(f)$ is the function

$$(x,z) \mapsto \min\{y : f(x,y,z)=0\} $$

In particular, $$ (\mu y)(f)(x,z) = \begin{cases} 0 & \text{if } x=z=0 \\ z/x & \text{if } x\neq 0 \\ \uparrow & \text{if } z\neq 0 \text{ and } x=0\end{cases}$$