MuBar Operator

computation

Definition

$\bar{\mu }$ Operator

The $\bar{\mu }$ operator defines a function $f:{\mathbb{N}}^{k+1}\to \mathbb{N}$ from a total function $g:{\mathbb{N}}^{k+1}\to \mathbb{N}$.

$$\begin{array}{rl}f& =\bar{\mu }g\\ f(x_1,x_2,\dots ,x_{k+1})& =\underset{y\ge 0}{\min }[g(y,x_1,\dots ,x_{k+1})=x_1]\end{array}$$

The minimum is taken over the first argument of $g$.

Examples

Example

$$\begin{array}{rl}(\bar{\mu }{P}_1^1)(n)& =\underset{y\ge 0}{\min }[y=n]\\ & =n\\ ⟹\bar{\mu }{P}_1^1& =P_1^1\end{array}$$

Example

$$\begin{array}{rl}(\bar{\mu }S)(n)& =\underset{y\ge 0}{\min }[y+1=n]\\ & =\{\begin{array}{ll}n-1& \text{if }n>0\\ \text{undefined}& \text{if }n=0\end{array}\end{array}$$

The above is the predecessor function, which is undefined for $n=0$.

Example

$$\begin{array}{rl}(\bar{\mu }\text{Add})(m,n)& =\underset{y\ge 0}{\min }[y+n=m]\\ & =\underset{y\ge 0}{\min }[y=m-n]\\ & =\{\begin{array}{ll}m-n& \text{if }m<n\\ \text{undefined}& \text{else}\end{array}\end{array}$$

The above is the subtraction function over $\mathbb{N}$.

Example

$$\begin{array}{rl}(\bar{\mu }\text{Mult})(m,n)& =\underset{y\ge 0}{\min }[y\cdot n=m]\\ & =\underset{y\ge 0}{\min }\left[y=\frac{m}{n}\right]\\ & =\{\begin{array}{ll}\frac{m}{n}& \text{if }n|m\\ \text{undefined}& \text{else}\end{array}\end{array}$$

The above is the division function over $\mathbb{N}$.

$\bar{\mu }E=\bar{\mu }\left[m,n\mapsto (n+6{)}^{2m+1}\right]$

Define $E$ as:

$$E(m,n)=(n+6{)}^{2m+1}$$

Then:

$$\begin{array}{rl}(\bar{\mu }E)(m,n)& =\underset{y\ge 0}{\min }\left[E(y,n)=m\right]\\ & =\underset{y\ge 0}{\min }\left[(n+6{)}^{2y+1}=m\right]\end{array}$$

Since $E(y,n)$ is strictly increasing in $y$ for each fixed $n$, there is at most one $y$ satisfying the equation. Therefore,

$$(\bar{\mu }E)(m,n)=\{\begin{array}{ll}y& \text{if }m=(n+6{)}^{2y+1}\text{ for some }y\in \mathbb{N}\\ \text{undefined}& \text{otherwise}\end{array}$$

The above is the partial inverse of $E$ with respect to the first argument.

For example, $E$ is undefined for $(0,0),(0,1)$.

$f(x,y)=x^2+y$

$$(\bar{\mu }f)(x,y)=\underset{z\ge 0}{\min }\left[z^2+y=x\right]$$

Examples:

$$\begin{array}{rl}(\bar{\mu }f)(2,1)& =\underset{z\ge 0}{\min }\left[z^2+1=2\right]=1\\ (\bar{\mu }f)(3,1)& =\underset{z\ge 0}{\min }(z^2+1=3)=\text{undefined}\end{array}$$