Definition:Bounded Minimization

This page has been identified as a candidate for refactoring of basic complexity. Until this has been finished, please leave {{Refactor}} in the code. New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Refactor}} from the code.

This article needs to be tidied. In particular: This notation is awfully obtuse Please fix formatting and $\LaTeX$ errors and inconsistencies. It may also need to be brought up to our standard house style. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Tidy}} from the code.

Definition

Function

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

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

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

$\map {\mu y \le z} {\map f {n_1, n_2, \ldots, n_k, y} = 0}$

and is specified as follows:

$\map {\mu y \le z} {\map f {n_1, n_2, \ldots, n_k, y} = 0} = \begin{cases}

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

Relation

Let $\map \RR {n_1, n_2, \ldots, n_k, y}$ be a $k + 1$-ary relation on $\N^{k + 1}$.

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

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

$\map {\mu y \le z} {\map \RR {n_1, n_2, \ldots, n_k, y} }$

and is specified as follows:

$\map {\mu y \le z} {\map \RR {n_1, n_2, \ldots, n_k, y} } = \begin{cases}

\text{the smallest } y \in \N \text{ for which } \map \RR {n_1, n_2, \ldots, n_k, y} \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$.