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 be a function. For each , set
is called the function obtained from by bounded maximization.
If is primitive recursive, so is .
The proof of this is very similar to the proof that is primitive recursive in the parent entry. The initial set up is the same: define , where is the sign function. So is primitive recursive.
Next, define by . So , and therefore its bounded product:
are primitive recursive. has the following property: given ,
if is the largest number less than or equal to such that , then
if no such exists, then , for all .
As a result, the bounded sum
and in particular, the function , are primitive recursive. After some simplification, becomes
Finally, the function , which is just , is primitive recursive too. ∎
Example. Using bounded maximization, we can show that , the quotient of , is primitive recursive. When , we set
First note that is the largest integer less than or equal to such that . Let . Then can be rewritten as
Define by . Then
Since is primitive recursive, so is . Since , the quotient may be defined as , and therefore is primitive recursive.
With , we may define , the remainder of , as , which is easily seen to be primitive recursive.
Remark. Please see this entry (http://planetmath.org/ExamplesOfPrimitiveRecursiveFunctions) for an alternative way of showing that and are primitive recursive without using bounded maximization. In the alternative method, one shows that is primitive recursive first. In addition, in the alternative method, as opposed to discussed here.
|Date of creation||2013-03-22 19:05:37|
|Last modified on||2013-03-22 19:05:37|
|Last modified by||CWoo (3771)|