# 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. ∎

Title definition by cases DefinitionByCases 2013-03-22 19:08:13 2013-03-22 19:08:13 CWoo (3771) CWoo (3771) 5 CWoo (3771) Example msc 03D20