Suppose $f$ is an arbitrary binary function and it is given to us: $$ f: \mathbb{R}^{d} \rightarrow \{0, 1\} $$ Prove that it is always possible to write this function, as a composition of two functions:
- A continuous function: $g: \mathbb{R}^{d} \rightarrow (0, 1) $
- A thresholding function: $h: (0, 1) \rightarrow \{0, 1\}$, e.g. $h(x) = 0.5 + 0.5 sgn(x - 0.5)$
such that: $ \forall X \in \mathbb{R}^d : \; \; \; f(x) = h(g(x))$.
If there is any requirement needed to have such decomposition, please state it.
Let's say the threshold is $t$, and that $h(x)=1$ when $x> t$ and $h(x)=0$ when $x\le t$. The other possibility is to have $h(x)=1$ for $x\ge t$ instead, I will deal with this at the end.
If $f=h\circ g$, then $f^{-1}(\{1\})=g^{-1}(h^{-1}(\{1\}))=g^{-1}((t,1))$. Since $g$ is continuous and $(t,1)$ is open, this implies $f^{-1}(1)$ is an open set. This gives a necessary condition for the decomposition to exist; $f^{-1}(\{1\})$ must be open.
This condition is also sufficient. If $f^{-1}(\{1\})$ is open, then $C:= f^{-1}(\{0\})$ is closed. Let $d:\mathbb R^n\to \mathbb R$ be defined by $$ d(x)= \text{dist}(x,C)=\inf_{c\in C}\|x-c\| $$ Since $C$ is closed, it follows $d(x)=0$ if and only if $x\in C$. Therefore, letting $$g(x)=\frac12 + \frac12\cdot \frac{d(x)}{1+d(x)},$$ then $g(x)=\frac12$ when $x\in C$, while $g(x)>\frac12$ when $x\not\in C$. This means that letting $h(x)=1$ when $x>\frac12$ and $h(x)=0$ when $x\le \frac12$, then $f=h\circ g$.
If you use the other type of threshold function, where $h(x)=1$ for $x\ge t$, then you instead get the necessary condition that $f^{-1}(\{1\})$ must be closed, but otherwise the same logic works. That is, the condition you need is that $f^{-1}(\{1\})$ is either open or closed.