## You are here

Homedefinition by cases

## Primary tabs

# definition by cases

Definition A (total) function $f:\mathbb{N}^{k}\to\mathbb{N}$ is said to be defined by cases if there are functions $f_{1},\ldots,f_{m}:\mathbb{N}^{k}\to\mathbb{N}$, and predicates $\Phi_{1}(\boldsymbol{x}),\ldots,\Phi_{m}(\boldsymbol{x})$, which are pairwise exclusive

$S(\Phi_{i})\cap S(\Phi_{j})=\varnothing$ |

for $i\neq j$, such that

$f(\boldsymbol{x}):=\left\{\begin{array}[]{ll}f_{1}(\boldsymbol{x})&\textrm{if % }\Phi_{1}(\boldsymbol{x}),\\ \cdots\\ f_{m}(\boldsymbol{x})&\textrm{if }\Phi_{m}(\boldsymbol{x}).\end{array}\right.$ |

Since $f$ is a total function (domain is all of $\mathbb{N}^{k}$), we see that $S(\Phi_{1})\cup\cdots\cup S(\Phi_{m})=\mathbb{N}^{k}$.

###### Proposition 1.

As above, if the functions $f_{1},\ldots,f_{m}:\mathbb{N}^{k}\to\mathbb{N}$, as well as the predicates $\Phi_{1}(\boldsymbol{x}),\ldots,\Phi_{m}(\boldsymbol{x})$, are primitive recursive, then so is the function $f:\mathbb{N}^{k}\to\mathbb{N}$ defined by cases from the $f_{i}$ and $\Phi_{j}$.

To see this, we first need the following:

###### Lemma 1.

If functions $f_{1},\ldots,f_{m}:\mathbb{N}^{k}\to\mathbb{N}$ are primitive recursive, so is $f_{1}+\cdots+f_{m}$.

###### Proof.

By induction on $m$. The case when $m=1$ is clear. Suppose the statement is true for $m=n$. Then $f_{1}+\cdots+f_{n}+f_{{n+1}}=\operatorname{add}(f_{1}+\cdots+f_{n},f_{{n+1}})$, which is primitive recursive, since $\operatorname{add}$ is, and that primitive recursiveness is preserved under functional composition. ∎

###### Proof of Proposition 1.

$f$ is just

$f(\boldsymbol{x}):=\left\{\begin{array}[]{ll}f_{1}(\boldsymbol{x})&\textrm{if % }\boldsymbol{x}\in S(\Phi_{1}),\\ \cdots\\ f_{m}(\boldsymbol{x})&\textrm{if }\boldsymbol{x}\in S(\Phi_{m}).\end{array}\right.$ |

which can be re-written as

$f=\varphi_{{S(\Phi_{1})}}f_{1}+\cdots+\varphi_{{S(\Phi_{m})}}f_{m},$ |

where $\varphi_{S}$ denotes the characteristic function of set $S$. By assumption, both $f_{i}$ and $\varphi_{{S(\Phi_{i})}}$ are primitive recursive, so is their product, and hence the sum of these products. As a result, $f$ is primitive recursive too. ∎

## Mathematics Subject Classification

03D20*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections