bounded maximization


The proof involved in showing that functions obtained via bounded minimizing (http://planetmath.org/BoundedMinimization) primitive recursive functionsMathworldPlanetmath 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:m+1 be a function. For each y, set

Af(𝒙,y):={zzy and f(𝒙,z)=0}.

Define

fbmax(𝒙,y):={maxAf(𝒙,y)if Af(𝒙,y),0otherwise.

fbmax is called the function obtained from f by bounded maximization.

Proposition 1.

If f:Nm+1N is primitive recursive, so is fbmax.

Proof.

The proof of this is very similar to the proof that fbmin is primitive recursive in the parent entry. The initial set up is the same: define g:=sgnf, where sgn is the sign function. So g is primitive recursive.

Next, define h:m+2 by h(𝒙,y,z)=g(𝒙,y-˙z). So h, and therefore its bounded product:

hp(𝒙,y,z):=i=0zh(𝒙,y,i)

are primitive recursive. hp has the following property: given y,

  • if k is the largest number less than or equal to y such that f(𝒙,k)=0, then

    hp(𝒙,y,z):={1if z<y-k,0otherwise.
  • if no such k exists, then hp(𝒙,y,z)=1, for all (𝒙,y,z)m+2.

As a result, the bounded sum

(hp)s(𝒙,y,z):=i=0zhp(𝒙,y,i),

and in particular, the function g*(𝒙,y):=(hp)s(𝒙,y,y), are primitive recursive. After some simplification, g* becomes

g*(𝒙,y):={y-kif k=maxAf(𝒙,y) exists,s(y)otherwise.

Finally, the function g**(𝒙,y):=y-˙g*(𝒙,y), which is just fbmax(𝒙,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 zyx. Let A(y,x)={zzyx}. Then A(y,x) can be rewritten as

{zzx and sgn(yz-˙x)=0}.

Define f:3 by f(x,y,t)=sgn(yt-˙x). Then

Af(x,y,t)={zzt and sgn(yz-˙x)=0}.

Since f is primitive recursive, so is fbmax(x,y,t). Since A(x,y)=Af(x,y,x), the quotient q(x,y) may be defined as fbmax(x,y,x), and therefore is primitive recursive.

With q(x,y), we may define rem(x,y), the remainder of x÷y, as x-˙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 rem(x,y) are primitive recursive without using bounded maximization. In the alternative method, one shows that rem(x,y) is primitive recursive first. In additionPlanetmathPlanetmath, 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