Simple example of the minimization operator $\mu i$?

Question

This is the definition of a minimization operator from A friendly Introduction to Mathematical Logic.

I'm having trouble understanding this. How can this map a function of $n+1$ variables to a function of $n$ variables if the operator seems to return a number $i$?

Can someone give me a simple example of a function $g$ and $(\mu i) g$?

Let $g$ be a function of arity $n + 1$ from $\Bbb N^{n+1}$ to $\Bbb N$.

Then, $(\mu i)[g(x_1, \dots, x_n, i)]$ denote the least natural number $i$ such that for any $j < i$, the value of $g(x_1, \dots x_n, j)$ is a natural number different from $0$ and the value of $g(x_1, \dots,x_n, i)$ is the natural number $0$.

We can view $(\mu i)[\dots]$ as an operator on functions. If we apply the operator to a function of $n+1$ variables, we get a function of $n$ variables.

Answer 1

See page 201-202 :

$f(x) = (\mu i)[g(x,i)]$,

where $g(u,v) = 0$ if $u = v^2$, and $g(u,v) = 1$ if $u \ne v^2$. Then, $g$ is a total function, but $f$ is not. If $x$ is not a perfect square, then the value of $f(x)$ is undefined. (If $x$ is a square, the value of $f(x)$ is defined and equals $\sqrt x$.)

In this example, we have that $g : \mathbb N \times \mathbb N \to \mathbb N$ and $f : \mathbb N \to \mathbb N$.

The function $f(x)$ means : "the least number $i$ such that $x=i^2$".

For $x=1$ we have that $i=1$, and thus $f(1)=1$.

For $x=2$, we have no $i$, and thus $f(2)$ is undefined. The same for $x=3$.

For $x=4$, instead, we have that $i=2$ and thus $f(4)=2$.

And so on.

---

But see the complete definition of the $\mu$-operator :

Suppose that $R(y, x_1, \ldots, x_k)$ is a fixed $(k+1)$-ary relation on the natural numbers. The "mu operator" "$\mu y$", in either the unbounded or bounded form, is a "number theoretic function" defined from the natural numbers to the natural numbers. However, "$\mu y$" contains a predicate over the natural numbers that delivers true when the predicate is satisfied and false when it is not.

Thus, Leary's definition must be read as a shorthand for :

given the binary fucntion $g(u,v)$, consider the corersponding binary relation $g(u,v)=0$ and apply to this the "mu operator".

Answer 2

The minimization function $\mu f$ may be partial even if $f$ is total: The function $f(x, y) = (x+y)− 3$ is total, while its minimization $\mu f$ is partial with ${\rm dom}(\mu f) = \{0, 1, 2, 3\}$ and $\mu f(0) = \mu f(1) = \mu f(2) = \mu f(3) = 0$.

The minimization function $\mu f$ may be total even if $f$ is partial: Take the partial function $f(x, y) = x − y$ if $y ≤ x$ and $f(x, y)$ undefined if $y > x$. The corresponding minimization $\mu f(x) = x$ is total with ${\rm dom}(\mu f) = {\Bbb N}_0$.

Referring to your definition, $y$ has the role of $i$ (last variable).