# Functions with and without distinction of cases

Consider computable functions $f: \mathbb{N} \rightarrow \mathbb{N}$, given as formulas. I assume that it is clear for at least some of them whether they contain a distinction of cases:

$$f(n) = n$$

obviously does not contain a distinction of cases (i.e. is d.c.-free),

$$g(n) = \begin{cases} 1 & \text{for } n = 0 \\ n & \text{otherwise} \end{cases}$$

obviously does, at least at the face of it.

What is not clear is whether there is a d.c.-free function $g'$ that is equivalent with $g$, is it?

What I believe to know:

1. It is not decidable whether there is a d.c.-free function equivalent with a given one (unless one can prove that there is one for every computable function!)

2. Especially, a d.c.-free function $g'$ is not "computable" (as a formula) from a given one $g$

3. Even when you are given one (by an oracle): showing the equivalence of $g'$ and $g$ is not decidable.

Nevertheless there are at least some trivial cases where a d.c.-free formula exists, e.g. for

$$g(n) = \begin{cases} 0 & \text{for } n = 0 \\ n & \text{otherwise} \end{cases}$$

Can anyone provide a non-trivial example?

• Can the formulas involve quantifiers in the definitions of the cases? – Carl Mummert Jun 26 '14 at 11:00
• As far as quantifiers can be mimicked by recursive functions. – Hans-Peter Stricker Jun 26 '14 at 12:35
• So you do not allow primitive recursion? – André Nicolas Jun 27 '14 at 0:08
• @AN: This objection is striking! (I did not realize that d.c. is an integral part of the definition of primitive recursion. But is it really and indispensably?) – Hans-Peter Stricker Jun 27 '14 at 7:23

The answer to this question heavily depends on what functions are allowed as building blocks for non d.c. functions. A little thought shows that if it's somehow possible to construct a step function using non d.c. functions, then any d.c. function can in principle be rewritten using these step functions - admittedly, not in a particularly nice way.

If we assume that $x\rightarrow x^2$ and $x\rightarrow \sqrt x$ are allowed as non-d.c. functions, then we can construct the absolute value function as $|x| = \sqrt{x^2}$, and using the absolute value function, we can then construct the max and min functions as

$$\max(a,b) = \frac{|a - b| + a + b}{2}\\ \min(a,b) = \frac{|a - b| - a - b}{2}$$

Using these functions, we can first construct $f(x) = \max(x+1,0)$ and $g(x) = \max(x,0)$. When restricted to the natural numbers, we see that $h = f - g$ is equivalent to $$h(n) = \begin{cases} 1&n \geq 0\\ 0 &n < 0\\ \end{cases}.$$

This step function can be translated to anywhere on the number line by defining $$h_a(n) = \max(n+1-a,0)-\max(n-a,0) = \begin{cases} 1 & n \geq a \\ 0 & n < a\end{cases}.$$

We can then get a generalized filter function by the product $h_a(1-h_b)$.

Any d.c. function can therefore be rewritten in terms of these products. For example, the function $$f = \begin{cases} 1 & n = 0 \\ 0 & \mathrm{otherwise} \end{cases}$$ can be written as $h_0\cdot(1- h_1)$.

Writing $f$ out explicitly (only in terms of abs!), we have

$f(n) = \frac 14 \left[\left(1-|n|\right)\left(1-|n| +|n-1| + |n+1|\right) + |n^2-1| \right]$

Checking, we see that $$f(0) = \frac 14 \left[1\cdot(1 + 1 +1) + 1\right] = 1,$$ while \begin{align}f(n)|_{n \geq 1} &= \frac 14 \left[(1-n)(1-n+n-1+n+1)+n^2-1\right]\\ &= \frac 14 (1-n^2 + n^2 -1) = 0\end{align}, and \begin{align}f(n)|_{n \leq -1} &= \frac 14 \left[(1+n)(1+n-n+1-n-1)+n^2-1\right]\\ &= \frac 14 (1-n^2 + n^2 -1) = 0\end{align},

exactly as desired. This also shows that the construction in terms of cases is a great deal more succinct (and clear) than the one presented here.

• Everything is fine! I appreciate the construction. The only thing I don't like is the - arbitrary - dependence of the function $f$ of the parameters $0$ and $1$ (in $h_0$ and $h_1$), which somehow play the role of the "definition by cases". But I cannot explain that any further. – Hans-Peter Stricker Jun 26 '14 at 18:54