$\mu $operator
$\mu $ on predicates
Let a property on nonnegative integers be given. Informally, the $\mu $operator looks for the smallest number satisfying the given property. The $\mu $operator is also known as the (unbounded^{}) minimization operator or the (unbounded) search operator. Formally,
Definition. Let $\mathrm{\Phi}(\bm{x},y)$ be an $(m+1)$ary predicate^{} (property) over $\mathbb{N}$, the set of natural numbers ($0$ included here), with $m$ a nonnegative integer ($\bm{x}$ is $m$ary). Define
$${A}_{\mathrm{\Phi}}(\bm{x}):=\{y\in \mathbb{N}\mid \mathrm{\Phi}(\bm{x},y)\},$$ 
The $\mu $operator on $\mathrm{\Phi}$ is given by
$$\mu y\mathrm{\Phi}(\bm{x},y):=\{\begin{array}{cc}\mathrm{min}{A}_{\mathrm{\Phi}}(\bm{x})\hfill & \text{if}{A}_{\mathrm{\Phi}}(\bm{x})\ne \mathrm{\varnothing},\hfill \\ \text{undefined}\hfill & \text{otherwise.}\hfill \end{array}$$ 
The notation $\mu y\mathrm{\Phi}(\bm{x},y)$ reads “the smallest $y$ such that $\mathrm{\Phi}(\bm{x},y)$ is satisfied”. Note that $y$ is used both as a variable and a number that the variable $y$ represents.
Note that $\mu y\mathrm{\Phi}(\bm{x},y)$ is a partial function^{} on $\bm{x}$ ($y$ is a bounded^{} variable). In other words, the $\mu $operator is a function that takes an $m+1$ary predicate to an $m$ary partial function. When $m=0$, $\mu $ is either an integer, or $\mathrm{\varnothing}$.
For example, suppose $\mathrm{\Phi}(x,y)$ is the property $(xy)(x+y)\ge 10$. Then $\mu y\mathrm{\Phi}(x,y)=0$ iff $x\ge 4$, and undefined otherwise.
The reason why the $\mu $operator is called the search operator comes from recursive function^{} theory. The search for the smallest $y$ such that $\mathrm{\Phi}(\bm{x},y)$ begins with testing for $\mathrm{\Phi}(\bm{x},0)$. If the test fails ($\mathrm{\Phi}(\bm{x},0)$ is false), then testing for $\mathrm{\Phi}(\bm{x},1),\mathrm{\Phi}(\bm{x},2),\mathrm{\Phi}(\bm{x},3),\mathrm{\cdots}$ are successively performed. The testing stops when a $y$ with $\mathrm{\Phi}(\bm{x},y)$ is found. This $y$ is also the smallest $y$ satisfying $\mathrm{\Phi}$. Nevertheless, the testing can conceivably go on indefinitely, hence the name unbounded. There is also a bounded version of $\mu $operation^{}:
Definition. Let $\mathrm{\Phi}(\bm{x},y)$ be given as above. Define
$${A}_{\mathrm{\Phi}}(\bm{x},y):=\{z\in \mathbb{N}\mid \mathrm{\Phi}(\bm{x},z)\text{and}z\le y\}.$$ 
The bounded $\mu $operator on $\mathrm{\Phi}$ is given by
$$\mu z\le y\mathrm{\Phi}(\bm{x},z):=\{\begin{array}{cc}\mathrm{min}{A}_{\mathrm{\Phi}}(\bm{x},y)\hfill & \text{if}{A}_{\mathrm{\Phi}}(\bm{x},y)\ne \mathrm{\varnothing},\hfill \\ y+1\hfill & \text{otherwise.}\hfill \end{array}$$ 
Thus the bounded $\mu $operator takes an $(m+1)$ary predicate (on $(\bm{x},z)$, where $z$ is a free variable^{}) to an $(m+1)$ary total function (on $(\bm{x},y)$, as $z$ is now bounded by $\mu $).
$\mu $ on total functions
The $\mu $ operator can also be defined on functions. We first discuss the case of $\mu $ on total functions.
Definition. Given a total $(m+1)$ary function $f:{\mathbb{N}}^{m+1}\to \mathbb{N}$, define
$${A}_{f}(\bm{x}):=\{y\in \mathbb{N}\mid f(\bm{x},y)=0\},$$ 
The $\mu $operator on $f$ is given by
$$\mu yf(\bm{x},y):=\{\begin{array}{cc}\mathrm{min}{A}_{f}(\bm{x})\hfill & \text{if}{A}_{f}(\bm{x})\ne \mathrm{\varnothing},\hfill \\ \text{undefined}\hfill & \text{otherwise.}\hfill \end{array}$$ 
This definition is actually equivalent^{} to the one regarding predicates, in the following sense: given a total function $f$ with arity $m+1$, define predicate ${\mathrm{\Phi}}_{f}(\bm{x},y)$ of arity $m+1$, as “$f(\bm{x},y)=0$”. Then
$$\mu yf(\bm{x},y)=\mu y{\mathrm{\Phi}}_{f}(\bm{x},y).$$ 
Conversely, given an $(m+1)$ary predicate $\mathrm{\Phi}(\bm{x},y)$, define an $(m+1)$ary function ${f}_{\mathrm{\Phi}}(\bm{x},y):=1\dot{}{\chi}_{\mathrm{\Phi}}(\bm{x},y)$, where ${\chi}_{\mathrm{\Phi}}$ is the characteristic function^{} of $\mathrm{\Phi}$. Then
$$\mu y\mathrm{\Phi}(\bm{x},y)=\mu y{f}_{\mathrm{\Phi}}(\bm{x},y).$$ 
Note also that $\mu f$ may be partial even if $f$ is total, since it is possible $f(\bm{x},y)\ne 0$ for all $y$, and the search will go on indefinitely. For example, let $f(x,z,y)={x}^{2}+{z}^{2}{y}^{2}$ if ${x}^{2}+{z}^{2}\ge {y}^{2}$, and $1$ otherwise. Clearly, $f$ is a total function. It is easy to see that $\mu yf(3,4,y)=5$, while $\mu yf(1,2,y)$ is undefined.
$\mu $ on partial functions
The definition of the $\mu $operator on total functions can be generalized to partial functions. However, in recursive functions theory, an additional condition is imposed in order to make the generalization^{}.
Definition. Given a partial $(m+1)$ary function $f:{\mathbb{N}}^{m+1}\to \mathbb{N}$, define
$${A}_{f}(\bm{x}):=\{y\in \mathbb{N}\mid f(\bm{x},y)=0\text{and}(\bm{x},z)\in \mathrm{dom}(f)\text{for all}z\le y\},$$ 
The $\mu $operator on $f$ is given by
$$\mu yf(\bm{x},y):=\{\begin{array}{cc}\mathrm{min}{A}_{f}(\bm{x})\hfill & \text{if}{A}_{f}(\bm{x})\ne \mathrm{\varnothing},\hfill \\ \text{undefined}\hfill & \text{otherwise.}\hfill \end{array}$$ 
The extra condition that $f(\bm{x},z)$ be defined for all $z\le y$ is needed in order to avoid situations where testing for $f(\bm{x},z)=0$ gets stuck in an infinite loop (in a Turing machine^{} or a URM) because $f(\bm{x},z)$ is undefined, before $y$ is ever reached for testing. If we drop this extra condition, then it is possible to find a partial recursive function $f$ such that $\mu f$ is not recursive.
Remarks.

•
Bounded $\mu $operator may also be defined on functions. In the case of partial functions, the definition can be given as follows: let $f(\bm{x},y)$ be an $(m+1)$ary partial function, with
$${A}_{f}(\bm{x},y):=\{z\in \mathbb{N}\mid f(\bm{x},z)=0,z\le y,\text{and}(\bm{x},t)\in \mathrm{dom}(f)\text{for all}t\le z\},$$ then
$$\mu z\le yf(\bm{x},z):=\{\begin{array}{cc}\mathrm{min}{A}_{f}(\bm{x},y)\hfill & \text{if}{A}_{f}(\bm{x},y)\ne \mathrm{\varnothing},\hfill \\ y+1\hfill & \text{if}{A}_{f}(\bm{x},y)=\mathrm{\varnothing}\text{and}(\bm{x},t)\in \mathrm{dom}(f)\text{for all}t\le y\hfill \\ \text{undefined}\hfill & \text{otherwise.}\hfill \end{array}$$ 
•
Given the set $\mathcal{P}\mathcal{R}$ of primitive recursive functions^{}, one obtains the set $\mathcal{R}$ of recursive functions by taking the closure^{} of $\mathcal{P}\mathcal{R}$ with respect to the application of the $\mu $operator. Furthermore, if $f\in \mathcal{R}$, so is $\mu f\in \mathcal{R}$, and it can be shown that any recursive function can be obtained from primitive recursive functions by no more than one application of the $\mu $operator. This is known as the Kleene normal form theorem^{}.

•
With respect to the bounded $\mu $operator, any primitive recursive function (or predicate) stays primitive recursive after an application of the bounded $\mu $, and any total recursive function stays total after an application of the bounded $\mu $.
Title  $\mu $operator 

Canonical name  muoperator 
Date of creation  20130322 19:05:47 
Last modified on  20130322 19:05:47 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  12 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03D20 
Synonym  minimization operator 
Synonym  minimizationoperator 
Synonym  search operator 
Synonym  searchoperator 