Question

Can you prove all functions can be decomposed into binary functions?

Some Math

Layer-Cake Decomposition

f(x) = \int_{0}^{\inf}{1_{f(x)>t}dt}

For any function, imagine it as a cake. As with a cake, you can slice it horizontally infinitely many times. Define the following:

A_t = \{ x : f(x) > t\}

The function $A_t$ is the set of all x such that f(x) is greater than t. Note this is just a formality to scope this representation to ONLY the non-negative real space. Then condition every differential that if the $f(x) > t$ to equal 1; 0 otherwise.

1_{f(x)>t} = \begin{cases} 1 \enspace t<f(x) \newline 0 \enspace t\geq f(x) \end{cases}

A slight aside is that the greater or equal to for the 0 condition is a formality but that the integral operation nullifies it.

Another comment is that we are integrating for the horizontal layers under the curve but the conditional in the first equation is for greater than. One may think that it’s 1 if over t. It’s written that way to imply we are measuring vertically up; indeed, it’s indicated 1 if under the curve not over.

\int_{0}^{\inf}{1_{f(x)>t}dt} = \int_{0}^{f(x)}{1dt} = f(x)

Thus,

f(x) = \int_{0}^{\inf}{1_{A_t}(x)dt}

QED.

In other words, a real function is a stack of binary threshold signals.

Discrete binary expansion of functions is the discrete version of this.

Given \space 0 \leq f(x) \leq 1, \newline f(x) = \sum_{k=1}^{\inf} 2^{-k}b_k(x)

It’s the same setup as the continuous version but since it’s discrete, we need to setup our own measuring stick, namely the base-2. So essentially, we sum up the layers where $2^-k$ gives the thickness. The conditional is given by $b_k(x)$ :

b_k(x) = \lfloor{2^kf(x)}\rfloor - 2\lfloor{2^{k-1}f(x)}\rfloor

The way this acts as a conditional is that the first term tells you how many dyadic intervals of size $2^{-k}$ fits in this term.

For $f(x) = 0.7$ , you get

2^3 f(x) = 8 × 0.7 = 5.6 \newline ⌊5.6⌋ = 5

In ordinary terms, that’s 5 intervals of size 1/8 fit in 0.7.

The second term does the same thing but uses a coarser scale by a factor of 1/2. When you subtract the two terms, you isolate whether the current layer exists or not. A good way to think about this is that each term is like a measuring stick. How many times you can measure with the $2^k$ measure stick gives you the first term. How many times you can measure with the $2^{k-1}$ measure stick gives you the second term. Since the $2^{k-1}$ is the “bigger” unit stick and $2^k$ is a smaller unit. It can never be more than 1 otherwise the coarser measuring stick would have another unit.

Regrouping to the key point,

f = \sum{2^{-k}b_k}

States any bounded function is the weighted sum of binary signals.

Some additional examples

Binary basis of function spaces

L^2[0,1]

The space bounded between 0 and 1 inclusive such that the square of the function is integrable.

And consider a wavelet, a small wave-like function localiyzed in space and frequency. They have zero mean $\int{\psi(x)dx}$

Short Answer

No. We know that every function can be represented by binary-valued pieces; however, it is NOT true that every possible function/space is composed of binary signals.

Representation $\neq$ Composition

Any representation can be written as:

f = \sum_k{w_k}{b_k}

where w = weights, b = binary

Note that $\pi$ can NEVER be produced by this representation.

Cardinality

The set of all functions

$f : \mathbb{R} \rightarrow \mathbb{R}$

has size

$|\mathbb{R}|^{|\mathbb{R}|}$

Compare that to all binary representations in the set {0,1} which has cardinality $2^{N_0}$ .

Binary Decomposition