Definition:Bounded Minimization

From ProofWiki
Jump to: navigation, search

Definition

Function

Let $f: \N^{k+1} \to \N$ be a function.

Let $\left({n_1, n_2, \ldots, n_k}\right) \in \N^k$ and let $z \in \N$ be fixed.

Then the bounded minimization operation on $f$ is written as:

$\mu y \le z \left({f \left({n_1, n_2, \ldots, n_k, y}\right) = 0}\right)$

and is specified as follows:

$\mu y \le z \left({f \left({n_1, n_2, \ldots, n_k, y}\right) = 0}\right) = \begin{cases} \text{the smallest } y \in \N \text{ such that } f \left({n_1, n_2, \ldots, n_k, y}\right) = 0 & : \exists y \in \N: y \le z \\ z + 1 & : \text{otherwise} \end{cases}$


Relation

Let $\mathcal R \left({n_1, n_2, \ldots, n_k, y}\right) $ be a $k+1$-ary relation on $\N^{k+1}$.

Let $\left({n_1, n_2, \ldots, n_k}\right) \in \N^k$ and let $z \in \N$ be fixed.

Then the bounded minimization operation on $\mathcal R$ is written as:

$\mu y \le z \mathcal R\left({n_1, n_2, \ldots, n_k, y}\right)$

and is specified as follows:

$\mu y \le z \mathcal R\left({n_1, n_2, \ldots, n_k, y}\right) = \begin{cases} \text{the smallest } y \in \N \text{ for which } \mathcal R \left({n_1, n_2, \ldots, n_k, y}\right) \text{ holds} & : \exists y \in \N: y \le z \\ z + 1 & : \text{otherwise} \end{cases}$


We can consider the definition for a function to be a special case of this.


The no-solution case

The choice of $z + 1$ for the value when there is no solution $y$ less than or equal to $z$ is arbitrary, but convenient.

It ensures a well-defined solution for every $z$.