bounded maximization
The proof involved in showing that functions obtained via bounded minimizing (http://planetmath.org/BoundedMinimization) primitive recursive functions^{} are themselves primitive recursive can be used to show the primitive recursiveness of another family of functions derived from existing primitive recursive functions via a similar technique, called bounded maximization.
Definition. Let $f:{\mathbb{N}}^{m+1}\to \mathbb{N}$ be a function. For each $y\in \mathbb{N}$, set
$${A}_{f}(\bm{x},y):=\{z\in \mathbb{N}\mid z\le y\text{and}f(\bm{x},z)=0\}.$$ 
Define
$${f}_{bmax}(\bm{x},y):=\{\begin{array}{cc}\mathrm{max}{A}_{f}(\bm{x},y)\hfill & \text{if}{A}_{f}(\bm{x},y)\ne \mathrm{\varnothing},\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$$ 
${f}_{bmax}$ is called the function obtained from $f$ by bounded maximization.
Proposition 1.
If $f\mathrm{:}{\mathrm{N}}^{m\mathrm{+}\mathrm{1}}\mathrm{\to}\mathrm{N}$ is primitive recursive, so is ${f}_{b\mathit{}m\mathit{}a\mathit{}x}$.
Proof.
The proof of this is very similar to the proof that ${f}_{bmin}$ is primitive recursive in the parent entry. The initial set up is the same: define $g:=\mathrm{sgn}\circ f$, where $\mathrm{sgn}$ is the sign function. So $g$ is primitive recursive.
Next, define $h:{\mathbb{N}}^{m+2}\to \mathbb{N}$ by $h(\bm{x},y,z)=g(\bm{x},y\dot{}z)$. So $h$, and therefore its bounded product:
$${h}_{p}(\bm{x},y,z):=\prod _{i=0}^{z}h(\bm{x},y,i)$$ 
are primitive recursive. ${h}_{p}$ has the following property: given $y$,

•
if $k$ is the largest number less than or equal to $y$ such that $f(\bm{x},k)=0$, then
$$ 
•
if no such $k$ exists, then ${h}_{p}(\bm{x},y,z)=1$, for all $(\bm{x},y,z)\in {\mathbb{N}}^{m+2}$.
As a result, the bounded sum
$${({h}_{p})}_{s}(\bm{x},y,z):=\sum _{i=0}^{z}{h}_{p}(\bm{x},y,i),$$ 
and in particular, the function ${g}^{*}(\bm{x},y):={({h}_{p})}_{s}(\bm{x},y,y)$, are primitive recursive. After some simplification, ${g}^{*}$ becomes
$${g}^{*}(\bm{x},y):=\{\begin{array}{cc}yk\hfill & \text{if}k=\mathrm{max}{A}_{f}(\bm{x},y)\text{exists},\hfill \\ s(y)\hfill & \text{otherwise.}\hfill \end{array}$$ 
Finally, the function ${g}^{**}(\bm{x},y):=y\dot{}{g}^{*}(\bm{x},y)$, which is just ${f}_{bmax}(\bm{x},y)$, is primitive recursive too. ∎
Example. Using bounded maximization, we can show that $q(x,y)$, the quotient of $x\xf7y$, is primitive recursive. When $y=0$, we set $q(x,y)=0$
First note that $q(x,y)$ is the largest integer $z$ less than or equal to $x$ such that $zy\le x$. Let $A(y,x)=\{z\in \mathbb{N}\mid zy\le x\}$. Then $A(y,x)$ can be rewritten as
$$\{z\in \mathbb{N}\mid z\le x\text{and}\mathrm{sgn}(yz\dot{}x)=0\}.$$ 
Define $f:{\mathbb{N}}^{3}\to \mathbb{N}$ by $f(x,y,t)=\mathrm{sgn}(yt\dot{}x)$. Then
$${A}_{f}(x,y,t)=\{z\in \mathbb{N}\mid z\le t\text{and}\mathrm{sgn}(yz\dot{}x)=0\}.$$ 
Since $f$ is primitive recursive, so is ${f}_{bmax}(x,y,t)$. Since $A(x,y)={A}_{f}(x,y,x)$, the quotient $q(x,y)$ may be defined as ${f}_{bmax}(x,y,x)$, and therefore is primitive recursive.
With $q(x,y)$, we may define $\mathrm{rem}(x,y)$, the remainder of $x\xf7y$, as $x\dot{}yq(x,y)$, which is easily seen to be primitive recursive.
Remark. Please see this entry (http://planetmath.org/ExamplesOfPrimitiveRecursiveFunctions) for an alternative way of showing that $q(x,y)$ and $\mathrm{rem}(x,y)$ are primitive recursive without using bounded maximization. In the alternative method, one shows that $\mathrm{rem}(x,y)$ is primitive recursive first. In addition^{}, $\mathrm{rem}(x,0):=0$ in the alternative method, as opposed to $x$ discussed here.
Title  bounded maximization 

Canonical name  BoundedMaximization 
Date of creation  20130322 19:05:37 
Last modified on  20130322 19:05:37 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  8 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03D20 
Related topic  BoundedMinimization 