You are here
Homebounded maximization
Primary tabs
bounded maximization
The proof involved in showing that functions obtained via bounded minimizing 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}(\boldsymbol{x},y):=\{z\in\mathbb{N}\mid z\leq y\mbox{ and }f(\boldsymbol% {x},z)=0\}.$ 
Define
$f_{{bmax}}(\boldsymbol{x},y):=\left\{\begin{array}[]{ll}\max A_{f}(\boldsymbol% {x},y)&\textrm{if }A_{f}(\boldsymbol{x},y)\neq\varnothing,\\ 0&\textrm{otherwise.}\end{array}\right.$ 
$f_{{bmax}}$ is called the function obtained from $f$ by bounded maximization.
Proposition 1.
If $f:\mathbb{N}^{{m+1}}\to\mathbb{N}$ is primitive recursive, so is $f_{{bmax}}$.
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:=\operatorname{sgn}\circ f$, where $\operatorname{sgn}$ is the sign function. So $g$ is primitive recursive.
Next, define $h:\mathbb{N}^{{m+2}}\to\mathbb{N}$ by $h(\boldsymbol{x},y,z)=g(\boldsymbol{x},y\dot{}z)$. So $h$, and therefore its bounded product:
$h_{p}(\boldsymbol{x},y,z):=\prod_{{i=0}}^{z}h(\boldsymbol{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(\boldsymbol{x},k)=0$, then
$h_{p}(\boldsymbol{x},y,z):=\left\{\begin{array}[]{ll}1&\textrm{if }z<yk,\\ 0&\textrm{otherwise.}\end{array}\right.$ 
if no such $k$ exists, then $h_{p}(\boldsymbol{x},y,z)=1$, for all $(\boldsymbol{x},y,z)\in\mathbb{N}^{{m+2}}$.
As a result, the bounded sum
$(h_{p})_{s}(\boldsymbol{x},y,z):=\sum_{{i=0}}^{z}h_{p}(\boldsymbol{x},y,i),$ 
and in particular, the function $g^{*}(\boldsymbol{x},y):=(h_{p})_{s}(\boldsymbol{x},y,y)$, are primitive recursive. After some simplification, $g^{*}$ becomes
$g^{*}(\boldsymbol{x},y):=\left\{\begin{array}[]{ll}yk&\textrm{if }k=\max A_{f% }(\boldsymbol{x},y)\mbox{ exists},\\ s(y)&\textrm{otherwise.}\end{array}\right.$ 
Finally, the function $g^{{**}}(\boldsymbol{x},y):=y\dot{}g^{*}(\boldsymbol{x},y)$, which is just $f_{{bmax}}(\boldsymbol{x},y)$, is primitive recursive too. ∎
Example. Using bounded maximization, we can show that $q(x,y)$, the quotient of $x\div y$, 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\leq x$. Let $A(y,x)=\{z\in\mathbb{N}\mid zy\leq x\}$. Then $A(y,x)$ can be rewritten as
$\{z\in\mathbb{N}\mid z\leq x\mbox{ and }\operatorname{sgn}(yz\dot{}x)=0\}.$ 
Define $f:\mathbb{N}^{3}\to\mathbb{N}$ by $f(x,y,t)=\operatorname{sgn}(yt\dot{}x)$. Then
$A_{f}(x,y,t)=\{z\in\mathbb{N}\mid z\leq t\mbox{ and }\operatorname{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 $\operatorname{rem}(x,y)$, the remainder of $x\div y$, as $x\dot{}yq(x,y)$, which is easily seen to be primitive recursive.
Remark. Please see this entry for an alternative way of showing that $q(x,y)$ and $\operatorname{rem}(x,y)$ are primitive recursive without using bounded maximization. In the alternative method, one shows that $\operatorname{rem}(x,y)$ is primitive recursive first. In addition, $\operatorname{rem}(x,0):=0$ in the alternative method, as opposed to $x$ discussed here.
Mathematics Subject Classification
03D20 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections