Vtgyjfy

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.

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".

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).