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(𝒙,y):=\{z\in \mathbb{N}\mid z\le y\text{ and }f(𝒙,z)=0\}.$$

Define

$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(𝒙,y,z)=g(𝒙,y\dot{-}z)$. So $h$, and therefore its bounded product:

$$h_p(𝒙,y,z):=\prod _{i=0}^{z}h(𝒙,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(𝒙,k)=0$, then

• if no such $k$ exists, then $h_p(𝒙,y,z)=1$, for all $(𝒙,y,z)\in {\mathbb{N}}^{m+2}$.

As a result, the bounded sum

$${(h_p)}_s(𝒙,y,z):=\sum _{i=0}^z{h}_p(𝒙,y,i),$$

and in particular, the function $g^{*}(𝒙,y):={(h_p)}_s(𝒙,y,y)$, are primitive recursive. After some simplification, $g^{*}$ becomes

Finally, the function $g^{**}(𝒙,y):=y\dot{-}{g}^{*}(𝒙,y)$, which is just $f_{bmax}(𝒙,y)$, is primitive recursive too. ∎

Example. Using bounded maximization, we can show that $q(x,y)$, the quotient of $x÷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\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÷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 $\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	2013-03-22 19:05:37
Last modified on	2013-03-22 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