definition by cases

Definition A (total) function f:k is said to be defined by cases if there are functions f1,,fm:k, and predicatesMathworldPlanetmath Φ1(𝒙),,Φm(𝒙), which are pairwise exclusive


for ij, such that

f(𝒙):={f1(𝒙)if Φ1(𝒙),fm(𝒙)if Φm(𝒙).

Since f is a total functionMathworldPlanetmath (domain is all of k), we see that S(Φ1)S(Φm)=k.

Proposition 1.

As above, if the functions f1,,fm:NkN, as well as the predicates Φ1(𝐱),,Φm(𝐱), are primitive recursive, then so is the function f:NkN defined by cases from the fi and Φj.

To see this, we first need the following:

Lemma 1.

If functions f1,,fm:NkN are primitive recursive, so is f1++fm.


By inductionMathworldPlanetmath on m. The case when m=1 is clear. Suppose the statement is true for m=n. Then f1++fn+fn+1=add(f1++fn,fn+1), which is primitive recursive, since add is, and that primitive recursiveness is preserved under functionalPlanetmathPlanetmathPlanetmathPlanetmath compositionMathworldPlanetmath. ∎

Proof of Proposition 1.

f is just

f(𝒙):={f1(𝒙)if 𝒙S(Φ1),fm(𝒙)if 𝒙S(Φm).

which can be re-written as


where φS denotes the characteristic function of set S. By assumptionPlanetmathPlanetmath, both fi and φS(Φi) are primitive recursive, so is their productPlanetmathPlanetmath, and hence the sum of these products. As a result, f is primitive recursive too. ∎

Title definition by cases
Canonical name DefinitionByCases
Date of creation 2013-03-22 19:08:13
Last modified on 2013-03-22 19:08:13
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 5
Author CWoo (3771)
Entry type Example
Classification msc 03D20