# 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}(\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
• 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}y-k&\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 (http://planetmath.org/ExamplesOfPrimitiveRecursiveFunctions) 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.

Title bounded maximization BoundedMaximization 2013-03-22 19:05:37 2013-03-22 19:05:37 CWoo (3771) CWoo (3771) 8 CWoo (3771) Definition msc 03D20 BoundedMinimization